概要
タイトルで韻を踏もうとしたが苦しい。CodeIQ に 結城浩さん が出題している「マヨイドーロ」という問題を解いたら、いにしえのD言語に迷い込んでしまった。
問題ほか
結城浩さんによるアナウンス tweet を参照。
本編
さて、問題文に含まれている例に少しの実験を加え、次の unittest から始めることにする。
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);
}
汚いながらも、最低限の考察から愚直に実装した。数学を専門としていた者にあるまじき態度だが、食後の眠いときだったので妥協してほしい。コードの中身は本筋に関係ないので。
/** 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日 で、これは私が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 からだが、これはなんと 2006年に file された issue であった。
ともあれ書き直す。
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 に関係するらしい。
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 上では確認できなかった) らしい。
+import std.bigint;
/** コメント略 */
auto solve(in ulong n)
{
- import std.bigint;
BigInt ret;
BigInt[3] current, next;
これでやっと提出・正解となった。
感想
こんな古いコンパイラ使ってられるか! 私は最新DMDにアップグレードするぞ! というのが正直なところだが、近年のD言語の進歩を垣間見ることができたということにしておこう。
しかしこれはD言語を始めるのが少し早かったら投げ出していたかもしれないな……。
-
正解は「フィボナッチ数列の項 (ただし1項おき) - 1」だった。もう少しよく見ればわかっただろう。つまり
std.range.recurrenceで一発のはずだ。 ↩