プロジェクトオイラー28問目

プロジェクトオイラーの28問目。

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

という5×5のスパイラルがあったとき、[1]、[3 5 7 9]、[13 17 21 25]という各サイズの正方形の角にある数字の合計は101。では、1001×1001のスパイラルのときの合計は。

Clojureで書いてみる。

(defn corner-total [n]
     (let [max (* n n)
	   diff (- n 1)]
       (if (not (== n 1))
	 (- (* max 4)
	    (* diff (+ 1 2 3)))
	 1)))

(defn total [n]
  (reduce + 
	  (map corner-total (range 1 (+ n 1) 2))))

(println
 (total 1001))

再帰っぽく。

(defn corner-seq [seq n]
  (let [start (* n n)
	diff (- n 1)]
    (if (== n 1)
      (cons 1 seq)
      (recur
       (concat (range (- start (* diff 3)) (+ start 1) diff) seq)
       (- n 2)))))
  
(defn e28 [n]
  (println
   (corner-seq () n))
  (println
   (reduce + (corner-seq () n))))

(e28 1001)

シーケンスって何だ。よくわからん。

TCOは再帰の呼び出しのところをrecurと明示的に書き直すだけでいいらしい。この例だと10万ぐらいの値を渡すとスタックオーバーフローを起こすけど、corner-seqをrecurにすると落ちなくなる。