Project Euler Problem 86

Ivar Thorson bio photo By Ivar Thorson

Despite it’s relative simplicity, I wasted hours on problem 86. One important thing that I learned is:

Sometimes you absolutely must formulate the problem in an incremental form!

My long and complex first attempt at this problem began by generating Pythagorean triples (as we did in previous problems), and computing cuboids whose geodesics were the same as those triples. Unfortunately, although this worked well, I did not formulate it in an incremental manner, so at best it would have O(n^2) performance for this kind of incremental search problem, as I realized in the final step.

On the other hand, if you formulate the problem in an incremental form, it is remarkably simple to solve:

(defn square? [x] (= x (expt (int (sqrt x)) 2)))

(defn cuboids [m]
  (reduce
   +
   (for [a (filter #(square? (+ (* % %) (* m m)))
                   (range 1 (inc (* 2 m))))]
     (if (> a m)
       (- (quot a 2) (- a m 1))
       (quot a 2)))))

(defn euler-86 [L]
  (count (take-while #(> L %) (reductions + (map cuboids (range))))))

(time (euler-86 1000000)) ;; "Elapsed time: 3872.220781 msecs"