2017年04月18日

TypeScriptでProject Euler #21 「友愛数」

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

昨年の12月からTypeScriptでProjectEulerを解く記事を書き続けてきましたが、 当初の目標の10問をクリアし、その倍の問題を解いたので、そろそろ、このProjectEulerの挑戦も終わりにしたいと思います。 ということで、これが最後の問題です。

問題

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. ) もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である. また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.

それでは10000未満の友愛数の和を求めよ.

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


約数を求めるDivisorsクラスを定義する

約数を求めるメソッドは、Divisorsクラスを作成し、その静的メソッドとして作成。 この手のメソッド書くときに迷うのが、TypeScriptの場合は、クラスではなく、単独の関数でも良いのかなということ。

名前空間に適切な名前を付ければ、そのほうが良いのかもしれないなーとは思いつつ、 C#erの僕は、クラスにすることを選択。

export class Divisors {
    // 約数を求める (自分自身は含めない)
    public static get(num: number): number[] {
        let ary = [];
        let m = Math.floor(num / 2);
        for (let n = 1; n <= m; n++) {
            if (num % n === 0) {
                ary.push(n);
            }
        }
        return ary;
    }
}


友愛数を求める

このメソッドができれば、友愛数を求めるのはそれほど難しくありませんね。

import * as Utils from './utils';
import { Divisors } from './math/divisors';


class Solver {
    exec(num: number): number {
        return this.amicableNumbers(num).map(x => x[0] + x[1]).reduce((x, y) => x + y,0);
    }

    // n 未満の友愛数のペアを列挙する
    private amicableNumbers(n: number): [number,number][] {
        var amicables = [];
        for (let a = 1; a < n; a++) {
            let temp = Divisors.get(a);
            let d = temp.reduce((x, y) => x + y,0);
            if (a >= d)
                continue;
            let y = Divisors.get(d).reduce((x, y) => x + y,0);
            if (a == y)
                amicables.push([a, d]);
        }
        return amicables;
    }
}


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

Application.run();
[number,number]

というのは、数値の要素を2つ持つオブジェクトという意味。 TypeScriptだと、これをタプルと言うらしいです。 まあ、実態は配列だけどね。

amicableNumbers メソッドでは、このタプルの配列を返しています。

なお、reduceの第2引数に 0 を与えていますが、これがないと例外が発生します。 JavaScriptのreduceは、第2引数が無いと、要素の数が 0 の時に例外が発生するんですね。 この第2引数は、reduceをする際の初期値を与えます。

最初は、第2引数与えななったので、例外が発生して、あれっなんで? ってちょっと悩んでしまいました。 よくよく考えると、「要素数ゼロの時は、何返したらいいかわからないよね、だから例外出すよ!」 ということで、至極当たり前の仕様ですね。

実行時間は、400ミリ秒でした。約数求めるところが効率悪いですから、まあ想定の範囲内です。


高速化する

Divisors.getメソッドをちょっと改良してみました。

export class Divisors {
    // 約数を求める (自分自身は含めない)
    public static get(num: number): number[] {
        let ary = [];
        if (num == 1)
            return ary;
        ary.push(1);
        let m = Math.floor(Math.sqrt(num));
        if (m * m === num) {
            ary.push(m);
            m--;
        }
        for (let i = 2; i <= m; i++) {
            if (num % i === 0) {
                ary.push(i);
                ary.push(Math.floor(num / i));
            }
        }
        return ary;
    }

}

かなりごちゃごちゃしたコードになりましたが、計算量が格段に減ってます。 これで、39ミリ秒まで速くすることができました。10倍の高速化です。

素因数分解から求めるという方法もあるのかもしれませんが、これで十分でしょう。


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

  

Posted by gushwell at 22:00Comments(0)TrackBack(0)

2017年04月17日

TypeScriptでProject Euler #20 「各位の数字の和 2」

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

問題

n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.

例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる. この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.

では, 100! の各位の数字の和を求めよ.

注: Problem 16 も各位の数字の和に関する問題です。解いていない方は解いてみてください。

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


BigUIntクラスを定義する

とうとう BigInt クラスを作る時が来たようです。 今回の問題では、BigInt * int が計算できれば良いのですが、 思い切って、BigInt * BigInt ができるクラスとしました。

なお、負の数は扱えないので、クラス名を BigUInt にしています。 加算と乗算だけの実装です。 減算、除算は実装していません。

const Fig: number = 10000000;
const Format: string = "000000";
const SliceNum: number = -7;

