結城先生出題の「マヨイドーロ問題」に取り組みました。

CodeIQで「Java言語で学ぶデザインパターン入門」でおなじみの結城先生が「マヨイドーロ問題」というのを出題されていたので、取り組んでみました。

#投稿した解答
以下がCodeIQに投稿したコードです。言語はJavaです。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class MayoiDouroCounterFinal {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		try {
			String line = readLine();
			int n = Integer.parseInt(line);
			BigInteger p = CountP(n);
			System.out.print(p);

		} catch(IOException e) {

		} catch(NumberFormatException e) {

		}
	}

	private static String readLine() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		return reader.readLine();
	}

	private static BigInteger CountP(int n)
    {
        int m = (n - 1) / 2;

        BigInteger pi = BigInteger.ZERO;

        switch (n)
        {
            case 0:
                pi = BigInteger.ZERO;
                break;
            case 1:
            case 2:
                pi = BigInteger.valueOf(2);
                break;
            default:
            	pi = BigInteger.valueOf(7);
            	BigInteger r0 = BigInteger.valueOf(2); // r0
            	BigInteger ri = BigInteger.valueOf(5); // r1
            	BigInteger num3 = BigInteger.valueOf(3); // 3
                for (int i = 2; i <= m; i++)
                {
                	BigInteger prevRi = ri;
                	ri = ri.multiply(num3).subtract(r0);
                    pi = pi.add(ri);
                    r0 = prevRi;
                }
                break;
        }

        return pi;
    }
}

以下、長文です。

#きっかけ
Twitterで結城先生をフォローしているんですが、タイムラインに「マヨイドーロ問題解いた！」ってツイートしている方のリツイートがばんばん表示されていました。「いつかやってみよう」と思いつつ日が経ちましたが、締め切りが迫ってきたので意を決して着手。12月13日のことでした。

#再帰でしょ？
問題を読んで「これは再帰で解けそうだな」と思い書いてみました。以下。

using System;

namespace MayoiDouro
{
    // オーソドックスなやつ
    class MayoiDouroCounter
    {
        private enum Place
        {
            None = 0,
            X = 1,
            Y = 2,
            Z = 3,
            A = 4,
            B = 5,
            C = 6
        }

        private int N;
        private int P;

        public int CountP(int n)
        {
            this.N = n;
            this.P = 0;
            Go(Place.X, Place.B, 0); // start!
            return P;
        }

        private void Go(Place from, Place now, int count)
        {
            if (count > N)
            {
                return;
            }

            switch (now)
            {
                case Place.A:
                    Go(now, Place.B, count + 1);
                    Go(now, Place.Y, count);
                    break;
                case Place.B:
                    Go(now, Place.A, from == Place.A || from == Place.X ? count + 1 : count);
                    Go(now, Place.C, from == Place.C ? count + 1 : count);
                    break;
                case Place.C:
                    Go(now, Place.B, count + 1);
                    break;
                case Place.Y:
                    P++;
                    break;
            }
        }
    }
}

ちなみに最初はC#でやってました。
これで解けた、と思いました。なんだ楽勝じゃん。
…ところがそうはいきませんでした。

#立ちはだかる関門
以下の2つの条件がありました。

• N=1000やN=2015も解けなくてはいけない
• 結果が1秒以内に出なくてはいけない

これは厳しいです。

ZはどうせNGなのだから考えなくていいとか、スタートはXではなくAだとみなしていいとか、そういうことは思いついていたのでもちろん盛り込みました。

再帰のアレンジで、ノードごとにメソッドを作るというのも考えました。少しだけ速くなりました。少しだけ。

using System;

namespace MayoiDouro
{
    class MayoiDouroCounter6
    {
        private const int O = 0;
        private const int A = 1;
        private const int B = 2;
        private const int C = 3;
        private const int X = 4;
        private const int Y = 5;
        private const int Z = 6;

        private int N;
        private int P;

        int[,,] route;

        public MayoiDouroCounter6()
        {
            Prepare();
        }

        private void Prepare()
        {
            route = new int[7,7,7];

            route[B, A, B] = 1;
            route[X, B, A] = 1;
            route[A, B, A] = 1;
            route[C, B, C] = 1;

            route[B, C, B] = 1;
        }

        public int CountP(int n)
        {
            this.N = n;
            this.P = 0;
            NodeB(X, 0); // start!
            return P;
        }

        private void NodeA(int from, int count)
        {
            if (count > N)
            {
                return;
            }

            int reverse = route[from, A, B];
            NodeB(A, count + reverse);
            NodeY();
        }

        private void NodeB(int from, int count)
        {
            if (count > N)
            {
                return;
            }

            int reverse = route[from, B, A];
            NodeA(B, count + reverse);
            reverse = route[from, B, C];
            NodeC(B, count + reverse);
        }

        private void NodeC(int from, int count)
        {
            if (count > N)
            {
                return;
            }

            int reverse = route[from, C, B];
            NodeB(C, count + reverse);
        }

        private void NodeY()
        {
            P++;
        }
    }
}

ノードではなく、ルートを組み合わせる方式を考えてみました。これも少し速くなるだけ。なお、

• ルートα … B→A→B
• ルートβ … B→C→B

です。

namespace MayoiDouro
{
    class MayoiDouroCounter9
    {
        const int Alpha = 0;
        const int Beta = 1;

        int P;
        int N;

        public int CountP(int n)
        {
            this.N = n;
            this.P = 0;
            RouteAlpha(Alpha, 0);
            RouteBeta(Alpha, 0);

            if (n > 0)
            {
                this.P++;
            }

            return this.P;
        }

