5
\$\begingroup\$

I am trying to teach myself haskell by means of project Euler

i sovled problem #9 by means of this code which is on the brute force side I was wondering if there is a more elegant/haskell/efficient solution

let project_euler_9 = [(a,b,c) | c <- [1..500], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a+b+c==1000 ]
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Your solution main not be the fastest one but it's easy to read. Here's another solution. Also, shouldn't you return the product of (a*b*c)? \$\endgroup\$
    – Larry Battle
    Sep 16, 2012 at 7:56
  • \$\begingroup\$ There are formulas to enumerate all pythagorean triples. You can use them to reduce the search space. \$\endgroup\$
    – nponeccop
    Sep 16, 2012 at 9:24
  • \$\begingroup\$ One thing that you could do is filter the list, a, b, c, to contain only values that have a integer as the square root. \$\endgroup\$
    – Larry Battle
    Sep 18, 2012 at 3:21
  • 1
    \$\begingroup\$ Consider the order of the conditions a+b+c==1000 and a^2+b^2 == c^2 and how that order might affect run time. Also, from a+b+c == 1000 you can replace a <- [1..b] with a = 1000-b-c. \$\endgroup\$
    – ErikR
    Oct 3, 2012 at 21:25

1 Answer 1

Reset to default
3
\$\begingroup\$

As already mentioned there are formulas for enumerating the pythagorean triples, but your solution can be made quite fast by bounding the search space more. You have already taken care of the symmetry in the solutions by letting a be less then b (a <- [1..b]), but note that since a + b + c == 1000, once you know the value of a and b you know that c = 1000 - a - b so you only need to check that one case:

[(a,b,c) | a <- [1..500], b <- [1..a], let c = 1000 - a - b, a^2 + b^2 == c^2]

The above code runs in less then a second on my machine with GHCi.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.