2016年12月13日

TypeScriptでProject Euler #0 はじめに

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

これまで、初めてのTypeScript(1),(2),(3),(4),(5),(6), と書いてきましたが、今回から記事のタイトルを変更します。

Project Euler とは

Project Eulerとは、数学的問題をひたすらプログラムで解いていくというサイトです。 現時点で500以上もの問題が掲載されています。

問題を日本語に訳してあるサイトもあります。 有志の方々が、日本語に訳して下さっているので、とてもありがたいです。

今回使うプログラミング言語は、C#ではなくTypeScript。Visual Studio Code + node.js の環境で動かします。

TypeScriptってどんな言語かを知るのが目的なので、それほど多くの問題を解くことはしないと思いますが、10問程度は解きたいと思います。

僕の貧弱な数学の知識では、そもそもそんなに多くの問題を解けるとは思いませんので、10問くらいがちょうどよいでしょう。

方針

なお、以下のような方針で臨みたいと思います。

速度にも気を配ったコードとする (時間を計測する)

すべての問題は、1分以内で解ける問題だということです。Project Eulerが開始されたのは、2001年ということですから、初期に出題された問題ならば、今のPCで最悪でも数秒程度で答えが求められるっていうことだと思います。 なので目標は10秒以内。速度にも気を配ったコードにしたいと思っています。

再利用可能なものはクラスとして独立させておく。

後で使えそうなロジックは、別クラスとして定義することとします。 これによって、一時的には、記述するコード量が増えてしまいますが、長い目でみれば、メリットがあると思います。

すべての問題に対して、Solverクラスのexecメソッドを実装する。

後述のひな形コードのように、たとえ冗長になったとしても、問題を解くコードは、Solver クラスの exec静的メソッド あるいは インスタンスメソッドとして実装することとします。 もちろん、execメソッドの引数は、その問題ごとに変化します。

なお、複数のやり方で問題を解いた場合は、SolverB、SolverC というクラスを定義し、そこに同じ引数のexecメソッドを実装します。

外部のライブラリは使わないことにする。

これはやってみたいとわからない部分もありますが、基本は、TypeScriptが持つ基本的な機能だけで問題を解きます。

ひな形コード

実は、前回の記事の「初めてのTypeScript (6)」で示したプログラムが、そのひな形コードになってます。 再度示しますね。

まずは、app.tsを示します。execメソッドの部分は、問題ごとに実装が異なるので、ひな形では、引数で得た値を返すだけのコードとしています。

import { Utils } from './utils';
import Stopwatch = Utils.Stopwatch;

class Solver {
    exec(maxnum: number): number {
        return maxnum;
    }
}

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

Application.run();

次は、utils.ts。

export class Stopwatch {
    private startTime: number;
    private stopTime: number;
    static startNew(): Stopwatch {
        let sw = new Stopwatch();
        sw.start();
        return sw;
    }
    start() {
        this.startTime = Date.now();
    }
    stop() {
        this.stopTime = Date.now();
    }
    elapsed(): number {
        return this.stopTime - this.startTime;
    }
    toString(): string {
        let tms = this.elapsed();
        let h = Math.floor(tms / (1000 * 60 * 60));
        let m = Math.floor(tms / (1000 * 60));
        let s = Math.floor(tms / 1000);
        let ms = Math.floor(tms % 1000);
        return `${this._zeroPadding(h)}:${this._zeroPadding(m)}:${this._zeroPadding(s)}:${this._zeroPadding(ms, 3)}`;
    }
    private _zeroPadding(n: number, d: number = 2): string {
        let zero = '';
        for (let i = 1; i < d; i++)
            zero += '0';
        return (zero + n).slice(-d);
    }
}

このutils.tsは、これから解くすべての問題で利用します。必要ならばここにクラスを追加していくかもしれません。

これで、動くはずですので、F5キーを押して、正しく動作することを確認します。

tsconfig.json, tasks.json, launch.json

説明は省略しますが、Visual Studio Codeの設定ファイルである tsconfig.json, tasks.json, launch.json も載せておきます。
 

■tsconfig.json

{
    "compilerOptions": {
        "target": "es6", 
        "module": "commonjs",
        "sourceMap": true
    }
}

■.vscode/tasks.json

{
  "version": "0.1.0",
  "command": "tsc",
  "isShellCommand": true,
  "args": ["-p", "."],
  "showOutput":"always",
  "problemMatcher": "$tsc"
}

■.vscode/launch.json

{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "起動",
      "type": "node",
      "request": "launch",
      "program": "${workspaceRoot}/ProjectEuler.js",
      "stopOnEntry": false,
      "args": [],
      "cwd": "${workspaceRoot}",
      "preLaunchTask": null,
      "runtimeExecutable": null,
      "runtimeArgs": [
        "--nolazy"
      ],
      "env": {
        "NODE_ENV": "development"
      },
      "console":"internalConsole",
      "sourceMaps": false,
      "outDir": null
    },
    {
      "name": "アタッチ",
      "type": "node",
      "request": "attach",
      "port": 5858,
      "address": "localhost",
      "restart": false,
      "sourceMaps": false,
      "outDir": null,
      "localRoot": "${workspaceRoot}",
      "remoteRoot": null
    },
    {
      "name": "プロセスにアタッチ",
      "type": "node",
      "request": "attach",
      "processId": "${command.PickProcess}",
      "port": 5858,
      "sourceMaps": false,
      "outDir": null
    }
  ]
}

次回は、これらのファイル(.ts, .json)があるフォルダーをコピーして利用します。


次のエントリーからは、実際に問題を解いていきます。

ただし、コードは載せますが、答えそのものは載せません。それは皆さんの楽しみのために取っておきましょう。



 

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

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