Problem 18 » 履歴 » リビジョン 4
リビジョン 3 (Noppi, 2024/01/01 05:20) → リビジョン 4/7 (Noppi, 2024/01/01 14:05)
[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]
# [[Problem 18]]
## 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$.
<div style="text-align:center"><span style="color:red">3</span><br />
<span style="color:red">7</span> 4<br />
2 <span style="color:red">4</span> 6<br />
8 5 <span style="color:red">9</span> 3</div>
That is, $3 + 7 + 4 + 9 = 23$.
Find the maximum total from top to bottom of the triangle below:
<div style="text-align:center">75<br />
95 64<br />
17 47 82<br />
18 35 87 10<br />
20 04 82 47 65<br />
19 01 23 75 03 34<br />
88 02 77 73 07 63 67<br />
99 65 04 28 06 16 70 92<br />
41 41 26 56 83 40 80 70 33<br />
41 48 72 33 47 32 37 16 94 29<br />
53 71 44 65 25 43 91 52 97 51 14<br />
70 11 33 28 77 73 17 78 39 68 17 57<br />
91 71 52 38 17 14 91 43 58 50 27 29 48<br />
63 66 04 68 89 53 67 30 73 16 69 87 40 31<br />
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23</div>
**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になる.
<div style="text-align:center"><span style="color:red">3</span><br />
<span style="color:red">7</span> 4<br />
2 <span style="color:red">4</span> 6<br />
8 5 <span style="color:red">9</span> 3</div>
この例では 3 + 7 + 4 + 9 = 23.
以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.
<div style="text-align:center">75<br />
95 64<br />
17 47 82<br />
18 35 87 10<br />
20 04 82 47 65<br />
19 01 23 75 03 34<br />
88 02 77 73 07 63 67<br />
99 65 04 28 06 16 70 92<br />
41 41 26 56 83 40 80 70 33<br />
41 48 72 33 47 32 37 16 94 29<br />
53 71 44 65 25 43 91 52 97 51 14<br />
70 11 33 28 77 73 17 78 39 68 17 57<br />
91 71 52 38 17 14 91 43 58 50 27 29 48<br />
63 66 04 68 89 53 67 30 73 16 69 87 40 31<br />
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23</div>
**注:** ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.
```scheme
#!r6rs
#!chezscheme
(import (chezscheme))
(define triangle
'#(#(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 (walkthrough triangle)
(let* ([triangle-length (vector-length triangle)]
[initial-result (let ([last-vector (vector-ref triangle (sub1 triangle-length))]
[initial-cells (make-vector triangle-length)])
(let loop-initial ([i 0])
(if (<= triangle-length i)
initial-cells
(let ([value (vector-ref last-vector i)])
(vector-set! initial-cells i `(,value ,value))
(loop-initial (add1 i))))))])
(if (= triangle-length 1)
(cdr initial-result)
(let loop1 ([current-index (- triangle-length 2)]
[result initial-result])
(let ([current-vector (vector-ref triangle current-index)])
(if (zero? current-index)
(let* ([i-cell (vector-ref result 0)]
[j-cell (vector-ref result 1)]
[i-value (car i-cell)]
[j-value (car j-cell)]
[i-tree (cdr i-cell)]
[j-tree (cdr j-cell)]
[current-value (vector-ref current-vector 0)])
(if (<= j-value i-value)
(cons current-value i-tree)
(cons current-value j-tree)))
(let ([temp-tree (make-vector (add1 current-index) #f)])
(let loop2 ([i 0])
(if (< current-index i)
(loop1 (sub1 current-index) temp-tree)
(let* ([j (add1 i)]
[i-cell (vector-ref result i)]
[j-cell (vector-ref result j)]
[i-value (car i-cell)]
[j-value (car j-cell)]
[i-tree (cdr i-cell)]
[j-tree (cdr j-cell)]
[current-value (vector-ref current-vector i)])
(if (<= j-value i-value)
(vector-set! temp-tree i
(cons (+ current-value i-value) (cons current-value i-tree)))
(vector-set! temp-tree i
(cons (+ current-value j-value) (cons current-value j-tree))))
(loop2 (add1 i))))))))))))
(define answer-18
(apply + (walkthrough triangle)))
(printf "18: ~D~%" answer-18)
```