Problem 9

In this post I will show how did I solve the 9th problem of the Euler project. This was one of the first problems that gave me performance issues and therefore a brute force approach was not good enough. However, I just realised that after building a brute force algorithm :-) I started describing all the conditions stated in the description of the problem. Therefore, I got this Haskell function:

    l = [ [a,b,c] | a <- [1..999],
                    b <- [1..999],
                    c <- [1..999],
                    a+b+c== 1000 && a^2 + b^2 == c^2 && a < b && b < c]

Then, with a simple function called value:

    value = product . head

By executing value l, I reached the following result: (371.90 secs, 32855979636 bytes) As one can see, it is not an interesting result for such a problem. I was just making too many combinations of a, b and c, and most of the conditions were unnecessary. From the problem description, it is possible to deduct that c can be written by means of a and b. Using this simple substitution and removing the unnecessary conditions, I reached this solution:

    h = [[a,b,1000-a-b] | a <- [1..999], b <- [1..999],a^2 + b^2 == (1000-a-b)^2]

After running value h, this was the result: (0.79 secs, 108452856 bytes), which is much better than the first one.