2048 Game: Slide and Merge Tiles on a 4x4 Board in Any of Four Directions
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
In the sliding-tile game 2048, a fixed 4 x 4 board holds numbered tiles. A move pushes the board in one of four directions: every tile slides as far as it can in that direction, and two tiles with the same value that collide merge into one tile holding their sum.
Implement a single move: given the board and a direction, return the board after the move. This function covers the move only. The full game would then add a random new tile, but that step is not part of this task, so no new tile appears in your output. The interviewer expected you to run your own tests, so check all four directions, not just the examples below.
### Function Signature
```python
def apply_move(board: list[list[int]], direction: str) -> list[list[int]]:
```
`board[r][c]` is the tile at row `r` and column `c`, or `0` if that cell is empty. `direction` is one of `"up"`, `"down"`, `"left"` and `"right"`.
### Rules
- Row `0` is the top row and column `0` is the leftmost column. `"left"` moves tiles toward column `0`, `"right"` toward column `3`, `"up"` toward row `0` and `"down"` toward row `3`.
- Each row (for `"left"` and `"right"`) or each column (for `"up"` and `"down"`) is processed independently. Call it a line, and call the end of the line that the tiles move toward its front.
- Take the line's nonzero tiles in order starting from the front, ignoring empty cells, and walk through them from the front. If the current tile and the next one have the same value, they merge into one tile whose value is their sum, and the walk continues after both. Otherwise the current tile stays as it is, and the walk continues with the next tile.
- A tile produced by a merge never merges again in the same move. For example, the line `[4, 4, 8, 0]` moved left becomes `[8, 8, 0, 0]`, not `[16, 0, 0, 0]`.
- When three equal tiles are in a line, the pair closest to the front merges: `[2, 2, 2, 0]` moved left becomes `[4, 2, 0, 0]`, and moved right becomes `[0, 0, 2, 4]`.
- The resulting tiles fill the line from the front with no gaps, in the order produced; the remaining cells of the line are `0`.
- If no tile can slide or merge, the board is unchanged. Return the result as a 4 x 4 list of lists.
### Constraints
- `board` has exactly 4 rows and 4 columns.
- Every cell is `0` or a power of two from `2` to `65536` inclusive, so every value in the output is at most `131072`.
- `direction` is exactly one of `"up"`, `"down"`, `"left"` and `"right"`.
- The board may be empty (all zeros) or completely full.
### Examples
**Example 1**
```text
Input: board = [[2, 2, 2, 2],
[0, 4, 4, 8],
[2, 0, 2, 0],
[8, 8, 16, 0]], direction = "left"
Output: [[4, 4, 0, 0],
[8, 8, 0, 0],
[4, 0, 0, 0],
[16, 16, 0, 0]]
```
Row 0: the two pairs merge separately into `4, 4`. Row 1: the two `4`s merge into `8`, and that new `8` does not merge with the existing `8`. Row 2: the empty cell between the two `2`s is ignored, so they merge into `4`. Row 3: the two `8`s merge into `16`, which does not merge again with the existing `16`.
**Example 2**
```text
Input: board = [[2, 0, 4, 2],
[2, 4, 4, 0],
[2, 0, 0, 2],
[0, 4, 8, 4]], direction = "up"
Output: [[4, 8, 8, 4],
[2, 0, 8, 4],
[0, 0, 0, 0],
[0, 0, 0, 0]]
```
Column 0 holds three `2`s: the two nearest the top merge into `4`, and the third ends directly below it. Column 1: the two `4`s merge into `8`. Column 2: the two `4`s merge into `8`, and the `8` from the bottom slides up below it. Column 3: the two `2`s merge into `4`, and the `4` from the bottom slides up below it.
**Example 3**
```text
Input: board = [[2, 0, 4, 2],
[2, 4, 4, 0],
[2, 0, 0, 2],
[0, 4, 8, 4]], direction = "down"
Output: [[0, 0, 0, 0],
[0, 0, 0, 0],
[2, 0, 8, 4],
[4, 8, 8, 4]]
```
The same board moved down. In column 0 the two `2`s nearest the bottom merge, so the `4` lands in row 3 and the remaining `2` sits above it. Column 1: the two `4`s merge into `8` in row 3. Column 2: the `8` is already at the bottom and stays, and the two `4`s merge into an `8` above it. Column 3: the `4` stays at the bottom, and the two `2`s merge into a `4` above it.
Overview: A coding question based on the 2048 sliding-tile game: given a fixed 4x4 board and one of four directions, return the board after every tile slides and equal tiles merge. It tests careful simulation, the merge-once and merge-order rules, handling all four directions with shared logic, and thorough self-testing.
In the sliding-tile game 2048, a fixed 4 x 4 board holds numbered tiles. A move pushes the board in one of four directions: every tile slides as far as it can in that direction, and two tiles with the same value that collide merge into one tile holding their sum.
Implement `apply_move(board, direction)`, which performs a single move and returns the board after the move. Only the move is in scope: the full game would then add a random new tile, but that step is not part of this task, so no new tile appears in your output.
`board[r][c]` is the tile at row `r` and column `c`, or `0` if that cell is empty. `direction` is one of `"up"`, `"down"`, `"left"` and `"right"`.
### Rules
- Row `0` is the top row and column `0` is the leftmost column. `"left"` moves tiles toward column `0`, `"right"` toward column `3`, `"up"` toward row `0` and `"down"` toward row `3`.
- Each row (for `"left"` and `"right"`) or each column (for `"up"` and `"down"`) is processed independently. Call it a line, and call the end of the line that the tiles move toward its front.
- Take the line's nonzero tiles in order starting from the front, ignoring empty cells, and walk through them from the front. If the current tile and the next one have the same value, they merge into one tile whose value is their sum, and the walk continues after both. Otherwise the current tile stays as it is, and the walk continues with the next tile.
- A tile produced by a merge never merges again in the same move. For example, the line `[4, 4, 8, 0]` moved left becomes `[8, 8, 0, 0]`, not `[16, 0, 0, 0]`.
- When three equal tiles are in a line, the pair closest to the front merges: `[2, 2, 2, 0]` moved left becomes `[4, 2, 0, 0]`, and moved right becomes `[0, 0, 2, 4]`.
- The resulting tiles fill the line from the front with no gaps, in the order produced; the remaining cells of the line are `0`.
- If no tile can slide or merge, the board is unchanged.
Return the result as a 4 x 4 list of lists, indexed the same way as `board`.
### Constraints
- `board` has exactly 4 rows and 4 columns.
- Every cell is `0` or a power of two from `2` to `65536` inclusive, so every value in the output is at most `131072`. Every value therefore fits in a signed 32-bit integer.
- `direction` is exactly one of `"up"`, `"down"`, `"left"` and `"right"`.
- The board may be empty (all zeros) or completely full.
### Example 1
```text
Input: board = [[2, 2, 2, 2],
[0, 4, 4, 8],
[2, 0, 2, 0],
[8, 8, 16, 0]], direction = "left"
Output: [[4, 4, 0, 0],
[8, 8, 0, 0],
[4, 0, 0, 0],
[16, 16, 0, 0]]
```
Row 0: the two pairs merge separately into `4, 4`. Row 1: the two `4`s merge into `8`, and that new `8` does not merge with the existing `8`. Row 2: the empty cell between the two `2`s is ignored, so they merge into `4`. Row 3: the two `8`s merge into `16`, which does not merge again with the existing `16`.
### Example 2
```text
Input: board = [[2, 0, 4, 2],
[2, 4, 4, 0],
[2, 0, 0, 2],
[0, 4, 8, 4]], direction = "up"
Output: [[4, 8, 8, 4],
[2, 0, 8, 4],
[0, 0, 0, 0],
[0, 0, 0, 0]]
```
Column 0 holds three `2`s: the two nearest the top merge into `4`, and the third ends directly below it. Column 1: the two `4`s merge into `8`. Column 2: the two `4`s merge into `8`, and the `8` from the bottom slides up below it. Column 3: the two `2`s merge into `4`, and the `4` from the bottom slides up below it.
Constraints
- `board` has exactly 4 rows and 4 columns.
- Every cell is `0` or a power of two from `2` to `65536` inclusive, so every value in the output is at most `131072` (every value fits in a signed 32-bit integer).
- `direction` is exactly one of `"up"`, `"down"`, `"left"` and `"right"`.
- The board may be empty (all zeros) or completely full.
Examples
Input: ([[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 'left')
Expected Output: [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Explanation: All-zero board: nothing slides or merges, so it is returned unchanged.
Input: ([[0, 0, 0, 0], [0, 0, 8, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 'left')
Expected Output: [[0, 0, 0, 0], [8, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Explanation: Single tile at row 1, column 2 slides left to column 0.
Hints
- Every row or column behaves the same way once you read it starting from the end the tiles move toward, so think about how to turn each direction into that one shared case.
- Empty cells never stop a merge, so it helps to look only at the nonzero tiles of a line, in order from the front.
- Remember that a tile created by a merge cannot take part in another merge during the same move.