Implement 2048 Board Tilts in Four Directions with Merging and Game-Over Detection

You are implementing the move logic of the sliding-tile game 2048. The board is a 4 x 4 grid. Each cell is either empty, written `0`, or holds a tile whose value is a power of two (`2`, `4`, `8`, ...). A swipe (the "tilt") in one of four directions (up, down, left or right) slides every tile as far as it can go in that direction and collapses the board: when two tiles with the same value meet, they merge into one tile holding their sum. This is the game itself, not a puzzle about the number 2048, and it has several edge cases. Build it in the order of the parts below. The interviewer's follow-up was how to tell that the game is over. ### Constraints and Clarifications - The board is 4 x 4, given as a list of rows with row `0` at the top. - Spawning a new random tile after each move belongs to the game loop, not to the tilt itself. Keep the tilt deterministic so it can be unit tested. - You may return a new board or update the board in place, but say which. ### Clarifying Questions - When three or four equal tiles sit in one line, which pair merges first? - Can a tile that was just created by a merge merge again during the same swipe? - Should the tilt report whether it changed anything, so the caller knows whether to spawn a tile? - Does reaching the 2048 tile end the game, or does play continue? ### Part 1 — Tilt in one direction Implement the left swipe for the whole board. Walk the rows `[2, 2, 2, 0]`, `[2, 2, 2, 2]`, `[4, 4, 8, 0]` and `[2, 0, 0, 2]` through your code and state its complexity. ```hint One line is enough A left swipe never moves a tile out of its row. Solve one row as a plain list first, then decide what your merge pass must remember so that a tile never takes part in two merges. ``` #### What This Part Should Cover - Sliding across gaps as well as merging adjacent equal tiles - The merge-once rule and the merge order for three or four equal tiles - Producing a row of the same length, padded with empty cells ### Part 2 — All four directions Extend the solution to right, up and down swipes. Aim for a design in which the other three directions reuse the first instead of copying it. ```hint Reuse the line solver A right swipe on a row behaves like a left swipe on the same row read backwards. Ask which sequence of cells a column swipe reads, and in which order. ``` #### What This Part Should Cover - One line-merging routine shared by all four directions - Correct merge priority for right and down swipes - Detecting whether a swipe changed the board at all ### Part 3 — Game over Follow-up: how do you decide that the game is over? Implement the check and say when the game loop should call it. ```hint What a dead board looks like The game ends when no swipe in any direction would change the board. Work out which local conditions let some swipe change it. ``` #### What This Part Should Cover - The exact game-over condition, not just "the board is full" - An efficient check that does not need to simulate every swipe, or a justified choice to simulate - Where the check belongs relative to spawning the next tile ### What a Strong Answer Covers - Merge semantics stated before coding and checked against the tricky rows - Code that handles all four directions without four copies of the logic - A game-over rule that accounts for a full board that still has a legal merge - Small, explicit test cases for the edge cases - Correct complexity for a tilt and for the game-over check ### Follow-up Questions - How would you add tile spawning while keeping the game testable, for example with an injectable random source? - How would you track the score, which in the real game grows by the value of every merged tile? - What changes if the board is `n x n` instead of 4 x 4? - How would you support undoing the last move?