Project Euler: Problem 4

If you been following me the last three times I've done this, then you really don't need any introductions.

Problem four is as follows:
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

And my results in the usual three languages are:
Hasekell:

  1. module Main where
  2.  
  3. import Data.List
  4.  
  5. --Stole numberToList code from:
  6. --http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.html
  7. numberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a))
  8.  
  9. is_palimdrome number = num_list == reverse num_list
  10. where
  11. num_list = numberToList number
  12.  
  13. main :: IO ()
  14. main = print . maximum . filter is_palimdrome $ zipWith (*) y z
  15. where y = [1000,999..100]
  16. z = [1000,999..100]

Python:

  1. #!/usr/bin/python
  2.  
  3. def int_to_list(number):
  4. return map(int, str(number))
  5.  
  6. def is_palindrome(number):
  7. local_list = int_to_list(number)
  8. return local_list == list(reversed(local_list))
  9.  
  10. if __name__ == "__main__":
  11. second_list = first_list = list(reversed(range(100,1000+1)))
  12. prod_set = map(lambda i,j: i*j, first_list, second_list)
  13.  
  14. print "%s" % max(filter(is_palindrome,prod_set))

And finally, Perl:

  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5. use List::MoreUtils qw(pairwise);
  6.  
  7. sub is_palimdrone
  8. {
  9. my ($number) = @_;
  10.  
  11. my @digits = split(//, $number);
  12. my @reversed_digits = reverse(@digits);
  13.  
  14. for (my $i = 0; $i < @digits; $i++)
  15. {
  16. return 0 if $digits[$i] != $reversed_digits[$i];
  17. }
  18.  
  19. return 1;
  20. }
  21.  
  22. my @two = my @one = reverse((1..1000));
  23.  
  24. my @join = pairwise { $a * $b } @one, @two;
  25.  
  26. foreach(@join)
  27. {
  28. if ( is_palimdrone($_))
  29. {
  30. print "$_\n";
  31. last;
  32. }
  33. }

Run Times
Haskell: 0m0.034s
Python: 0m0.060s
Perl: 0m0.166s

For anyone that is not aware, haskell should win this statistic every time. Out of the three languages its the only one that is compiled. If anyone knows of a way to run haskell interpretively, and without using ghci, please let me know. I've tried looking on the internets for this piece of information, but have come up short.

I am still open to code suggestions or improvements. I have found these to be very helpful and useful. So thank you to everyone that has said something before.

UPDATE
So here is the new code that fixes the problem of my algo before. I'm leaving the old up just to future readers aren't confused.

Thanks goes out to Jeremiah, Tom.B, Juster, and Guillaume for the code ideas used to fix the mistakes in the code above. Thanks guys!

Haskell:

  1. module Main where
  2.  
  3. import Data.List
  4.  
  5. --Stole numberToList code from:
  6. --http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.html
  7. numberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a))
  8.  
  9. is_palimdrome number = num_list == reverse num_list
  10. where
  11. num_list = numberToList number
  12.  
  13. main :: IO ()
  14. main = print . maximum $ [ x * y | x <- nums, y <- nums, is_palimdrome (x * y)]
  15. where nums = [1000,999..100]

Python:
  1. #!/usr/bin/python
  2.  
  3. def int_to_list(number):
  4. return map(int, str(number))
  5.  
  6. def is_palindrome(number):
  7. local_list = int_to_list(number)
  8. return local_list == list(reversed(local_list))
  9.  
  10. if __name__ == "__main__":
  11. print "%s" % max([x * y for x in range(1000,100, -1) \
  12. for y in range(1000,100,-1) \
  13. if is_palindrome(x * y)])

