2017年04月05日

TypeScriptでProject Euler #18 「最大経路の和 その1」

   このエントリーをはてなブックマークに追加 Clip to Evernote

TypeScriptでProject Euler #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行あるので, 総当りでは解けない. もっと賢い方法が必要である.

   Project Euler日本語翻訳サイト から引用


どうやって解くか

効率のよいやり方は、Problem67で考えることとして(確実にそこまでたどり着かないと思いますが...)、 この 18 では、全経路を辿るやり方を書こうと思います。

それでも、これまでの問題のなかで一番頭を使いました。 最初書いたコードは、正しい結果は求まったもののあまりにもごちゃごちゃしたコードだったので、 一度頭を冷やし、考え直したのが以下のコードです。


TypeScriptのコード

import * as Utils from './utils';

class Solver {
    exec(triangle: number[][]): number {
        this.triangle = triangle;
        return this._solve(0, 0);
    }

    private triangle: number[][];

    private _solve(x: number, y: number): number {
        if (x == this.triangle.length - 1)
            return this.triangle[x][y];
        var a = this._solve(x + 1, y);
        var b = this._solve(x + 1, y + 1);
        return Math.max(a, b) + this.triangle[x][y];
    }

}

class Application {
    static run(): void {
        let sw = Utils.Stopwatch.startNew();
        try {
            let p = new Solver();
            let n = p.exec(this.triangle);
            console.log(n);
        } finally {
            sw.stop();
            console.log(sw.toString());
        } 
    }

    static triangle: number[][] = [
        [75],
        [95, 64],
        [17, 47, 82],
        [18, 35, 87, 10],
        [20,  4, 82, 47, 65],
        [19,  1, 23, 75,  3, 34],
        [88,  2, 77, 73,  7, 63, 67],
        [99, 65,  4, 28,  6, 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,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
        [ 4, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60,  4, 23],
    ];

 
}

Application.run();


簡単な解説

xが縦、yが横位置を表すとした場合、 位置(x,y)を頂点とした三角形で下に辿ったときの最大値を f(x,y) とすれば f(x,y) は f(x+1,y)とf(x+1,y+1)のどちらか大きいほうに (x,y)の数を足したものになります。

ただし xが最終段(最下行)の時は、(x,y)の位置の値そのものとなります。 これを素直にコードに落としたのが、exec(x,y)メソッドです。

はじめから、こういった数学的定義を考えてから、コードを書くべきでした。

最初は、再帰を使い全経路を辿ろうという意識が強すぎて、無駄に複雑化したコートになってしまいました。最初に書いたコードは恥ずかしくて人に見せられないので、ここでは掲載しません。

ちなみに、僕のマシンだと 14ミリ秒で求めることができました。 これくらいのデータ量ならば、十分すぎる速さです。

ちなみに、TypeScriptのstaticメソッドの中で、staticなメンバーを参照する場合は、this.メンバー名 でも、class名.メンバー名でもどちらでも良いんですね(Applicationクラスのtriangleを参照しているところ)


※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52488919