Arantium Maestum

プログラミング、囲碁、読書の話題

Clojure入門 - Project Eulerを解いてみる 問11

第11問。

20×20の数字のグリッドの中から、縦横斜めのいずれかの方向で連続している四つの数字の商の最大値を求める。

以下ネタバレ。

問題解決に必要なポイントは二つ。

  1. データを読み込んでアクセスしやすい構造にすること
  2. 「四つの連なり」というをどうコードに落とし込むか

まずはデータ読み込み:

(use '[clojure.string :only (split replace)])

(def str-list 
     (-> (slurp "q11_input.txt")
         (replace #"0[0-9]" #(subs %1 1))
         (split #"\n")))

(defn str-to-vec [num-string] (str "[" num-string "]"))

(defn str-to-num [num-string]
  (-> num-string
      (str-to-vec)
      (read-string)))

(def data (map str-to-num str-list))

(defn get-data [i j]
  (nth (nth data i) j))

一番めんどくさかったのは、元のテキストデータが全ての数字を2桁で表すために01などと表記してあり、Clojureの文字→数字の関数が08あたりで例外投げて死んでくれたところ。多分01とかは8進法で評価しているのだろう。無理矢理元のテキスト内で0xをxにreplaceしてから変換。read-stringを使っているのもあまりよろしくないが、この場合はインプットが決まっているので大丈夫。

さて、それではこの問題の最大の肝である「四つの連なり」というをどうコードに落とし込むか、だが。横方向ならiが0-19の間、jが0-16の間で([i j] [i j+1] [i j+2] [i j+3])、などと定義していく方法もあるにはある。が、各方向でiとjが取り得る値をいちいち別々に指定しないといけなかったり、あまり書きやすくも読みやすくもない。

代わりにこうしよう。

まず全ての座標のリストを作る。これは0<=i<20、0<=j<20の[i j]なので400通りある。

(def rows 20)
(def cols 20)
(def adjs 4)

(def indices
  (into #{}
    (for [i (range rows) 
          j (range cols)] 
      [i j])))

次に、これら全ての座標から、縦、横、斜め左下、斜め右下の4方向に四連続する座標のリストのリストを作る。

(def horizontals
  (for [[i j] indices]
    (for [n (range adjs)]
      [i (+ j n)])))

(def verticals
  (for [[i j] indices]
    (for [n (range adjs)]
      [(+ i n) j])))

(def diagonals1
  (for [[i j] indices]
    (for [n (range adjs)]
      [(+ i n) (+ j n)])))

(def diagonals2
  (for [[i j] indices]
    (for [n (range adjs)]
      [(+ i n) (- j n)])))

(def adjacents
  (concat horizontals verticals diagonals1 diagonals2))

四つの座標の連なりのうち、一つでも0<=i<20、0<=j<20の条件から外れる座標が含まれるものは除外する。

(defn all-indices-valid [index-list]
  (every? #(some #{%} indices) index-list))

(def valid-adjs
  (filter all-indices-valid adjacents))

あとはデータと合わせて、これらの座標を数字に変え、四つの数字を掛け合わせて最大値を求めるだけ。

(defn index-to-num [index-vec]
  (apply get-data index-vec))

(defn indices-to-num [index-list]
  (map index-to-num index-list))

(def multiples
  (map #(apply * %) (map indices-to-num valid-adjs)))

(apply max multiples)