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



 

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

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