This algorithm has me stumped. I'm pretty novice to data structures and alogithms, I understand what the code needs to do, but can't wrap my brain on how to actually code it.
The problem is as follows:
Determines whether the matrix includes a golden ticket. A golden ticket consists of 6 upper-case 'G' where three pairs of Gs are right above each other as shown below. Note that I left out the single quotes to improve readability.
G G
G G
G G
E.g.,
[A b - - C d m]
[- G G Z G G -]
[H o - r G G D] this matrix returns true
[H o - r G G D]
E.g.,
[R g G - C d m W]
[- G G Z G G - r] this matrix returns false
[o G G G r G G D] because the Gs are not in the specified position
[S t C - G G a -] relative to each other
The matrix should be 'rectangular', which means, all rows should have the same number of elements. If that is not the case, an IllegalArgumentException should be thrown.
This is what I have written:
public static boolean goldenTicket(char[][] matrix) {
if (matrix == null) return false;
if (matrix.length == 0) return false;
char char1, char2;
int matchCount = 0;
int indexOne = 0, indexTwo = 0, prevIndex1 = 0,prevIndex2 = 0;
int rows = matrix.length;
int columns = matrix[0].length;
for(int i = 0; i < rows;i ) {
if(matrix[i].length != columns)
throw new IllegalArgumentException("Length of row doesn't match");
if(matrix[i].length == 0) return false;
if(matchCount == 3) return true;
for(int j=1;j<columns;j ) {
if(matrix[i][j] == 'G' && matrix[i][j - 1] =='G') {
if(prevIndex1 == 0 && prevIndex2 == 0) {
indexOne = j-1;
indexTwo = j;
matchCount ;
}
else {
prevIndex1 = j-1;
prevIndex2 = j;
matchCount ;
}
}
}
if(prevIndex1 == indexOne && prevIndex2 == indexTwo) {
matchCount ;
}
}
return false;
}
However, the problem is the code passes both example one and two as above, instead of only passing example 1. I've already turned in the assignment with only passing 24/25 tests, I just really want to understand how this should work and maybe a better way to code it for future reference.
Thanks in advance!
CodePudding user response：
It could be solved with O(ncol*nrow), where ncol is the number of columns and nrow is the number of rows.
You should generate a matrix with the same rows and columns as your original matrix, and for each item you consider a pair of number which first element represent number of sequential G's including this item in the row, and second element represent number of sequential G's including this item in the column.
To fill this matrix(I named it onlyGMatrix) we check if item (i,j) is G, if not we simply put pair (0,0) otherwise for i>0 and j>0 we put min {onlyGMatrix(i-1,j)[0] , onlyGMatrix(i,j-1)[0]} 1 as first element and min {onlyGMatrix(i-1,j)[1] , onlyGMatrix(i,j-1)[1]} 1 as the second element.
Using your first matrix we would reach the below onlyGMatrix:
(0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0)
(0,0) (0,0) (0,0) (0,0) (1,1) (2,1) (0,0)
(0,0) (0,0) (0,0) (0,0) (2,1) (2,2) (0,0)
(0,0) (0,0) (0,0) (0,0) (3,1) (3,2) (0,0)
And for your second matrix we would have:
(0,0) (0,0) (1,1) (0,0) (0,0) (0,0) (0,0) (0,0)
(0,0) (1,1) (2,2) (0,0) (1,1) (2,1) (0,0) (0,0)
(0,0) (1,2) (2,3) (3,1) (0,0) (1,2) (2,1) (0,0)
(0,0) (0,0) (0,0) (0,0) (1,1) (2,1) (0,0) (0,0)
now your algorithm simply would end successfully when you see pair (3,2) when you building this onlyGMatrix, and if you reach the last element of matrix and you didn't see this pair then you should return false.
CodePudding user response：
This is the type of problem where divide and conquer can help simplify the code.
The task is to find a 2 x 3 matrix of the letter "G" in a larger matrix.
So, we write a method to check each 2 x 3 matrix within a larger matrix.
Here are the results of one of my tests.
[a, G, G, a]
[a, G, G, a]
[a, G, a, a]
[a, a, a, a]
false
[a, G, G, a]
[a, G, G, a]
[a, G, G, a]
[a, a, a, a]
true
[a, a, a, a]
[a, a, G, G]
[a, a, G, G]
[a, a, G, G]
true
I wrote two methods.
The goldenTicket method checks to see if the matrix is null, less than a 2 x 3 matrix, or if the column lengths are the same. The last code block goes through the matrix looking for the golden ticket.
The isTicket method checks to see if the current 2 x 3 section of the matrix consists of all "G" letters.
Breaking up the code into two methods makes each method smaller and easier to read, and hides somewhat the fact that it takes 4 nested for loops to solve the task correctly.
Here's the complete runnable code.
import java.lang.reflect.Array;
import java.util.Arrays;
public class GoldenTicketExample {
public static void main(String[] args) {
char[][] matrix1 = { { 'a', 'G', 'G', 'a' }, { 'a', 'G', 'G', 'a' },
{ 'a', 'G', 'a', 'a' }, { 'a', 'a', 'a', 'a' } };
displayOutput(matrix1);
char[][] matrix2 = { { 'a', 'G', 'G', 'a' }, { 'a', 'G', 'G', 'a' },
{ 'a', 'G', 'G', 'a' }, { 'a', 'a', 'a', 'a' } };
displayOutput(matrix2);
char[][] matrix3 = { { 'a', 'a', 'a', 'a' }, { 'a', 'a', 'G', 'G' },
{ 'a', 'a', 'G', 'G' }, { 'a', 'a', 'G', 'G' } };
displayOutput(matrix3);
}
private static void displayOutput(char[][] matrix) {
for (char[] row : matrix) {
System.out.println(Arrays.toString(row));
}
System.out.println(goldenTicket(matrix));
}
public static boolean goldenTicket(char[][] matrix) {
if (matrix == null) {
return false;
}
if (matrix.length < 3) {
return false;
}
int columns = matrix[0].length;
if (columns < 2) {
return false;
}
for (int row = 1; row < matrix.length; row ) {
if (matrix[row].length != columns) {
throw new IllegalArgumentException(
"Length of row doesn't match");
}
}
for (int row = 0; row < matrix.length - 2; row ) {
for (int column = 0; column < matrix[row].length - 1; column ) {
if (isTicket(matrix, row, column)) {
return true;
}
}
}
return false;
}
private static boolean isTicket(char[][] matrix, int row, int column) {
for (int r = row; r < row 3; r ) {
for (int c = column; c < column 2; c ) {
if (matrix[r][c] != 'G') {
return false;
}
}
}
return true;
}
}