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

私が 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で斜めがつくれるのすごいです。がんばって読みます。