【Project EulerにRubyで挑戦シリーズ】問11:Largest product in a grid

スポンサーリンク

今回の問題

Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

下の 20×20 の格子のうち, 斜めに並んだ4つの数字が赤くマークされている.

— 略 —

それらの数字の積は 26 × 63 × 78 × 14 = 1788696 となる.
上の 20×20 の格子のうち, 上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものはいくつか?

書いた内容

とりあえず格子状の数列を配列で取りたい

20×20 の格子の数字を配列で取ることができれば、
問8でも用いた each_consメソッドで横と縦の計算は簡単にできそう。

ということで、各行の文字列を each_lineメソッドでブロック変数 line に渡し、
改行を除外して、splitで半角スペースごとに切り分けて配列にし

integer型に変換した上で table に格納しました。

table = []
File.open('number.txt') do |numbers|
  numbers.each_line do |line|
    table << line.chomp.split.map(&:to_i)
  end
end

横と縦の計算

横はそのままeach_cons(4)で隣接する4つの数字をかけ合わせれば終わり。
縦は transposeメソッドで行列を変換した後に同じ処理をすればよいです。

--省略--
results_array = []

# right, left
table.each do |row|
  row.each_cons(4) do |adjacent_array|
    result = adjacent_array.inject(:*)
    results_array << result
  end
end

# up, down
transpose_table = table.transpose
transpose_table.each do |row|
  row.each_cons(4) do |adjacent_array|
    result = adjacent_array.inject(:*)
    results_array << result
  end
end

斜めの計算

右斜め下と右斜め上の2方向があります。
良い方法が浮かばなかったので、
each.with_index でループを回しながらちから技で計算しています。

diagonally_right_down_array、 diagonally_right_up_array
で2方向の4つの数列を得るメソッドは別で定義しておき、
20×20 の格子に収まる範囲でのみ利用しています。

def diagonally_right_down_array(table:, row:, column:)
  Array.new(4){ |i| table[row + i][column + i] }
end

def diagonally_right_up_array(table:, row:, column:)
  Array.new(4){ |i| table[row - i][column + i] }
end

# diagonally
table.each.with_index(0) do |row, i|
  row.each.with_index(0) do |number, j|
    if i <= 16 && j <= 16
      results_array << diagonally_right_down_array(table: table, row: i, column: j).inject(:*) end if i >= 3 && j <= 16
      results_array << diagonally_right_up_array(table: table, row: i, column: j).inject(:*)
    end
  end
end

最終型

最終形は下記。
問10とは打って変わって重たい問題でした。

横と縦の計算は中身が全く同じだったので
tables という変数に渡してリファクタリングしています。

def diagonally_right_down_array(table:, row:, column:)
  Array.new(4){ |i| table[row + i][column + i] }
end

def diagonally_right_up_array(table:, row:, column:)
  Array.new(4){ |i| table[row - i][column + i] }
end

table = []
File.open('number.txt') do |numbers|
  numbers.each_line do |line|
    table << line.chomp.split.map(&:to_i)
  end
end

tables, results_array = [table, table.transpose], []

# right, left, up, down
tables.each do |each_table|
  each_table.each do |row|
    row.each_cons(4) do |adjacent_array|
      results_array << adjacent_array.inject(:*)
    end
  end
end

# diagonally
table.each.with_index(0) do |row, i|
  row.each.with_index(0) do |number, j|
    if i <= 16 && j <= 16
      results_array << diagonally_right_down_array(table: table, row: i, column: j).inject(:*)
    end

    if i >= 3 && j <= 16
      results_array << diagonally_right_up_array(table: table, row: i, column: j).inject(:*)
    end
  end
end

puts results_array.max

※Project Eulerのリポジトリ

この記事の内容が役に立ったと思いました、SNSで記事を共有していただけますと幸いです。