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

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