Implement the core movement logic for the **2048** game. You are given an `n x n` integer board where `0` represents an empty cell and every nonzero value represents a tile. Implement a method such as `move(direction)` that updates the board **in place** after a single move in one of four directions: `up`, `down`, `left`, or `right`. The rules for one move are: - All tiles slide as far as possible in the chosen direction (no gaps remain between a tile and the wall or the tiles ahead of it). - Two adjacent tiles with the **same** value merge into one tile of double the value. - A tile may participate in **at most one merge** per move. - After sliding and merging, the remaining cells are filled with `0`. - You do **not** need to implement the UI or scoring. If random new-tile spawning is needed, keep it **separate** from the deterministic movement logic so the move can be unit-tested. Worked examples for a `left` move on a single row (the leading edge is the left wall): - `[2, 0, 2, 0] -> [4, 0, 0, 0]` - `[2, 2, 2, 0] -> [4, 2, 0, 0]` - `[2, 2, 2, 2] -> [4, 4, 0, 0]` - `[4, 4, 2, 2] -> [8, 4, 0, 0]` - `[2, 0, 0, 2] -> [4, 0, 0, 0]` ```hint Decompose the problem Notice that a move in any direction is the **same one-dimensional operation applied to each row or column**. Solve "collapse one line toward index 0" once, then reuse it for all four directions by transforming the board so the chosen direction becomes "left". ``` ```hint The 1-D collapse For a single line, do it in two passes to avoid double-merging: (1) drop all zeros so nonzero values are packed to the front, then (2) scan left to right and merge `line[i] == line[i+1]` into `2*line[i]`, advancing past both. A "skip the next index after a merge" flag is what enforces *at most one merge per tile per move*. ``` ```hint Reusing one line function for four directions `left` is the line function directly. `right` is the line function applied to each **reversed** row (then reverse back). `up`/`down` apply it to **columns** — transpose the board, run the row logic, transpose back (reverse rows too for `down`). This keeps merge correctness in exactly one place. ``` ### Constraints & Assumptions - The board is square, `n x n`, with `n` typically small (e.g. `4`), but your solution should work for any `n >= 1`. - Tile values are positive powers of two; `0` denotes empty. - The board can have up to `n*n` tiles; aim for `O(n^2)` time and `O(n)` or `O(1)` extra space per move. - `move` mutates the board in place (or you may return the new board — state your choice). Spawning a new random tile after a move is out of scope for the deterministic logic. ### Clarifying Questions to Ask - Should `move` mutate the board in place, or return a new board and leave the input untouched? - Does the interviewer want `move` to report whether the board actually changed (useful for deciding whether to spawn a new tile)? - Are tile values guaranteed to be powers of two, or can the board contain arbitrary integers (which would only affect merge equality, not the algorithm)? - Is `n` always `4`, or must the solution generalize to arbitrary `n`? - For the merge order on `left`, do tiles merge starting from the leading (wall) edge? (Standard 2048 merges from the direction you push toward, so `[2,2,2]` → `[4,2]`, not `[2,4]`.) ### What a Strong Answer Covers - **One reusable core operation.** Implements the 1-D "collapse toward the wall" once and derives all four directions from it (via reverse / transpose), rather than writing four near-duplicate, bug-prone routines. - **Correct merge semantics.** Two passes (compact, then merge) so that `[2,2,2,2] -> [4,4,...]` and `[2,2,2] -> [4,2]`, and never `[2,2,2,2] -> [8,...]`; each tile merges at most once. - **In-place vs. returned state, and "did it change?"** A clear, stated contract; ideally a boolean signalling whether the move altered the board. - **Separation of concerns.** Deterministic movement is isolated from random tile spawning, making the logic unit-testable. - **Complexity.** `O(n^2)` time, modest extra space, and an awareness that the transpose/reverse approach trades a little copying for far simpler, correct code. - **Edge cases.** Empty board, a full board with no merges, a single row/column, `n = 1`, and a line that is all zeros. ### Follow-up Questions - Implement `isGameOver()`: return `true` when no legal move remains. The board is over when there are **no empty cells** and **no two horizontally- or vertically-adjacent equal tiles**. What is its time complexity, and can you do it without simulating all four moves? - Add a `canMove(direction)` / `hasMoved` signal so the caller knows when to spawn a new tile. How would you implement it cheaply inside `move`? - How would you unit-test the movement logic exhaustively for `n = 4`? What property-based invariants hold (e.g. tile-value sum is conserved except where merges occur, number of nonzero tiles never increases)? - Generalize: suppose tiles could merge in chains of three equal values, or the board were non-square. Which parts of your design stay fixed and which change?