Project Euler Problem 62

Ivar Thorson bio photo By Ivar Thorson

Problem 62 asks us to find the smallest cube which, when permuted, can form 4 other cubes.

This is a piece of cake to solve if you choose the right approach. Rather than starting with a cube, making permutations of it and filtering again for cubicity, we can avoid a tremendous amount of work by simply converting each cube to a standard (sorted) permutation, and then testing for equality with the other cubes.

For convenience, let’s just push the cubes’ standard (i.e. sorted) permutations into a hash, and as soon as a key has 5 entries in it we can quit.

(defn euler-62 []
  (loop [m {}
         n 1]
    (let [c (* n n n)
          k (sort (str c))
          e (conj (m k) c)]
      (if (<= 5 (count e))
        (last e)
        (recur (assoc m k e) (inc n))))))

(time (euler-62)) ;; "Elapsed time: 102.420625 msecs"

Efficient and concise. See you tomorrow!