Project Euler Problem 11

problem_11.clj

;;; In the 20x20 grid below, four numbers along a diagonal line have been marked in red.
;;;   :
;;; (snip)
;;;   :
;;; The product of these numbers is 26 * 63 * 78 * 14 = 1788696.
;;; What is the greatest product of four adjacent numbers
;;; in any direction (up, down, left, right, or diagonally)  in the 20x20 grid?

(ns projecteuler.problem-11
  (:use clojure.test))

(def grid-size-w "問題文の配列のサイズ(横20)" 20)

(def grid-size-h "問題文の配列のサイズ(縦20)" 20)

(def grid-20x20- "問題文の(w)x(h)の数字列"
  '( 8  2 22 97 38 15  0 40  0 75  4  5  7 78 52 12 50 77 91  8
    49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48  4 56 62  0
    81 49 31 73 55 79 14 29 93 71 40 67 53 88 30  3 49 13 36 65
    52 70 95 23  4 60 11 42 69 24 68 56  1 32 56 71 37  2 36 91
    22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
    24 47 32 60 99  3 45  2 44 75 33 53 78 36 84 20 35 17 12 50
    32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
    67 26 20 68  2 62 12 20 95 63 94 39 63  8 40 91 66 49 94 21
    24 55 58  5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
    21 36 23  9 75  0 76 44 20 45 35 14  0 61 33 97 34 31 33 95
    78 17 53 28 22 75 31 67 15 94  3 80  4 62 16 14  9 53 56 92
    16 39  5 42 96 35 31 47 55 58 88 24  0 17 54 24 36 29 85 57
    86 56  0 48 35 71 89  7  5 44 44 37 44 60 21 58 51 54 17 58
    19 80 81 68  5 94 47 69 28 73 92 13 86 52 17 77  4 89 55 40
     4 52  8 83 97 35 99 16  7 97 57 32 16 26 26 79 33 27 98 66
    88 36 68 87 57 62 20 72  3 46 33 67 46 55 12 32 63 93 53 69
     4 42 16 73 38 25 39 11 24 94 72 18  8 46 29 32 40 62 76 36
    20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74  4 36 16
    20 73 35 29 78 31 90  1 74 31 49 71 48 86 81 16 23 57  5 54
     1 70 54 71 83 51 54 69 16 92 33 48 61 43 52  1 89 19 67 48))

(def problem-grid "問題文の(w)x(h)の配列(vectorで作る)。"
  (->> grid-20x20-
       (partition grid-size-w)
       (map vec)
       vec))

(defn get-value-at-xy
  "[x, y]の位置にある数値を取ってくる(範囲外の座標が指定されたらnilを返す)。"
  [x y]
  (if (or (< x 0) (>= x grid-size-h) (< y 0) (>= y grid-size-h)) nil
      (nth (nth problem-grid y) x)))

(def offset-map
  "連続した4つの数値を取ってくるためのoffset(4方向)"
  [[[ 0 0] [ 1 0] [ 2 0] [3 0]]   ;; - horizontal
   [[ 0 0] [ 0 1] [ 0 2] [0 3]]   ;; | vertical
   [[ 0 0] [ 1 1] [ 2 2] [3 3]]   ;; \ diagonally
   [[-3 3] [-2 2] [-1 1] [0 0]]]) ;; / diagonally

(defn get-4-values
  "[x, y]を起点とした4つの連続した数値をリストにして返す。"
  [x y xyvec]
  (->> xyvec
       (map (fn [[dx dy]] (get-value-at-xy (+ x dx) (+ y dy))))
       (filter (comp not nil?))))

(defn get-values-all
  "盤面上のすべての数値に対し、xyvec で指定された方向の値をリストにして返す。"
  [xyvec]
  (for [x (range grid-size-w) y (range grid-size-h)]
    (get-4-values x y xyvec)))

;;; (mapcat get-values-all offset-map)
;;; => ((8 2 22 97) (49 49 99 40) (81 49 31 73) ... (89 57 36 36) (19 5 16) (67 54) (48))

