マヨイドーロで迷い olD

# 概要
タイトルで韻を踏もうとしたが苦しい。[CodeIQ](https://codeiq.jp/) に [結城浩さん](http://hyuki.com/) が出題している「マヨイドーロ」という問題を解いたら、いにしえのD言語に迷い込んでしまった。

# 問題ほか

[結城浩さんによるアナウンス tweet](https://twitter.com/hyuki/status/677453411760005122) を参照。

# 本編

さて、問題文に含まれている例に少しの実験を加え、次の unittest から始めることにする。

```d
unittest
{
	assert (0.solve == 0);
	assert (1.solve == 2); // B, C
	assert (2.solve == 2);
	assert (3.solve == 7); // CAC, CAB, CBC, BAB, BAC
	assert (4.solve == 7);
}
```

汚いながらも、最低限の考察から愚直に実装した。数学を専門としていた者にあるまじき態度だが、食後の眠いときだったので妥協してほしい。コードの中身は本筋に関係ないので。

```d
/** The number of sequences of alphabets,
    with length not larger than n,
    starts with B or C,
    B/C after A,
    A or C after eventh/oddth (zero-origin) B,
    A/B after C
*/
auto solve(in ulong n)
{
	ulong ret;
	ulong[3] current, next;
	current[0] = 1;
	foreach (i; 0..n)
	{
		next[] = 0;
		next[0] = current[2] + (i & 1) * current[1];
		next[1] = current[0] + current[2];
		next[2] = current[0] + ((i & 1) ^ 1) * current[1];
		current = next;
		if (i & 1)
			continue;
		ret += current[0] + current[1] + current[2];
	}
	return ret;
}

import std.stdio, std.conv, std.string;
void main()
{
	readln.chomp.to!ulong.solve.writeln;
}
```

`rdmd -unittest` でうまく動いていることを確認する。ちょっと試しただけでは規則性はよくわからない[^1]が、まあ大丈夫だろうと思って提出。**が、コンパイルエラーに。**

```
コンパイルエラーが発生したため、ソースコードの実行はされませんでした。(D (dmd) dmd-2.042)
```

[**DMD 2.042** のリリースは2010年03月19日](http://dlang.org/changelog/2.042.html) で、これは私がDを始めるより前のことである。これでは、このような短いコードであっても「**そんな昔のバージョンでコンパイルできるわけないだろ!**」というのが D言語er の常識。しかし、せっかく書いたコードもコンパイルできなければ採点もされない。エラー読んで古めかしいコードに書き直そう。

最初のコンパイルエラーは、いきなり unittest 内から。

>error code:11
>prog.d(3): found 'solve' when expecting ')'
>prog.d(3): found ')' when expecting ';' following 'statement'
>prog.d(4): found 'solve' when expecting ')'
>prog.d(4): found ')' when expecting ';' following 'statement'
>prog.d(5): found 'solve' when expecting ')'
>prog.d(5): found ')' when expecting ';' following 'statement'
>prog.d(6): found 'solve' when expecting ')'
>prog.d(6): found ')' when expecting ';' following 'statement'
>prog.d(7): found 'solve' when expecting ')'
>prog.d(7): found ')' when expecting ';' following 'statement'

エラーはピリオドのまわり。整数リテラルを第1引数とする UFCS は、このときには使えなかった。原則として全ての型に UFCS が使えるようになったのは [DMD 2.059](http://dlang.org/changelog/2.059.html) からだが、これはなんと [2006年に file された issue](https://issues.dlang.org/show_bug.cgi?id=662) であった。

ともあれ書き直す。

```diff
 unittest
 {
-	assert (0.solve == 0);
-	assert (1.solve == 2); // B, C
-	assert (2.solve == 2);
-	assert (3.solve == 7); // CAC, CAB, CBC, BAB, BAC
-	assert (4.solve == 7);
+	assert (solve(0) == 0);
+	assert (solve(1) == 2); // B, C
+	assert (solve(2) == 2);
+	assert (solve(3) == 7); // CAC, CAB, CBC, BAB, BAC
+	assert (solve(4) == 7);
 }
```

しかし、これくらいでコンパイルエラーがなくなるわけではない。

>error code:11
>prog.d(39): Error: template std.conv.to(T,S) if (!implicitlyConverts!(S,T) && isSomeString!(T) && isSomeString!(S)) does not match any function template declaration
>prog.d(39): Error: template std.conv.to(T,S) if (!implicitlyConverts!(S,T) && isSomeString!(T) && isSomeString!(S)) cannot deduce template function from argument types !()(string)
>prog.d(39): Error: (to(T,S) if (!implicitlyConverts!(S,T) && isSomeString!(T) && isSomeString!(S)))(chomp(readln('\x0a'),null)) isn't a template
>Error: no property 'solve' for type 'int'
>Error: no property 'writeln' for type 'int'

`std.conv.to` が名指しされたのは不可解だが、これも UFCS に関係するらしい。

```diff
 void main()
 {
-	readln.chomp.to!ulong.solve.writeln;
+	writeln(solve(to!ulong(readln.chomp)));
 }
```

「これでコンパイル通った!」と提出したら、入力が大きいときに出力が合わない。見たところ指数オーダーで大きくなるようなのに頭打ちになっているから、オーバーフローのようだ。こんなときのために、D には `std.bigint` が用意されている。

```
 auto solve(in ulong n)
 {
-	ulong ret;
-	ulong[3] current, next;
+	import std.bigint;
+	BigInt ret;
+	BigInt[3] current, next;
 	current[0] = 1;
 	foreach (i; 0..n)
 	{
-		next[] = 0;
+		next[] = BigInt(0);
 		next[0] = current[2] + (i & 1) * current[1];
 		next[1] = current[0] + current[2];
 		next[2] = current[0] + ((i & 1) ^ 1) * current[1];
```

しかしまたコンパイルエラー。

>error code:11
>prog.d(19): found 'import' instead of statement

[Scoped import も最近になって追加されたもの (ドキュメントは 2.058 だが、changelog 上では確認できなかった)](https://github.com/D-Programming-Language/dlang.org/commit/bf370b110460cd515c0dee5f7fde0605e3663aeb) らしい。

```diff
+import std.bigint;
 /** コメント略 */
 auto solve(in ulong n)
 {
-	import std.bigint;
 	BigInt ret;
 	BigInt[3] current, next;
```

これでやっと提出・正解となった。

# 感想

**こんな古いコンパイラ使ってられるか! 私は最新DMDにアップグレードするぞ!** というのが正直なところだが、近年のD言語の進歩を垣間見ることができたということにしておこう。

しかしこれはD言語を始めるのが少し早かったら投げ出していたかもしれないな……。

[^1]: 正解は「フィボナッチ数列の項 (ただし1項おき) - 1」だった。もう少しよく見ればわかっただろう。つまり `std.range.recurrence` で一発のはずだ。