Perl:
  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5. use List::Util qw(max);
  6.  
  7. sub is_palimdrone
  8. {
  9. my ($number) = @_;
  10.  
  11. my @digits = split(//, $number);
  12. my @reversed_digits = reverse(@digits);
  13.  
  14. for (my $i = 0; $i < @digits; $i++)
  15. {
  16. return 0 if $digits[$i] != $reversed_digits[$i];
  17. }
  18.  
  19. return 1;
  20. }
  21.  
  22. my @two = my @one = reverse((100..999));
  23. my @three;
  24.  
  25. for my $one (@one)
  26. {
  27. for my $two (@two)
  28. {
  29. my $three = $two * $one;
  30. next unless is_palimdrone($three);
  31. push @three, $three;
  32. }
  33. }
  34.  
  35. print max(@three);

Console.WriteLine(Enumerable.

Console.WriteLine(Enumerable.Range(100, 900).Select(n => new {left = n, right = Enumerable.Range(100, 900)}).SelectMany(m => m.right.Select(o => o*m.left)).Where(a => new String(a.ToString().Reverse().ToArray()) == a.ToString()).Max());

Thank you for the comment,

Thank you for the comment, what language is that in?

C Version + last python version

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdbool.h>
  4.  
  5. bool is_palindrome(int const n)
  6. {
  7. unsigned int cum = 0;
  8. unsigned int n2 = n;
  9. while(n2 > cum)
  10. {
  11. cum *= 10;
  12. cum += n2 % 10;
  13. n2 /= 10;
  14. }
  15.  
  16. return n2 == cum;
  17. }
  18.  
  19.  
  20. unsigned int find_palindrome()
  21. {
  22. unsigned int max_palin = 0;
  23. unsigned int minj = 99;
  24.  
  25. for(unsigned int i = 999; i > 99; i--)
  26. {
  27. if(i*i < max_palin)
  28. {
  29. break;
  30. }
  31. for(unsigned int j = i; j > minj; j--)
  32. {
  33. unsigned int const new_palin = i*j;
  34. if(is_palindrome(new_palin))
  35. {
  36. minj = j;
  37. if(new_palin > max_palin)
  38. {
  39. max_palin = new_palin;
  40. }
  41. break;
  42. }
  43. }
  44. }
  45.  
  46. return max_palin;
  47. }
  48.  
  49. int main()
  50. {
  51. unsigned int const max = find_palindrome();
  52. printf("%d\n",max);
  53. for(unsigned int i = 0; i < 10000; i++)
  54. {
  55. unsigned int const max = find_palindrome();
  56. }
  57. }

  1. def find_palindrome():
  2. max_palin = 0
  3. minj = 99
  4.  
  5. for i in xrange(999,99,-1):
  6. if i*i < max_palin:
  7. # because new tested values are less or equal i*i, we can stop
  8. # because their is no palindrom that is bigger that the current one
  9. break
  10.  
  11. # iter between i and minj for j
  12. # - i because it useless to have a value of j which is bigger than i (we
  13. # allready tested that case)
  14. # - to minj because the last founded palindrom was (i+n) * minj, so i *
  15. # min_j is smaller
  16. for j in xrange(i, minj, -1):
  17.  
  18. # the is_palindrom test as been inline because it is quite simple
  19. # and give really good speed
  20. new_palin = i*j
  21. s = str(new_palin)
  22. if s == s[::-1]:
  23. minj = j
  24. max_palin = max(new_palin, max_palin)
  25.  
  26. # We can shortcut the loop, because with that value of i, it is
  27. # useless to test lower values of j
  28. break
  29.  
  30. return max_palin
  31.  
  32. if __name__ == '__main__':
  33. import timeit
  34. print find_palindrome()
  35.  
  36. # return the time of one run, tested for 10000 runs
  37. print timeit.Timer('find_palindrome()','from __main__ import find_palindrome').timeit(10000) / 10000

times:

C

% 14:54 guillaume@guillaume-desktop ~ gcc -std=c99 -O3 -march=native palindrom.c
% 14:54 guillaume@guillaume-desktop ~ time ./a.out
906609
./a.out 0.87s user 0.01s system 100% cpu 0.878 total

ie ~0.08ms / run

Python

% 14:16 guillaume@guillaume-desktop ~ time python palindrome.py
0.00366615915298
python palindrome.py 3.68s user 0.00s system 99% cpu 3.687 total

for 1000 runs, ie, 3ms / run

Pypy
% 14:17 guillaume@guillaume-desktop ~ time pypy palindrome.py
0.00065650241375
~/src/pypy/pypy-1.3/bin/pypy palindrome.py 6.56s user 0.01s system 99% cpu 6.576 total

for 10000 runs, ie ~0.6ms runs.

5x faster Python and psyco only helped a little.

  1. #!/usr/bin/python
  2. import time, psyco
  3.  
  4. psyco.full()
  5.  
  6. def is_palindrome(number):
  7. local_list = "%s"%number
  8. local_list1 = list(local_list[:])
  9. local_list1.reverse()
  10. return local_list == "".join(local_list1)
  11.  
  12. def main():
  13. maxVal=0
  14. for x in range(1000,100, -1):
  15. for y in range(1000,100,-1):
  16. if is_palindrome(x * y):
  17. maxVal = max(x * y, maxVal)
  18. return maxVal
  19.  
  20. if __name__ == "__main__":
  21. t1 = time.time()
  22. print main()
  23. print time.time() - t1

Hey Darrell, thanks for

Hey Darrell, thanks for joining the conversation.

I will admit that your code it is a lot faster. However, your code is also producing the wrong answer. If it makes you feel better I was getting the same answer when I first started this problem and in playing around with things a little more I realized it. These puzzles are kind of tricky that way. ;) If you take a second to read through the comments you should get a pretty strong hint on how to fix it.

Why are you saying that his

Why are you saying that his code is false. For me it gives the right answer which is 906609.

But by the way I'm still does not understand why:

1) Every one iter in reverse. If you evaluate all the possibilities, the order of iteration does not change anything.
2) Why everyone writes really complex is_palindrom function when the really simple I proposed one week ago is faster ;)

