2017年02月26日

TypeScriptでProject Euler #8 「数字列中の最大の積」

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

TypeScriptでProject Euler #8 「数字列中の最大の積」

問題

次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.

73167176531330624919225119674426574742355349194934  
96983520312774506326239578318016984801869478851843  
85861560789112949495459501737958331952853208805511  
12540698747158523863050715693290963295227443043557  
66896648950445244523161731856403098711121722383113  
62229893423380308135336276614282806444486645238749  
30358907296290491560440772390713810515859307960866  
70172427121883998797908792274921901699720888093776  
65727333001053367881220235421809751254540594752243  
52584907711670556013604839586446706324415722155397  
53697817977846174064955149290862569321978468622482  
83972241375657056057490261407972968652414535100474  
82166370484403199890008895243450658541227588666881  
16427171479924442928230863465674813919123162824586  
17866458359124566529476545682848912883142607690042  
24219022671055626321111109370544217506941658960408  
07198403850962455444362981230987879927244284909188  
84580156166097919133875499200524063689912560717606  
05886116467109405077541002256983155200055935729725  
71636269561882670428252483600823257530420752963450  

この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.

EX 6桁の数123789から5個の連続する数字を取り出す場合, 1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9=3024が最大の総乗となる.

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

解き方

順に13文字づつ取り出して、それを掛けていき、その結果を記憶して、一番大きな値を求めればいいだけです。

数学の問題というよりも、文字列と配列を扱う問題ですね。

TypeScriptのコード

numbersメソッドを定義して、この中で、13個の数字を掛けた結果を、配列にため込んで、結果として返しています。 なお、この13っていう数字は、引数で渡してもらうことにします。

solveメソッドでは、それを reduce使い、最大値を求めています。 TypeScriptでは、reduceって意外と使い道多そうです。LINQ の Aggregate と同じですね。

import * as Utils from './utils';

class Solver {
    exec(text: string, digit: number): number {
        return this.numbers(text, digit).reduce((x, y) => (x > y) ? x : y);
    }

    numbers(s: string, digit:number): Array<number> {
        let ary: number[] = [];
        for (let i = 0; i <= s.length - digit; i++) {
            let num = 1;
            for (let j = i; j < i + digit; j++)
                num *= parseInt(s[j]);
            ary[i] = num;
        }
        return ary;
    }
}

class Application {
    private static text: string  =
        "73167176531330624919225119674426574742355349194934" +
        "96983520312774506326239578318016984801869478851843" +
        "85861560789112949495459501737958331952853208805511" +
        "12540698747158523863050715693290963295227443043557" +
        "66896648950445244523161731856403098711121722383113" +
        "62229893423380308135336276614282806444486645238749" +
        "30358907296290491560440772390713810515859307960866" +
        "70172427121883998797908792274921901699720888093776" +
        "65727333001053367881220235421809751254540594752243" +
        "52584907711670556013604839586446706324415722155397" +
        "53697817977846174064955149290862569321978468622482" +
        "83972241375657056057490261407972968652414535100474" +
        "82166370484403199890008895243450658541227588666881" +
        "16427171479924442928230863465674813919123162824586" +
        "17866458359124566529476545682848912883142607690042" +
        "24219022671055626321111109370544217506941658960408" +
        "07198403850962455444362981230987879927244284909188" +
        "84580156166097919133875499200524063689912560717606" +
        "05886116467109405077541002256983155200055935729725" +
        "71636269561882670428252483600823257530420752963450";

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

Application.run();

TypeScriptに随分と慣れてきたような気がしますが、久しぶりに配列のインデックスをごにょごにょするコードを書いたので頭がパニックおこしました(笑)。
 


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

  

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

2017年02月23日

TypeScriptでProject Euler #7 「10001番目の素数」

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

問題

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.

10001 番目の素数を求めよ.

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

素数を列挙する

まずは、素数を列挙する関数を作成。他でも使えそうなので、別ファイル(primeNumber.ts)として独立させておきます。これは、mathフォルダに入れておきます。

とりあえず、ナイーブな実装で良しとします。

export class PrimeNumber {
    public static * enumerate(): IterableIterator<number> {
        yield 2;
        let i = 3;
        while (true) {
            if (PrimeNumber.isPrime(i))
                yield i;
            i += 2;
        }
    }

