I started the Emma’s Supercomputer HackerRank problem last week. This problem is also known as Two Pluses. Last week I got quite busy so I did not have time until this morning to complete the solution for the problem. Last Wednesday I was able to get my code to pass 20 of 23 test cases. I figured out what I could do to pass the last three, but until this morning I had no time.
The problem is ranked Medium difficulty, but I spent time like it was more difficult than that. Read the description in the HackerRank web site. The description is straight forward. I understood what the idea was with the plus signs, but from there to implement a solution that is a different story.
My idea was to come up with all the different plus signs of at least 5 units in 
size that we could draw in the 15 x 15 grid and then check for all combinations that do not overlap (brute force) until we get the two largest plus signs.
I tried different things, some of them in different order, but I was looking for a clean and elegant solution. In this case chances are that I will not revisit this code unless someone mentions an issue that was not detected by the test cases. But in practice (at work) I like to develop code that is easy for me and others to understand. This specially holds true if a long time passes between implementation and maintenance.
5 6 GGGGGG GBBBGB GGGGGG GGBBGB GGGGGG 5 6 6 BGBBGB GGGGGG BGBBGB GGGGGG BGBBGB BGBBGB 25 7 7 GBGBGGB GBGBGGB GBGBGGB GGGGGGG GGGGGGG GBGBGGB GBGBGGB 45 8 8 GGGGGGGG GBGBGGBG GBGBGGBG GGGGGGGG GBGBGGBG GGGGGGGG GBGBGGBG GGGGGGGG 81 6 7 GGGGGGG BGBBBBG BGBBBBG GGGGGGG GGGGGGG BGBBBBG 5
The test cases that I left are the ones provided by HackerRank or the ones that I purchased for 5 hackos. I typically do not purchase test cases but like I mentioned this problem seemed to be screaming “brute force”. Hopefully after you see the solution you will like it.
// **** open scanner ****
private static final Scanner scanner = new Scanner(System.in);
/*
* Test scaffolding.
*/
public static void main(String[] args) throws IOException {
// **** ****
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** read n and m ****
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
// int m = Integer.parseInt(nm[1]);
// **** read matrix ****
String[] grid = new String[n];
for (int i = 0; i < n; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}
// **** generate result ****
int result = twoPluses(grid);
// **** write result ****
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
// **** close buffered writter ****
bufferedWriter.close();
// **** close scanner ****
scanner.close();
}
The test scaffolding is provided by HackerRank. I like to understand and comment it to make sure I do not go on a tangent and loose time working on a solution. In this case we read the row and column dimensions for a grid followed by the grid contents. The grid holds a letter ‘G’ for places we can use to draw a plus sign and a letter ‘B’ for places we cannot use. Note that once a plus sign is selected, its grid locations cannot be shared with any other plus sign.
/*
* Complete the twoPluses function below.
*/
static int twoPluses(String[] grid) {
// **** instantiate array list to hold all plus signs ****
ArrayList<PlusSign> al = new ArrayList<PlusSign>();
// **** ****
int result = 1;
// **** ****
int R = grid.length;
int C = grid[0].length();
// **** create a fresh map ****
char[][] map = freshMap(grid);
// **** populate array list with all plus signs ****
for (int c = 1; c < (C - 1); c++) {
for (int r = 1; r < (R - 1); r++) { // **** compute plus sign at the specified location (y = row, x = column) **** int size = plusSize(map, r, c); // **** loop instantiating and adding plus signs to the array based on (r,c) while (size >= 5) {
// ***** instantiate a new plus sign ****
PlusSign plusSign = new PlusSign(r, c, size);
// **** add plus sign to the array list ****
al.add(plusSign);
// **** decrement size ****
size -= 4;
}
}
}
// **** check the number of plus signs ****
switch (al.size()) {
case 0:
return 1;
case 1:
return al.get(0).size;
default:
// **** continue ****
break;
}
// **** loop finding non-overlaping areas ****
for (int i = 0; i < (al.size() - 1); i++) {
for (int j = (i + 1); j < al.size(); j++) {
// **** refresh the map ****
map = freshMap(grid);
// **** determine if these plus signs overlap ****
boolean overlap = al.get(i).overlap(map, al.get(j));
if (!overlap) {
// **** check and update result ****
if (result < al.get(i).size * al.get(j).size) { result = al.get(i).size * al.get(j).size; } } } } // **** update result (if needed) **** if (al.size() == 1) { result = al.get(0).size; } // **** update result (if needed) **** if ((result == 1) && (al.size() == 2)) { if (al.get(0).size >= al.get(1).size) {
result = al.get(0).size;
} else {
result = al.get(1).size;
}
}
// **** return result ****
return result;
}
This is the function that implements the core of the problem. You need to define your approach and then provide support for it.
We define an ArrayList to hold all the plus signs that we can draw in the specified grid. As we further see the solution, the key is to list all possible plus signs. As a hint, if you find a plus sign of size 9 at a specified location, we should also consider the plus sign at the same location with size 5. This is the most important hint. Some of the test cases may require for you to use a smaller plus sign centered in the same coordinates.
We then create a fresh map implemented as a two dimensional character array. Will use the map to check where we can draw plus signs. When we draw a plus sign we need to make sure we do not draw others that overlap. We will have to flag each used coordinate.
We now loop through all coordinates in the map checking if we can draw a plus sign centered at each location. Since we are interested in plus signs with at least a size of 5, we can safely skip all coordinates on the edge of the map (e.g., (0,0), (0,1), … (1, 0), (2,0), …) since they can only hold a plus sign of size 1 which is just a square (not a plus sign).
The plusSize() function will determine the largest plus sign we can draw at a specified coordinate. Once that is done we enter a while loop to add the largest plus sign and any other valid smaller plus sign at the specified coordinate.
There are some end conditions and this is where we check them. If we do not find a plus sign, then we return a 1. If we found a single plus sign, we cannot multiply its size with another so we return the size of the plus sign. If more than one plus sign is found we need to search for the two largest so we can multiply their sizes.
We now loop through making all possible combinations of plus signs and determining if they overlap. If they do not, we pick up the largest and update the result.
Once we have processed all plus signs, we need to check if we only have a single plus sign. If we just have a single plus sign and we can only produce smaller ones in the same coordinate, they will all overlap so they would not be of use. I believe this is a leftover check from the development process. We should probably remove it but at this time I will leave it as is.
We update the result and return it.
/*
* Create a fresh map. It only contains 'G' and 'B' cells. 'B' == bad, 'G' ==
* good, and 'X' == used by plus. Top left side of grid at (0, 0).
*/
static char[][] freshMap(String[] grid) {
// **** grid dimensions ****
int R = grid.length;
int C = grid[0].length();
// **** create map ****
char[][] map = new char[R][C];
// **** initialize map with grid values ****
for (int row = 0; row < R; row++) {
String s = grid[row];
for (int col = 0; col < C; col++) {
map[row][col] = s.charAt(col);
}
}
// **** return map ****
return map;
}
The freshMap() function creates an array similar to the grid which we will use to draw our plus signs. We could have reused it (had to clean it after a loop) or which is probably more complicated directly use the grid. Feel free to experiment with these other approaches to draw plus signs is a virgin canvas.
/*
* Compute and return the size of the largest plus sign at the specified
* location. The contents of the map are NOT updated.
*/
static int plusSize(char[][] map, int r, int c) {
// **** ****
int R = map.length;
int C = map[0].length;
// **** check if this cell is NOT available ****
if (map[r] != 'G') {
return 0;
}
// **** [0] == up, [1] == right, [2] == down and [3] == left ****
int[] span = new int[4];
// **** check up ([0] == up) ****
for (int row = (r - 1); row >= 0; row--) {
if (map[row] == 'G') {
span[0]++;
} else {
break;
}
}
// **** check right ([1] == right) ****
for (int col = c + 1; col < C; col++) {
if (map[r][col] == 'G') {
span[1]++;
} else {
break;
}
}
// **** check down ([2] == down) ****
for (int row = r + 1; row < R; row++) { if (map[row] == 'G') { span[2]++; } else { break; } } // **** check left ([3] == left ) **** for (int col = c - 1; col >= 0; col--) {
if (map[r][col] == 'G') {
span[3]++;
} else {
break;
}
}
// **** compute size from span array (minimum common value) ****
int size = span[0];
for (int i = 0; i < span.length; i++) {
if (span[i] < size) {
size = span[i];
}
}
// **** take into account the four sides and the center (if needed) ****
if (size != 0) {
size *= 4;
size += 1;
}
// **** return the size of the plus sign *****
return size;
}
This function looks for the largest plus sign it can be drawn at a specified coordinate. This is important for the approach I took. Note that this function does not alter the map. If this is the case we do not have to refresh the map on each loop. The twoPluses() function refreshes the map on each pass. Seems like I left it in from previous passes in which I would create the different plus signs and would flag them with an ‘X’. Perhaps that is still the case. We will find out shortly.
/*
* Defines a point used for the plus signs.
*/
class Point {
// **** members ****
int r;
int c;
/*
* Constructor.
*/
public Point(int r, int c) {
this.r = r;
this.c = c;
}
/*
* Return a string for this point. Row is displayed first, then column is
* displayed.
*/
public String toString() {
return "(" + this.r + "," + this.c + ")";
}
}
This class is used to manipulate the plus signs. It is used to represent the center coordinate of a plus sign.
class PlusSign {
// **** members ****
Point c;
int size;
int side;
int arm;
/*
* Constructor.
*/
public PlusSign(int r, int c, int size) {
// **** center of plus sign ****
this.c = new Point(r, c);
// **** size of plus sign (1, 5, 9, 13, ...) ****
this.size = size;
// **** side of plus sign (1, 3, 5, 7, ...) ****
this.side = (size / 2) + 1;
// **** arm of plus sign (0, 1, 2, 3, ...) ****
this.arm = (size - 1) / 4;
}
/*
* Draw the plus sign on the map. Returns true is plus sign can be drawn;
* otherwise returns false.
*/
public boolean draw(char[][] map) {
// **** draw center (if possible) ****
if (map[this.c.r][this.c.c] == 'G') {
map[this.c.r][this.c.c] = 'X';
} else {
return false;
}
// **** draw up (if possible) ****
for (int row = this.c.r - 1; row >= this.c.r - this.arm; row--) {
if (map[row][this.c.c] == 'G') {
map[row][this.c.c] = 'X';
} else {
return false;
}
}
// **** draw right (if possible) ****
for (int col = this.c.c + 1; col <= this.c.c + this.arm; col++) {
if (map[this.c.r][col] == 'G') {
map[this.c.r][col] = 'X';
} else {
return false;
}
}
// **** draw down (if possible) ****
for (int row = this.c.r + 1; row <= this.c.r + this.arm; row++) { if (map[row][this.c.c] == 'G') { map[row][this.c.c] = 'X'; } else { return false; } } // **** draw left (if possible) **** for (int col = this.c.c - 1; col >= this.c.c - this.arm; col--) {
if (map[this.c.r][col] == 'G') {
map[this.c.r][col] = 'X';
} else {
return false;
}
}
// **** able to draw plus sign ****
return true;
}
/*
* Determine if the specified plus sign overlaps this plus sign.
*/
public boolean overlap(char[][] map, PlusSign ps) {
// **** draw this plus sign ****
boolean drawn = this.draw(map);
// **** draw plus sign ****
drawn = ps.draw(map);
// **** inform caller if plus signs overlap ****
return !drawn;
}
/*
* Generate a string with the contents of the specified plus sign.
*/
public String toString() {
// **** ****
StringBuilder sb = new StringBuilder();
// **** ****
sb.append(" c: " + this.c.toString());
sb.append(" size: " + this.size);
sb.append(" side: " + this.side);
sb.append(" arm: " + this.arm);
// **** ****
return sb.toString();
}
}
The plus signs are defined by the coordinate of the center point and the size. For ease of use I added the other two members (size and arm). Not sure if they are used in the current implementation. If this would be production code I would have to check and remove all unused variables, members, functions and method.
The draw() method seems to alter the contents of the map. This implies that we need to refresh the map when starting a new loop.
The overlap() function determines if two plus signs overlap.
The toString() method was used for debugging. I would leave it for future maintenance operations. Perhaps we should just add a note to the comments in the description.
Hope you liked this solution. I always recommend trying to solve the problem and do not look at any other solution until you have a working model. You can always update to make it better.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa