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



 

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

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