    public static isPrime(n: number): boolean {
        let r = Math.sqrt(n);
        for (let i = 3; i <= r; i += 2) {
            if (n % i === 0)
                return false;
        }
        return true;
    }
}

問題を解く

上記PrimeNumberクラスを使い、問題を解くコードを書きます。

import * as Utils from './utils';
import { PrimeNumber } from './math/primeNumber';

class Solver {
    exec(maxnum: number): number {
        let i = 0;
        for (let n of PrimeNumber.enumerate()) {
            if (++i >= maxnum)
                return n;
        }
        // ここには到達しない。
        return -1;
    }
}


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

Application.run();

10001番目を求めるループがダサいけど、LINQが標準でないので、我慢します。

自分で、IterableIterator<T> の拡張メソッドskip(n)を書こうと思ったのですが、どう書いたら良いのかわかりませんでした。TypeScriptで拡張メソッド書くには、protptypeに突っ込めばいいんだよという記事を見つけたのですが、interfaceに対してだと、どうやってやったら良いのかわかりませんでした。

まだまだ TypeScriptの知識は不足していますね。



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

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

2017年02月21日

TypeScriptでProject Euler #6 「二乗和の差」

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

問題

最初の10個の自然数について, その二乗の和は,

12 + 22 + ... + 102 = 385

最初の10個の自然数について, その和の二乗は,

(1 + 2 + ... + 10)2 = 3025

これらの数の差は 3025 - 385 = 2640 となる.

同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

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

TypeScriptのコード

3つの方法で書いてみました。

オーソドックスなTypeScript のコード

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

class Solver {
    exec(num: number): number {
        let a = 0;
        let b = 0;
        for (let i = 1; i <= num; i++) {
            a += i;
            b += (i * i);
        }
        return a * a - b;
    }
}

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

Application.run();

reduceを使ったコード

