2012-11-14

Project Euler - Problem 4

Here's my solution to Project Euler problem 4:

# handy function to check if a number is palindrome
def is_palindrome(i):
    return str(i) == str(i)[::-1]

# what's the max?
max_p = 0

# multiply all numbers `i` between 100 and 998, with all between i+1 and 999
for i in xrange(100, 999):
    for j in xrange(i+1, 1000):
        p = i * j
        if is_palindrome(p) and p > max_p:
            max_p = p

print max_p

Comments are welcome.

Update: fixed as per Alex comment.

13 comments:

koalillo said...

Drop the if, please, just return the condition.

if x:
return True
else:
return False

drives me batty. return x already!

Sandro Tosi said...

@Alex: oh god, you're so damn right! updating

Kontre said...

Would it be faster to check only the firesst half versus the last half instead of the whole string ?

James said...

Mines basically algorithmicly the same, just with a single list comprehension.

https://bitbucket.org/prologic/euler/src/bc50ae139f3027d22e32f4fdf925abf8153e42a0/4.py?at=default

cheers
James

Sandro Tosi said...

@Kontre: probably yes, but then you'll have to handle when len is odd (so the central element should either be ignored or included in both the sub-strings)

@James: yep, same logic, just one note: you're comparing both A*B and B*A which for a long list would take some time

Adam M. Donahue said...

Why do you skip squares? There is no constraint that the numbers have to be different.

James Thiele said...

Rather than count up, count down. Find a max palindrome, then you can limit how small a number you need to multiply by. This saves a lot of multiplies.

Sorry about the lack of indentation, but I can't figure out how to post code.
--

# handy function to check if a number is palindrome
def is_palindrome(i):
return str(i) == str(i)[::-1]

# what's the max?
max_p = 0
min_mult = 99

# start at 999, work your way down
for i in xrange(999, 99, -1):
if max_p != 0:
min_mult = max_p/i
if min_mult > i:
break
for j in xrange(i, min_mult, -1):
p = i * j
if is_palindrome(p) and p > max_p:
max_p = p
break

print max_p

---

I called yours pal0.py, mine pal1.py.


$ time python pal0.py
906609

real 0m0.558s
user 0m0.488s
sys 0m0.031s
J$ time python pal1.py
906609

real 0m0.068s
user 0m0.033s
sys 0m0.023s
$

sylvain said...
This comment has been removed by the author.
sylvain said...

Or you reverse the order: you first find the potential palindromes, then you find if there is a matching product of two 3-digits numbers. As a one-liner:

iter(pal for pal in (num for num in xrange(999 * 999, 100 * 100, -1) if str(num) == str(num)[::-1]) if any((i * j == pal) for i in xrange(999, 99, -1) for j in xrange(i, pal / i - 1, -1))).next()

This only works well because Python allows the palindrome enumeration to be written as a generator expression, and act as a co-routine to the outside dividers search criteria.

Rafael Augusto said...

I will avoid the nitpicks and try to make an interesting suggestion. Palindromes are endian independent, that means that if you take the bytearray and convert to int using little endian or big endian you'll get the same number.

It could be interesting to solve a problem about numbers using it's own properties instead of converting them to strings.

Anonymous said...

two signifant improvements on sylvain's solution:
A)
- 999*999 = 998001, so the biggest possible palindrome is 997799
- incidentally, 231*481 = 111111, so it's a valid candidate
- so the solution is between 111111 and 997799, hence it has 6 digits

- 6 digit palindromes can be generated from numbers from 999 to 100:
999[999], 998[899], 997[799]...

So the outer loop in sylvain's solution can be written this way:

for pal in (int(str(num) + str(num[::-1])) for num in xrange(997,99,-1)):
...

B) less significant improvement: the inner loop can start at math.floor(math.sqrt(pal)) instead of 999

Anonymous said...

@Rafael Augusto: I'm not sure how you mean to use that property, but note that a base 10 palindrome is not a base 2 palindrome (e.g. 11 (base10) = 1011 (base2))

sylvain said...

@mpomme: Ahahaha... You are absolutely right -- I didn't give enough thoughts about the specific meaning of what is a 6 digits base 10 palindrome; your enumeration is a significant improvement.