Problem. Implement a simplified 2048 engine on a 4×4 grid. Given an initial board (0 = empty) and a sequence of moves ("left", "right", "up", "down"), apply each move by sliding and merging tiles. Each tile can merge at most once per move. Do not add random tiles after a move.
Examples:
- Board
[[2,0,2,4],[0,0,0,0],[0,0,0,0],[0,0,0,0]], moves["left"]→[[4,4,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] - Board
[[2,2,2,2],[0,0,0,0],[0,0,0,0],[0,0,0,0]], moves["left"]→[[4,4,0,0],...]— two merges, not one chain. - Board
[[2,0,0,2],[4,0,4,0],[0,0,0,0],[8,8,8,8]], moves["left"]→[[4,0,0,0],[8,0,0,0],[0,0,0,0],[16,16,0,0]]
Solution. Reduce every direction to “slide-left on a single row”: extract the row/column, compress non-zeros, merge adjacent equals (mark merged), compress again, pad with zeros. Rotate or transpose the board for up/down/right.
def slide_row_left(row):
tiles = [v for v in row if v] # remove zeros
merged = []
skip = False
for i in range(len(tiles)):
if skip:
skip = False
continue
if i + 1 < len(tiles) and tiles[i] == tiles[i + 1]:
merged.append(tiles[i] * 2)
skip = True
else:
merged.append(tiles[i])
return merged + [0] * (4 - len(merged))
def move_2048(board, direction):
import copy
b = copy.deepcopy(board)
if direction == "left":
b = [slide_row_left(r) for r in b]
elif direction == "right":
b = [slide_row_left(r[::-1])[::-1] for r in b]
elif direction == "up":
cols = list(zip(*b))
cols = [slide_row_left(list(c)) for c in cols]
b = [list(r) for r in zip(*cols)]
elif direction == "down":
cols = list(zip(*b))
cols = [slide_row_left(list(c)[::-1])[::-1] for c in cols]
b = [list(r) for r in zip(*cols)]
return b
def simulate(board, moves):
for m in moves:
board = move_2048(board, m)
return board
O(16 × M) where M is the number of moves — effectively O(M).
Gotchas.
- A tile can merge only once per move:
[2,2,2,2]left →[4,4,0,0], not[8,0,0,0]. - Slide before merge, then slide again to close gaps.
- Up/down are column operations — transpose, slide left, transpose back.
- Deep-copy the board if you need immutability between steps.