2017年02月05日

TypeScriptでProject Euler #4「最大の回文積」

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

またまた前回の第3回目から随分と間が空いてしまいましたが、気にせずマイペースで進めます。

問題

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数の最大値を求めよ.

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

TypeScriptのコード

今回は、Solverクラスに問題を解くすべての機能を組み込んでしまいました。しばらく時間が空いていたので、TypeScriptの文法かなり忘れています(^^;; 

import * as Utils from './utils';
import Stopwatch = Utils.Stopwatch;

class Solver {
    private max: number;
    private min: number;
    private figure: number

    public exec(figure: number): number {
        this.figure = figure;
        this.max = Math.pow(10, figure) - 1;
        this.min = Math.pow(10, figure - 1);
        for (let n = this.max * this.max; n >= (this.min * this.min); n--) {
            if (this.isKaibun(n) && this.isSameFigure(n))
                return n;
        }
        return 0;
    }

    private isKaibun(num: number): boolean {
        let s = num.toString();
        if (s.length % 2 !== 0)
            return false;
        return s === this.reverse(s);
    }

    private isSameFigure(n: number): boolean {
        for (let i = this.max; i >= this.min; i--) {
            if (n % i === 0 && ((n / i) | 0).toString().length === this.figure)
                return true;
        }
        return false;
    }

    private reverse(s: string): string {
        return s.split("").reverse().join("");
    }
}

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

Application.run();

ちょっと説明など

問題は3桁固定ですが、桁数を execの引数に渡せるようにしています。

困ったのは、文字列の反転のメソッドがTypeScriptの標準にはないこと。 配列の反転があるので、一旦配列に変換したものを反転して、それをjoinで結合しています。

このreverse関数が定義できれば、あとは、回文判定を行う IsKaibun と figureと同じ桁数かを判定する isSameFigure というメソッド定義すれば、あとは、ループさせるだけ。

ただし、大きい値から小さい値へと調べていくのがポイント。まあ、ごくありふれたコードですね。

一番はまったのは、TypeScriptには整数という型がないから、割り算の結果が整数にならないこと。 exec(2) で求めた結果が、9009 にならずに間違った答えを出して、なんで?って悩みました。

割り算の結果は Math.floor()で整数にする方法もあるけど、ここでは、((n / i) | 0) で整数にしています。

JavaScriptは、数値に対してビット演算を適用すると、浮動小数点形式から32ビットの整数に変換されるらしいです。TypeScriptもこの辺りは同じなので、0 と ビットOR を取れば整数部分だけを求めることができます。 ただ、32ビット整数よりも大きな値では結果が正しくならないので、注意が必要。

こういったイディオムは言語によっていろんなのがあるんですね。

僕のマシンだと 165ミリ秒で求めることができました。

 

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



 

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

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