Project Euler Problem 28

Ivar Thorson bio photo By Ivar Thorson

Problem 28 asks us to find the sums of the diagonals in a square matrix of numbers created by spiraling outward from the number 1 in a clockwise direction.

My first attempt was a little clunky because I named too many things:

(defn diagonals [start space]
  (take 4 (drop 1 (take-nth space (range start (+ start (* 5 space)))))))

(defn euler-28 [spiral]
  (loop [sum 1
         start 1
         by 2]
    (let [ds (diagonals start by)]
      (if (>= start (* spiral spiral))
        (recur (+ sum (reduce + ds)) (last ds) (+ 2 by))))))

(euler-28 1001)

However, a little thought and I realized I could simplify this a little without too much ugliness:

(defn euler-28-revised [n]
  "Compute the sum of the diagonals in an n by n clockwise spiral. "
  (assert (and (> n 0) (odd? n))) ;; Must be odd to have diagonals!
  (let [diags (fn [m] (take 4 (iterate #(- % (dec m)) (* m m))))
        squares (take-while #(> % 1) (iterate #(- % 2) n))]
    (reduce + (flatten [(map diags squares) 1]))))

(euler-28-revised 1001)

Maybe that code is a bit dense, but it doesn’t have any recursion, which means it should be safe for the stack even for very big spirals. If flatten is incremental, it probably is safe for the heap as well and could be used to compute really really big spirals. Let’s check if flatten is incremental and lazy:

user> (take 6 (flatten (partition 2 1 (range))))
(0 1 1 2 2 3)

Since flatten is working lazily, I am going to guess that when combined with reduce in the above, only a very small number of elements are held in memory here and this will not damage the heap even with a gajillion elements.

I added the assert just to prevent myself from accidentally giving the function meaningless input values, but I’ve seen very little clojure code that uses assert yet so I’m not sure of the proper idiom for using it.