I said what I said because

I said what I said because when I copied his code, I got 580085 as my answer. I might have copied it wrong. (I'm not able to check at the moment, I will when I get home.)

And I totally agree with you Guillaume, your is_palindrome function is as concise as it could possibly be. I know I wrote mine out that way because I wasn't aware of being able to reverse a string with a simple [::-1]. I can't speak for everyone else, but that is certainly going into my python toolbox.

My haskell solution from way back

To convert numbers to a list, I just abused show:

  1. isPalindrome n = n == (read (reverse (show n))::Int)
  2. solution = maximum [ a * b | a <- [100..999], b <- [a..999], isPalindrome (a * b) ]

Your isPalindrome function is

Your isPalindrome function is rather nice Bro! Looks to be a greatly more efficient way of doing the reverse check than what I have. Going to have to remember this method. :)

Spot the subtle optimisation

Hey mate,

There's a subtle optimisation in my solution that I can't see in anyone else's so far. Can you see it? :)

Blog post about Euler #4 in Perl

I did a series of blog posts about Euler #4 in Perl:

* http://transfixedbutnotdead.com/2009/11/21/between-thought-and-expression/
* http://transfixedbutnotdead.com/2009/11/26/euler-euler-euler-oi-oi-oi/
* http://transfixedbutnotdead.com/2009/11/30/eulergy/

First post pulls in Clojure, Python & Ruby examples as well.

/I3az/

Still some optimisation for haskell

Like my python optimisation you don't use in the post update, there is a way to optimise is_palindrome in haskell:

  1. is_palimdrome number = num_list == reverse num_list
  2. where
  3. num_list = show number

@home, it runs five time quicker.

Now for the main loop:

  1. find_palindrome :: Int -> Int -> Int -> Int -> Int
  2. find_palindrome current_max minj i j
  3. | is_palimdrome number = find_palindrome (maximum [current_max,number]) j (i-1) (i-1)
  4. | j == minj = find_palindrome current_max minj (i-1) (i-1)
  5. | i == 99 = current_max
  6. | otherwise = find_palindrome current_max minj i (j-1)
  7. where
  8. number = i*j
  9.  
  10. main :: IO ()
  11. main = print (find_palindrome 0 99 999 999)

It's the first time I wrote haskell of my life, so some stuff may be wrong, but I win ten times the speed ;)

You seem to be picking up

You seem to be picking up Hasekll pretty quickly. Congratulations! You palindrome does look to be much faster than mine. I can't help but feel that is the haskell translation of the Python code you submitted in your first post.(Not trying to be insulting, just stating an observation.)

I didn't just copy your previous code because I need to figure this stuff out for myself (Haskell especially) and just blindly copying code doesn't allow me to learn anything. So I look at the code that everyone has shared and then I try to incorporate into mine.

With pypy and a better algo

Hello again.

The code I suggested yesterday, ie:

  1. def is_palindrome(number):
  2. s = str(number)
  3. return s == s[::-1]
  4.  
  5. print max((i*j,i,j) for i in range(100,1000) for j in range(100,1000) if is_palindrome(i*j))

