Project Euler Problem 39 Solution

Question

If pp is the perimeter of a right angle triangle with integral length sides, {a,b,c}\{a,b,c\}, there are exactly three solutions for p=120p = 120.

{20,48,52},{24,45,51},{30,40,50}\displaystyle \{20,48,52\}, \{24,45,51\}, \{30,40,50\}

For which value of p1000p \leq 1000, is the number of solutions maximised?

Haskell

import Data.Function (on)
import Data.List (maximumBy)

solutions :: Int -> [(Int, Int, Int)]
solutions p = [(a, b, c) | a <- [1..p `quot` 4],
                           let b = (p * (p - 2*a)) `quot` (2 * (p - a)),
                           let c = floor $ sqrt $ fromIntegral (a^2 + b^2),
                           a + b + c == p]

main :: IO ()
main = print $ maximumBy (compare `on` (length . solutions)) [2,4..1000]
$ ghc -O2 -o right-triangles right-triangles.hs
$ time ./right-triangles
real   0m0.004s
user   0m0.000s
sys    0m0.000s

Python

#!/usr/bin/env python
from collections import defaultdict
        
def calculate_solutions(limit):
    res = defaultdict(list)
    for a in range(1, limit+1):
        for b in range(a, limit+1):
            for c in range(b, limit+1):
                if a**2 + b**2 == c**2:
                    res[a+b+c].append((a,b,c))
    return res
            
def main():
    solutions = calculate_solutions(500)
    most = max(len(s) for s in list(solutions.values()))
    for p, s in sorted(solutions.items()):
        if len(s) == most:
            print(p)

if __name__ == "__main__":
    main()
$ time python3 triangle-solve.py
real   0m18.075s
user   0m17.952s
sys    0m0.008s

Ruby

#!/usr/bin/env ruby
solutions = {}
(1..500).each do |a|
  (a..500).each do |b|
    (b..500).each do |c|
      if a**2 + b**2 == c**2
        solutions[a+b+c] ||= 0
        solutions[a+b+c] += 1
      end
    end
  end
end
puts solutions.max { |a,b| a[1] <=> b[1] }[0]
$ time ruby triangle-solve.rb
real   0m3.305s
user   0m3.280s
sys    0m0.000s

Questions? Comments? Send me an email: z@chdenton.com