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)TypeScript

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)TypeScript

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)TypeScript

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)TypeScript

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)TypeScript

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)TypeScript