HackerRank Java 1D Array (Part 2)

Don't be misled by its puzzling name, this fun little HackerRank problem has its main interest not in its implementation language (I should admit that I designed it thinking more pythonesquely than javaly) nor in the use of the array data structure, but in the algorithm you should think to solve it.

There is a one dimensional board. Each cell in it could be set to zero or one. At startup the pawn is placed on the first cell to the left, and its job is going out to the right. It could be moved only on zero cells moving forward by 1 or 'leap' positions, and backward just by one.

Having specified the zeros and ones on the board, and the value of leap (non negative and not bigger than the board size), can we say if the game could be won?

It looks to me that Dynamic Programming is the a good approach to be used here. The problem splits naturally in a series of simple steps, that contribute to the requested solution. There's one issue that muddies the water, the backward move. The rest of the algorithm is pretty straightforward. Start from the last cell in the board. Determine if a pawn could be placed there and if this would lead to a win. Move to the next one of its left, up to the leftmost one. Then return the win condition for the first cell.

I implemented my idea in this way using, as required, Java as implementation language.

Firstly, I create a cache to store all the intermediate values:
boolean[] memo = new boolean[game.length];
if (game[game.length - 1] == 0)
    memo[memo.length - 1] = true;
They are all initialized to false, but the last one, and only if a pawn could go there.

Having set this initial condition, I could loop on all the other elements.
for (int i = memo.length - 2; i >= 0; i--) {
    // ... see below
}

return memo[0];
In the end, the first cell of my cache would contain the solution.

Each cell in the board is set to true if one of these conditions holds:
if (game[i] == 0 && (i + leap >= game.length || memo[i + 1] || memo[i + leap])) {
    memo[i] = true;
    // ... see below
}
First thing, check the current value in the board. If it is not zero, I can't put the pawn there, so there is nothing to do, the cache value surely stays set to false.
Otherwise, one of the following three conditions lead to true in cache:
- adding the current position to the leap value pushes the pawn out of the board
- the next cell in the board is a good one
- the next leap cell is a good one.

Now the funny part. When I set to true a cell, I should ensure that a few cells to the right are marked as good, too. This is due to the backward move. It is a sort of domino effect, that should stop when we find a cell where our pawn can't go.
for (int j = i + 1; j < memo.length && game[j] == 0; j++)
    memo[j] = true;
Full Java code and test case pushed on GitHub.

No comments:

Post a Comment