        private void RouteAlpha(int from, int count)
        {
            count += 1 + (from ^ Alpha ^ 1);
            if (count > N) return;
            RouteAlpha(Alpha, count);
            RouteBeta(Alpha, count);
            count++;
            P += count <= N ? 1 : 0;
        }

        private void RouteBeta(int from, int count)
        {
            count += 1 + (from ^ Beta ^ 1);
            if (count > N) return;
            RouteAlpha(Beta, count);
            RouteBeta(Beta, count);
            P += count <= N ? 1 : 0;
        }
    }
}

ルートで考える方式をさらにアレンジして、数値でルートパターンを作って0をルートα、1をルートβとみなして計算する方法も考えました。計算が増えて返って遅くなるだけでした。

using System;

namespace MayoiDouro
{
    class MayoiDouroCounter8C
    {
        public int CountP(int n)
        {
            int P = 0;

            int a = 0;

            int max = (int)Math.Pow(2, n);

            while (a <= max)
            {
                int rc = CountReverse(a);
                if (rc <= n)
                {
                    P += 1 + (int)((n - rc) / 2.0);
                }
                a++;
            }

            if (n > 0)
            {
                P++;
            }

            return P;
        }

        private int CountReverse(int a)
        {
            int reverseCount = 0;
            int prev = 0;
            int b = 0;
            do
            {
                b = a & 1;
                reverseCount += 1 + (prev ^ b ^ 1);
                prev = b;
                a >>= 1;
            } while (a > 0);

            reverseCount += (b ^ 1);

            return reverseCount;
        }
    }
}

このほか、「if文を減らせば速くなるはず」と思ってルートパターンをDictionary(Map)や配列で保持する方法もかんがえましたが、やはり遅くなるだけでした。

#法則探し
万策つきました。

いろいろためしてもさっぱり要求を満たす速度が出ない。

そこで「これだけ何をやっても時間がかかるなら正攻法ではだめなのだろう」
「何か単純な計算で求める方法があるのではないか？」
と考え、結果数値をExcelに並べて法則がないか探しました。差分を求めたりして。

そうしたところ、次のことに気づきました。
「1個手前のやつを3倍して2個手前のやつを引けば、差分を求めることができる。」

式で表すとこんな感じでしょうか。

rは差分です。

これに基づき、プログラムを作ってみました。

using System;

namespace MayoiDouro
{
    class MayoiDouroCounter10
    {
        public int CountP(int n)
        {
            int m = (n - 1) / 2;

            int pi = 7;

            switch (n)
            {
                case 0:
                    pi = 0;
                    break;
                case 1:
                case 2:
                    pi = 2;
                    break;
                default:
                    int r0 = 2; // r0
                    int ri = 5; // r1
                    for (int i = 2; i <= m; i++)
                    {
                        int prevRi = ri;
                        ri = ri * 3 - r0;
                        pi += ri;
                        r0 = prevRi;
                    }
                    break;
            }

            return pi;
        }
    }
}

おお、答えが合っている！しかも、速度もとても速い！
これでようやく正解だ＾＾
そう思いました。

#最後の関門
よーく見ると、答えがおかしいです。いえ、N=32ぐらいまではあっているんですが…
というか、N=100ぐらいまではいけてるんですが。
Nの値が大きくなると、Pの値がマイナスになったりします。
「桁あふれだ！」そう気づきました。

困りました。longにしてもだめ。ulongにしてもだめ。
それどころかdecimalにするとOverflowExceptionが発生する始末。

「これは相当大きな値が扱える型がないとだめだ…自作か！？」

残された時間はあと1日。昼間は仕事もある。
でもここまできたら、やってやろう。
そう思って、大きな値を扱うためのクラスを作り始めました。

#Javaへスイッチ
16日夜。締め切りは明日の午前10時。
やってみると、意外と面倒です。AddとMultiplyまではできましたが、
Subtractがどうにも…。
時間さえあれば…。
もっと早くに取り組んでおけばよかった…。

そう思ったとき、ふと思い出しました。
そういえばJavaにはBigDecimal(BigInteger)があったな。
あれはどうなんだ！？

C#で作ったプログラムをJavaに移植してみることにしました。
移植といってもほとんど同じなのであまり変える部分はないですが。

BigIntegerで実装。ついにやりました！
ものすごい桁数の数字が表示されていきます…。

あとで調べて気づいたんですが、C#にもBigIntegerありますね。
車輪の再発明だった(笑)
でも、CodeIQに投稿してみたら、なんかSystem.numerics.dllがアセンブリ参照されていないみたいでコンパイルエラーになっちゃうんですよね。
Ideone公式だと通るんですが…。

#そして、投稿へ…。
どきどきしながらCodeIQの問題のページへ投稿。ぽち！
実行中であることを示すインジケータがくるくる回ります。
どきどき。

正解！正解！正解！
全問正解！

「この程度で」と思われそうですが、すごくうれしかったです。

#感想・その他
関門がいくつもあって良問だったと思います。
最初は正攻法でプログラムを書いていましたが、これも法則を見つけるための足がかりとなったので必要だったと思います。
「これ、ナントカ数列って名前がついていそうだ」って思いました。フィボナッチ数列ですか？
無学でごめんなさい(o_ _)o

C#版は前述の通り System.Numericsが使えなくてだめでした。
Perl版とPHP版も12/17の朝にこしらえて投稿してみましたが、
やはり最後の２，３個のテストケースがNGです。
PerlでもBigInteger的なものがuseできるようですが、調べている時間がありませんでした。時間切れ。

最終的にJavaで作ったプログラムもなんかもっとシンプルになりそうな気がするなー。
解説読もうっと。
…結果画面をXPSで保存しようとしたんですが、ブラウザがその瞬間フリーズしてしまい解説を保存しそびれたので、解説公開待ち…(笑)