【Project EulerにRubyで挑戦シリーズ】問18:Maximum path sum I

スポンサーリンク

今回の問題

Maximum path sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.

以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.

注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.

考え方

三角形の頂点 75 から総当たりで試行すると 16,384 通りとのことですが最大にならないルートを追う必要はないです。

こういう場合は、下の底辺から考えていくと分かりやすいです。

下から2つ目の列と底辺の数列について考えてみると、

  • 下から2つ目の列5つ目の 89 を例として考える
  • 下に移動するルートは、89→23 または 89→9 の2通り
  • その和が最大になるの23と9を比較して数が大きい89→23のルート
  • 下から2つ目の列の数字各々で和が最大になるルートで新たな数列を作る
  • その新たな数列を底辺として、下から3列目と同様に最大にルートが出せる

ということになります。

これを繰り返すことで
三角形が下からだるま落としのように削られていき最後に残る数字が最大値となります。

書いた内容

三角形状の数列を取り出すメソッド

def path_array
  File.open('number.txt') do |numbers|
    numbers.each_line.map { |line| line.split.map(&:to_i) }.reverse
  end
end

#=>[[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23], [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31], [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48], [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57], [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14], [41, 48, 72, 33, 47, 32, 37, 16, 94, 29], [41, 41, 26, 56, 83, 40, 80, 70, 33], [99, 65, 4, 28, 6, 16, 70, 92], [88, 2, 77, 73, 7, 63, 67], [19, 1, 23, 75, 3, 34], [20, 4, 82, 47, 65], [18, 35, 87, 10], [17, 47, 82], [95, 64], [75]]
  • number.txtファイルに問題の数列を記載して読み込む
  • each_lineメソッドで各行を取り出してmapメソッドで2次元配列を作成
  • mapの中では、splitで半角スペースごとに切り取り配列にしてInteger型に変換
  • reverseで逆転させることで三角形状の数列を下から2次元配列の形で取り出す

最大値を求める計算

考え方で示した内容をプログラムに落としました。

  • だるま落としの部分は shift メソッドで実行
  • 最大となるルートは三項演算子を用いて算出した変数 bigger で計算
  • until total.empty? でだるま落としが終わるまでループ
total = path_array
bottom = total.shift
 until total.empty?
  new_bottom = []
  total.first.each_with_index do |number, i|
    bigger = bottom[i] > bottom[i + 1] ? bottom[i] : bottom[i + 1]
    new_bottom << number + bigger
  end
  bottom = new_bottom
  total.shift
end
 puts bottom.max

map.with_indexメソッドでリファクタリング

最後に new_bottom という変数を定義するのが冗長だったのでリファクタリングしました

until total.empty?
  bottom = total.first.map.with_index do |number, i|
    bigger = bottom[i] > bottom[i + 1] ? bottom[i] : bottom[i + 1]
    number + bigger
  end
  total.shift
end

なお、問67もこのプログラムを用いて回答しました。

※問18ブランチのプルリクエスト

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