2017年04月18日
TypeScriptでProject Euler #21 「友愛数」
昨年の12月からTypeScriptでProjectEulerを解く記事を書き続けてきましたが、 当初の目標の10問をクリアし、その倍の問題を解いたので、そろそろ、このProjectEulerの挑戦も終わりにしたいと思います。 ということで、これが最後の問題です。
問題
d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. ) もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.
例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である. また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.
それでは10000未満の友愛数の和を求めよ.
約数を求めるDivisorsクラスを定義する
約数を求めるメソッドは、Divisorsクラスを作成し、その静的メソッドとして作成。 この手のメソッド書くときに迷うのが、TypeScriptの場合は、クラスではなく、単独の関数でも良いのかなということ。
名前空間に適切な名前を付ければ、そのほうが良いのかもしれないなーとは思いつつ、 C#erの僕は、クラスにすることを選択。
export class Divisors {
// 約数を求める （自分自身は含めない）
public static get(num: number): number[] {
let ary = [];
let m = Math.floor(num / 2);
for (let n = 1; n <= m; n++) {
if (num % n === 0) {
ary.push(n);
}
}
return ary;
}
}
友愛数を求める
このメソッドができれば、友愛数を求めるのはそれほど難しくありませんね。
import * as Utils from './utils';
import { Divisors } from './math/divisors';
class Solver {
exec(num: number): number {
return this.amicableNumbers(num).map(x => x[0] + x[1]).reduce((x, y) => x + y,0);
}
// n 未満の友愛数のペアを列挙する
private amicableNumbers(n: number): [number,number][] {
var amicables = [];
for (let a = 1; a < n; a++) {
let temp = Divisors.get(a);
let d = temp.reduce((x, y) => x + y,0);
if (a >= d)
continue;
let y = Divisors.get(d).reduce((x, y) => x + y,0);
if (a == y)
amicables.push([a, d]);
}
return amicables;
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(10000);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();[number,number]というのは、数値の要素を２つ持つオブジェクトという意味。 TypeScriptだと、これをタプルと言うらしいです。 まあ、実態は配列だけどね。
amicableNumbers メソッドでは、このタプルの配列を返しています。
なお、reduceの第2引数に 0 を与えていますが、これがないと例外が発生します。 JavaScriptのreduceは、第2引数が無いと、要素の数が 0 の時に例外が発生するんですね。 この第2引数は、reduceをする際の初期値を与えます。
最初は、第2引数与えななったので、例外が発生して、あれっなんで？ ってちょっと悩んでしまいました。 よくよく考えると、「要素数ゼロの時は、何返したらいいかわからないよね、だから例外出すよ！」 ということで、至極当たり前の仕様ですね。
実行時間は、400ミリ秒でした。約数求めるところが効率悪いですから、まあ想定の範囲内です。
高速化する
Divisors.getメソッドをちょっと改良してみました。
export class Divisors {
// 約数を求める （自分自身は含めない）
public static get(num: number): number[] {
let ary = [];
if (num == 1)
return ary;
ary.push(1);
let m = Math.floor(Math.sqrt(num));
if (m * m === num) {
ary.push(m);
m--;
}
for (let i = 2; i <= m; i++) {
if (num % i === 0) {
ary.push(i);
ary.push(Math.floor(num / i));
}
}
return ary;
}
}かなりごちゃごちゃしたコードになりましたが、計算量が格段に減ってます。 これで、39ミリ秒まで速くすることができました。10倍の高速化です。
素因数分解から求めるという方法もあるのかもしれませんが、これで十分でしょう。
※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。
2017年04月17日
TypeScriptでProject Euler #20 「各位の数字の和 2」
問題
n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.
例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる. この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.
では, 100! の各位の数字の和を求めよ.
注: Problem 16 も各位の数字の和に関する問題です。解いていない方は解いてみてください。
BigUIntクラスを定義する
とうとう BigInt クラスを作る時が来たようです。 今回の問題では、BigInt * int が計算できれば良いのですが、 思い切って、BigInt * BigInt ができるクラスとしました。
なお、負の数は扱えないので、クラス名を BigUInt にしています。 加算と乗算だけの実装です。 減算、除算は実装していません。
const Fig: number = 10000000;
const Format: string = "000000";
const SliceNum: number = -7;
export class BigUInt {
private list: number[] = [];
constructor(n: number) {
let i = 0;
while (n > 0) {
this.list[i] = n % Fig;
n = Math.floor(n / Fig);
i++;
}
}
private create(src: number[]): BigUInt {
var obj = new BigUInt(0);
obj.list = src;
return obj;
}
public clone(): BigUInt {
var obj = new BigUInt(0);
for (var i = 0; i < this.list.length; i++)
obj.list[i] = this.list[i];
return obj;
}
public add(num: BigUInt): BigUInt {
let sum: number[] = [];
let carry = 0;
if (this.list.length > num.list.length) {
var a = this.list;
var b = num.list;
} else {
var a = num.list;
var b = this.list;
}
for (var i = 0; i < a.length; i++) {
if (i < b.length)
var n = a[i] + b[i] + carry;
else
var n = a[i] + carry;
sum[i] = n % Fig;
carry = Math.floor(n / Fig);
}
if (carry > 0)
sum[i] = carry;
return this.create(sum);
}
public multiple(num: BigUInt): BigUInt {
let ans = new BigUInt(0);
let wrk: number[] = [];
let a = this.list;
let b = num.list;
for (let ax = 0; ax < a.length; ax++) {
for (let i = 0; i < ax; i++)
wrk[i] = 0;
let carry = 0;
for (var bx = 0; bx < b.length; bx++) {
var n = a[ax] * b[bx] + carry;
wrk[bx + ax] = n % Fig;
carry = Math.floor(n / Fig);
}
wrk[bx+ax] = carry;
let w = this.create(wrk);
ans = ans.add(w);
}
return ans;
}
public toString() {
var s: string = "";
for (var i = this.list.length - 1; i >= 0; i--) {
var n = this.list[i];
s += (Format + n).slice(SliceNum);
}
return s.replace(/^0+/g, '');
}
}
BigUIntクラスを使って問題を解く
BigUInt クラスができれば、100! を求めるのは、ロジック的には、int での計算と変わらないですね。 このBigUIntを使って、以下のようなコードを書きました。 答えはあっているので、この BigUIntは、いちおう正しく動いているようです。
import * as Utils from './utils';
import { BigUInt } from './math/bigUInt';
class Solver {
exec(maxnum: number): number {
var a = new BigUInt(1);
for (var i = 2; i <= maxnum; i++) {
a = a.multiple(new BigUInt(i));
}
return a.toString().split("")
.map(x => parseInt(x))
.reduce((x, y) => x + y);
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(100);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。
2017年04月10日
TypeScriptでProject Euler #19 「日曜日の数え上げ」
問題
次の情報が与えられている.
- 1900年1月1日は月曜日である.
- 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.
- 2月は28日まであるが, うるう年のときは29日である.
- うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.
20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか?
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」 を見てください。
2017年04月05日
TypeScriptでProject Euler #18 「最大経路の和 その1」
TypeScriptでProject Euler #18 「最大経路の和 その1」
問題
以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.
3 7 4 2 4 6 8 5 9 3この例では 3 + 7 + 4 + 9 = 23.
以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.
どうやって解くか
効率のよいやり方は、Problem67で考えることとして（確実にそこまでたどり着かないと思いますが...)、 この 18 では、全経路を辿るやり方を書こうと思います。
それでも、これまでの問題のなかで一番頭を使いました。 最初書いたコードは、正しい結果は求まったもののあまりにもごちゃごちゃしたコードだったので、 一度頭を冷やし、考え直したのが以下のコードです。
TypeScriptのコード
import * as Utils from './utils';
class Solver {
exec(triangle: number[][]): number {
this.triangle = triangle;
return this._solve(0, 0);
}
private triangle: number[][];
private _solve(x: number, y: number): number {
if (x == this.triangle.length - 1)
return this.triangle[x][y];
var a = this._solve(x + 1, y);
var b = this._solve(x + 1, y + 1);
return Math.max(a, b) + this.triangle[x][y];
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(this.triangle);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
static triangle: number[][] = [
[75],
[95, 64],
[17, 47, 82],
[18, 35, 87, 10],
[20, 4, 82, 47, 65],
[19, 1, 23, 75, 3, 34],
[88, 2, 77, 73, 7, 63, 67],
[99, 65, 4, 28, 6, 16, 70, 92],
[41, 41, 26, 56, 83, 40, 80, 70, 33],
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
[63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
[ 4, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 4, 23],
];
}
Application.run();
簡単な解説
xが縦、yが横位置を表すとした場合、 位置(x,y)を頂点とした三角形で下に辿ったときの最大値を f(x,y) とすれば f(x,y) は f(x+1,y)とf(x+1,y+1)のどちらか大きいほうに (x,y)の数を足したものになります。
ただし xが最終段（最下行）の時は、(x,y)の位置の値そのものとなります。 これを素直にコードに落としたのが、exec(x,y)メソッドです。
はじめから、こういった数学的定義を考えてから、コードを書くべきでした。
最初は、再帰を使い全経路を辿ろうという意識が強すぎて、無駄に複雑化したコートになってしまいました。最初に書いたコードは恥ずかしくて人に見せられないので、ここでは掲載しません。
ちなみに、僕のマシンだと 14ミリ秒で求めることができました。 これくらいのデータ量ならば、十分すぎる速さです。
ちなみに、TypeScriptのstaticメソッドの中で、staticなメンバーを参照する場合は、this.メンバー名 でも、class名.メンバー名でもどちらでも良いんですね（Applicationクラスのtriangleを参照しているところ）
※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。
2017年04月02日
TypeScriptでProject Euler #17 「数字の文字数」
問題
1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.
注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.
TypeScriptのコード
単にアルファベットの数を足していっても良かったのですが、文字列を組み立て、最後に長さを求めたほうが直感的だったので、これを採用しました。 かなり泥臭いコードになってしまいましたが、1000までならば、あっというまに答えが求まるので良しとします。
import * as Utils from './utils';
class Solver {
exec(maxnum: number): number {
return Utils.makeSeq(1, maxnum)
.map(x => this.numToString(x).length)
.reduce( (x,y) => x + y);
}
numToString(num: number): string {
if (num < 100) {
return this.numToStringUnder100(num);
}
if (num < 1000) {
var s = "";
s += this.numbers[Math.floor(num / 100)] + this.numbers[100];
if (num % 100 != 0) {
s = s + "and" + this.numToStringUnder100(num % 100);
}
return s;
}
return this.numbers[1000];
}
numToStringUnder100(num: number): string {
if (num < 20)
return this.numbers[num];
if (num % 10 === 0)
return this.numbers[num];
else
return this.numbers[Math.floor(num / 10) * 10] + this.numbers[num % 10];
}
numbers: { [key: number]: string } = {
1: "one", 2: "two", 3: "three", 4: "four", 5: "five", 6: "six", 7: "seven", 8: "eight", 9: "nine", 10: "ten",
11: "eleven", 12: "twelve", 13: "thirteen", 14: "fourteen",
15: "fifteen", 16: "sixteen", 17: "seventeen", 18: "eighteen", 19: "nineteen",
20: "twenty", 30: "thirty", 40: "forty", 50: "fifty", 60: "sixty", 70: "seventy", 80: "eighty", 90: "ninety",
100: "hundred", 1000: "onethousand"
};
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(1000);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();makeSeqで、1から1000までの配列を作り、mapでそれぞれの文字列を組み立てその長さを配列にし、reduceで合計を求めています。
※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。
2017年03月29日
TypeScriptでProject Euler #16 「べき乗の数字和」
問題
215 = 32768 であり, 各位の数字の和は 3 + 2 + 7 + 6 + 8 = 26 となる.
同様にして, 21000 の各位の数字の和を求めよ.
簡易BigIntクラスを書く
C#ならば、BigIntegerを使って簡単に実装できますが、BigInteger がないTypeScriptだとそういわけにもいきません。
しかたないので、2倍するTwiceメソッドだけを実装した桁数無制限のBigIntクラスを作成しました。
このProjectEulerの連載をこのまま続けていくと、加減乗除できる BigIntクラスが必要になりそうですが、まあ、そこまで続ける予定はないので、この方針でいきます。
// twiceだけを行うBigIntクラス
const Fig: number = 1000000000000000;
const Format: string = "00000000000000";
const SliceNum: number = -15;
export class BigInt {
private list: number[] = [];
constructor(n: number) {
this.list.push(n);
}
private create(src: number[]): BigInt {
var obj = new BigInt(0);
obj.list = src;
return obj;
}
public twice() {
var ans: number[] = [];
var carry: number = 0;
for (var n of this.list) {
var a: number = n + n + carry;
carry = Math.floor(a / Fig);
ans.push(a % Fig);
}
if (carry > 0)
ans.push(carry);
return this.create(ans);
}
public toString() {
var s: string = "";
for (var i = this.list.length - 1; i >= 0; i--) {
var n = this.list[i];
s += (Format + n).slice(SliceNum);
}
return s.replace(/^0+/g, '');
}
}割り算の商を求めるのに、最初は、
var q = parseInt(a / Fig);と書いたのですが、型が違うとエラーになってしまいました。
なので、
var q = a / Fig;
var qstr = (q < 1) ? "0" : q.toString();
carry = parseInt(qstr);と書いたのですが、あまりにも泥臭いコードなので没。 調べたら、Mathクラスのfloor が使えることがわかりました。
ところで、TypeScriptには、for...in と、for...of という構文があるんですよね。 ほんとうにまぎらわしいです...
それと、toStringメソッドが思いのほか面倒くさかったです。C#のような String.Formatがほしいです。 ところで、const がクラスの中に書けないんですね。なんで？って感じです。
const Figの値は、大きければ大きいほど効率が良くなりますが、TypeScriptの場合は、これが最高値だと思います。
プログラムを完成させる
BigIntクラスができたので、あとはこれを使って、問題を解くコードを書くだけです。
import * as Utils from './utils';
import { BigInt } from './math/bigInt';
class Solver {
exec(num: number): number {
var int = new BigInt(2);
for (var i = 1; i < num; i++) {
int = int.twice();
}
var s = int.toString();
return s.split("").map(x => parseInt(x)).reduce((x, y) => x + y);
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(1000);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();今回のBingIntクラスも、math フォルダーに格納しています。
※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。