(defn problem-11
  "Project Euler Problem-11"
  []
  (->> (mapcat get-values-all offset-map)
       (map #(apply * %))
       (apply max)))

(defn problem-11
  "Project Euler Problem-11"
  []
  (->> (mapcat get-values-all offset-map)
       (map #(apply * %))
       (apply max)))

;;;=> result
;;;???

;;; test code for `get-value-at-xy`
(are [x y expected] (= expected (get-value-at-xy x y))
     0 0 8
     0 19 1
     0 20 nil
     19 0 8
     20 0 nil
     19 19 48)

;;; test code for `get-4-values` (direction: horizontal)
(are [x y expected] (= expected (get-4-values x y (first offset-map)))
     0 0 '(8 2 22 97)
     18 0 '(91 8)
     0 20 ())

;;; test code for `get-4-values` (direction: vertical)
(are [x y expected] (= expected (get-4-values x y (second offset-map)))
     0 0 '(8 49 81 52)
     0 18 '(20 1)
     20 0 ())

;;; test code for `get-4-values` (direction: diagonally '\')
(are [x y expected] (= expected (get-4-values x y (nth offset-map 2)))
     0 0 '(8 49 31 23)
     18 18 '(5 48)
     20 0 ()
     0 20 ())

;;; test code for `get-4-values` (direction: diagonally '/')
(are [x y expected] (= expected (get-4-values x y (nth offset-map 3)))
     0 0 '(8)
     1 0 '(49 2)
     2 0 '(81 49 22)
     3 0 '(52 49 99 97)
     0 1 '(49)
     20 0 '(2 36 0)
     19 0 '(37 13 62 8)
     19 19 '(48)
     20 19 ())

考え方とか感想とか

• 問題の数値を 20x20 の２次元配列にしています(vector)。
• すべてのマス目に対して、縦横斜めの４つの数値を取得してリストにします。
• 取得したリストの各要素を掛け算して最大の値を答えとします。
• 問題の領域がさほど大きくなかったので、今回も力技でやりました。
• 一度公開して「あれ？間違ってる？？？」ってなったのですが、結局は間違ってませんでしたorz。

最初のリビジョン を見ています.
［全ての点について『4つの「4つの dx, dy の組」について』］という解法はすっきりしていて良いと思います.

構造
problem-11 -> get-values-all -> get-4-values -> get-value-at-xy
という呼出し階層の底に問題の入力である problem-grid がハードコードされており
problem-grid も grid-20x20- をハードコードしています.

• 複数の入力を与えられたとき
• 入力のサイズが変わったとき

などに, 呼出しのトップでなく, 呼出しの底のコードを改変しなければならないので, それぞれの段階であまり汎用的なコードになっていないことが分かります.
(もちろんこの問題を解く分には十分ですが, 問題を題材にした勉強ということで)

何カ所かダイナミックスコープの変数にして, binding で包むようにすると, 入力を置き換えられるようになりますが, それよりも, 全体の構造を見直してみると良いかもしれません.

keep

(filter (comp not nil?) (map f coll))

の (comp not nil?) は identity で良いですね.
さらに, (filter identity (map f coll)) 相当の keep という関数があって
(keep f coll)
と書けます. (私も最近知ったのですが.)
例

user=> (keep (fn [x] (if (pos? x) (* x x))) '(3 0 4 -1 5))
(9 16 25)

例えば, (引数の引き回しが少々煩わしいですが)

(defn get-value-at-xy
  [x y mat w h]
  (if (or (< x 0) (>= x w) (< y 0) (>= y h)) nil
      (nth (nth mat y) x)))
                                ; for example
(defn problem-11 [grid w h]     ; grid (range 25) w 5 h 5
  (let [mat (partition w grid)] ; mat '((0 1 ...) (5 ...) (10 ...) (15 ...) (20 ...))
    (...
      (for [y (range h)         ; y 1                                          
            x (range w)         ; x 2                                          
            xyvec offset-map    ; xyvec [[0 0] [0 1] [0 2] [0 3]]              
            :let [xys (map (fn [[dx dy]] [(+ x dx) (+ y dy)]) xyvec)
                                ; xys [[2 1] [2 2] [2 3] [2 4]]
                  four (keep (fn [[x y]] (get-value-at-xy x y mat w h)) xys)]]
                                ; four [7 12 17 22]
        ...))))

という構造では如何でしょうか.

汎用性を考えて作るというのは僕も賛成です。

offset-map も値でなくて、必要な長さを与えるとリストを返す関数にするのはいかがでしょう。

(defn offset-map [count]
  [(mapv vector (range count) (repeat 0))
   (mapv vector (repeat 0) (range count))
   (mapv vector (range count) (range count))
   (mapv vector (range (- count) 1) (range (- count) 1))])

なんかすごくベタな実装ですが。。。

変数の引き回しの点ですが、gridから直接幅と高さを取得するようにすれば、w と h は不要ですよね？
そうすると、あちこちでwとhを計算するはめになりますが、どこからやってきたか分らない値を信じてチェックにするよりも、処理的に安心できます。

(defn get-value-at-xy [x y mat]
  (let [w (count (first mat))
        h (count mat)]
    (if (and (< 0 x w) (< 0 y h))
      (get-in mat [y x])
      nil)))

比較演算子を多引数でつかうのは、どこかで見てからのお気に入りです。
あと、get-in はmapでなくても使えます。

keep いいですね。 使わせていただきます。
実は、quotも知らなくてこの勉強会で見て知りました。 APIもっと調べないと(って何回思ったことか！)

kohyama さん

• 汎用的でない点のご指摘、ごもっともです。今回はちょっと中途半端な感じは自分でもしていたのですが、どうしたらよいかいろいろ考えていたのですが、他にもやることがあって時間切れになりました orz
• 自分はあまり大量にコードを書く側の人間ではないのですが、「他人の見本」となる立場となることがままあり、汎用性、拡張性、パフォーマンス、シンプルさ、等々バランスを考える(考えこんでしまい先に進まない)ことが多いです。
• (comp not nil?) は identity ... kohyama さんだけじゃなく、こういう指摘をいただける場を提供していただいた tnoda_ さんにも感謝すべきですね。keep について、最近 tnoda_ さんに教えてもらったような気が...orz
• 何にせよ、勉強になりました。ありがとうございます。

ypsilon-takai さん

• gridから直接幅と高さを取得、は自分も迷いました。
• get-in 、知りませんでした...(知らんことばっかし)。あと、(< 0 x w) も参考になります。こういう使い方ができるんですね。

Clojure の Core API、まだまだ知らないことがいっぱいありそうです。

自分のを改めて見てみると、そもそもget-inは、値が無ければnilを返すので、わざわざget-value-at-xyを作るまでもなく、単に、

(get-in mat [y x])

とすればいいですね。 処理の命名のために関数化するにしても、

(defn get-value-at-xy [x y mat]
      (get-in mat [y x]))

で充分です。

私が Project Euler を解くときはたいてい REPL で済ませていて，汎用性を考えることはありませんでした．ちょうどいい機会なので，この問題で練習してみます． @kohyama の

• 複数の入力を与えられたとき
• 入力のサイズが変わったとき

というのはちょうどよい汎用性だと思いますので，それを目指して書いてみます．

---

https://gist.github.com/4394295

ここに貼り付けていた別解は，新たに gist を作って，そこに移動させました．さすがにコメントとしてはちょっと長すぎて邪魔になっていました．

@ypsilon-takai さん
get-in いいですね.
下の方で nil を返すと上の処理がやりやすいですよね.
get-in を使わないで (nth (nth ...) ...) にしても IndexOutOfBounds を捕まえて nil を返すとか.
多引数の < もいいですね. 言われてみれば「< も + 他と同様 LISP では演算子ではなく関数」と.
いろいろ勉強になります.

@ypsilon-takai さん, @ponkore さん.
w, h を与えるか, 与えられたデータから計算するかは悩みますよね.
後者は粗結合になるので, 少々計算量を犠牲にしても利がある気がします.

@tnoda さん
take-nth などいろいろと参考になります. 勉強になります. ありがとうございます.
grid の中に input がハードコードされているのが惜しい気がします.
拙解 にも御 fence と似たような考えが出てきますが, 0 詰めや nil 詰めをしない方針で考えました. ご参照ください.

汎用性
汎用性を考える場合, 問題中の 4 も可変とするかどうか, 入力はどの状態から始めるか, あたりが悩みどころですよね.

• 入力はテキストで与えられた行の集合
• 積を取る連接の個数も可変

として input は @tnoda さんの意味で, 以下のテストを満足するよう ... を埋める, ところを汎用性の目安としては如何でしょうか.

(defn solver
  ([] (solver 4 input))
  ([n text]
    ...))

(is (= (solver 2 "
3 1 4
1 5 9
2 6 5
")
         54))

(is (= (solver 3 "
3 1 4 1
5 9 2 6
5 3 5 8
")
         180)))

拙解です.
https://gist.github.com/4381176

私もやってみました。

コードはこちら https://gist.github.com/4388634

斜め方向のラインの作り方と、ラインを作った後にいきなりpartition 4せずに候補の絞り込みをしているところがポイントですかね。tnoda さんと同様に行端のガードに0をconsして処理しています。

0を含むと解にはならないので、数値のシーケンスを0で分割 (partition-by zero?) しています。この時点でシーケンスの長さが4より短ければそのシーケンスは候補から脱落となります。

@mnzk 解答公開ありがとうございます．zip で transpose しているだけかと思いきや，zip-partition でずらしながら斜めの線を求めているんですね．この考え方いいですね．詳しいコメントは後ほど コードのある gist のほうに．

@mnzk さん. 別解面白いです. 御 gist の方にコメントさせていただきます.

コメントありがとうございます。
ここに書いてから色々修正しましたが、基本路線は同じです。

シーケンス操作を重ねるとどうしてもオーバヘッドが生じるので、生配列で速度重視したコードも書いてみたいですね。

私も解いてみました。
基本的な方針は @kohyama さんと同じでgridを回転させています。ただし、45度きれいに回転させようとまで思い至らず、左下半分が潰れてしまう手抜き実装を、左右反転したデータ両方に適用することで補っています。
https://gist.github.com/4443766

@tnoda さんの解のfenceの考え方は思いつきませんでした。@mnzk さんの解、partitionで斜めがつくれるのすごいです。がんばって読みます。