[解決済み] ブルガリアソリティアJava

質問

APコンピュータサイエンスのコースで、数日後に以下の課題を提出することになっています。

この課題では、ブルガリアン・ソリティアというゲームをモデル化することになります。このゲームは45枚のカードで始まります。それらをランダムな大きさのいくつかの山にランダムに分割します。例えば、20、5、1、9、10の大きさの山から始めるかもしれない。各ラウンドで、それぞれの山から1枚ずつカードを取り、新しい山を作ります。たとえば、この例では、19,4,8,10,5という大きさの山が作られます。そして、1、2、3、4、5、6、7、8、9の順に並んだらソリティアは終了です。

プログラムで、ランダムな開始時の構成を生成し、それを表示します。その後、ソリティアのステップを適用し続け、その結果をプリントしてください。ソリティア最終構成に到達したら停止してください"。

これを解決するプログラムを思いついたのですが、問題は、時々非常に長い時間がかかることです。私の予想通り、ほとんど瞬時に解決することもあれば、18,000回以上反復することもあります。

によると http://mancala.wikia.com/wiki/Bulgarian_Solitaire の場合、(k^2)-kステップ以内で解を求めることができます（この場合のkは9）。私は多くの場合、72ステップ以下で解を見つけることはできません。このプログラムを何時間も見て、もっと速くできないかといろいろいじりましたが、十分な数の反復で動作させることができません。そこで、今、私はStack Overflowにやってきて、皆さんの誰かが私を正しい方向に導くのを助けることができるかどうかを見ています。

以下は私のコードです。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class BulgarianSolitaire {

    ArrayList<Integer> cards = new ArrayList<Integer>();
    Random rand = new Random();
    boolean cont = true;
    boolean cont2 = true;

    public static void main(String[] args) {
        BulgarianSolitaire game = new BulgarianSolitaire();
    }

    public BulgarianSolitaire() {
        System.out.println("Started");
        int sum = 0;
        while (cont) {
            if (sum < 45) {
                cards.add(rand.nextInt(46 - sum));
            } else {
                cont = false;
            }

            sum = 0;
            for (int i = 0; i < cards.size(); i++) {
                sum += cards.get(i);
            }

            removeZeros(cards);

            System.out.println(cards);
        }

        System.out.println("Finished Generating Start");

        while (cont2) {
            solitaireStep();
            System.out.println(cards);
            if (checkCards()) {
                cont2 = false;
            }
        }

        Collections.sort(cards);
        System.out.println("Cards are sorted");
        System.out.println(cards);
    }

    public void removeZeros(ArrayList<Integer> list) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) == 0) {
                list.remove(j);
            }
        }
    }

    public void solitaireStep() {

        int numberRemoved = 0;

        for (int i = 0; i < cards.size(); i++) {
            int value = cards.get(i);
            cards.set(i, value - 1);
            removeZeros(cards);
            numberRemoved++;
        }

        cards.add(numberRemoved);
    }

    public boolean checkCards() {
        ArrayList<Integer> expectedCards = new ArrayList<Integer>();

        for (int i = 1; i < 10; i++) {
            expectedCards.add(i);
        }

        ArrayList<Integer> sortedCards = cards;
        Collections.sort(sortedCards);
        boolean equal = true;
        if (sortedCards.size() != expectedCards.size()) {
            equal = false;
        }

        for (int i = 0; i < sortedCards.size(); i++) {
            if (sortedCards.size() == expectedCards.size()) {
                if (sortedCards.get(i) != expectedCards.get(i)) {
                    equal = false;
                }
            }
        }

        return equal;
    }
}

だから、基本的には0から45までの乱数を生成して、それをカードのリストに加えることから始めるんだ。そして、合計が45より小さい限り、乱数を生成してリストに入れ続けます。生成される乱数は、0から45の間、つまり最後の反復でリストに入れられた数の合計となります。リストの中の0は、その都度削除されます。

リストが生成されると、リスト内のすべての数値から1を引き、0を取り除き、減ったスタック数に等しい新しい値を追加するステップを実行する。また、カードスタックの順序をリスト{1, 2, 3, 4, 5, 6, 7, 8, 9}に対してチェックし、一致するものを見つけたら、そのソリティアステップを実行しないようにブール型 cont2 を false にセットしています。

そんなところです。助けてくれる人に感謝を捧げます。

解決方法は？

あなたの欠点は、あなたの removeZeros メソッドを使用します。

public void removeZeros(ArrayList<Integer> list) {
    for (int j = 0; j < list.size(); j++) {
        if (list.get(j) == 0) {
            list.remove(j);
        }
    }
}

で要素を削除すると j の場合、リストのサイズは1だけ小さくなります。 j も、そうです。

これに変えてください。

  public void removeZeros(ArrayList<Integer> list) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) == 0) {
                list.remove(j);
                j--;
            }
        }
    }

チェックの仕方も複雑すぎる。

ソリティアのステップで、0に等しいはずの値をすべて0に設定してください。

次に、ゼロを削除します（改訂版メソッドで）。 ループの外側 .

そして、配列を並べ替えます。

そして、配列がソートされているので、チェックメソッドで。

public boolean checkCards() {
    for(int i = 0; i < cards.size(); i++) {
        if(cards.get(i) != i + 1) {
            return false;
        }
    }
    return true;
}

もっとシンプルに。そして、うまくいくのです。