2017年03月26日

TypeScriptでProject Euler #15 「格子経路」

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

問題

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

では, 20×20 のマス目ではいくつのルートがあるか.

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

最初に書いたコード

最初に、再帰を使ったコードを書いたのですが、 あまりにも時間がかかりすぎて、使い物になりません。
コードは間違っていないはずですが、 待てど暮らせど、プログラムが終わりません。 まずは、そのめちゃくちゃ遅いコード。

import * as Utils from './utils';

class Solver {
        exec(num: number): number {
            return this.f(num + 1, num + 1);
        }

        private f(x: number, y: number): number {
            if (x <= 1 || y <= 1)
                return 1;
            return this.f(x - 1, y) + this.f(x, y - 1);
        }

}

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

Application.run();

改良する

上記の再帰処理コードはとても簡潔で綺麗なコードなのですが、何回も何回も同じ計算をしてしまうのが欠点です。
そのため、効率を考えて書き直してみました。 2次元配列(ジャグ配列)を用意し、一度計算した結果を覚えておくように (メモ化)してみました。
メソッド f で、既に計算済みの値の場合は、配列の値を返して、再帰処理するのを端折っています。

class Solver {
    exec(num: number): number {
        this.array = new Array(num + 2);
        for (var i = 0; i < this.array.length; i++)
            this.array[i] = new Array(num + 2);
        return this.f(num + 1, num + 1);
    }

    private array: number[][];

    private f(x: number, y: number): number {
        var val = this.array[x][y];
        if (val !== undefined)
            return val;         // もう結果はわかっているので、計算済みの値を返す。
        if (x <= 1 || y <= 1)
            return 1;
        var n = this.f(x - 1, y) + this.f(x, y - 1);
        this.array[x][y] = n;
        return n;
    }
}

これならば、16ミリ秒で終わりました。ほんのちょっとした工夫で、劇的に速度が改善しました。

非再帰版も書いて見る

ついでに、非再帰版も書いてみました。 再帰版は、最後の右下から逆に求めていくやり方だけど、非再帰版は、左上から答えを求めています。

ちなみに、 f が経路の数だとすると
f(x - 1, y) + f(x, y - 1);

で、(x,y)点までの経路の数を求める基本的考え方は変わりません。

こちらも、16ミリ秒で計算できました。

class Solver {
    exec(num: number): number {
        var size = num + 2;
        var array: number[][] = new Array(size);
        for (var i = 0; i < size; i++) {
            array[i] = new Array(size);
            for (var j = 0; j < size; j++)
                array[i][j] = 0;
        }
        array[1][1] = 1;
        for (var x = 1; x < size; x++) {
            for (var y = 1; y < size; y++) {
                if (x === 1 && y === 1)
                    continue;
                // 計算済みの結果を利用し、次の値を求める。
                array[x][y] = array[x - 1][y] + array[x][y - 1];
            }
        }
        return array[num + 1][num + 1];
   }
}

2番目のコードと同様、2次元配列(ジャグ配列)に経路数を記憶させていますが、記憶した値は、次のステップで利用しています。 ここが、再帰版とは微妙に違っています。
この3番目のコードは、動的計画法の一種ですかね。 動的計画法 って、なんか小難しくて偉そうな名前ですが、それほど難しい概念じゃないですね。


話がそれました。 それにしても、TypeScriptの配列の初期化はとんでもなく面倒くさいです。 C#ならば、以下の1行で、すべての要素が 0になるのに、TypeScriptは、いちいち 初期値を与えなくてはいけません。

var array = new long[size, size];

もっと簡単に書ける方法があるのではと思って調べたのですが、わかりませんでした。 undefinedという概念がある TypeScriptでは仕方がないのかなー?


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



 

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

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