2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jan 24 at 9:21
  • \$\begingroup\$ @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. \$\endgroup\$ – AJNeufeld Jan 24 at 14:42
  • \$\begingroup\$ @PeterTaylor “about 8 seconds to about 4 secs” sounds like about double the performance. Not bad for a “micro-optimization” :-) \$\endgroup\$ – AJNeufeld Jan 24 at 14:45
  • \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jan 24 at 14:59
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – nakiya Jan 24 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.