Today is not a nice day in the Twin Cities of Minneapolis and St. Paul. It rained all night long and will continue to do so until late evening. Currently the temperature at 44 F and will continue to drop a few degrees. It is a perfect day to make and bake pizza.
After breakfast I made the dough from scratch. It is important to have quality high gluten flower and yeast. The dough is now sitting in a bowl in the kitchen covered with a towel letting it rise. Apparently we are missing red onions and green peppers. My wife and I will stop by Hy-Vee around noon to get the missing ingredients. We are making thick pepperoni pizzas.
Yesterday my wife and I stopped by my son’s house in the Twin Cities. They 
were celebrating the birthdays of his two sons with family and friends. It was cold and very windy. That said; my son managed to grill hot-dogs and burgers. It was a pleasant afternoon.
The topic for this post is the HackerRank challenge The Bomberman Game. I thought it was interesting and harder that suggested. If interested, read the requirements, and think about how you would approach the solution. Then come back to this post.
It seems that there are four steps. The first two are the initial ones. The last two repeat as long as required by each test case.
I tried different approaches to implement the fuse. It starts with a value of 3 seconds and decrements once per second. During the simulation cycle, two additional events must be taken care of. The Bomberman plants fresh bombs on open grid locations and the bombs need to detonate 3 seconds after they were planted.
The final diagram illustrates what I got out of the requirements:
decrement fuse
plant nothing plant detonate bombs
initial bombs
bombs
0 -------- 1 -------- 2 -------- 3 --------> time in sec
^ v
| |
+----------+
I decide to use char arrays holding the values given the fact that strings are immutable. I used binary values 3, 2, 1, and 0 but later decided to switch to their ASCII representations due to the fact that they were easier to print.
I used the following test case with different counts to test what I considered a solution candidate.
Please disregard the annotations at this time and concentrate on the result for each test.
6 7 0 ....... ...O... ....O.. ....... OO..... OO..... ....... ...O... ....O.. ....... OO..... OO..... 6 7 1 ....... ...O... ....O.. ....... OO..... OO..... ...O... ....O.. ....... OO..... OO..... <=== multiple of 2 6 7 2 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 3 6 7 3 ....... ...O... ....O.. ....... OO..... OO..... OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO <=== multiple of 2 6 7 4 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 5 6 7 5 ....... ...O... ....O.. ....... OO..... OO..... ....... ...O... ....O.. ....... OO..... OO..... <=== multiple of 2 6 7 6 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 3 6 7 7 ....... ...O... ....O.. ....... OO..... OO..... OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO <=== multiple of 2 6 7 8 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 5 6 7 9 ....... ...O... ....O.. ....... OO..... OO..... ....... ...O... ....O.. ....... OO..... OO..... <=== multiple of 2 6 7 10 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 3 6 7 11 ....... ...O... ....O.. ....... OO..... OO..... OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO <=== multiple of 2 6 7 12 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 5 6 7 13 ....... ...O... ....O.. ....... OO..... OO..... ....... ...O... ....O.. ....... OO..... OO..... <=== multiple of 2 6 7 14 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 3 6 7 15 ....... ...O... ....O.. ....... OO..... OO..... OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO <=== multiple of 2 6 7 16 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 5 6 7 17 ....... ...O... ....O.. ....... OO..... OO..... ....... ...O... ....O.. ....... OO..... OO..... <=== multiple of 2 6 7 18 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 3 6 7 19 ....... ...O... ....O.. ....... OO..... OO..... OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO <=== multiple of 2 6 7 20 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 5 6 7 21 ....... ...O... ....O.. ....... OO..... OO..... ....... ...O... ....O.. ....... OO..... OO..... <=== multiple of 2 6 7 22 ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO <=== pattern 3 6 7 23 ....... ...O... ....O.. ....... OO..... OO..... OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO
Some few cases past the first submission but most timed out. I had to optimize the code. After spending some time decided to purchase a test case. I believe it was # 11.
Take a look at the first 3 numbers in this test case:
1 199 181054341 O..OO........O..O........OO.O.OO.OO...O.....OOO...OO.O..OOOOO...O.O..O..O.O..OOO..O..O..O....O...O....O...O..O..O....O.O.O.O.....O.....OOOO..O......O.O.....OOO....OO....OO....O.O...O..OO....OO..O...O
The single string with a length of 199 values had to be updated 181,054,341 one hundred and eighty one million times. That would take a long time so what could be done?
Take a look at the first few results using the sample input and let’s see if we can determine a pattern. The reason for this is the fact that the first two steps are initialization and the rest repeat.
The edited screen capture seems to have a pattern. All even cases for n are grids with ‘O’s. That is easy to figure without having to simulate 181,054,341 seconds. But wait, the problem is that the count is even.
After further looking, it seems that there are two additional repeating patterns. I flagged them a pattern3 and pattern5 respectively. The end of the tunnel seems near.
The number of counts (n) is associated with when these last two patterns appear. After a couple minutes we can figure the following:
3 + 4 + 4 + 4 ... and 5 + 4 + 4 + 4 ...
Now you can see why I named one frequency3 and the other frequency5. We could write some Java code to determine in which case a large value of n falls into. In the additional test case it seems that it falls into test case 5:
<=== pattern 5 6 7 181054341 ....... ...O... ....O.. ....... OO..... OO..... ....... ...O... ....O.. ....... OO..... OO.....
Instead of looping millions of times, we can perform some calculations, generate the first few patters and then jump to the result. The approach is illustrated in the following Java code written using the Eclipse IDE:
/*
* Complete the bomberMan function below.
*/
static String[] bomberMan( int n, // the number of seconds to simulate
String[] grid) { // array of strings that represents the grid
// **** build initial grid of characters ****
char[][] g = initialGrid(grid);
// **** compute the number for the final grid ****
int fg = finalGrid(n);
// **** to save intermediate grids (as needed) ****
char[][] g2 = null;
char[][] g3 = null;
char[][] g5 = null;
// **** set the number of cycles to run ****
int maxCycle = n;
if (n >= 5)
maxCycle = 5;
// ***** run first few cycles in the simulation ****
for (int cycle = 2 ; cycle <= maxCycle; cycle++) {
// **** decrement fuses [1] ****
g = decrementFuses(g);
// **** plant bombs (3 second fuse) [2] ****
if ((cycle % 2) == 0) {
g = plantBombs(g);
}
// **** detonate bombs [3] ****
else {
g = detonateBombs(g);
}
// **** save the grid (as needed) ****
if (cycle == 2) {
g2 = cloneArray(g);
} else if (cycle == 3) {
g3 = cloneArray(g);
} else if (cycle == 5) {
g5 = cloneArray(g);
}
}
// **** replace the grid to return ****
if (fg == 2)
g = g2;
else if (fg == 3)
g = g3;
else if (fg == 5)
g = g5;
// **** generate strings for this grid ****
grid = charToStringArray(g);
// **** return grid of strings ****
return grid;
}
We start by building the initial grid using a two dimensional char array.
As we discussed earlier, we need to determine which final pattern we need to use. The finalGrid() method returns such information.
The next step is to declare placeholders for the 3 patterns we will need. The first one g2 is for even number of cycles, the g3 and g5 hold respectively pattern3 and pattern5.
After determining the number of cycles we need to execute in order to generate set of three patterns (g2, g3 and g5) we run the first few cycles of the simulation.
We decrement the fuse count by one (second), on even number cycles the 
Bomberman plants bombs with fresh fuses and finally on every loop we need to decrement the fuse so the bombs can detonate.
The last few lines in the loop allow us to store the three grids of interest.
Note that we only cycle at most five times. When done with the loop we determine if we use the current grid or one of the saved patterns. After converting the grid of characters into an array of strings we return our solution.
Let’s go briefly over each method in the solution.
/*
* Generate initial grid as char[][]
*/
static char[][] initialGrid(String[] grid) {
// **** ****
int rows = grid.length;
// **** ****
char[][] g = new char[rows][];
// **** ****
for (int r = 0; r < rows; r++) {
// **** replace 'O' with '2' ****
grid[r] = grid[r].replace('O', '2');
// **** convert string to char array ****
g[r] = grid[r].toCharArray();
}
// **** return char array grid ****
return g;
}
This method takes the initial array of strings with ‘.’s and ‘’O’s and returns a two dimensional array of chars with ‘.’s for places without a bomb and ‘2’s for places with a bomb. Note that we use character ‘2’ instead of character ‘3’ because the second step is to delay for one second. We could have started with ‘3’s and then decrement them by one to end up with ‘2’s.
/*
*
*/
static char[][] cloneArray(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** ****
char[][] gc = new char[rows][cols];
// **** ****
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
gc[r] = g[r];
// **** ****
return gc;
}
There are a few ways to clone an array. I tried a couple (e.g., System.arraycopy() and array.clone()) but they did not seem to work like I expected, so I decided to implement this method.
The next method is used to decrement by one the fuse count:
/*
* Decrement fuse count
*/
static char[][] decrementFuses(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** traverse the grid decrementing fuse counts ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// **** ****
if (g[r] == '3')
g[r] = '2';
else if (g[r] == '2')
g[r] = '1';
else if (g[r] == '1')
g[r] = '0';
}
}
// **** ****
return g;
}
The idea is quite simple. Traverse the grid of characters and replace ‘3’ with ‘2’, ‘2’ with ‘1’ and ‘1’ with ‘0’. Like I previously stated I could have used ‘\003’, \002’, ‘\001’ and ‘\000’ but I was displaying the values and preferred to use the ASCII equivalents.
I believe you can just decrement a char value by one, but decided to use if statements instead. If I would have written this code in C / C++ I would have used binary values instead of ASCII.
/*
* Detonate bombs
*/
static char[][] detonateBombs(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** copy the grid ****
char[][] cg = cloneArray(g);
// **** traverse the grid detonating bombs ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) { // **** detonate this bomb **** if (cg[r] == '0') { // **** up **** if (r > 0)
g[r - 1] = '.';
// **** down ****
if (r < rows - 1)
g[r + 1] = '.';
// **** right ****
if (c < cols - 1) g[r] = '.'; // **** left **** if (c > 0)
g[r] = '.';
// **** center ***
g[r] = '.';
}
}
}
// **** returned the cloned grid ****
return g;
}
Note that when a bomb detonates, it destroys the top, right, bottom and left bombs and of course itself. The issue we have is not to disturb other bombs in the vicinity which need to detonate as we traverse the grids. Because of this issue, we need to operate of a copy of the grid.
After a copy of the grid is made, we check for bombs in the original grid, but need to mark its effects in a separate grid. The only location we set to ‘.’ is the location for the bomb that has detonated.
/*
* plant bombs with 3-second fuse
*/
static char[][] plantBombs(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** traverse the grid ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// **** plant bomb (if needed) ****
if (g[r] == '.')
g[r] = '3';
}
}
// **** return updated grid ****
return g;
}
This method plants bombs in all locations in the grid which do not have one. We replace the ‘.’ with a character ‘3’ to indicate a bomb with a full fuse.
/*
* Generate string array from char[][] grid
*/
static String[] charToStringArray(char[][] g) {
// **** number of rows in the grid ****
int rows = g.length;
// **** allocate the string grid ****
String[] grid = new String[rows];
// **** make a copy of the input grid ****
char[][] copy = cloneArray(g);
// **** generate strings for the grid ****
for (int r = 0; r < rows; r++) {
// **** ****
for (int c = 0; c < copy[r].length; c++) { if (copy[r] >= '1' && copy[r] <= '3')
copy[r] = 'O';
else
copy[r] = '.';
}
// **** generate this string ****
grid[r] = new String(copy[r]);
}
// **** return the string grid ****
return grid;
}
This method is used to generate an array of strings from the character array. Note that in order not to disturb the grid, we use a clone.
/*
* Return the number for the final grid
*/
static int finalGrid(int n) {
// ???? ????
System.out.println("finalGrid <<< n: " + n);
// **** ****
if (n <= 5)
return n;
else if (n % 2 == 0)
return 2;
else if ((n - 3) % 4 == 0)
return 3;
else if ((n - 5) % 4 == 0)
return 5;
// **** ****
return -1;
}
This method is used to determine which pattern will be used as a returned value when the simulation ends; otherwise we would have to run all the steps in the simulation which would take too much iteration. Note that the sample input uses 3 seconds.
The entire code for the solution follows:
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
/*
*
*/
public class Solution {
/*
* Generate initial grid as char[][]
*/
static char[][] initialGrid(String[] grid) {
// **** ****
int rows = grid.length;
// **** ****
char[][] g = new char[rows][];
// **** ****
for (int r = 0; r < rows; r++) {
// **** replace 'O' with '2' ****
grid[r] = grid[r].replace('O', '2');
// **** convert string to char array ****
g[r] = grid[r].toCharArray();
}
// **** return char array grid ****
return g;
}
/*
*
*/
static char[][] cloneArray(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** ****
char[][] gc = new char[rows][cols];
// **** ****
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
gc[r] = g[r];
// **** ****
return gc;
}
/*
* Decrement fuse count
*/
static char[][] decrementFuses(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** traverse the grid decrementing fuse counts ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// **** ****
if (g[r] == '3')
g[r] = '2';
else if (g[r] == '2')
g[r] = '1';
else if (g[r] == '1')
g[r] = '0';
}
}
// **** ****
return g;
}
/*
* Detonate bombs
*/
static char[][] detonateBombs(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** copy the grid ****
char[][] cg = cloneArray(g);
// **** traverse the grid detonating bombs ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) { // **** detonate this bomb **** if (cg[r] == '0') { // **** up **** if (r > 0)
g[r - 1] = '.';
// **** down ****
if (r < rows - 1)
g[r + 1] = '.';
// **** right ****
if (c < cols - 1) g[r] = '.'; // **** left **** if (c > 0)
g[r] = '.';
// **** center ***
g[r] = '.';
}
}
}
// **** returned the cloned grid ****
return g;
}
/*
* plant bombs with 3-second fuse
*/
static char[][] plantBombs(char[][] g) {
// **** ****
int rows = g.length;
int cols = g[0].length;
// **** traverse the grid ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// **** plant bomb (if needed) ****
if (g[r] == '.')
g[r] = '3';
}
}
// **** return updated grid ****
return g;
}
/*
* Generate string array from char[][] grid
*/
static String[] charToStringArray(char[][] g) {
// **** number of rows in the grid ****
int rows = g.length;
// **** allocate the string grid ****
String[] grid = new String[rows];
// **** make a copy of the input grid ****
char[][] copy = cloneArray(g);
// **** generate strings for the grid ****
for (int r = 0; r < rows; r++) {
// **** ****
for (int c = 0; c < copy[r].length; c++) { if (copy[r] >= '1' && copy[r] <= '3')
copy[r] = 'O';
else
copy[r] = '.';
}
// **** generate this string ****
grid[r] = new String(copy[r]);
}
// **** return the string grid ****
return grid;
}
/*
* Return the number for the final grid
*/
static int finalGrid(int n) {
// ???? ????
System.out.println("finalGrid <<< n: " + n);
// **** ****
if (n <= 5) return n; else if (n % 2 == 0) return 2; else if ((n - 3) % 4 == 0) return 3; else if ((n - 5) % 4 == 0) return 5; // **** **** return -1; } /* * Complete the bomberMan function below. */ static String[] bomberMan( int n, // the number of seconds to simulate String[] grid) { // array of strings that represents the grid // **** build initial grid of characters **** char[][] g = initialGrid(grid); // **** compute the number for the final grid **** int fg = finalGrid(n); // **** to save intermediate grids (as needed) **** char[][] g2 = null; char[][] g3 = null; char[][] g5 = null; // **** set the number of cycles to run **** int maxCycle = n; if (n >= 5)
maxCycle = 5;
// ***** run first few cycles in the simulation ****
for (int cycle = 2 ; cycle <= maxCycle; cycle++) {
// **** decrement fuses [1] ****
g = decrementFuses(g);
// **** plant bombs (3 second fuse) [2] ****
if ((cycle % 2) == 0) {
g = plantBombs(g);
}
// **** detonate bombs [3] ****
else {
g = detonateBombs(g);
}
// **** save the grid (as needed) ****
if (cycle == 2) {
g2 = cloneArray(g);
} else if (cycle == 3) {
g3 = cloneArray(g);
} else if (cycle == 5) {
g5 = cloneArray(g);
}
}
// **** replace the grid to return ****
if (fg == 2)
g = g2;
else if (fg == 3)
g = g3;
else if (fg == 5)
g = g5;
// **** generate strings for this grid ****
grid = charToStringArray(g);
// **** return grid of strings ****
return grid;
}
private static final Scanner scanner = new Scanner(System.in);
/*
* Edited test scaffolding
*/
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
String[] rcn = scanner.nextLine().split(" ");
int r = Integer.parseInt(rcn[0]);
int c = Integer.parseInt(rcn[1]);
int n = Integer.parseInt(rcn[2]);
String[] grid = new String[r];
for (int i = 0; i < r; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}
// // **** loop a few times to display loops ****
// for (int cycle = 0; cycle <= n; cycle++) {
//
// // ???? ????
// System.out.println("main <<< cycle: " + cycle);
//
// // **** ****
// String[] result = bomberMan(cycle, grid);
String[] result = bomberMan(n, grid);
// **** display string array ****
for (int i = 0; i < result.length; i++) {
bufferedWriter.write(result[i]);
if (i != result.length - 1) {
bufferedWriter.write("\n");
}
}
bufferedWriter.newLine();
// // ???? ????
// bufferedWriter.newLine();
// bufferedWriter.flush();
// }
// **** ****
bufferedWriter.close();
scanner.close();
}
}
Please note that I edited the test scaffolding so it could cycle producing multiple results. Such code has been commented out.
If you are interested in the actual code you can find it in my GitHub repository.
Hope you enjoyed this challenge. I did.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn!
John
Follow me on Twitter: @john_canessa