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)) sum (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)
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.