Skip to content

Problem 9

November 5, 2009

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 you 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,1000ab] | a <- [1..999], b <- [1..999],a^2 + b^2 == (1000ab)^2]

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

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: