Problem 68 was one of those strange problems where you start with 23 lines of code that take 77 seconds to run, and by the time you are done thinking about the problem, you end up with 6 lines of code that takes 0.1 milliseconds to complete.

Optimizing your understanding of a problem apparently can result in improvements of ~770,000 times better performance. I wonder what that says about vague problem definitions and engineering specifications…?

It’s easier to explain this problem with a picture, so just go over to Project Euler and look at the problem for a moment so you understand what I’m doing here.

My first solution was the brute-force approach, which considered all 10!=3628800 possibilities. This is obviously the worst way to do it, but required absolutely no thought about the problem:

(use '[clojure.contrib.combinatorics :only (permutations)])

(defn all-sums-same? [colls]
  (apply = (map #(apply + %) colls)))

(defn n-gon-triples [n coll]
  {:pre [(= (* 2 n) (count coll))]}
  (let [outs (take n coll)
        outmin (apply min outs)
        outers (take n (drop-while #(not (= outmin %)) (cycle outs)))
        inners (drop n coll)
        inner-pairs (take n (partition 2 1 (cycle inners)))]
    (map conj inner-pairs outers)))

(defn euler-68 []
  (apply
   max
   (for [p (permutations (range 1 (inc 10)))
         t [(n-gon-triples 5 p)]
         :when (all-sums-same? t)
         num [(bigint (apply str (mapcat str (flatten t))))]
         :when (= 16 (count (str num)))]
     num)))

 
(time (euler-68 5)) ;; "Elapsed time: 77247.20763 msecs" 

Then I sighed and looked at the problem again, looking for hints as to how I might reduce the problem’s search space.

Since we know that there are only 16 digits in the answer, we know the 10 must be in the outer ring. We also can safely assert that the largest possible output number would result in the inner ring of numbers should being comprised of the smaller numbers, and the outer ring should contain the larger numbers. Since we also know that the number will have to start with the lowest number in the outer ring, we can reduce the number of possibilities from 10! to only 5!+4!=144.

The implementation using these two cribs looked like:

(use '[clojure.contrib.combinatorics :only (permutations)])

(defn all-sums-same? [colls]
  (apply = (map #(apply + %) colls)))

(defn euler-68-faster []
  (apply
   max
   (for [i (permutations (range 1 6))
         o (map #(concat [6] %) (permutations (range 7 11))) 
         t [(map conj (take 5 (partition 2 1 (cycle i))) o) ]
         :when (all-sums-same? t)]
     (bigint (apply str (mapcat str (flatten t)))))))

(time (euler-68-faster)) ;; "Elapsed time: 47.712967 msecs"

But wait! There is a reason this thing is called a ‘magic’ n-gon. We can use that magic number property to deduce essentially everything about the largest possible solution and compute it directly without bothering to compute any permutations at all!

;; Observation:
;; Inner ring must contain the smaller digits
;; Outer ring must contain the larger digits

;; First Trick: Magic Number
;; The 'magic' number is equal to the sum of these 6 numbers divided by 2:
;;   the biggest number in outer ring
;;   the smallest number in outer ring
;;   the two biggest number in inner ring
;;   the two smallest numbers in inner ring

;; Second Trick:
;; Outside ring must have a pattern like [6 10 9 8 7] to be maximum. 
;; ie, lowest in outer ring, followed by remaining numbers in decreasing order.

;; Third Trick:
;; Start with the largest of the inner ring numbers.
;; Going around the inner ring, the next number is (- magic prev-inner outer)

(defn euler-68-magic [n]
  {:pre [(odd? n)]}
  (let [magic (/ (+ 1 2 (inc n) (* 2 n) n (dec n)) 2) 
        outers (concat [(inc n)] (reverse (range (+ 2 n) (inc (* 2 n)))))
        inners (butlast (reductions #(- magic %1 %2) n outers))]
    (apply str (mapcat conj (partition 2 1 (cycle inners)) outers))))


(euler-68-magic 3) ;; "432621513"

(time (euler-68-magic 5)) ;; "Elapsed time: 0.132305 msecs"

Amazing how some reasoning results in us doing such little computation that we make something very nearly a million times faster than the first-try solution.