can really be upgraded, like that :

  1. def find_palindrome():
  2. max_palin = 0, (0,0)
  3. minj = 99
  4.  
  5. for i in xrange(999,99,-1):
  6. for j in xrange(i-1, minj, -1):
  7. if is_palindrome(i*j):
  8. minj = j
  9. max_palin = max((i*j, i, j), max_palin)
  10.  
  11. return max_palin

Currently I get 5ms / run (median of 1000 run with timeit) with python2. It drops to 4ms / run if I inline the is_palindrome function.

with pypy 1.3 it drops to 1.4 ms without inline and 0.9 ms with inline.

Note: quad core i7 here, but only one core used.

There is still room for improvment.

Use xrange(i, minj, -1) to

Use xrange(i, minj, -1) to allow square values to be evaluated

great idea

juster,

  1. shift @a;

It's a great idea, I didn't see it
I added a Benchmark module in order to avoid the interpreter startup

Problem with my code

Thank niceperl. My solution was pretty much the same as yours other than that. In my script I'm not sure if only looping from 900 to 999 is fair. Owell it's all for fun. I'm glad we represented perl.

Sadly there is an error in my code. I should not have modified the array while looping over it with for. Instead it is better to make two copies of the array, one for the inner and one for the outer loop. The for loop in my post actually skips every other number. Let this be a warning to others!

Thanks Bryce for being brave enough to post code on your blog and be open to suggestions. I must also thank you for fixing the perl codetags and getting me hooked on project euler! The number theory is very fun.

Thanks for that comment

Thanks for that comment Juster!! Its not everyday that I get a comment like that.

And you might want to wait a little while before you thank me for introducing you to Project Euler. In a couple of months you might be cursing my name for the same reason after losing sleep to solve problems and the like. ;)

I agree this number theory stuff is fun, its a great way to stretch your normal programming patterns. I'm glad your starting to enjoy it.

More Perl and Optimizing

Just another perl hacker, here. You should not use List::MoreUtil's "pairwise" for this problem. What you want instead is something similar to the cartesian product of the two sets of numbers. Pairwise shifts each array, and operates on those two elements. When using pairwise you can only find palindromes made out of squares.

My solution doesn't check the same product twice and also uses Jeremiah's trick to only check between 900-999. It's a little faster than niceperl's because of these tricks. Niceperl's is the only other perl example that gives the correct answer.

  1. my @nums = reverse 900..999;
  2. for my $x ( @nums ) {
  3. shift @nums; # <-- don't check things twice
  4. for my $y ( @nums ) {
  5. my $z = $x * $y;
  6. next unless $z eq reverse $z;
  7. print "$x * $y = $z\n";
  8. exit 0;
  9. }
  10. }

PS why is there no perl sourcecode tag? I had to use ruby. :(

Hey juster, Thanks for

Hey juster,

Thanks for posting.

First off I'll look into the Perl source tags problem and thanks for saying something.

I also agree with what your saying regarding pairwise. It was a flaw in my logic (in all 3 languages ). I programmed Perl to work similarly to what you wrote. But I ended up changing it because I thought this was a more clever way of doing it. Turns out that ultimately I should have stuck with the original idea for Perl.

Thanks again for the comment and sharing of your code.

Just as a quick update to my

Just as a quick update to my own post. I have fixed things so that both the perl & haskell code tags work. Again thanks Juster for saying something.

better perl implementation


use strict;
use Benchmark ':hireswallclock';

sub main {
my ($r, $p, $a, $b) = (0, 0);
my @a = reverse (100..999);
A: foreach $a(@a) {
foreach $b(@a) {
$r = $a * $b;
next A if( $r <= $p );
$p = $r if $r eq reverse($r);
}
}
print $p, "\n";
}

my $t = timeit(1, 'main');
print timestr($t),"\n";

#results (on my laptop): 0.00717092 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU)

Faster variant def

Faster variant


def is_palindrome (number):
n = str (number)
if n [0] != n [-1]:
return False
n = n [1:-1]
while len (n)>1 and n[0]==n[-1]:
n = n [1:-1]
return len (n) <= 1

I'm not sure I quite

I'm not sure I quite understand your problem, but

1) is_palindrom can be writed like

#!/usr/bin/python
def is_palindrome(number):
s = str(number)
return s == s[::-1]

2) your algo is false, you only find the square of a number of three digits that is palindrome. The real answer is 906609 = 993 x 913

it can be found with this trivial algo:

print max((i*j,i,j) for i in range(100,1000) for j in range(100,1000) if is_palindrome(i*j))

