Warum gibt mein Algorithmus Stackoverflow-Ausnahme zurück?

Question

Ich muss einen Algorithmus machen, der ein zweidimensionales Array mit zufälligen (zwischen 0 und 2) Zahlen füllt, die einzige Bedingung ist, dass ich die gleiche Anzahl 3 oder mehr Mal horizontal und vertikal haben kann. Zum Beispiel

[0,0,1,2,1 
0,1,2,1,2 
1,2,0,1,0] 

ist ok

[0,0,0,2,1 
0,1,2,1,2 
1,2,0,1,0] 

oder

[0,0,1,2,1 
0,1,1,1,2 
1,2,1,1,0] 

falsch ist.

So, hier ist mein Algorithmus:

public class CandyHelper { 

    private final int minimumChainLength = 3; 
    private final int searchChainSize = 3; 

    public Candy[][] randomInit(int rowCount, int columnCount) { 
     Candy[][] map = new Candy[rowCount][columnCount]; 
     for (int row = 0; row < rowCount; ++row) { 
      for (int column = 0; column < columnCount; ++column) { 
       // Fill square with random candy. 
       Random rand = new Random(); 
       int value = rand.nextInt(3); 
       Candy candy = new Candy(); 
       candy.setType(value); 
       map[row][column] = candy; 
      } 
     } 

     if (findHint(map)) { 
      //System.out.println("Winning conditions"); 
      map = null; 
      map = randomInit(rowCount, columnCount);   
     } else { 
      System.out.println("no wining"); 
     } 

     return map; 
    } 

    // Function which searches for match of at least `MinimumChainLength`. 
    private boolean findHint(Candy[][] map) { 
     int rowCount = map.length; 
     int columnCount = map.length; 

     List<Candy> hintMove = new ArrayList<Candy>(); 

     // Search rows. 
     for (int row = 0; row < rowCount; ++row) { 
      // Search for chain. 
      for (int chainStart = 0; chainStart < columnCount - searchChainSize; ++chainStart) { 
       // Add initial cell in chain. 
       hintMove.clear(); 
       hintMove.add(map[row][chainStart]); 
       for (int nextInChain = chainStart + 1; nextInChain < columnCount; ++nextInChain) { 
        if (map[row][nextInChain].getType() == hintMove.get(0).getType()) { 
         hintMove.add(map[row][nextInChain]); 
        } else { 
         break; 
        } 
       }   
       // Was a chain found? 
       if (hintMove.size() >= minimumChainLength) 
        return true; 
      } 
     } 

     // Search columns. 
     for (int column = 0; column < columnCount; ++column) { 
      // Search for chain. 
      for (int chainStart = 0; chainStart < rowCount - searchChainSize; ++chainStart) { 
       // Add initial cell in chain. 
       hintMove.clear(); 
       hintMove.add(map[chainStart][column]); 
       for (int nextInChain = chainStart + 1; nextInChain < rowCount; ++nextInChain) { 
        if (map[nextInChain][column].getType() == hintMove.get(0).getType()) { 
         hintMove.add(map[nextInChain][column]); 
        } else { 
         break; 
        } 
       } 
       // Was a chain found? 
       if (hintMove.size() >= minimumChainLength) 
        return true; 
      } 
     } 

     // No chain was found, so clear hint. 
     hintMove.clear(); 
     return false;  
    } 

} 

und meine pojo:

public class Candy { 
    private int type; 

    public int getType() { 
     return type; 
    } 

    public void setType(int type) { 
     this.type = type; 
    } 

    @Override 
    public String toString() { 
     return "Candy{" + "type=" + type + '}'; 
    } 

} 

Wenn ich aus einer Reihe von 10x10 beginne ich immer die Stack-Überlauf-Fehler starten. Was soll ich tun, um sie zu korrigieren?

Vielen Dank im Voraus.

Answer 1

Ihr Problem ist diese Zeile:

map = randomInit(rowCount, columnCount); 

im Wesentlichen jedes Mal findHint true zurück, Sie gehen zu rekursiv randomInit aufzurufen. Das bedeutet, je größer die Wahrscheinlichkeit ist, dass FindHint True zurückgibt, desto höher ist die Wahrscheinlichkeit eines Stackoverflows. In deinem Fall gilt: Je größer du dein Raster machst, desto höher ist die Wahrscheinlichkeit, dass FindHint wahr wird, und bei Größe 10 ist es fast sicher, dass es in einem Stackoverflow endet.

Ich bin ganz ehrlich Ich bin mir nicht sicher, warum Sie RandomInit hier wieder aufrufen, anstatt nur die Karte zurück zu geben?

Answer 2

Ohne Ihren Code ausgeführt zu haben, würde ich vermuten, dass es sich um randomInit() handelt, wenn sich findHint() aufruft. Ich finde nichts falsch mit Ihrem Code für findHint() (abgesehen von ein paar Performance-Tweaks - zB brauchen Sie keine Liste von Übereinstimmungen zu erstellen, nur um zu zählen, wie viele es gibt), sondern die Tatsache, dass Sie vermutlich nur auf dieses Problem stoßen auf 10x10 Grids erzählt. Jedes 10x10-Raster von Objekten mit nur drei Typen hat sehr wahrscheinlich drei hintereinander - wahrscheinlich genug, dass Ihr randomInit() sich oft genug nennt, um Ihren Stack-Overflow zu bekommen.

Ich bin nicht 100% sicher, was Sie wollen randomInit() zu tun. Wenn Sie es wünschen ein zufälliges Gitter zu halten Erzeugung, bis es keine Sätze von N sind, würde ich vorschlagen, die Gittergenerierung Code in einem separaten Verfahren setzen (nennen wir es generate()) und dann randomInit() Anruf es in einer while-Schleife haben:

boolean setFound; 
do { 
    map = generate(rowCount, columnCount); 
    setFound = findHint(map); 
} while (setFound);