Project Euler problem 9
To sharpen by coding teeth, I’ve started working through the problems on Project Euler in Haskell (while forcing myself to get used to Emacs).
When you solve a problem, you get access to its associated forum thread, where you can see how others solved it. Problem 9 was particularly interesting for me, because I realised how much faster something can be done when you use a formula based on some mathematical insight. Problem 9 is given as:
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a^2 + b^2 = c^2.
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
My first attempt got the answer in about 40 seconds, it uses a list comprehension that is filtered by the constraints:
pythagTriplets = [[a,b,c] |
c <- [1 ..], b <- [1 .. c], a <- [1 .. b],
a^2 + b^2 == c^2, a+b+c == 1000]
solution9 = product (head pythagTriplets)
That is pretty nasty.
I then saw that one guy had solved it without writing a program, using Euclid’s formula
I used Euclid’s insight in a list comprehension with local bindings:
pythagTriplets = [[a,b,c] |
n <- [1 ..], m <- [1 .. n - 1],
let a = n^2 - m^2
b = 2 * m * n
c = n^2 + m^2,
a + b + c == 1000]
solution9 = product (head pythagTriplets)
This version yields the answer almost instantaneously. This really convinced me to learn more maths if I want to get better at this kind of algorithmic stuff. Very much in awe of mathematicians right now.