Project Euler: Problem 9

Happy New Year Ladies(?) and Geeks

Trying to get the year off to a good start, I'm posting up my solution for the ninth Project Euler problem. I'm not going to spend a lot of time talking about it, because the solution is a pretty easy one. Here is the code in Python:

  1. #!/usr/bin/python3
  2. """
  3. python solution for project euler problem #9.
  4. """
  5.  
  6. print( [a*b*(1000 - b -a) for a in range(1,500+1) for b in range(1,500+1) \
  7. if a * a + b * b == ((1000 -b -a) * (1000 - b - a))][0])

And here is the code in Haskell:

  1. module Main where
  2.  
  3. main :: IO()
  4. main = print . head $ [a*b*(1000-b-a) | a <- [1..500] , b <- [1..500], a ^ 2 + b ^ 2 == (1000 - b - a) ^ 2]

See, it really is that simple. There really isn't anything interesting between to the solutions, but I would like to make a quick note on the luxury of being able to use “head” in Haskell to simplify the whole process. In the Python solution, the answer is generated twice, that's just the nature of the algorithm, and to just get one number, I just ask for the first item in the list. Thanks to Haskell's lazy evaluation, I only have to calculate the answer once, and I think this may be reflected in the run times.

So now the part that I know everyone loves to read the most, Times:

python-2.6.6 : .165s
python-3.1.2 : .110s
haskell(runghc) : 1.921s
haskell(compiled) : .086s

problem solved in c#

https://sites.google.com/site/eulerproblemsincsharp/home/problem-9

just use numpy arange

[user@server ~]$cat euler_9.py
#!/usr/bin/env python
"""
python solution for project euler problem #9.
"""
import numpy as np
from datetime import datetime as time
t0 = time.now()
print( [a*b*(1000 - b -a) for a in np.arange(1,500+1) for b in np.arange(1,500+1) \
if a * a + b * b == ((1000 -b -a) * (1000 - b - a))][0])

print time.now()-t0
[user@server ~]$python euler_9.py
31875000
0:00:02.703267

I guess it depends on the machine as well...

Thanks for the comment John,

Thanks for the comment John, I'm a little confused why I would want to use numpy's arange instead of pythong's builtin range function. What are the benefits of arange over range?

Weirdly, it seems that the

Weirdly, it seems that the plain old dumb way of coding is faster than all others.

  1. def dumb_solution():
  2. for a in range(1, limit + 1):
  3. for b in range(1, limit + 1):
  4. c = 1000 - b - a
  5. if a * a + b * b == c * c:
  6. return a * b * c

Even more weirdly, the use of xrange slows down the computation!

You can make the python version a tad shorter

by using:
(1000 - b - a) ** 2
instead of:
(1000 - b - a) * (1000 - b - a)
Not sure what is the effect on run time

You know Gaetan, I tried

You know Gaetan, I tried that. But just as a little "I wonder" moment. Doing it my way actually turned out to have lower run times on my machine. Granted these weren't huge differences, and your version is MUCH more readable and maintainable. I wanted to post the correct code for my runtimes.

I will also admit that I find it kind of weird that my run times would be affect by such a change. But then, my run times aren't exactly accurate.

pypy is faster by more than an order of magnitude (or two)

Combining Jack's suggestion with my own:
s="(a*b*(1000 - b -a) for b in xrange(1,500+1) for a in xrange(b,500+1) if a * a + b * b == ((1000 -b -a) * (1000 - b - a))).next()"

(C)Python 2.6.4:
>>> min(timeit.Timer(s).repeat(100, 10))
0.28002095222473145

pypy 1.4.1 (Python 2.5.2):
>>>> min(timeit.Timer(s).repeat(10000, 10))
0.0070629119873046875

For reference, using your original python statement on (C)Python 2.6.4:
>>> min(Timer(s).repeat(100, 10))
0.88044905662536621

Use Python Generators

To find the first matching item and stop use python generator comprehensions. These print the same thing but the second version stops when it hits 3.
print [x for x in range(10) if x == 3][0]
print (x for x in range(10) if x == 3).next()

Now your python version should be as fast as the Haskell version.

Thanks for that code and the

Thanks for that code and the idea of using generators Jack. Those generators are definitely something I need to put into my python toolbox.

Improve your algorithm

print( [a*b*(1000 - b -a) for b in xrange(1,500+1) for a in xrange(b,500+1) if a * a + b * b == ((1000 -b -a) * (1000 - b - a))][0])

Thanks for the improvement

Thanks for the improvement Benjamin, that enhancement alone but my runtime in half.

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