Project Euler #011 – 4連続で最大の積

23 12月 2009

Project EulerをClojureでおさらいシリーズ。
Problem 11

日本語訳：

下の20×20の数字の中で斜めに連続する4つの数字が赤くマークされている。

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 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 03 45 02 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 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

この4つの数字の積は 26 × 63 × 78 × 14 = 1788696 である。

この20×20のなかで上下左右斜めのいずれかの方向に連続する4つの数字の積で最大のものを求めよ。

総当たりで計算する問題ですね。

各方向に4つの数字をとる際に20×20からはみ出ないように注意するだけ。

昔にRubyで解いたときのコードがこれ：

#!/usr/bin/env ruby
 
grid = []
grid << %w(08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08)
grid << %w(49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00)
grid << %w(81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65)
grid << %w(52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91)
grid << %w(22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80)
grid << %w(24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50)
grid << %w(32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70)
grid << %w(67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21)
grid << %w(24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72)
grid << %w(21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95)
grid << %w(78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92)
grid << %w(16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57)
grid << %w(86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58)
grid << %w(19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40)
grid << %w(04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66)
grid << %w(88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69)
grid << %w(04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36)
grid << %w(20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16)
grid << %w(20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54)
grid << %w(01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48)
 
grid.map!{|line| line.map!{|num| num.to_i}}
 
grid_num = 20
 
largest = 0
 
0.upto(grid_num-1).each do |y|
  0.upto(grid_num-1).each do |x|
    # to right
    if x < grid_num - 3
      prod = grid[y][x] * grid[y][x+1] * grid[y][x+2] * grid[y][x+3]
      largest = prod if prod > largest
    end
 
    # to down
    if y < grid_num - 3
      prod = grid[y][x] * grid[y+1][x] * grid[y+2][x] * grid[y+3][x]
      largest = prod if prod > largest
    end
 
    # to rightdown
    if x < grid_num - 3 && y < grid_num - 3
      prod = grid[y][x] * grid[y+1][x+1] * grid[y+2][x+2] * grid[y+3][x+3]
      largest = prod if prod > largest
    end
 
    # to leftdown
    if x > 3 && y < grid_num - 3
      prod = grid[y][x] * grid[y+1][x-1] * grid[y+2][x-2] * grid[y+3][x-3]
      largest = prod if prod > largest
    end
  end
end
 
p largest

恥ずかしいほどに同じようなコードが散在しています。これはなんとかしたい。

縦横斜めを「方向」というパラメータにしてまとめるとよさそうです。

方針としては

4つの方向を定義する
[開始点(x,y) 方向(x,y)]のセットを生成する(20×20×4)
グリッドからはみ出たものをフィルタで除く
残った組み合わせでグリッドから4つの数字を取り出す。
積をとる
最大値をとる

という流れでいけそうです。

ベクトルの加算は: (map + [y x] [dy dx])

グリッド要素(x,y)の取得は: (reduce nth grid [y x]) — 参考

でできますね。

(ns euler.p11
  (:use clojure.contrib.seq-utils))
 
(def num-text
  "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
   49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
   81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
   52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 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 03 45 02 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 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
   24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
   21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
   78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
   16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
   86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
   19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
   04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
   88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
   04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
   20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
   20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
   01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48")
 
(def num-grid
     (partition 20 (map #(Integer. %) (re-seq #"[0-9]+" num-text))))
 
(def directions [[0 1] [1 0] [1 1] [1 -1]])
 
(defn all-in-range?
  "Retuen true if all elements is in 0..19"
  [coll]
  (every? #(< -1 % 20) (flatten coll)))
 
(def possible-list-of-four
     (filter all-in-range?
	     (for [start-y (range 20)
		   start-x (range 20)
		   step-yx directions]
	       (take 4 (iterate #(map + % step-yx) [start-y start-x])))))
 
(defn prod-of-four
  "Return product of four number"
  [yx-coll]
  (apply * (map #(reduce nth num-grid %) yx-coll)))
 
(println "Answer : "
	 (apply max
		(map #(prod-of-four %) possible-list-of-four)))

うーん。いまいちだなぁ。

関数に汎用性がないのはともかく、possible-list-of-four などのムダな定義が目立つ。

小分けに関数が定義されているのは、無名関数がネストしそうになったのでやむをえずに。

なんかしっくりこない。

そもそも方針(2)で生成したセットがネストしているのでフィルタするときも mapがネストしてしまうのが理由かな。

(2)でセットを生成するときに(3)の「はみでるかどうか」の処理も同時にしてしまえばそれ以降がスッキリするんだけどなぁ。

あ、はみ出た値を参照したときに 0 を返す関数を定義すれば解決するかも。

(ns euler.p11
  (:use clojure.contrib.seq-utils))
 
(def num-text
  "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
   49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
   81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
   52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 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 03 45 02 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 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
   24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
   21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
   78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
   16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
   86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
   19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
   04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
   88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
   04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
   20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
   20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
   01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48")
 
(def num-grid
     (partition 20 (map #(Integer. %) (re-seq #"[0-9]+" num-text))))
 
(defn pick-value
  "Pick value at pos[y x]. Return 0 if pos is out of grid."
  [coll pos]
  (if (every? #(< -1 % 20) pos)
    (reduce nth coll pos)
    0))
 
(println "Answer : "
	 (apply max
		(for [start-x (range 20)
		      start-y (range 20)
		      step-yx [[0 1] [1 0] [1 1] [1 -1]]]
		  (apply * (take 4 (map #(pick-value num-grid %)
					(iterate #(map + % step-yx)
						 [start-y start-x])))))))