Design 2048

01The design, in the six-step framework

1. Requirements and use cases

2048 looks like a grid exercise, but its real content is one small pure function. Get the slide-and-merge of a single line right, and the four directions, the undo and the tests all follow from it. Most of the bugs candidates write come from coding the merge four times.

• A game starts on a 4×4 board with two random tiles.
• A player moves up, down, left or right; tiles slide as far as they can and equal neighbours merge once.
• Every merge adds the new tile's value to the score.
• A move that changes nothing is ignored: no tile spawns and no turn is used.
• A move that changes the board spawns a new tile: 2 with probability 0.9, otherwise 4.
• The game reports a win on reaching 2048 and a loss when no move can change the board.
• A player can undo a move.

Out of scope: animation, high-score storage, a solver. Constraints: a seeded random source so a game can be replayed; the board size and target must be parameters, not literals; undo must restore the score and the spawned tile, and must not cost a deep copy of anything mutable.

2. Core entities and relationships

• Board: an immutable grid of integers (0 for empty). Every operation returns a new board.
• Direction: an enum of the four moves.
• Spawner: chooses where a new tile goes and what its value is, from an injected random source.
• Rules: a small family of related objects (spawner, win test), so a variant is built in one place.
• Game: the current board, score, status and a history stack.
• Snapshot: a board and a score; the undo record.

The game composes its history. A snapshot only aggregates a board, because immutable boards are safely shared between the current state and any number of snapshots.

3. Interfaces and key methods

import random
from dataclasses import dataclass
from enum import Enum
from typing import Protocol, Tuple

class Direction(Enum):
    LEFT = "left"
    RIGHT = "right"
    UP = "up"
    DOWN = "down"

class Status(Enum):
    PLAYING = "playing"
    WON = "won"
    LOST = "lost"

def slide_line(line: Tuple[int, ...]) -> Tuple[Tuple[int, ...], int]:
    """Slide one line towards index 0 and merge; return the new line and points scored."""

class Spawner(Protocol):
    def spawn(self, board: "Board") -> "Board":
        """Return a board with one new tile on an empty cell."""

class Rules(Protocol):
    def make_spawner(self) -> Spawner: ...
    def has_won(self, board: "Board") -> bool: ...

class Game:
    def move(self, direction: Direction) -> bool:
        """Apply a move; False and no change if the board would not change."""
    def undo(self) -> bool:
        """Restore the previous board and score; False if there is nothing to undo."""

Invariants: a board never changes after it is built; slide_line is pure, and each tile takes part in at most one merge per move; the score equals the sum of merged values; a tile spawns exactly once per board-changing move.

4. Design patterns and the choices behind them

One line function, four directions by transformation

The force: four directions would otherwise mean four nested loops that drift apart. Write the rule once for a line sliding left, and turn the other directions into that case: right is reversed rows, up is the transpose, down is the transpose of reversed rows. This is the key move in modeling boards and grids: pick a canonical orientation and map everything onto it.

The merge rule hides in one word, once. The line [2, 2, 2, 2] becomes [4, 4, 0, 0], not [8, 0, 0, 0]. The line [2, 2, 2, 0] becomes [4, 2, 0, 0], with the merge on the side the tiles move towards. Scanning the compacted tiles and skipping past a merged pair gives both behaviours in a few lines.

An immutable board makes undo free

The force: undo must restore the board, the score and the spawned tile. Because Board is an immutable value object built on tuples, a snapshot is just two references. The usual command pattern stores an inverse operation, but merges cannot be inverted without extra data: a 4 might have been 2 plus 2 or a spawned tile. Storing the prior immutable state is the simplest correct form of the command history here. For a 4×4 board the new tuples per move are cheap.

A family of rule objects

The force: a variant such as a 5×5 board with a target of 4096 and different spawn odds changes several objects at once, and they must stay consistent. A Rules object producing the spawner and answering the win test is a small abstract factory. For two objects this is on the edge of too much; say so, and note a plain constructor argument would serve until a second variant really exists.

Randomness behind a seam

The spawner takes a seeded random source. A test can then use a scripted spawner and assert exact boards, which is the whole of designing for unit tests in this problem. slide_line needs no seam at all, and a table of input and output lines is its entire test suite.

5. Core flow and code

1. Game.move refuses if the game has ended, then calls Board.slide for the direction.
2. slide rotates rows into the canonical form, runs slide_line on each, sums the points, and rotates back.
3. If the new board equals the old one, the move is a no-op and returns False.
4. Otherwise the current board and score go on the history stack, and the score grows.
5. The spawner adds a tile, then the game tests for a win, or a loss if no move can change the board.

def slide_line(line: Tuple[int, ...]) -> Tuple[Tuple[int, ...], int]:
    tiles = [v for v in line if v]
    merged, points, i = [], 0, 0
    while i < len(tiles):
        if i + 1 < len(tiles) and tiles[i] == tiles[i + 1]:
            merged.append(tiles[i] * 2)
            points += tiles[i] * 2
            i += 2                    # both tiles are consumed: one merge per tile
        else:
            merged.append(tiles[i])
            i += 1
    return tuple(merged + [0] * (len(line) - len(merged))), points

