If we go back to the rules, there is one more thing that needs to be done. In a certain step Bomberman plants bombs in all slots without bombs.
Click to share on Google+ (Opens in new window)
Once I got this test setup I started to implementextractParams.
One possible alternative would be having the function take an extra parameter indicating if it is exploding or not. I decided to leave this way.
An edge test case forexplode(test if explodes correctly not having anything to the top and left):
In my first version I was mistakenly exploding bombs at 1 secondOff by 1 errorsare kinda annoying right?
You are commenting using your Google+ account.(LogOut/Change)
I found a challenge calledThe Bomberman Game on HackerRankand I found it pretty interesting.
Repeat 3 and 4 until N seconds passes
Bomberman plants some bombs (youre given an input with the map)
Breaking down the code in smaller functions that are responsible for specific things makes tasks way easier to accomplish, understand, test and change.
It might look like it is thesameasnextStateAfterExplosion, but it isnt. Because when a explosion happen and the slot is a bomb in 2 seconds it will set the slot to empty (-1) instead of reducing a second from the bomb (element – 1).
The first scenario I implemented was the explosion, so when Im iterating the matrix and find a0the next state of it is an explosion. Thetickfunction doesnt need to know how to explode a bomb, it just has to set the map to a new state. So to handle the explosion I created a function explode.
It boils down to something like this:
Click to share on Reddit (Opens in new window)
I didnt have anyone to make a Code Review before I sent the code, that would probably make me write somethings different to improve my code.
Wait, what? Make it fail? Yes. Making a test fail will help you check that the test is running correctly. Sometimes it is possible to write a test that will always pass (by accident or something) and you will get a false positive.
The first thing I though was to solve it with a generator (well, there was no real need to use it, but since it is about a game I thought it would be fun to be able to access any state of the game).
React: How To a guide byexample
In thetickfunction we can set upyieldafter a single explosion, or second pass for a single bomb:
TypeScript also helped (it always helps). You can avoid a significant amount of issues and time loss while coding just by having your project in TypeScript.
Notify me of new comments via email.
With the tests I created and TypeScript I feel extremely confident to change anything, refactor at will.
This way each step would be an interaction on a single slot, which might help to find problems (since exploding everything and checking the result later might be difficult).
You are commenting using your Twitter account.(LogOut/Change)
View brunolm7s profile on Facebook
Fill in your details below or click an icon to log in:
export function* tick( cols, matrix, rows, seconds : Settings) let turn = 0; let result = [ …matrix.map(row = […row]), ]; let currentSeconds = seconds + 1; while (currentSeconds–) for (let row = 0; row rows; row++) for (let col = 0; col cols; col++) if (result[row][col] === 0) explode(result, col, cols, row, rows ); else if (result[row][col] 0) result[row][col] = nextStateAfterTick(result[row][col]); yield result; // plant bombs if ((turn & 1) === 1) result = [ …result.map(row = row.map(col = col === -1 ? 3 : col)), ]; turn++;
How I solved Bomberman challenge onHackerRank
Workflowy: A tool for storing yourbrain
nextStateAfterTickis a function to get the next state of a empty slot or bomb (that is not exploding).
nextStateAfterExplosionwas created to get the state the slot should be after the explosion.
View brunolm7s profile on Twitter
To find out more, including how to control cookies, see here:Cookie Policy%dbloggers like this:>
Power NVM A Node Version Manager forWindows
Sfrom SOLID stands forSingle responsibilityand I think it was the key to build a nice solution to this challenge.
export function* tick( cols, matrix, rows, seconds : Settings) let result = [ …matrix.map(row = […row]), ]; let currentSeconds = seconds + 1; while (currentSeconds–) for (let row = 0; row rows; row++) for (let col = 0; col cols; col++) if (result[row][col] === 0) explode(result, col, cols, row, rows ); else if (result[row][col] 0) // bomb not ready result[row][col] = nextStateAfterTick(result[row][col]); yield result;
Click to share on Facebook (Opens in new window)
If the neighbor bomb is exploding dont touch it, else clear whatever is in there.
export function processData(input: string) const settings = extractParams(input); const tickGen = tick(settings); let fieldState; // step all the way to the end // as I said, it doesnt make much sense here // but it is fun // we could make a replay of the game with it for (const state of tickGen) fieldState = state; return fieldState;
Drawing is also good to get a better picture of what youre trying to do.
A little disclaimer before showing the code: I implemented it in a way that its easier to implement, understand and is maintainable (not perfect, I could still improve it), I could improve the performance a lot by implementing without a matrix and doing some different things. But in any case it did pass all performance tests either way.
To implement that I had to changetick.
it(returns map with cleared neighbors after explosion, () = const matrix = [ [0, 2], [3, 1], ]; const expected = [ [emptySlot, emptySlot], [emptySlot, 1], ]; explode(matrix, col: 0, cols: 2, row: 0, rows: 2 ); expect(matrix).toEqual(expected); );
export function* tick( cols, matrix, rows, seconds : Settings) let result = [ …matrix.map(row = […row]), ]; let currentSeconds = seconds + 1; while (currentSeconds–) for (let row = 0; row rows; row++) for (let col = 0; col cols; col++) if (result[row][col] === 0) explode(result, col, cols, row, rows ); yield result;
Click to share on Pocket (Opens in new window)
Now the code is handling bombs exploding, bombs not ready, empty slots. Great!
Bombs explode at the same time: I cant clear the position of a bomb that is also exploding, because it is exploding at the same time, so I need to keep it there until I get to it and make it explode
With that I could build a unit test for this function and make it fail.
There are a lot of scenarios to test in this case:
The reason I choose to create a matrix was to be able to simulate the game, so I can know the exact state of the game at any second (for the end goal it doesnt matter to know if a bomb has 1, 2 or 3 seconds, it just matters if a bomb is there or not, but for fun its cool).
describe(nextStateAfterTick, () = it(returns 2 when seconds to explode is 3, () = expect(nextStateAfterTick(3)).toBe(2); ); it(returns 1 when seconds to explode is 2, () = expect(nextStateAfterTick(2)).toBe(1); ); it(returns 0 when seconds to explode is 1, () = expect(nextStateAfterTick(1)).toBe(0); ); it(returns 0 when seconds to explode is 0, () = expect(nextStateAfterTick(0)).toBe(0); ); it(returns emptySlot value when it is an empty slot, () = expect(nextStateAfterTick(emptySlot)).toBe(emptySlot); ); );
View brunolms profile on GitHub
Hint: if you want to find the fastest way possible, try drawing like that.
The challenge calls a function namedprocessDatapassing the input. Theinputparameter is a string and within it there are data you need to extract, so the first thing I did was to create a function to parse the input. This way Imseparating concernsand avoiding theGOD anti-pattern.
This challenge reminded me of2 kyu Binary Genetic Algorithms katathat a friend and I broke into aseries of 5 katas. A really big and complex challenge was broken down into 5 easy ones.
Magic numbers? From Wikipedia: Unique values with unexplained meaning or multiple occurrences which could (preferably) be replaced with named constants
Bombs that are about to go off explode at the same time
export function explode(matrix: Arraynumber[], col, cols, row, rows ) if (col – 1 = 0) matrix[row][col – 1] = nextStateAfterExplosion(matrix[row][col – 1]); if (col + 1 cols) matrix[row][col + 1] = nextStateAfterExplosion(matrix[row][col + 1]); if (row – 1 = 0) matrix[row – 1][col] = nextStateAfterExplosion(matrix[row – 1][col]); if (row + 1 rows) matrix[row + 1][col] = nextStateAfterExplosion(matrix[row + 1][col]); matrix[row][col] = emptySlot;
The funny thing about this is that it also applies to things in life,big problems can be broken down in smaller ones.
if (result[row][col] === 0) explode(result, col, cols, row, rows ); yield result; // here else if (result[row][col] 0) result[row][col] = nextStateAfterTick(result[row][col]); yield result; // here
Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
export function extractParams(input: string): Settings const pieces = input.split(\n); const [rows, cols, seconds] = pieces[0] .split( ) .map(setting = +setting); const matrix = pieces.slice(1) .map(row = row.split().map(e = e === O ? 3 : emptySlot)); return cols, matrix, rows, seconds, // hint: change *something* here for performance ;
You are commenting using your Facebook account.(LogOut/Change)
View brunolms profile on LinkedIn
Bydrawing the board in different stateswe can start to see some patterns. But dont assume that all patterns you see really exist from a single drawing, consider that different scenarios can change the results of what you see in this drawing.
Well, one cool thing about generator function is that you can take a single step and check what is going on.
What couldve been better? I couldve usedsubstringandreplaceinstead of splitting the string and mapping the matrix.
There were few things to watch out when I was implementing the other scenarios:
A second passes. Bomberman plants bombs on all empty slots
I got the first line from the input and extracted the 3 numbers into 3 variables and then converted it from strings to numbers.
At this point I had all the application flow required to make bombs explode. Next I had to go back totickand make a second pass to empty slots and to bombs that were not yet ready to explode.
Workflowy: A tool for storing yourbrain
Boundaries: I shouldnt change a position that doesnt even exist in the matrix (ex: col -1)
export function nextStateAfterTick(element: number) if (element === 0) return element; if (element === emptySlot) return emptySlot; return element – 1;
I made so the function would decrement a second from the total and run some code returning a result each time a second pass.
Click to share on Twitter (Opens in new window)
Blazor: Running C in Frontend(cross-browser)
Step 1: Make the function fail a test.
Click to share on LinkedIn (Opens in new window)
How I solved Bomberman challenge onHackerRank
When a bomb explodes it clears its tile and 1 tile up, down, left, right
Now that I had the parsed parameters I created another function, I called ittick. This is my generator function where each step in it is a second passing.
You are commenting using your account.(LogOut/Change)
I also didnt have, but I like, a Tech Review. Before starting to implement something talk to a teammate about the thing you want to do, you might realize something way before it gets in the Code Review.
Step 2: Test a scenario that doesnt exist then implement it.
By having a function to handlenextStateAfterExplosionwe can test the change of state in there and not have to worry about it here. We can just test with the correct slots were changed and test edge cases.
In theexplodefunction I basically got the map and position where the bomb had to go off. So I started (after the failing test) to test exploding the slot the bomb is in.
And I added tests for all paths on it.
With the map I converted it to a matrix of numbers, replacing bombs with3(3 seconds to explode) and empty slots with-1which I calledemptySlot(no magic numbers).
If a bomb explodes next to another that is not about to go off then the nearby bomb is just cleared
This is how I started my function to parse the input:
Return the map after N seconds have passed.
describe(extractParams, () = it(returns parameters as object, () = const settings = extractParams(sampleInput); ls).toBe(7); expect(settings.matrix).toEqual(expectedMatrix); expect(settings.rows).toBe(6); expect(settings.seconds).toBe(3); ); );
Hey, how did you use typescript in Hackerrank?
Now I had all pieces and I could put them together:
This entry was posted inGeneraland taggedalgorithm,hackerrank,javascript,typescripton
describe(nextState, () = it(returns emptySlot value when seconds to explode is 3, () = expect(nextStateAfterExplosion(3)).toBe(emptySlot); ); it(returns emptySlot value when seconds to explode is 2, () = expect(nextStateAfterExplosion(2)).toBe(emptySlot); ); it(returns emptySlot value when seconds to explode is 1, () = expect(nextStateAfterExplosion(1)).toBe(emptySlot); ); it(returns 0 when seconds to explode is 0, () = expect(nextStateAfterExplosion(0)).toBe(0); ); it(returns emptySlot value when it is an empty slot, () = expect(nextStateAfterExplosion(emptySlot)).toBe(emptySlot); ); );
React: How To a guide byexample