export class BigUInt {
    private list: number[] = [];
    constructor(n: number) {
        let i = 0;
        while (n > 0) {
            this.list[i] = n % Fig;
            n = Math.floor(n / Fig);
            i++;
        }
    }
    private create(src: number[]): BigUInt {
        var obj = new BigUInt(0);
        obj.list = src;
        return obj;
    }
    public clone(): BigUInt {
        var obj = new BigUInt(0);
        for (var i = 0; i < this.list.length; i++)
            obj.list[i] = this.list[i];
        return obj;
    }
    public add(num: BigUInt): BigUInt {
        let sum: number[] = [];
        let carry = 0;
        if (this.list.length > num.list.length) {
            var a = this.list;
            var b = num.list;
        } else {
            var a = num.list;
            var b = this.list;
        }
        for (var i = 0; i < a.length; i++) {
            if (i < b.length)
                var n = a[i] + b[i] + carry;
            else
                var n = a[i] + carry;
            sum[i] = n % Fig;
            carry = Math.floor(n / Fig);
        }
        if (carry > 0)
            sum[i] = carry;
        return this.create(sum);
    }
    public multiple(num: BigUInt): BigUInt {
        let ans = new BigUInt(0);
        let wrk: number[] = [];
        let a = this.list;
        let b = num.list;
        for (let ax = 0; ax < a.length; ax++) {
            for (let i = 0; i < ax; i++)
                wrk[i] = 0;
            let carry = 0;
            for (var bx = 0; bx < b.length; bx++) {
                var n = a[ax] * b[bx] + carry;
                wrk[bx + ax] = n % Fig;
                carry = Math.floor(n / Fig);
            }
            wrk[bx+ax] = carry;
            let w = this.create(wrk);
            ans = ans.add(w);
        }
        return ans;
    }
    public toString() {
        var s: string = "";
        for (var i = this.list.length - 1; i >= 0; i--) {
            var n = this.list[i];
            s += (Format + n).slice(SliceNum);
        }
        return s.replace(/^0+/g, '');
    }
}


BigUIntクラスを使って問題を解く

BigUInt クラスができれば、100! を求めるのは、ロジック的には、int での計算と変わらないですね。 このBigUIntを使って、以下のようなコードを書きました。 答えはあっているので、この BigUIntは、いちおう正しく動いているようです。

import * as Utils from './utils';
import { BigUInt } from './math/bigUInt';


class Solver {
    exec(maxnum: number): number {
        var a = new BigUInt(1);
        for (var i = 2; i <= maxnum; i++) {
            a = a.multiple(new BigUInt(i));
        }
        return a.toString().split("")
            .map(x => parseInt(x))
            .reduce((x, y) => x + y);
    }
}



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

Application.run();

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

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

2017年04月10日

TypeScriptでProject Euler #19 「日曜日の数え上げ」

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

問題

次の情報が与えられている.

  1. 1900年1月1日は月曜日である.
  2. 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.
  3. 2月は28日まであるが, うるう年のときは29日である.
  4. うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.

20世紀(1901年1月1日から2000年12月31日)中に月の初めが日曜日になるのは何回あるか?

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


Dateクラスを使って解く

Dateクラス使えばなんてことは無い問題ですね。

これは、TypeScriptが悪いんじゃなくて、JavaScriptの問題ですけど、なんで、月が 0 から始まるんでしょうか? ひどい仕様ですね。

import * as Utils from './utils';

class Solver {
    exec(year1: number, year2: number): number {
        let count = 0;
        let sunday = 0;
        let dt = new Date(year1, 1-1, 1);
        while (dt < new Date(year2, 12 - 1, 31)) {
            dt.setMonth(dt.getMonth() + 1);
            if (dt.getDay() == sunday)
                count++;
        }
        return count;
    }
}


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

Application.run();


Dateクラスを使わずに解く

でも、これだと頭の体操にはならないので、Dateを使わないコードも書いてみました。 ちなみに曜日は0が日曜、1が月曜、2が火曜... としています。

class Solver {
    exec(year1: number, year2: number): number {
        // w の初期値は 1900/1/1の曜日。0 が日曜、1が月曜...
        let w = 0;
        let count = 0;
        for (let year = 1900; year <= year2; year++) {
            var ary = this.getMonthArray(year);
            for (let m = 1; m <= 12; m++) {
                // 各月の1日の曜日を求め、year1 以上で、日曜日ならカウントアップ
                w += (ary[m]);
                if (year >= year1 && w % 7 === 0)
                    count++;
            }
        }
        return count;
    }
                                       //   1   2   3   4   5   6   7   8   9  10  11  12
    private static month1: number[] = [ 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ];
    private static month2: number[] = [ 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ];

    private getMonthArray(year: number): number[]  {
        if ((year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0)))
            return Solver.month2;
        return Solver.month1;
    }
}

速度は、後者の 非Date版の方が速かったです。16ミリ秒程度で求めることができました。


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

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

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」 を見てください。

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

2017年04月02日

TypeScriptでProject Euler #17 「数字の文字数」

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

問題

1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.

では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.

注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

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

TypeScriptのコード

単にアルファベットの数を足していっても良かったのですが、文字列を組み立て、最後に長さを求めたほうが直感的だったので、これを採用しました。 かなり泥臭いコードになってしまいましたが、1000までならば、あっというまに答えが求まるので良しとします。

