I'm trying to solve problem 86 in Project Euler. After some tinkering, I managed to unroll the DP solution into a loop. But still the solution takes >150s to complete. What can I do to improve the performance of this algorithm?
(defn- square [n] (* n n)) (defn- is-perfect-square? [n] (let [sq (int (Math/sqrt n))] (= n (* sq sq)))) ;; See: https://math.stackexchange.com/a/1189884/7078 (Second case) ;; So lengths = [sqrt(l^2 + b^2 + h^2 + 2bh), sqrt(l^2 + b^2 + h^2 + 2lb), sqrt(l^2 + b^2 + h^2 + 2lh)] ;; Shortest length is the smallest of the above. == sqrt(l^2 + b^2 + h^2 + min(2bh, 2lb, 2lh)) (defn- shortest-cuboid-dist-has-int-length? ([a b c] (->> (min (* a b) (* b c) (* c a)) (* 2) (+ (square a) (square b) (square c)) (is-perfect-square?))) ([[a b c]] (shortest-cuboid-dist-has-int-length? a b c))) ;; if F(n) denotes number of integer shortest lengths for cuboids with dimensions equal to or less than (n,n,n), ;; F(i+1) = F(i) + int_lengths(cuboids with at least one side dimension of i+1) (defn- get-int-dist-above [lim] (loop [dim 0 c 0 i 1 j 1] (cond (> c lim) dim (= i (inc dim)) (recur (inc dim) c 1 1) (= j (inc i)) (recur dim c (inc i) 1) :else (recur dim (if (shortest-cuboid-dist-has-int-length? dim i j) (inc c) c) i (inc j))))) (defn problem-86  (get-int-dist-above 1000000)) (time (problem-86)) ;; Takes 150s