[Project Euler] Problem 18 「最大経路の和 その1」

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

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23.

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

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

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

下から順番に足していけば経路が求まりそうです.

1. 例の下から２段目を考える.
2. 左端の２からたどり着ける数は８と５であり, 大きい方の８を取る.
3. 左端の２を８との和10に置き換える.
4. 同様にして４を13, ６を15に置き換える.
5. この操作を上に向けて続けると23を得る.

この操作を手続として定義すると次のようになります.

(require srfi/1)

(define (front lst)
  (reverse (cdr (reverse lst))))

(define (sum-row upper lower)
  (map (lambda (u l1 l2) 
         (+ u (if (< l1 l2) l2 l1)))
       upper
       (cdr lower)
       (front lower)))


(define data '((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)))
        

(define (loop lower rest)
  (display lower)
  (newline)
  (if (null? rest)
      lower
      (loop (sum-row (car rest) lower) (cdr rest))))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (loop (car (reverse data))
        (cdr (reverse data)))
(4 62 98 27 23 9 70 98 73 93 38 53 60 4 23)
(125 164 102 95 112 123 165 128 166 109 122 147 100 54)
(255 235 154 150 140 179 256 209 224 172 174 176 148)
(325 246 187 178 256 329 273 302 263 242 193 233)
(378 317 231 321 354 372 393 354 360 293 247)
(419 365 393 387 419 425 430 376 454 322)
(460 434 419 475 508 470 510 524 487)
(559 499 479 536 514 526 594 616)
(647 501 613 609 533 657 683)
(666 614 636 684 660 717)
(686 640 766 731 782)
(704 801 853 792)
(818 900 935)
(995 999)
(1074)
(1074)
>