import * as Utils from './utils';

class Solver {
    exec(maxnum: number): number {
        return Utils.makeSeq(1, maxnum)
                    .map(x => this.numToString(x).length)
                    .reduce( (x,y) => x + y);           
    }

    numToString(num: number): string {
        if (num < 100) {
            return this.numToStringUnder100(num);
        }
        if (num < 1000) {
            var s = "";
            s += this.numbers[Math.floor(num / 100)] + this.numbers[100];
            if (num % 100 != 0) {
                s = s + "and" + this.numToStringUnder100(num % 100);
            }
            return s;
        }
        return this.numbers[1000];
    }

    numToStringUnder100(num: number): string {
        if (num < 20)
            return this.numbers[num];
        if (num % 10 === 0)
            return this.numbers[num];
        else
            return this.numbers[Math.floor(num / 10) * 10] + this.numbers[num % 10];
    }

    numbers: { [key: number]: string } = {
        1: "one", 2: "two", 3: "three", 4: "four", 5: "five", 6: "six", 7: "seven", 8: "eight", 9: "nine", 10: "ten",
        11: "eleven", 12: "twelve", 13: "thirteen", 14: "fourteen",
        15: "fifteen", 16: "sixteen", 17: "seventeen", 18: "eighteen", 19: "nineteen",
        20: "twenty", 30: "thirty", 40: "forty", 50: "fifty", 60: "sixty", 70: "seventy", 80: "eighty", 90: "ninety",
        100: "hundred", 1000: "onethousand"
    };

}

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

Application.run();

makeSeqで、1から1000までの配列を作り、mapでそれぞれの文字列を組み立てその長さを配列にし、reduceで合計を求めています。


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

  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2017年03月29日

TypeScriptでProject Euler #16 「べき乗の数字和」

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

問題

215 = 32768 であり, 各位の数字の和は 3 + 2 + 7 + 6 + 8 = 26 となる.

同様にして, 21000 の各位の数字の和を求めよ.

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


簡易BigIntクラスを書く

C#ならば、BigIntegerを使って簡単に実装できますが、BigInteger がないTypeScriptだとそういわけにもいきません。
しかたないので、2倍するTwiceメソッドだけを実装した桁数無制限のBigIntクラスを作成しました。

このProjectEulerの連載をこのまま続けていくと、加減乗除できる BigIntクラスが必要になりそうですが、まあ、そこまで続ける予定はないので、この方針でいきます。

// twiceだけを行うBigIntクラス

const Fig: number = 1000000000000000;
const Format: string = "00000000000000";
const SliceNum: number = -15;

export class BigInt {

    private list: number[] = [];

    constructor(n: number) {
        this.list.push(n);
    }

    private create(src: number[]): BigInt {
        var obj = new BigInt(0);
        obj.list = src;
        return obj;
    }

    public twice() {
        var ans: number[] = [];
        var carry: number = 0;
        for (var n of this.list) {
            var a: number = n + n + carry;
            carry = Math.floor(a / Fig);
            ans.push(a % Fig);
        }
        if (carry > 0)
            ans.push(carry);
        return this.create(ans);
    }

    public toString() {
        var s: string = "";
        for (var i = this.list.length - 1; i >= 0; i--) {
            var n = this.list[i];
            s += (Format + n).slice(SliceNum);
        }
        return s.replace(/^0+/g, '');
    }
}

割り算の商を求めるのに、最初は、

var q = parseInt(a / Fig);

と書いたのですが、型が違うとエラーになってしまいました。

なので、

var q = a / Fig;
var qstr = (q &lt; 1) ? "0" : q.toString();
carry = parseInt(qstr);

と書いたのですが、あまりにも泥臭いコードなので没。 調べたら、Mathクラスのfloor が使えることがわかりました。

ところで、TypeScriptには、for...in と、for...of という構文があるんですよね。 ほんとうにまぎらわしいです...

それと、toStringメソッドが思いのほか面倒くさかったです。C#のような String.Formatがほしいです。 ところで、const がクラスの中に書けないんですね。なんで?って感じです。

const Figの値は、大きければ大きいほど効率が良くなりますが、TypeScriptの場合は、これが最高値だと思います。


プログラムを完成させる

BigIntクラスができたので、あとはこれを使って、問題を解くコードを書くだけです。

import * as Utils from './utils';
import { BigInt } from './math/bigInt';

class Solver {
    exec(num: number): number {
        var int = new BigInt(2);
        for (var i = 1; i < num; i++) {
            int = int.twice();
        }
        var s = int.toString();
        return s.split("").map(x => parseInt(x)).reduce((x, y) => x + y);
    }
}

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

Application.run();

今回のBingIntクラスも、math フォルダーに格納しています。


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

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

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」 を見てください。

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

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」 を見てください。

  
Posted by gushwell at 21:30Comments(0)TrackBack(0)