🔗 Crane Claw Machine Game

Jordy, a game developer, wants to make a crane claw machine into a mobile game. To make the game more fun, Jordy plans to reflect the following screen layout and rules in the game logic.

The game screen is an "N x N" square grid made up of "1 x 1" sized cells, with a crane at the top and a basket to the right. (The picture above is an example of "5 x 5" size). Each grid cell contains one of various dolls, and cells without a doll are empty. Every doll occupies a single "1 x 1" grid cell, and dolls are stacked up from the bottom of the grid. The game user can move the crane left and right, and pick up the topmost doll at wherever it stops. Picked-up dolls are stacked in the basket, starting from the bottom of the basket. The following picture shows the result of picking up dolls in order from positions [1, 5, 3] and putting them into the basket.

If two dolls of the same shape end up stacked consecutively in the basket, both dolls burst and disappear from the basket. Continuing from the state above, if you then pick up a doll from position [5] and stack it in the basket, the two dolls of the same shape disappear.

When the crane operates, there's never a case where no doll gets picked up, but if the crane operates at a position with no doll, nothing happens. Also, assume the basket is large enough to hold every doll. (In the picture, it's shown with only 5 cells due to display constraints)

Given a 2D array board containing the state of the game screen's grid, and an array moves containing the positions where the crane was operated to pick up dolls, as parameters, complete the solution function so that it returns the number of dolls that burst and disappeared after all crane operations.

• The board array is a 2D array with a size between "5 x 5" and "30 x 30" inclusive.
• Each cell of board contains an integer between 0 and 100 inclusive.
  • 0 represents an empty cell.
  • Each number from 1 to 100 represents a different doll shape, and the same number represents dolls of the same shape.
• The size of the moves array is between 1 and 1,000 inclusive.
• Each element of the moves array is a natural number between 1 and the width of the board array inclusive.

Input/Output Example #1

The initial state of the dolls matches the example given in the problem. After the crane picks up dolls in order from positions [1, 5, 3, 5, 1, 2, 1, 4] and moves them into the basket, the state is as shown in the picture below, and 4 dolls burst and disappeared during the process of placing them in the basket.

1. Pick a doll. If there's no doll at that position, pick nothing.
2. Put the picked doll into the basket.
3. If the doll just picked is the same as the last doll picked, remove both.
4. Count the number of removed dolls. (+2 per removal operation)

Note that it's not the count of removal operations, but the count of removed dolls. Note that they're removed in pairs.

As the crane moves, put dolls in one at a time. We need an array to hold them, and a resizable array like ArrayList seems appropriate. Since the computation is done with the most recently added data, I'd like to make full use of Stack's characteristics.

JAVA
for (int move : moves)
{
	int j = move - 1;
	
	for (int i = 0; i < board.length; i++)
	{
		// If a doll is picked
		if (board[i][j] > 0)
		{
			// Operation
		}
	}
}

That's the operation for picking a doll. Based on column j, move down row by row and check whether board[i][j] > 0.

Remove that doll from board and push the doll onto the stack. At this point, if the last doll on the stack is the same as the picked doll, remove the last doll from the stack and add to the count of removed dolls.

If the dolls are different, don't remove anything—just push the doll onto the stack.

Looking at the problem, it's easy to think "couldn't we just pick all the dolls first and do the removal all at once at the end?", but actually approaching it this way is harder.

If you remove them all at once later, the moment a doll is removed there's a chance other dolls become adjacent, so you'd need to repeat the computation until there are no more adjacent dolls left.

For example, for 1 3 2 2 3, removing the adjacent 2s results in 1 3 3. Since removing the 2s causes the 3s to become adjacent, repeated computation becomes necessary.

JAVA
import java.util.Stack;

/**
 * Crane Claw Machine Game class
 *
 * @author RWB
 * @since 2021.12.09 Thu 21:40:58
 */
class Solution
{
	private final Stack<Integer> bag = new Stack<>();
	
	/**
	 * Method that returns the answer
	 *
	 * @param board: [int[][]] The board size
	 * @param moves: [int[]] The crane operation positions
	 *
	 * @return [int] The answer
	 */
	public int solution(int[][] board, int[] moves)
	{
		int answer = 0;
		
		for (int move : moves)
		{
			int j = move - 1;
			
			for (int i = 0; i < board.length; i++)
			{
				// If a doll is picked
				if (board[i][j] > 0)
				{
					// If there's a picked doll already, and the last doll matches the one just picked
					if (!bag.isEmpty() && bag.peek() == board[i][j])
					{
						bag.pop();
						
						answer += 2;
					}
					
					// If not
					else
					{
						bag.push(board[i][j]);
					}
					
					board[i][j] = 0;
					
					break;
				}
			}
		}
		
		return answer;
	}
}