# Project Euler Problem 39

I found this one to be rather interesting, but maybe I just had a lot of coffee this morning and am in an especially good mood. Problem 39 asks us to find the number n < 1000 for which there are the most number of right triangles with integer sides and a perimeter of n.

Although we could generate triangles at random and then check that they are right triangles using a brute force approach, why would we do that when a variety of equations already let us generate the so-called “pythagorean triples” directly?

(defn pythagorean-triple [m n k]
"Uses Eulcid's formula to generate pythagorean triples."
(map #(* k %) [(- (* m m) (* n n)) (* 2 m n) (+ (* m m) (* n n))]))

(defn pythagorean-perimeters [p]
(let [sq (int (Math/sqrt p))]
(into #{}
(for [n (range 1 sq)
m (range (inc n) sq)
k (range 1 (/ p (+ (* m m) (* n n))))
t [(sort (pythagorean-triple m n k))]
:when (>= p (apply + t))]
t))))

(defn euler-39 []
(let [h (reduce (fn [hsh e]
(if (nil? (hsh e))
(assoc hsh e 1)
(assoc hsh e (inc (hsh e)))))
{}
(map #(apply + %) (pythagorean-perimeters 1000)))]
(reduce #(if (> (h %1) (h %2)) %1 %2) (keys h))))

(time (euler-39)) ;; "Elapsed time: 33.017842 msecs"


Writing pythagorean-perimeters was a little tricky, but once that was in place, pushing everything into a hashmap was a simple way to record the number of ways a particular perimeter could be formed. Performance seems very good, although I think euler-39 could still be improved somehow by using a standard sequence function…

(defn euler-39 []
(let [h (frequencies (map #(apply + %) (pythagorean-perimeters 1000)))]
(reduce #(if (> (h %1) (h %2)) %1 %2) (keys h))))

Ahh, that’s much better.