お姉さん問題を実際にコードで表現して計算してみた

お姉さん問題って？

https://www.youtube.com/watch?v=Q4gTV4r0zRs
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！

こちらのyoutubeの動画です。
組み合わせの爆発を伝えたいお姉さんが一生をかけて組み合わせのすごさを身をもって教えるという動画です。

ここで取り上げられている問題が、
「N × Nのマス目があり、左上のスタートから右下ゴールまで遠回りしてもいいから何通りの道順がとれるか」
というものです。みんなで数えてみようって言われているので数えるしかありません。

制約としては、同じ道を通ってはいけないというもののみです。

N	組み合わせ
1	2
2	12
3	184
4	8512
5	1262816
6	575780564
7	789360053252
8	3266598486981642
9	41044208702632496804
10	1568758030464750013214100

気になったので自分でも検証してみたい!!という記事です。

今回のアルゴリズム

お姉さんをリスペクトして愚直な方法を使います。具体的に2×2の場合は以下のように判断します。
ここで、説明のため、
[0][0]をスタート、[2][2]をゴールとします。

① 初めに[0][0]をスタックにつめる
② スタックから[0][0]を取り出す
③ 上に進めるか判断する。(今回は進めない)
④ 下に進めるか判断する。(今回は進める)
⑤ スタックに[0][0]→[1][0]に進んだルートを詰める
⑥ 右に進めるか判断する。(今回は進める)
⑦ スタックに[0][0]→[0][1]に進んだルートを詰める
⑧ 左に進めるか判断する。(今回は進めない)
⑨ ②に戻る。(その際、スタックが空なら処理終了)

いたってシンプルなアルゴリズムです。

ルートに判断させる

オブジェクト指向っぽく実装する練習がしたかったので、その方針で検討。

トランザクションスクリプトっぽく実装すると、
「このルートはこの経路を通ったことがあるから、右か左にいける」
と人間が判断しますが、

「ルートくん、右に進むことはできますか？」
「はい」
のように、実際のルートが自分が右にいけるか左にいけるかを判断してもらうようにします。

具体的には

List<Integer> route = routeSet.getLatest();
if (route == (何らかの条件)){
  右にすすめる
}

ではなく

if (route.canGoLeft())

のようにルートに判断してもらい、実際の移動も

route.goLeft();

のように実装したいと思います。

ソースコード

上記のルートに判断させる、というのを意識して書いてみました。

実際にRouteクラスの中身は意識せずとも動きは直感的に理解できるようにはなるように実装したつもりなのですが、いかがでしょうか。
ルートを動かした後の処理は共通化したかったのですが、いい名前が思いつかず、postMoveProcessとか謎なメソッド名になってしまいました・・・

import java.util.Scanner;
import java.util.Stack;

public class MazeSolver {

    private static long count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        sc.close();

        long start = System.nanoTime();
        Stack<Route> stack = new Stack<>();

        stack.add(new Route(len));

        while (stack.size() > 0) {
            Route route = stack.pop();
            if (route.canGoDown()) {
                Route clone = route.clone();
                clone.goDown();
                postMoveProcess(stack, clone);
            }
            if (route.canGoUp()) {
                Route clone = route.clone();
                clone.goUp();
                postMoveProcess(stack, clone);
            }
            if (route.canGoRight()) {
                Route clone = route.clone();
                clone.goRight();
                postMoveProcess(stack, clone);
            }
            if (route.canGoLeft()) {
                Route clone = route.clone();
                clone.goLeft();
                postMoveProcess(stack, clone);
            }
        }
        System.out.println(count + "通り");
        System.out.println(((System.nanoTime() - start) / 1000000) + "ms");
    }

    private static void postMoveProcess(Stack<Route> stack, Route route) {
        if (route.isGoal()) {
            route.printRoute();
            count++;
            return;
        }
        stack.add(route);
    }
}

次にRouteクラスの方の実装です。
[0][0]と二次元配列でもつのは大変そうだったので、

