Problem Statement
The problem describes a pseudocode that operates on a rectangular grid. Each cell value on a row is a value of function operated on the previous row.
For i = 0 to H-2:
For j = 0 to W-2:
//Get the current colors of cells (i,j) and (i,j+1)
A = Color(i,j) , B = Color(i,j+1)
If (A,B) == (White, White) Then:
Do nothing.
EndIf
If (A,B) == (Black, White) Then:
Repaint cells (i+1,j) and (i+1,j+1) Black.
EndIf
If (A,B) == (White, Black) Then:
Repaint cells (i+1,j) and (i+1,j+1) White.
EndIf
if (A,B) == (Black, Black) Then:
Swap the colors in cells (i+1,j) and (i+1,j+1).
EndIf
EndFor
EndForApproach
From the problem statement, we notice small input constraints, giving us a hint to try out all possibility. Let’s discuss how to try all possibility, Consider the grid as set of binary values, and with little observation, it’s clear that first Row values are not affected. So, starting from row=1, we can try out all combinations by checking if previous row state applied over currently computed combination yields the output row. If yes, save the calculated state and proceed to next. And any simulation that follows a sequence of steps can be undone by repeating the negation of steps in reverse order. eg: consider the sequence <s1:f1, s2:f2, s3:f3> and result is Y. So, to reverse the execution start from <s3:f’3, s2:f’2, s1:f’1> where f’ denotes the complement function. The time complexity of the algorithm is O(N^2*2^N). Above approach, reverting the operation performed in linear time is discussed in below code.
Code
public String[] makeProgram_2(String[] output) {
int column = output[0].length();
int row = output.length;
for (int i = row - 2; i >= 0; i--) {
char[] outputV = output[i + 1].toCharArray();
for (int j = column - 2; j >= 0; j--) {
char a, b;
a = output[i].charAt(j);
b = output[i].charAt(j + 1);
if ((a == 'W' && b == 'B')) {
if (outputV[j] == 'B' || outputV[j + 1] == 'B')
return new String[0];
outputV[j] = '?';
outputV[j + 1] = '?';
} else if (a == 'B' && b == 'B') {
char t = outputV[j];
outputV[j] = outputV[j + 1];
outputV[j + 1] = t;
} else if (a == 'B' && b == 'W') {
if (outputV[j] == 'W' || outputV[j + 1] == 'W')
return new String[0];
outputV[j] = '?';
outputV[j + 1] = '?';
}
}
for (int j = 0; j < column; j++)
if (outputV[j] == '?')
outputV[j] = 'B';
output[i + 1] = String.valueOf(outputV);
}
return output;
}
public String simulateAlgorithm(String rowAction, String current) {
char[] result = current.toCharArray();
for (int i = 0; i < rowAction.length() - 1; i++) {
char A = rowAction.charAt(i);
char B = rowAction.charAt(i + 1);
if (A == 'W' && B == 'W') {
} else if (A == 'W' && B == 'B') {
result[i] = result[i + 1] = 'W';
} else if (A == 'B' && B == 'W') {
result[i] = result[i + 1] = 'B';
} else {
char temp = result[i];
result[i] = result[i + 1];
result[i + 1] = temp;
}
}
return String.valueOf(result);
}
public String[] makeProgram(String[] output) {
int len = output.length;
int w = output[0].length();
for (int i = len - 1; i > 0; i--) {
int j = 0;
for (; j < (1 << w); j++) {
char[] possibleSet = new char[w];
for (int k = 0; k < w; k++) {
if ((j & (1 << k)) > 0)
possibleSet[w - k - 1] = 'W';
else
possibleSet[w - k - 1] = 'B';
}
String possibleString = String.valueOf(possibleSet);
String getAnswer = simulateAlgorithm(output[i - 1], possibleString);
if (getAnswer.equals(output[i])) {
output[i] = possibleString;
break;
}
}
if (j == (1 << w))
return new String[0];
}
return output;
}