2017年03月22日

TypeScriptでProject Euler #14 「最長のコラッツ数列」

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

TypeScriptでProject Euler #14 「最長のコラッツ数列」

問題

正の整数に以下の式で繰り返し生成する数列を定義する.

n → n/2 (n が偶数)

n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)

さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.

注意: 数列の途中で100万以上になってもよい

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

最初に書いたコード

import * as Utils from './utils';

class Solver {
    exec(num: number): number {
       let max = 0;
       let ans = 0;
       for (let n = num - 1; n > 0; n--) {
           let collatz = this.nextCollatz(n);
           let count = 2;  // 数列の2番目までは求め終わっている
           while (collatz !== 1) {
               collatz = this.nextCollatz(collatz);
               count++;
           }
           if (max < count) {
               max = count;
               ans = n;
           }
       }
       return ans;
    }

    nextCollatz(n: number): number {
        if (n % 2 === 0)
            return n / 2;
        return 3 * n + 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();

新しいMacにしたのでコンピュータの性能は向上していると思うのですが、それでも3秒近くかかります。

改良できないか考えてみる

もう少し速くできないか考えてみました。 例えば、13からはじめた数列が求め終わっていた場合、40や20などから始まる数列の長さは 13からはじめた数列の長さよりも短いことは明白です。 そのため、いったん求まった数列の個数を ハッシュテーブル(C#で言うDictionary)に覚えておけば、 また同じ数列を求めなおす必要がないので、効率的に解を求められます。

例えば、

Key  - Value
13  - 9
40 - 8
20 - 7
...
4 - 2
2 - 1
1 - 0

というように、覚えておけば、数列を求めていく途中で、ハッシュテーブル に存在している値が出現すれば、 それ以降の数列を求めなくても、途中まで求めた数列の数と、ハッシュテーブルもっと高速化できそうです。 試しに、この考えで solveメソッドのコードを書き換えてみました。

TypeScriptでは、以下のように書くと、ハッシュテーブルが使えるようです。

let known: { [key: number]: number } = [];

まあ、実態はJavaScriptのArrayなので、あくまでも、TypeScript側で型チェックできるというだけのようですが... ということでsolveメソッドを以下のように書いてみました。

改良後のコード

class Solver {
    // ハッシュテーブル
    private known: { [key: number]: number } = [];

    exec(num:  number): number  {
        let max = 0;
        let ans = 0;
        for (let n = num; n > 0; n--) {
            if (this.known[n] !== undefined)
                continue;
            let x =   this.CollatzSequence(n);
            let count = x[0];
            let list = x[1];
            if (max < count) {
                max = count;
                ans = n;
            }
            // let k = count;
            while (list.length > 0) {
                this.known[list.shift()] = count--;
            }
        }
        return ans;
    }

    // シーケンスを生成し返す。 その時のシーケンスの数も返したいので、Tupleを返す
    CollatzSequence(n:number) : [ number , Array<number> ] {
        let seq: Array<number> = new Array();
        let collatz = n;
        let count = 0;
        while (collatz !== 1) {
            if (this.known[collatz] !== undefined) {
                count += this.known[collatz];
                break;
            }
            seq.push(collatz);
            count++;
            collatz = this.nextCollatz(collatz);
        }
        return [ count, seq ];
    }

    nextCollatz(n: number): number {
        if (n % 2 === 0)
            return n / 2;
        return 3 * n + 1;
    }
}

コードは複雑になりましたが、これで2秒きることができました。


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



 

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

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