Help us understand the problem. What is going on with this article?

マヨイドーロで迷い olD

More than 3 years have passed since last update.

概要

タイトルで韻を踏もうとしたが苦しい。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項おき) - 1」だった。もう少しよく見ればわかっただろう。つまり std.range.recurrence で一発のはずだ。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away