Project Euler problem 86 taking a long time

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

Given: 1 ≤ a ≤ b ≤ c = M,

then, min(a*b, b*c, a*c) == a*b

This means, you can remove 2 multiplications and the min operation from shortest-cuboid-dist-has-int-length? as long as you pass your room’s length, width, and height in the proper order.

• In practical terms, replace (min (* a b) (* b c) (* c a)) with (* b c). In my timing tests with lim 70000 this reduces the time from about 8 seconds to about 4 secs. – Peter Taylor Jan 24 at 9:21
• @PeterTaylor Ah! b & c are the shorter dimensions; a is the longest. I couldn’t grok the clojure syntax enough to figure out what was happening in that loop. Thanks. – AJNeufeld Jan 24 at 14:42
• @PeterTaylor “about 8 seconds to about 4 secs” sounds like about double the performance. Not bad for a “micro-optimization” :-) – AJNeufeld Jan 24 at 14:45
• Not bad at all, especially given how counterintuitive micro-optimising Clojure seems to be. I thought it would be better to continue by combining (* b c)(* 2) into (* b c 2), but the runtime jumped up to about 5.5 secs. I suspect that there's an optimiser which is turning (* 2) into a bit-shift, but I'm not certain. – Peter Taylor Jan 24 at 14:59

Micro-optimisation

AJNeufeld's answer removes two multiplications and a min from shortest-cuboid-dist-has-int-length?. The next step, which is a much bigger rewrite, is to remove the remaining multiplications.

Suppose you have cached the value of $$\{len}^2(dim, i, j) = {dim}^2 + i^2 + j^2 + 2ij\$$. Now you increment $$\j\$$: $$\j' = j + 1\$$. Then $$\begin{eqnarray}{len}^2(dim, i, j') &=& {dim}^2 + i^2 + j'^2 + 2ij' \\ &=& {len}^2({dim}, i, j) + 2(i + j) + 1 \\ &=& {len}^2({dim}, i, j) + 2(i + j') - 1\end{eqnarray}$$ So instead of five multiplications you only need one.

Similar caching of $$\{len}^2(dim, i, 1)\$$ allows you to optimise the calculation of $$\{len}^2(dim, i+1, 1)\$$, and caching $$\{len}^2(dim, 1, 1)\$$ allows you to optimise the calculation of $$\{len}^2(dim+1, 1, 1)\$$.

Algorithmic optimisation

I don't want to go into too much detail here because I'm conscious of the ethos of Project Euler, but I think there are some things I can reasonably propose.

Rewrite as $$\{len}^2 = {dim}^2 + (i+j)^2\$$ where $$\2 \le i+j \le 2{dim}\$$. You could use a double loop rather than a triple one, and if you find a value $$\2 \le s \le 2{dim}\$$ for which $$\{dim}^2 + s^2\$$ is a perfect square then increment the count of solutions by the number of integer values of $$\i\$$ for which $$\1 \le i \le s - i \le dim\$$.

Then instead of looping over $$\{dim}\$$ and $$\s\$$ and testing whether they're the shorter legs of a Pythagorean triple, you could look for a way to generate Pythagorean triples and test whether their shorter legs meet the constraints. With a good generation process this is probably the fastest option.

• I actually went in the way of using a previous solution which required generating Pythagorean triples, but gave up halfway because I couldn't figure out how to vary dim. Perhaps I can give a try again. Thank you for all the suggestions. – nakiya Jan 24 at 16:36