[0][0] → 0
[0][1] → 1
[0][2] → 2
[1][0] → 3
・・・
[2][2]→8

のように一次元の配列で管理しました。
(今回ルートの長さが決まっておらず、出力大変そうだったので、重いですがArrayList使ってしまいました・・・)

import java.util.ArrayList;

class Route implements Cloneable {

    private int len;

    private int goal;

    private ArrayList<Integer> route;

    private int location;

    Route(int len) {
        this.len = len + 1;
        this.route = new ArrayList<>();
        route.add(0);
        this.goal = (len + 1) * (len + 1) - 1;
        this.location = 0;
    }

    public boolean contains(int point) {
        return route.contains(point);
    }

    public boolean canGoUp() {
        int newLocation = location - len;
        if (newLocation < 0 || contains(newLocation)) {
            return false;
        }
        return true;
    }

    public void goUp() {
        int newLocation = location - len;
        if (!canGoUp()) {
            return;
        }
        move(newLocation);
    }

    public boolean canGoDown() {
        int newLocation = location + len;
        if (newLocation > goal || contains(newLocation)) {
            return false;
        }
        return true;
    }

    public void goDown() {
        int newLocation = location + len;
        if (!canGoDown()) {
            return;
        }
        move(newLocation);
    }

    public boolean canGoRight() {
        int newLocation = location + 1;
        if (newLocation % len == 0 || contains(newLocation)) {
            return false;
        }
        return true;
    }

    public void goRight() {
        int newLocation = location + 1;
        if (!canGoRight()) {
            return;
        }
        move(newLocation);
    }

    public boolean canGoLeft() {
        int newLocation = location - 1;
        if (location % len == 0 || contains(newLocation)) {
            return false;
        }
        return true;
    }

    public void goLeft() {
        int newLocation = location - 1;
        if (!canGoLeft()) {
            return;
        }
        move(newLocation);
    }

    private void move(int newLocation) {
        location = newLocation;
        route.add(newLocation);
    }

    public boolean isGoal() {
        return location == goal;
    }

    public void printRoute() {
        System.out.println(route.toString());
    }

    @SuppressWarnings("unchecked")
    @Override
    public Route clone() {
        Route clone = null;
        try {
            clone = (Route) super.clone();
            clone.route = (ArrayList<Integer>) this.route.clone();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return clone;
    }
}

多少冗長な気はしますが、Routeの呼び出し元が分かりやすいメリットの方が大きいと感じています。

実行してみよう！

2×2の出力は以下のようです。
点に色々判断したのが功を奏したのか一発目からきちんと正しく動きました。

複雑なロジックほどオブジェクト指向が強いなというのを実感をもって学べました。

2
[0, 1, 2, 5, 8]
[0, 1, 2, 5, 4, 3, 6, 7, 8]
[0, 1, 2, 5, 4, 7, 8]
[0, 1, 4, 3, 6, 7, 8]
[0, 1, 4, 5, 8]
[0, 1, 4, 7, 8]
[0, 3, 4, 5, 8]
[0, 3, 4, 1, 2, 5, 8]
[0, 3, 4, 7, 8]
[0, 3, 6, 7, 8]
[0, 3, 6, 7, 4, 5, 8]
[0, 3, 6, 7, 4, 1, 2, 5, 8]
12通り
1ms

ルートごとの出力をやめて(ここのIOすごい時間かかりそうだったので)
実行してみた結果が以下のようです。7は検証中です。

N	組み合わせ	かかった時間
1	2	1ms
2	12	1ms
3	184	4ms
4	8512	64ms
5	1262816	3935ms
6	575780564	2578538ms
7	789360053252
8	3266598486981642
9	41044208702632496804
10	1568758030464750013214100

感想

• オブジェクト指向を実践しつつ効果も実感できた。
• 今更ではあるんですが、6億通り近い経路を現実的な時間で計算してしまうコンピュータってすごいなと。
• 組み合わせ爆発を身をもって体感しました。
• お姉さんの気持ちがわかりました。