怪盗BisCoのロック解除ゲーム

SOUNDGAME Java

こんな感じで計算させてみました。

package calc;

import java.util.HashSet;

public class PairCards {

    private int finalPairs = 0;
    private long[] games = new long[0];
    
    private PairCards(int pairs) {
        this.finalPairs = pairs;
        this.games = new long[pairs * 2];
    }
    
    public static void main(String[] args) {
        int pairs = 10;
        if (args != null && args.length > 0) {
            try {
                pairs = Integer.parseInt(args[0]);
            } catch (NumberFormatException nfe) {
                // NOP
            }
        }
        new PairCards(pairs).start();
    }
    
    private void start() {
        long startMillis = System.currentTimeMillis();
        generatePatterns(new char[0], 0);
        long endMillis = System.currentTimeMillis();
        // result
        long elapsed = endMillis - startMillis;
        System.out.println("elapsed: " + elapsed + " (ms)");
        for (int i = finalPairs; i < finalPairs * 2; i++) {
            System.out.println(i + " turns : " + games[i]);
        }
    }
    
    private void generatePatterns(char[] parents, int pairs) {
        int currentPairs = pairs + 1;
        char[] cards = new char[parents.length + 2];
        char newCard = (char)('a' + currentPairs - 1);
        
        int inserts = currentPairs * 2 - 1;
        cards[0] = newCard;
        cards[1] = newCard;
        for (int i = 2; i < cards.length; i++) {
            cards[i] = parents[i - 2];
        }
        
        for (int j = 0; j < inserts; j++) {
            if (j > 0) {
                // swap
                char x       = cards[j];
                cards[j]     = cards[j + 1];
                cards[j + 1] = x;
            }
            if (currentPairs >= this.finalPairs) {
                play(cards);
            } else {
                generatePatterns(cards, currentPairs);
            }
        }
    }

    private void play(char[] cards) {
        HashSet<Character> appeared = new HashSet<Character>();
        int turns = 0;
        int cidx = 0;
        
        while (cidx < cards.length) {
            // 1st-card
            Character first = (Character)cards[cidx++];
            if (appeared.contains(first)) {
                // got pair.
                turns++;
                continue;
            } else {
                // memory this-card
                appeared.add(first);
            }
            
            // 2nd-card
            Character second = (Character)cards[cidx++];
            if (first == second) {
                // LUCKY!! got pair.
                turns++;
            } else if (appeared.contains(second)) {
                // will get pair in next turn.
                turns += 2;
            } else {
                // memory this-card
                appeared.add(second);
                turns++;
            }
        }
        
        games[turns]++;
    }
}

実行結果はこんな感じで出力されました。6分かかってない。

elapsed: 348735 (ms)
10 turns : 1
11 turns : 330
12 turns : 38940
13 turns : 1940708
14 turns : 38250520
15 turns : 235449500
16 turns : 310432606
17 turns : 67020602
18 turns : 1594846
19 turns : 1022

解説とか

すべての順列で試すと計算量が爆発する（カード20枚の場合は、20! = 243 2902 0081 7664 0000）ので、すべての組み合わせ（カード20枚の場合は、19×17×15×……×3×1 = 6 5472 9075）で計算させます。

まずは2枚の場合

当然1ターンで終了です。このとき、カードが「A」と「a」であった場合、順列だと「Aa」「aA」の2通りありますが、いずれも1ターンで終了するため、この2枚を同一視して「AA」とみなしても確率は2/2 = 1/1 と同じ結果になります。

つぎに4枚の場合

カードが「A」、「a」、「B」、「b」の場合、順列だと 4! = 24 通りになります。すべて書き出すと、

  1. AaBb : 2ターン
  2. aABb : 2ターン
  3. AabB : 2ターン
  4. aAbB : 2ターン
  5. BbAa : 2ターン
  6. bBAa : 2ターン
  7. BbaA : 2ターン
  8. bBaA : 2ターン
  9. ABab : 3ターン
  10. aBAb : 3ターン
  11. AbaB : 3ターン
  12. abAB : 3ターン
  13. BAba : 3ターン
  14. bABa : 3ターン
  15. BabA : 3ターン
  16. baBA : 3ターン
  17. ABba : 3ターン
  18. aBbA : 3ターン
  19. AbBa : 3ターン
  20. abBA : 3ターン
  21. BAab : 3ターン
  22. bAaB : 3ターン
  23. BaAb : 3ターン
  24. baAB : 3ターン

2ターンは8通り、3ターンは16通りですので、確率だと2ターン = 8/24 = 1/3、いっぽう3ターン = 16/24 = 2/3となります。

組み合わせだと「AABB」「ABAB」「ABBA」の3通りに集約できます。このとき、「AABB」は2ターンで終了、「ABAB」は3ターンで終了、 「ABBA」も3ターンで終了です。確率で見ると、2ターン = 1/3、いっぽう3ターン = 2/3で、順列でも組み合わせでも確率は同じ値になります。

組み合わせの数え上げについて

以下のような手順でもれなく数え上げることが出来ます。
2枚から4枚のときは、「ZZ」に対して2枚の「Y」を差し込みます。差し込むときは、「◎●Z●Z●」のように考えて、「◎」に1枚目の「Y」を固定で配置し、「●」のいずれかに2枚目の「Y」を配置します。

4枚から6枚のときも同様に、「YYZZ」「YZYZ」「YZZY」に2枚の「X」を差し込みます。最初の「YYZZ」に対しては、「XXYYZZ」「XYXYZZ」「XYYXZZ」「XYYZXZ」「XYYZZX」の5通りが考えられ、残りの「YZYZ」「YZZY」にも同様に5通りずつの差し込み方が考えられます。

このアルゴリズムで、指定のペア数に対する数え上げが出来ます。Javaソースでは、generatePatterns(char[], int) メソッドが再帰呼出しで実装されています。

ターン数の数え上げについて

ツイート再掲。


上記のJavaソースでは、play(char[]) メソッドにて実装されています。

既に出てきたカードを覚えておくためのSet<Character>を生成し、#contains(Character)で既出かどうかの判定をします。
1枚目をめくり、Setに含まれていれば、そのペアを取って1ターン終了。ターン終了なので、次にめくるのはまた1枚目です。
1枚目に含まれていなければ、Setに覚えさせます。

2枚目をめくり、1枚目と同じカードならペアを取って1ターン終了です。ラッキーですね。
1枚目とは違うカードで、Setに含まれていれば、次のターンでそのペアを取ります。よって2ターンかかります。
1枚目とは違うカードで、Setに含まれていなければ、Setに覚えさせて、1ターン終了です。

計算速度について

このアルゴリズムは、char[] cards を線形に辿るだけで計算量はO(n)です。また、Set#contains(Character)はハッシュ関数で、このパターンでは衝突も発生しないため、計算量はO(1)です。

実行環境では、6億5千万通りに対して350秒で処理を終えています。1秒あたり188万通りの組み合わせに対してターン数の数え上げができています。非常に現実的な範囲での計算時間だったことに、正直なところ安堵しています。