@dataclass(frozen=True)
class Board:
    cells: Tuple[Tuple[int, ...], ...]

    @staticmethod
    def empty(size: int = 4) -> "Board":
        return Board(tuple((0,) * size for _ in range(size)))

    def _transpose(self) -> "Board":
        return Board(tuple(zip(*self.cells)))

    def _mirror(self) -> "Board":
        return Board(tuple(row[::-1] for row in self.cells))

    def _slide_left(self) -> Tuple["Board", int]:
        results = [slide_line(row) for row in self.cells]
        return Board(tuple(r for r, _ in results)), sum(p for _, p in results)

    def slide(self, direction: Direction) -> Tuple["Board", int]:
        if direction is Direction.LEFT:
            return self._slide_left()
        if direction is Direction.RIGHT:
            board, points = self._mirror()._slide_left()
            return board._mirror(), points
        if direction is Direction.UP:
            board, points = self._transpose()._slide_left()
            return board._transpose(), points
        board, points = self._transpose()._mirror()._slide_left()
        return board._mirror()._transpose(), points

    def empty_cells(self) -> list:
        return [(r, c) for r, row in enumerate(self.cells) for c, v in enumerate(row) if v == 0]

    def with_tile(self, row: int, col: int, value: int) -> "Board":
        rows = [list(r) for r in self.cells]
        rows[row][col] = value
        return Board(tuple(tuple(r) for r in rows))

    def can_move(self) -> bool:
        return any(self.slide(d)[0] != self for d in Direction)

    def highest(self) -> int:
        return max(max(row) for row in self.cells)

class RandomSpawner:
    def __init__(self, rng: random.Random, four_chance: float = 0.1) -> None:
        self.rng, self.four_chance = rng, four_chance
    def spawn(self, board: Board) -> Board:
        row, col = self.rng.choice(board.empty_cells())
        return board.with_tile(row, col, 4 if self.rng.random() < self.four_chance else 2)

class ClassicRules:
    def __init__(self, target: int = 2048, seed: int = 0) -> None:
        self.target, self.seed = target, seed
    def make_spawner(self) -> RandomSpawner:
        return RandomSpawner(random.Random(self.seed))
    def has_won(self, board: Board) -> bool:
        return board.highest() >= self.target

@dataclass(frozen=True)
class Snapshot:
    board: Board
    score: int
    status: Status

class Game:
    def __init__(self, rules: Rules, size: int = 4) -> None:
        self.rules = rules
        self.spawner = rules.make_spawner()
        self.board = self.spawner.spawn(self.spawner.spawn(Board.empty(size)))
        self.score = 0
        self.status = Status.PLAYING
        self.history: list = []

    def move(self, direction: Direction) -> bool:
        if self.status is not Status.PLAYING:
            return False
        moved, points = self.board.slide(direction)
        if moved == self.board:
            return False
        self.history.append(Snapshot(self.board, self.score, self.status))
        self.score += points
        self.board = self.spawner.spawn(moved)
        if self.rules.has_won(self.board):
            self.status = Status.WON
        elif not self.board.can_move():
            self.status = Status.LOST
        return True

    def undo(self) -> bool:
        if not self.history:
            return False
        snap = self.history.pop()
        self.board, self.score, self.status = snap.board, snap.score, snap.status
        return True

if __name__ == "__main__":
    assert slide_line((2, 2, 2, 2)) == ((4, 4, 0, 0), 8)
    assert slide_line((2, 2, 2, 0)) == ((4, 2, 0, 0), 4)
    assert slide_line((0, 4, 0, 4)) == ((8, 0, 0, 0), 8)
    assert slide_line((4, 2, 2, 8)) == ((4, 4, 8, 0), 4)
    board = Board(((2, 0), (2, 4)))
    assert board.slide(Direction.UP)[0] == Board(((4, 4), (0, 0)))
    assert board.slide(Direction.RIGHT)[0] == Board(((0, 2), (2, 4)))

6. Extensions, concurrency and what interviewers probe

• "Why does a no-op move not spawn?" It is in the rules, and it is why comparing the old and new boards matters. Immutable boards with value equality make that one comparison.
• "How do you detect game over?" A full board is not enough, because neighbours may still merge. can_move tries all four slides, which is simple and costs four small passes.
• "Add an AI hint." Immutable boards are ideal for search: expectimax can branch freely with no undo logic, and Board.slide is the only rule it needs.
• "Keep playing past 2048." The status moves to WON and a continue_play call returns it to PLAYING with a higher target; Rules owns that value.
• Concurrency: none in the single-player game. Immutable boards also mean a renderer on another thread can read game.board without a lock; it always sees a complete board.
• Common mistake: merging a tile twice in one move, as in [2, 2, 4] becoming [8], by merging in place while scanning; and spawning a tile after a move that changed nothing.

02Where this question was reported

• workat.tech · workat.tech machine coding (SDE I)
• techprep.app · TechPrep LLD library (no company shown)
• GitHub · Machine coding list, all companies