『フカシギの数え方』 おねえさんといっしょにみんなも25万年数えよう

組み合わせ爆発について、おねえさんが教えてくれて壮大で切ない結末を迎えるという動画が話題になっていました。おねえさんの決意に感動すること間違いなしです。

そこで、ぼくたちもおねえさんと一緒に25万年数えるためのプログラムを作ってみました。
LinkedList#popメソッドが、最後からとってくるんだと思ったら最初からとってきてたという勘違いではまったけど。

工夫なく計算してるので、6x6マスの時点で5分くらいかかります。
考え方としては、始点から上右下左と移動して、移動先でも上右下左と移動して、移動できなくなったら戻るという感じでやってます。

あと、最初に右に行くパターンと下に行くパターンは対称なので同じ回数ずつあるということから、最初は右に行ったことにして、最後に２倍してます。
まあでも、この程度の工夫では25万年が12.5万年になるくらいで、根本的な解決にはなりません。
計算量としては、各点について上下左右４通りの移動があって、点はnの2乗あるので、のような形になるんじゃないですかね。n乗は出てくると思います。

最適化のアイデアとしては、移動可能範囲の形と相対的な始点終点での組み合わせを覚えておいて、同じパターンが出てきたら再利用するという動的計画法を用いたものが考えられます。移動可能範囲のマッチングには多項式時間しかからないので、それなりに計算時間削減できるような気がします。そのかわり、メモリを食いますけど。

勉強して、おねえさんがロボット化しないでいいようにがんばりましょうかｗ

超高速グラフ列挙アルゴリズム:〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ

計算困難問題に対するアルゴリズム理論 (組合せ最適化・ランタ゛マイセ゛ーション・近似・ヒューリスティクス)

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

目次
『フカシギの数え方』 おねえさんといっしょにみんなも25万年数えよう
おねえさんを組み合わせ爆発から救う：格子グラフを生成する
おねえさんを組み合わせ爆発から救う：2分決定木を作る
おねえさんを組み合わせ爆発から救う：無駄を省いてBDDを作る
おねえさんを組み合わせ爆発から救う：ZDDがおねえさんを救う
おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった

ソース

import java.util.LinkedList;

/**
 * 組み合わせ爆発を数える 
 * http://www.youtube.com/watch?v=Q4gTV4r0zRs
 */
public class Keiro {
    
    //方向
    static final int UP = 0;
    static final int RIGHT = 1;
    static final int DOWN = 2;
    static final int LEFT = 3;
    static final String[] dn = {"UP", "RIGHT", "DOWN", "LEFT"};
    //移動距離
    static final int[] dx = { 0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1,  0};
    
    //軌跡
    static class Lucus{
        int x;
        int y;
        int direction;

        public Lucus(int x, int y, int direction) {
            this.x = x;
            this.y = y;
            this.direction = direction;
        }

        @Override
        public String toString() {
            return String.format("%d:%d:%s", x, y, dn[direction]);
        }
        
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // 1:2 2:12 3:184 4:8512 5:1262816 6:575780564 7:789360053252
        countRoute(7, false);
    }
    
    /**
     * 
     * @param cells マスのサイズ
     * @param display 道順を表示するかどうか
     */
    public static void countRoute(int cells, boolean display){
        int size = cells + 1;
        //パターン数
        long count = 0;
        //通った場所
        boolean[][] traced = new boolean[size][size];
        //現在位置
        int x = 1;
        int y = 0;
        //左上は通ったことにする
        traced[0][0] = true;
        //ひとつ右も通ったことにする
        //(最初に右に行く場合と下に行く場合は同じ数あるので右に行った場合を倍にする)
        traced[1][0] = true;
        LinkedList<Lucus> trace = new LinkedList<>();
        //一歩目は上に
        Lucus l = new Lucus(x, y, UP);
        MAIN: for(;;){
            x += dx[l.direction];
            y += dy[l.direction];
            if(x == size - 1 && y == size - 1){
                //右下にたどりついた
                if(display){
                    for(Lucus dl : trace){
                        System.out.print(dl + " ");
                    }
                    System.out.print(l);
                    System.out.println();
                }
                ++count;
            } else if(x < 0 || y < 0 || x >= size || y >= size || traced[x][y]){
                //はみでたか、通ったところ
            } else{
                //まだいける
                //通った
                traced[l.x][l.y] = true;
                trace.push(l);
                //まずは上に
                l = new Lucus(x, y, UP);
                continue;
            }
            for(;;){
                //向きを変えてみる
                int d = l.direction + 1;
                if(d < 4){
                    //次にいく
                    x = l.x;
                    y = l.y;
                    l = new Lucus(x, y, d);
                    continue MAIN;
                }
                //戻る
                if(trace.isEmpty()){
                    //もうどこにもいけない
                    break MAIN;
                }
                //一歩戻る
                l = trace.pop();
                x = l.x;
                y = l.y;
                traced[x][y] = false;
            }
        }

        System.out.println(count * 2);
    }
}