RubyでProject Euler - Problem 18 : PamGau

Problem 18 (Project Euler) [和訳])

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 5

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:

(中略)

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)

「しらみつぶしなんかしてたら、問題67でどえらいめにあうぞ」と珍しく脅し加減の注記があります。

エディタの中で問題の三角形をきれいに並べる作業をしている最中に、三角形の頂点を指で押すと、数字がより下の段の数字に加算されていくイメージがひらめきました。上の突端を押すとアラームが止まるピラミッド型の目覚まし時計がありましたなぁ…。

というわけで下記のコードとなりました。

  VAL_STR ="                  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"

  v = VAL_STR.split(/\n/).map!{|s| s.lstrip.split(/\s+/)}
  v.map! do |s|
    s.map!{|s| s.to_i}
  end

  (1..14).each do |i|
    (0..i).each do |j|
      if j == 0
        v[i][j] += v[i-1][j]
      elsif j == i
        v[i][j] += v[i-1][j-1]
      else
        v[i][j] += [v[i-1][j], v[i-1][j-1]].max
      end
    end
  end

  puts v[14].max

課題から各段ごとの群数列を作り、各項をすぐ上段の２項のいずれか大きい方と加算した数値に書き換えます。結局、最下段に相当する部分数列の最大値が求める答えとなります。

ご注意: 当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意: 当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。

RubyでProject Euler - Problem 18

TrackBack

Comments