Question
If p is the perimeter of a right angle triangle with integral length sides, \{a,b,c\}, there are exactly three solutions for p = 120.
\{20,48,52\}, \{24,45,51\}, \{30,40,50\}
For which value of p \leq 1000, is the number of solutions maximised?
Haskell
import Data.Function (on)
import Data.List (maximumBy)
solutions :: Int -> [(Int, Int, Int)]
= [(a, b, c) | a <- [1..p `quot` 4],
solutions p let b = (p * (p - 2*a)) `quot` (2 * (p - a)),
let c = floor $ sqrt $ fromIntegral (a^2 + b^2),
+ b + c == p]
a
main :: IO ()
= print $ maximumBy (compare `on` (length . solutions)) [2,4..1000] main
$ ghc -O2 -o right-triangles right-triangles.hs
$ time ./right-triangles
real 0m0.003s
user 0m0.000s
sys 0m0.003s
Python
#!/usr/bin/env python
from collections import defaultdict
def calculate_solutions(limit):
= defaultdict(list)
res 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:
+b+c].append((a,b,c))
res[areturn res
def main():
= calculate_solutions(500)
solutions = max(len(s) for s in list(solutions.values()))
most for p, s in sorted(solutions.items()):
if len(s) == most:
print(p)
if __name__ == "__main__":
main()
$ time python3 triangle-solve.py
real 0m19.434s
user 0m19.433s
sys 0m0.000s
Ruby
#!/usr/bin/env ruby
= {}
solutions 1..500).each do |a|
(..500).each do |b|
(a..500).each do |c|
(bif a**2 + b**2 == c**2
[a+b+c] ||= 0
solutions[a+b+c] += 1
solutionsend
end
end
end
puts solutions.max { |a,b| a[1] <=> b[1] }[0]
$ time ruby triangle-solve.rb
real 0m3.043s
user 0m3.043s
sys 0m0.000s