Here :

real 0m4.293s
user 0m2.316s
sys 0m0.029s

3) quicker with

print max((i*j,i,j) for i in xrange(100,1000) for j in xrange(i+1,1000) if is_palindrome(i*j))

Hi Guillaume, After looking

Hi Guillaume,

After looking at what you posted I have to agree with you that I did get my algo wrong. Using your examples I see where I made my mistakes and I will fix them shortly.

Thanks also for the python code posted. I think incorporating both your second solution with Tom's range(1000,100,-1) technique would be more efficient in finding the highest palindrome numeral.

Thanks again for posting and sharing. I appreciate it!

But I'm wondering, why are

But I'm wondering, why are your iterating in reverse order ?

You can assume that the

You can assume that the number is closer to the top of the range. For two digit numbers it is 9009 = 91 × 99. So if you start with 99x99, it will take fewer tests than starting with 10x10.

Yes, but this does changes

Yes, but this does changes nothing in this code, because all the options are evaluated.

Is that code correct?

Unless a requirement is missing, I believe your code is incorrect. The code given is calculating perfect squares, then finding the largest one that's a palindrome.

It's giving 698896, which is 836*836, but the answer should be 993*913 = 906609.

Calculated using this Python code:

  1. #!/usr/bin/python
  2.  
  3. def is_palindrome(number):
  4. return str(number) == str(number)[::-1]
  5.  
  6. if __name__ == "__main__":
  7. # Assumes that the largest palindrome will be created by two numbers in the range 900-1000
  8. print('{}*{} = {}'.format(*max((i,j,i*j)
  9. for i in range(1000, 900, -1)
  10. for j in range(1000, 900, -1)
  11. if is_palindrome(i*j))))

Fixed Haskell

Simple fix for the Haskell:

  1. main :: IO ()
  2. main = print . maximum $ [x*y | x <- nums, y <- nums, is_palimdrome (x*y)]
  3. where nums = [1000,999..100]

avoiding duplicates in the list comprehension is faster

The version below is faster as it avoids duplicate numbers in the list comprehension. Also since 1000 is a 4 digit number and the problem states "... product of two 3-digit numbers" then nums = [999, 998..100]
giving

  1. main :: IO ()
  2. main = print . maximum $ [x*y | x <- nums, y <- nums, x >= y, is_palimdrome (x*y)]
  3. where nums = [999, 998..100]

Hey Jeremiah, thanks for the

Hey Jeremiah, thanks for the code posts. Both the Python & Haskell code snippets.

I tried using your python code, but I had issues. So I just copied your list comprehension from your haskell code and translated it to python and put it there.

Thanks again for sharing!

For the Python example, line

For the Python example, line 11 could be:
second_list = first_list = range(1000, 99, -1)

That should be faster than creating the initial list (call to range), creating an iterator that reverses the values, then converting that iterator to another list. I'm not sure how significant (if at all) the difference would be, but it's probably worth testing.

Also I'm curious to know why you used 2 different references to the same list (first_list and second_list) instead of just 1 (map can take the same argument multiple times). Since it's still the same list I doubt there would be any appreciable performance penalty, but it's also unnecessary code IMHO.

Other than that, neat examples!

Hey Tom, Thanks for the post

Hey Tom,

Thanks for the post and also thanks for the way to use range backwards. Its one of those pieces of code that after looking at it I slapped my hand to my forehead because its simple enough that I should have been able to figure it out on my own yet didn't.

I'll incorporate this change into my next revision, as it has to be more efficient than creating a range and then revering it.

Entire problem

In fact, your entire problem can be expressed as:

use strict;
use warnings;
use List::MoreUtils qw(pairwise);
use List::Util qw(first);

my @nums = reverse 100 .. 999;
print first { $_ eq reverse $_ } pairwise { $a * $b } @nums, @nums;

sub is_palimdrone { $_[0] eq

sub is_palimdrone { $_[0] eq reverse $_[0] }

is far shorter and neater :)

Hey Paul, Thanks for the

Hey Paul,

Thanks for the comment also that is a much cleaner version of palindrome verification than both of our code. Also, as mentioned by Juster above and in regards to your previous comment, pairwise isn't a good function to use for this problem because it manipulates $a and $b together. so you get 1000 * 1000, 999 * 999, etc. Instead of the needed 1000 * 999.

Thanks again for the code submittal!

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share