Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 67]]

## Maximum Path Sum II

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.

<p style="text-align:center"><span style="color:red"><b>3</b></span><br><span style="color:red"><b>7</b></span> 4<br>

2 <span style="color:red"><b>4</b></span> 6<br>

8 5 <span style="color:red"><b>9</b></span> 3</p>

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

Find the maximum total from top to bottom in [triangle.txt](https://projecteuler.net/resources/documents/0067_triangle.txt) (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

<b>NOTE:</b> This is a much more difficult version of [[Problem 18]]. It is not possible to try every route to solve this problem, as there are 2<sup>99</sup> altogether! If you could check one trillion (10<sup>12</sup>) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

## 最大経路の和 その2

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

<p style="text-align:center"><span style="color:red"><b>3</b></span><br><span style="color:red"><b>7</b></span> 4<br>

2 <span style="color:red"><b>4</b></span> 6<br>

8 5 <span style="color:red"><b>9</b></span> 3</p>

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

100列の三角形を含んでいる15Kのテキストファイル [triangle.txt](https://projecteuler.net/resources/documents/0067_triangle.txt) (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけよ.

注：これは, [[Problem 18]]のずっと難しいバージョンです.

全部で2<sup>99</sup> 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません！

あなたが毎秒1兆本の(10<sup>12</sup>)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう.

解決するための効率的なアルゴリズムがあります. ;o)

```scheme

(import (scheme base)

        (gauche base)

        (scheme file))

(define (read-triangle filename)

  (read-from-string

    (format "#(~a)"

            (call-with-output-string

              (^[string-port]

                (call-with-input-file

                  filename

                  (^[file-port]

                    (let loop ([line (read-line file-port)])

                      (unless (eof-object? line)

                        (format string-port "(~a)" line)

                        (loop (read-line file-port)))))

                  :element-type :character))))))

(define (walkthrough triangle)

  (assume (vector? triangle))

  (assume (positive? (vector-length triangle)))

  (let* ([triangle-length (vector-length triangle)]

         [initial-result (let ([last-vector (vector-ref triangle (- triangle-length 1))])

                           (map (^n `(,n ,n))

                                last-vector))])

    (let loop1 ([current-index (- triangle-length 2)]

                [result initial-result])

      (if (negative? current-index)

        (cdar result)

        (let* ([current-vector (vector-ref triangle current-index)]

               [initial-list current-vector])

          (let loop2 ([rest-nums initial-list]

                      [rest-tree result]

                      [temp-tree '()])

            (if (null? rest-nums)

              (loop1 (- current-index 1) (reverse temp-tree))

              (let* ([i-cell (car rest-tree)]

                     [j-cell (cadr rest-tree)]

                     [i-value (car i-cell)]

                     [j-value (car j-cell)]

                     [i-tree (cdr i-cell)]

                     [j-tree (cdr j-cell)]

                     [current-value (car rest-nums)])

                (if (<= j-value i-value)

                  (loop2 (cdr rest-nums)

                         (cdr rest-tree)

                         (cons (cons (+ current-value i-value) (cons current-value i-tree))

                               temp-tree))

                  (loop2 (cdr rest-nums)

                         (cdr rest-tree)

                         (cons (cons (+ current-value j-value) (cons current-value j-tree))

                               temp-tree)))))))))))

(define answer-67

  (apply +

         (walkthrough (read-triangle "triangle.txt"))))

(format #t "67: ~d~%" answer-67)

```