      exec(num: number): number {
          let a = Utils.makeSeq(1, num).reduce((x, y) => x + y);
          let b = Utils.makeSeq(1, num).reduce((x, y) => x + y * y);
          return a * a - b;
      }

makeSeq関数(TypeScriptでProject Euler #5「最小の倍数」で作成)の第2引数は、countではなく、最後の値を指定します。

変数bの値を求める際は、配列の最初が 0 であることを利用しています。

公式を使ったコード

      exec(num: number): number {
          let a = (num * (num + 1)) / 2;
          let b = (num * (num + 1) * (2 * num + 1)) / 6;
          return a * a - b;
      }

12 + 22 + 32 + 42... + n2 の公式は、ネットで検索すると解説しているページがたくさんヒットします。

なるほどなーと感心します。

ただ、公式使っても、最初の100個となるとたいして速度の差がでないです。


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

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

2017年02月17日

TypeScriptでProject Euler #5「最小の倍数」

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

問題

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

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

考え方

配列用意して、 素数を求める際に使うエラストテネスの篩いのような感じで、素因数を求めていくやり方です。 こうすれば、かなり速く求めることができると思います。

例えば、1から10までの場合は、

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 が最大の値です。これを
1 * 2 * 3 * 2 * 5 * 1 * 7 * 2 * 3 * 1 のようにすれば最小値が求まります。

これを nまでと一般化すれば、[0,1,2,3,4,5,6,7,8,9,10, ... n] という 配列用意して、以下の手順で配列の値を変更していきます。

  1. 4,6,8,10... 番目の値を 2番目の値(この場合2) で割った値に置き換える

  2. 6,9,12... 番目の値を 3番目の値(この場合3) で割った値に置き換える

  3. 8,12,16...番目の値を 4番目の値(すでに2で割っているので2)で割っていく。

  4. 10,15,20 ...番目の値を 5番目の値で割っていく。

  5. 以下同様

これをnまで繰り返していって、最後に、これらの値(0番目は除きく)をすべて掛けあわせれば答えを求めることができます。

TypeScriptのコード

まず、連番を求める関数 makeSeq を定義します。これれは、以前作成した utils.tsファイルに追加することにします。

    export function makeSeq(begin: number, end: number): Array<number> {
        let ary = new Array(end - begin + 1);
        let i = 0;
        for (let n = begin; n <= end; n++)
            ary[i++] = n
        return ary;
    }

これを使った問題を解くコードを以下に示します。

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

class Solver {
    exec(n: number): number {
        let nums = Utils.makeSeq(0, n);
        for (var j = 2; j < nums.length/2; j++) {
            let d = nums[j];
            if (d === 1)
                continue;
            for (let k = j + j; k <= n; k += j) {
                nums[k] = nums[k] / d;
            }
        }
        let r = 1;
        nums.slice(2).forEach(x => r *= x);
        return r;
    }
}

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

Application.run();

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

おまけ

ここまで書いて気が付いたのですが、

let r = 1;
nums.slice(2).forEach(x => r *= x);
return r;

上の3行は、以下の行に置き換え可能ですね。

return nums.slice(2).reduce((x, y) => x * y);

reduceは、LINQの Aggregate と同じような関数ですね。

slice や reduceが IterableIterator<T> に使えないのは残念だなー。外部ライブラリ探せばありそうだけど、TypeScriptの言語機能を知るのが目的なので、これ以降も初めの方針通り、外部ライブラリは使わないでいこうと思います。


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

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

2017年02月12日

書籍『実戦で役立つ-C#プログラミングのイディオム-定石-パターン』

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

僕の書いたC#プログラミングの書籍『実戦で役立つ-C#プログラミングのイディオム-定石-パターン』が、技術評論社様より出版されることになりました。

2月18日発売です。現在、amazonにて予約受付中です。



初級者を対象とした本ですが、内容的には妥協はしていません。そのため、496ページとかなりのボリュームになりました。その分、中級者の方にも得るものがあると思います。

以下に示した目次から推測されるように、C#プログラミングと.NET Frameworkの基本的な使い方を中心に解説した本ですが、単なる無味乾燥なTIPS集、API解説集とはならないよう、説明にはいろいと工夫をしています。
例えば、良いコードと悪いコードを対比したり、旧来のコードの書き方と新しいコードの書き方を示したり、僕がどんなことを大切にしてコードを書いているかを記したり... などなど。

自分で言うのもなんですが、きちんとしたプログラミングの基礎を身につけようと考えている方には、有用な書籍になっているかなーと思っています。

初級者向けなので、はじめは易しく(優しく)丁寧に、そして、徐々に高度な内容に移っていき、最後まで読み通せば、しっかりとした知識と実力が身につく、そんな構成にしたつもりです。
各章の最後には演習問題も載せていますので、教育の現場でも利用できると思います。
 

一方、WPF, UWP, WinForms, ASP.NET など特定のアプリ形態にはできるだけ依存しないようにしたので、
・WPFで◯
◯を××するには?
・ASP.NET MVCで◯◯を××するには?
といったものを期待している方には向かないと思います。


なお、文法解説書ではありませんが、文法がまだきちんと頭に入っていない方にも、安心して読んでいただけるよう、初心者・初級者の方が迷いそうな文法については、本文、コラムなどで随時解説しています。

興味のある方は、本屋などで手にとって内容を確認していただけると嬉しいです。


-- 目次 --

Part 1 [準備編]

 Chapter 1 オブジェクト指向プログラミングの基礎
 Chapter 2 C# でプログラムを書いてみよう
 Chapter 3 ラムダ式と LINQ の基礎

Part 2 [基礎編]

 Chapter 4 基本イディオム
 Chapter 5 文字列の操作
 Chapter 6 配列と List<T> の操作
 Chapter 7 ディクショナリの操作
 Chapter 8 日付、時刻の操作

Part 3 [実践編]

 Chapter 9 ファイルの操作
 Chapter 10 正規表現を使った高度な文字列処理
 Chapter 11 XML ファイルの操作 
 Chapter 12 シリアル化、逆シリアル化
 Chapter 13 EntityFrameworkによるデータアクセス
 Chapter 14 その他のプログラミングの定石

Part 4 [ステップアップ編]

 Chapter 15 LINQ を使いこなす
 Chapter 16 非同期 / 並列プログラミング
 Chapter 17 実践オブジェクト指向プログラミング
 Chapter 18 スタイル、ネーミング、コメント
 Chapter 19 良いコードを書くための指針

  
Posted by gushwell at 21:30Comments(7)

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

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