Y箱

18の問題と同じで、データが大きくなった問題。
18を解いたときにもそれなりに考えて作ったんだけれども、電車に乗っているとにきいい方法を思いついたので、実装してみた。

ライン数で10分の1くらいになったんじゃないかな？





基本的な考えかたは18を解いたときと同じ。
この問題は、最大の数だけわかればいいので、上からたどっていって、合計が大きくなるものを見付ければいい。たとえば下のような場面では、

  o A B o
 o o X o o

Xの値に影響するのはA、Bの2つのみ。 それぞれAとBまでのルートの和が大きくなる方からXに来るのが大きいルート。例題の場合

1:    3
2:   7 4
3:  2 4 6
4: 8 5 9 3

2列目は、それぞれ上が3なので、10と7。

3列目。

 10  7
 /\ /\
2  4  6

2のところにくるのは、10からのルートのみなので、12になる。
4のところは、10からと7からの2通りある。 大きいほうを取って、14
6のところは、7からのルートのみなので、13
結果として、3列目の大きい方の合計は、
12 14 13

4列目

  12 14 13
  /\ /\ /\
 8  5  9  3

3列目と同様にやって、

20 19 23 16

答が23っと。


18を解いたときは、全部の情報を持っているデータの構造を作って、それに対してこの操作をするようになっていました。問題にしては重量級の仕組みです。途中の情報を後で参照したければこのほうがいいのでしょうけれど、答が出ればいいのであればそんな仕組みは不要です。
今、書いたとおりに、それぞれの段の合計数のリストだけもって、つぎの段に行けばいいわけです。
で、「あ、reduce使えばいいじゃん」と思ったわけです。
そのためには、結果と次の段のリストを使って次の結果を出す方法が必要です。
こんな風にしてみました。

4列目(8 5 9 3)を例にします。前の結果は、(12 14 13)です。 これを、4列目に2回ずつ適用して結果を出すことになります。それだと面倒です。図をよくみると、 \\\ の適用と /// の適用が見えます。ずらしてあるわけです。
なら、ずれたデータを作ればいいのではないか。というわけで、

12 14 13      ：左ずらし l
   12 14 13   ：右ずらし r
8   5  9  3

あいてるところはどうしましょうか？ 手作業なら無視できますけど、計算ではそうはいきませんね。
データは足し算をするので、ここは、0を入れます。掛けるなら1かな。

12 14 13  0   ：左ずらし l
 0 12 14 13   ：右ずらし r
 8  5  9  3

こうしておいて、右ずらしと左ずらしそれぞれ足したときに大きいほうを採用する。という手順で行けば、よさそうです。





- pe-67
問題を解くのはこれだけです。
各段が1つずつのリストになった問題を受け取ります。
((3) (7 4) (2 4 6)(8 5 9 3)) という感じ。
reduceで1行ずつ取ってきて、解き方のように左右にずらし(rt-rとrt-l)て合計が大きい方をとり、新しいリストを作成するということを繰り返す。
最後のリストの最大値が答。

- pe-67-with-file
問題データをファイルから読み込んで、pe-67に渡して解く関数。
with-openでファイルを開いて、文字列を数値に変換してリスト化します。