euler39.clj

;; 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 <= 1000, is the number of solutions maximised?
;; http://projecteuler.net/problem=39


; Any triple of positive integers can serve as the side lengths of an integer
; triangle as long as it satisfies the triangle inequality: the longest side
; is shorter than the sum of the other two sides.
; http://en.wikipedia.org/wiki/Integer_triangle#Integer_triangles_with_given_perimeter
;
; Because the triples must correspond to right angle triangles they have to
; follow the Pythagorean theorem
;   a^2 + b^2 = c^2
; where c is the longest side.

(defn triangle-triples [perimeter]
  (let [min-side 1
        max-side (- perimeter (* 2 min-side))
        hypotenuses (range min-side (inc max-side))]
      (reduce (fn [triples hypotenuse]
                ; For the triple to be an integer triangle the longest side
                ; must be shorter than the sum of the other two sides. Ex.
                ; there's no integer triangle of perimeter 5 with a
                ; hypotenuse of 3, because 3 is NOT shorter than the sum of
                ; the other two sides, which should be 2 (5-3).
                ; So, if the hypotenuse doesn't meet that criteria, there's
                ; no need to explore those triple combinations.
                (if (>= hypotenuse (- perimeter hypotenuse))
                    triples
                    ; How to avoid repetitions? Ex. for triangles with a
                    ; perimeter of 7 how to avoid generating both of these...
                    ;   [4 1 2]
                    ;   [4 2 1]
                    ; For this, the generated triples will be ordered so that
                    ; the second element always corresponds to the second
                    ; longest side. So... what's the range of all possible
                    ; second longest sides?
                    ; The maximum length must be
                    ;   perimeter - hypotenuse - min-side
                    ; OTOH, knowing that...
                    ;   perimeter = hypotenuse + side2 + side3
                    ; and
                    ;   side2 >= side3
                    ; then
                    ;   side2 >= perimeter - hypotenuse - side2
                    ;   2*side2 >= perimeter - hypotenuse
                    ;   side2 >= (perimeter - hypotenuse)/2
                    ;
                    (let [other-sides-max-length
                              (- perimeter hypotenuse min-side)
                          second-longest-side-min-length
                              (long (Math/ceil (/ (- perimeter hypotenuse) 2)))]
                      (concat triples
                              (map #(vector hypotenuse
                                            %
                                            (- perimeter hypotenuse %))
                                   (range second-longest-side-min-length
                                          (inc other-sides-max-length)))))))
              ()
              hypotenuses)))


(defn right-angle-triangle? [[hypotenuse side2 side3]]
  (= (* hypotenuse hypotenuse)
     (+ (* side2 side2) (* side3 side3))))

(defn max-solutions [max-perimeter]
  (let [perimeter-solutions-pairs
          (map (fn [perimeter]
                 {:perimeter perimeter
                  :solutions (filter right-angle-triangle?
                                     (triangle-triples perimeter))})
               (range (inc max-perimeter)))]
       ;; (first (sort-by #(count (:solutions %))
       ;;                 >
       ;;                 perimeter-solutions-pairs))))
       ; Using reduce instead of the code commented out above doesn't require
       ; to sort the entire list and it's quite faster
       (reduce (fn [max perimeter-solutions]
                 (first (sort-by #(count (:solutions %))
                                 >
                                 [max perimeter-solutions])))
               perimeter-solutions-pairs)))

(time
  (println (max-solutions 1000)))
; "Elapsed time: 243849.531 msecs"