dogfish
BAN USERpublic static void main(String[] args) {
System.out.println();
System.out.println("Generating matrix");
int [][] matrix = generateMatrix(10);
for(int row = 0; row < matrix.length; ++row){
for(int col = 0; col < matrix.length; ++col){
System.out.print(" " + matrix[row][col]);
}
System.out.println();
}
}
public static int [][] generateMatrix(final int N){
int [][] result = new int[N][N];
for(int row = 0; row < N; ++row){
for(int col = 0; col < N; ++col){
setValidNum(row, col, result);
}
}
return result;
}
//idea is to fill the rows and cols up in ascending order so we only need
//to look backwards for problems, can have at most 2 invalid nums
private static void setValidNum(int row, int col, int [][] arr){
int invalidNum1 = 0;
int invalidNum2 = 0;
if(col-2 >= 0 ){
if(arr[row][col-1] == arr[row][col-2]){
invalidNum1 = arr[row][col-1];
}
}
if(row-2 >= 0){
if(arr[row-1][col] == arr[row-2][col]){
invalidNum2 = arr[row-1][col];
}
}
Random rand = new Random();
int result = rand.nextInt(4) + 1;
while(result == invalidNum1 || result == invalidNum2){
result = rand.nextInt(4) + 1;
}
arr[row][col] = result;
}
Good question, I used a trie and a tree set to solve this. I recursively search every node in the Trie searching for the pattern, and then add words found with the pattern to the TreeSet, which will order the words by the position of the pattern in the word. This needs to be optimized to avoid blowing the stack..
- dogfish January 14, 2017