use rand::rngs::StdRng;
use rand::{RngExt as _, SeedableRng as _};
pub const SIZE: usize = 4;
pub const WIN_VALUE: u32 = 2048;
pub type Row = [u32; SIZE];
pub type Grid = [Row; SIZE];
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Direction {
Up,
Down,
Left,
Right,
}
impl Direction {
pub const ALL: [Self; 4] = [Self::Up, Self::Down, Self::Left, Self::Right];
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Status {
Playing,
Won,
Lost,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct MoveOutcome {
pub changed: bool,
pub gained: u64,
}
const fn cell_at(dir: Direction, i: usize, j: usize) -> (usize, usize) {
match dir {
Direction::Left => (i, j),
Direction::Right => (i, SIZE - 1 - j),
Direction::Up => (j, i),
Direction::Down => (SIZE - 1 - j, i),
}
}
pub fn slide_line(line: &Row) -> (Row, u64) {
let mut compacted = [0u32; SIZE];
let mut len = 0;
for &value in line {
if value != 0 {
compacted[len] = value;
len += 1;
}
}
let mut out = [0u32; SIZE];
let mut score = 0;
let mut read = 0;
let mut write = 0;
while read < len {
if read + 1 < len && compacted[read] == compacted[read + 1] {
let merged = compacted[read] * 2;
out[write] = merged;
score += u64::from(merged);
read += 2;
} else {
out[write] = compacted[read];
read += 1;
}
write += 1;
}
(out, score)
}
pub fn apply_move(grid: &mut Grid, dir: Direction) -> MoveOutcome {
let before = *grid;
let mut gained = 0;
for i in 0..SIZE {
let mut line = [0u32; SIZE];
for (j, slot) in line.iter_mut().enumerate() {
let (row, col) = cell_at(dir, i, j);
*slot = grid[row][col];
}
let (merged, score) = slide_line(&line);
gained += score;
for (j, &value) in merged.iter().enumerate() {
let (row, col) = cell_at(dir, i, j);
grid[row][col] = value;
}
}
MoveOutcome {
changed: *grid != before,
gained,
}
}
pub fn is_stuck(grid: &Grid) -> bool {
for row in 0..SIZE {
for col in 0..SIZE {
let value = grid[row][col];
if value == 0 {
return false;
}
if col + 1 < SIZE && grid[row][col + 1] == value {
return false;
}
if row + 1 < SIZE && grid[row + 1][col] == value {
return false;
}
}
}
true
}
pub struct Game {
grid: Grid,
score: u64,
best: u64,
status: Status,
win_acknowledged: bool,
history: Vec<Snapshot>,
future: Vec<Snapshot>,
rng: StdRng,
spawned: Option<(usize, usize)>,
moves: u64,
}
#[derive(Debug, Clone, Copy)]
struct Snapshot {
grid: Grid,
score: u64,
moves: u64,
}
impl Game {
pub fn new(best: u64) -> Self {
Self::start(rand::make_rng(), best)
}
pub fn with_seed(seed: u64, best: u64) -> Self {
Self::start(StdRng::seed_from_u64(seed), best)
}
pub fn from_grid(grid: Grid, best: u64) -> Self {
let mut game = Self::start(StdRng::seed_from_u64(0), best);
game.grid = grid;
game.history.clear();
game.future.clear();
game.spawned = None;
game.refresh_status();
game
}
fn start(rng: StdRng, best: u64) -> Self {
let mut game = Self {
grid: [[0; SIZE]; SIZE],
score: 0,
best,
status: Status::Playing,
win_acknowledged: false,
history: Vec::new(),
future: Vec::new(),
rng,
spawned: None,
moves: 0,
};
game.reset();
game
}
fn reset(&mut self) {
self.grid = [[0; SIZE]; SIZE];
self.score = 0;
self.status = Status::Playing;
self.win_acknowledged = false;
self.history.clear();
self.future.clear();
self.spawned = None;
self.moves = 0;
self.spawn_tile();
self.spawn_tile();
}
pub fn restart(&mut self) {
self.reset();
}
pub fn slide(&mut self, dir: Direction) -> bool {
if self.status != Status::Playing {
return false;
}
let before = self.snapshot();
let outcome = apply_move(&mut self.grid, dir);
if !outcome.changed {
return false;
}
self.history.push(before);
self.future.clear();
self.score += outcome.gained;
self.best = self.best.max(self.score);
self.moves += 1;
self.spawn_tile();
self.refresh_status();
true
}
pub fn undo(&mut self) -> bool {
let Some(previous) = self.history.pop() else {
return false;
};
self.future.push(self.snapshot());
self.restore(previous);
true
}
pub fn redo(&mut self) -> bool {
let Some(next) = self.future.pop() else {
return false;
};
self.history.push(self.snapshot());
self.restore(next);
true
}
fn snapshot(&self) -> Snapshot {
Snapshot {
grid: self.grid,
score: self.score,
moves: self.moves,
}
}
fn restore(&mut self, snapshot: Snapshot) {
self.grid = snapshot.grid;
self.score = snapshot.score;
self.moves = snapshot.moves;
self.spawned = None;
self.refresh_status();
}
pub fn continue_after_win(&mut self) {
if self.status == Status::Won {
self.win_acknowledged = true;
self.refresh_status();
}
}
pub fn spawned(&self) -> Option<(usize, usize)> {
self.spawned
}
pub fn grid(&self) -> &Grid {
&self.grid
}
pub fn tile(&self, row: usize, col: usize) -> u32 {
self.grid[row][col]
}
pub fn score(&self) -> u64 {
self.score
}
pub fn best(&self) -> u64 {
self.best
}
pub fn moves(&self) -> u64 {
self.moves
}
pub fn status(&self) -> Status {
self.status
}
pub fn can_undo(&self) -> bool {
!self.history.is_empty()
}
pub fn can_redo(&self) -> bool {
!self.future.is_empty()
}
pub fn max_tile(&self) -> u32 {
self.grid.iter().flatten().copied().max().unwrap_or(0)
}
fn spawn_tile(&mut self) -> Option<(usize, usize)> {
let mut empty = [(0usize, 0usize); SIZE * SIZE];
let mut len = 0;
for row in 0..SIZE {
for col in 0..SIZE {
if self.grid[row][col] == 0 {
empty[len] = (row, col);
len += 1;
}
}
}
if len == 0 {
self.spawned = None;
return None;
}
let (row, col) = empty[self.rng.random_range(0..len)];
self.grid[row][col] = if self.rng.random_range(0..10) == 0 {
4
} else {
2
};
self.spawned = Some((row, col));
Some((row, col))
}
fn refresh_status(&mut self) {
if !self.win_acknowledged && self.max_tile() >= WIN_VALUE {
self.status = Status::Won;
} else if is_stuck(&self.grid) {
self.status = Status::Lost;
} else {
self.status = Status::Playing;
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn slides_gaps_away() {
assert_eq!(slide_line(&[0, 0, 2, 4]), ([2, 4, 0, 0], 0));
assert_eq!(slide_line(&[0, 0, 0, 2]), ([2, 0, 0, 0], 0));
assert_eq!(slide_line(&[0; SIZE]), ([0; SIZE], 0));
}
#[test]
fn merges_equal_neighbours_once() {
assert_eq!(slide_line(&[2, 2, 0, 0]), ([4, 0, 0, 0], 4));
assert_eq!(slide_line(&[2, 2, 2, 2]), ([4, 4, 0, 0], 8));
assert_eq!(slide_line(&[2, 2, 4, 0]), ([4, 4, 0, 0], 4));
assert_eq!(slide_line(&[4, 4, 8, 0]), ([8, 8, 0, 0], 8));
assert_eq!(slide_line(&[2, 0, 2, 4]), ([4, 4, 0, 0], 4));
}
#[test]
fn moves_are_directional() {
let grid = [[2, 2, 4, 4], [0; SIZE], [0; SIZE], [0; SIZE]];
let mut left = grid;
assert!(apply_move(&mut left, Direction::Left).changed);
assert_eq!(left[0], [4, 8, 0, 0]);
let mut right = grid;
assert!(apply_move(&mut right, Direction::Right).changed);
assert_eq!(right[0], [0, 0, 4, 8]);
let mut up = [[2, 0, 0, 0], [2, 0, 0, 0], [4, 0, 0, 0], [4, 0, 0, 0]];
assert!(apply_move(&mut up, Direction::Up).changed);
assert_eq!(up, [[4, 0, 0, 0], [8, 0, 0, 0], [0; SIZE], [0; SIZE]]);
let mut down = [[2, 0, 0, 0], [2, 0, 0, 0], [4, 0, 0, 0], [4, 0, 0, 0]];
assert!(apply_move(&mut down, Direction::Down).changed);
assert_eq!(down, [[0; SIZE], [0; SIZE], [4, 0, 0, 0], [8, 0, 0, 0]]);
}
#[test]
fn a_move_conserves_the_total_of_all_tiles() {
assert_eq!(slide_line(&[2, 2, 2, 2]).0.iter().sum::<u32>(), 8);
let grid = [[2, 2, 4, 4], [8, 0, 8, 0], [0, 4, 0, 4], [2, 0, 0, 0]];
for dir in Direction::ALL {
let before: u32 = grid.iter().flatten().sum();
let mut next = grid;
apply_move(&mut next, dir);
let after: u32 = next.iter().flatten().sum();
assert_eq!(before, after, "sum changed moving {dir:?}");
}
}
#[test]
fn a_move_never_increases_the_number_of_tiles() {
let grid = [[2, 2, 4, 4], [8, 0, 8, 0], [0, 4, 0, 4], [2, 0, 0, 0]];
for dir in Direction::ALL {
let before = grid.iter().flatten().filter(|&&v| v != 0).count();
let mut next = grid;
apply_move(&mut next, dir);
let after = next.iter().flatten().filter(|&&v| v != 0).count();
assert!(after <= before, "tile count grew moving {dir:?}");
}
}
#[test]
fn a_move_that_changes_nothing_is_rejected() {
let mut grid = [
[2, 4, 8, 16],
[4, 8, 16, 32],
[8, 16, 32, 64],
[16, 32, 64, 128],
];
let before = grid;
let outcome = apply_move(&mut grid, Direction::Left);
assert!(!outcome.changed);
assert_eq!(grid, before);
assert_eq!(outcome.gained, 0);
}
#[test]
fn detects_a_stuck_board() {
let stuck = [[2, 4, 2, 4], [4, 2, 4, 2], [2, 4, 2, 4], [4, 2, 4, 2]];
assert!(is_stuck(&stuck));
let mut open = stuck;
open[3][3] = 0;
assert!(!is_stuck(&open));
let mut mergeable = stuck;
mergeable[0][1] = mergeable[0][0];
assert!(!is_stuck(&mergeable));
}
#[test]
fn from_grid_recognises_a_board_that_already_won() {
let game = Game::from_grid([[2048, 0, 0, 0], [0; SIZE], [0; SIZE], [0; SIZE]], 0);
assert_eq!(game.status(), Status::Won);
}
#[test]
fn a_stuck_winning_board_continues_into_a_loss() {
let grid = [[2048, 2, 4, 8], [4, 8, 2, 4], [2, 4, 8, 2], [8, 2, 4, 8]];
let mut game = Game::from_grid(grid, 0);
assert_eq!(game.status(), Status::Won);
game.continue_after_win();
assert_eq!(game.status(), Status::Lost);
}
#[test]
fn a_new_game_starts_with_two_tiles_and_no_score() {
let game = Game::with_seed(42, 0);
let filled = game.grid().iter().flatten().filter(|&&v| v != 0).count();
assert_eq!(filled, 2);
assert_eq!(game.score(), 0);
assert_eq!(game.status(), Status::Playing);
assert!(!game.can_undo());
assert!(
game.grid()
.iter()
.flatten()
.all(|&v| v == 0 || v == 2 || v == 4)
);
}
#[test]
fn a_productive_move_spawns_exactly_one_tile() {
let mut game = Game::with_seed(7, 0);
let before = game.grid().iter().flatten().filter(|&&v| v != 0).count();
assert!(game.slide(Direction::Left));
let after = game.grid().iter().flatten().filter(|&&v| v != 0).count();
assert_eq!(after, before + 1);
assert!(game.spawned().is_some());
assert_eq!(game.moves(), 1);
}
#[test]
fn redo_puts_back_exactly_what_undo_removed() {
let mut game = Game::with_seed(11, 0);
assert!(game.slide(Direction::Down));
let after_move = (*game.grid(), game.score(), game.moves());
assert!(!game.can_redo(), "nothing has been undone yet");
assert!(game.undo());
assert!(game.can_redo());
assert!(game.redo());
assert_eq!((*game.grid(), game.score(), game.moves()), after_move);
assert!(!game.can_redo(), "the redo stack is used up");
}
#[test]
fn a_new_move_discards_the_redo_branch() {
let mut game = Game::with_seed(11, 0);
assert!(game.slide(Direction::Down));
assert!(game.undo());
assert!(game.can_redo());
assert!(game.slide(Direction::Left));
assert!(!game.can_redo());
assert!(!game.redo());
}
#[test]
fn undo_and_redo_can_be_walked_back_and_forth() {
let mut game = Game::with_seed(3, 0);
let mut states = vec![(*game.grid(), game.score())];
for dir in [Direction::Left, Direction::Down, Direction::Right] {
assert!(game.slide(dir));
states.push((*game.grid(), game.score()));
}
for expected in states.iter().rev().skip(1) {
assert!(game.undo());
assert_eq!((*game.grid(), game.score()), *expected);
}
assert!(!game.can_undo());
for expected in states.iter().skip(1) {
assert!(game.redo());
assert_eq!((*game.grid(), game.score()), *expected);
}
assert!(!game.can_redo());
}
#[test]
fn redoing_into_a_finished_position_reports_it_as_lost() {
let mut game = Game::from_grid([[2, 4, 2, 4], [4, 2, 4, 2], [2, 4, 2, 4], [4, 2, 4, 0]], 0);
for step in 0..200 {
if game.status() == Status::Lost {
break;
}
game.slide(Direction::ALL[step % 4]);
}
assert_eq!(game.status(), Status::Lost);
assert!(game.undo());
assert_eq!(game.status(), Status::Playing);
assert!(game.redo());
assert_eq!(
game.status(),
Status::Lost,
"redo must restore the finished state, not silently resume"
);
}
#[test]
fn undo_restores_board_and_score() {
let mut game = Game::with_seed(11, 0);
let grid = *game.grid();
let score = game.score();
assert!(game.slide(Direction::Down));
assert!(game.can_undo());
assert!(game.undo());
assert_eq!(*game.grid(), grid);
assert_eq!(game.score(), score);
assert_eq!(game.moves(), 0);
assert!(!game.can_undo());
}
#[test]
fn score_is_the_sum_of_merged_tiles() {
let mut game = Game::from_grid([[2, 2, 4, 4], [0; SIZE], [0; SIZE], [0; SIZE]], 0);
assert!(game.slide(Direction::Left));
assert_eq!(game.score(), 12); assert_eq!(game.best(), 12);
}
#[test]
fn best_score_is_never_lowered() {
let mut game = Game::from_grid([[2, 2, 0, 0], [0; SIZE], [0; SIZE], [0; SIZE]], 1000);
assert!(game.slide(Direction::Left));
assert_eq!(game.score(), 4);
assert_eq!(game.best(), 1000);
}
#[test]
fn reaching_the_win_value_wins_once() {
let mut game = Game::from_grid([[1024, 1024, 0, 0], [0; SIZE], [0; SIZE], [0; SIZE]], 0);
assert!(game.slide(Direction::Left));
assert_eq!(game.status(), Status::Won);
assert_eq!(game.max_tile(), WIN_VALUE);
assert!(!game.slide(Direction::Down));
game.continue_after_win();
assert_eq!(game.status(), Status::Playing);
assert!(game.slide(Direction::Down));
assert_eq!(game.status(), Status::Playing);
}
#[test]
fn a_full_board_with_no_merges_is_lost() {
let mut game = Game::from_grid([[2, 4, 2, 4], [4, 2, 4, 2], [2, 4, 2, 4], [4, 2, 4, 2]], 0);
assert_eq!(game.status(), Status::Lost);
assert!(!game.slide(Direction::Left));
assert!(!game.slide(Direction::Up));
}
#[test]
fn status_always_agrees_with_the_board() {
let mut game = Game::with_seed(31337, 0);
for step in 0..2000 {
if game.status() == Status::Won {
game.continue_after_win();
}
if game.status() == Status::Lost {
break;
}
game.slide(Direction::ALL[step % 4]);
assert_eq!(
game.status() == Status::Lost,
is_stuck(game.grid()),
"status disagrees with the board at step {step}:\n{:?}",
game.grid()
);
}
assert_eq!(
game.status(),
Status::Lost,
"a badly played game must eventually end"
);
}
#[test]
fn restart_clears_progress_but_keeps_the_best() {
let mut game = Game::from_grid([[2, 2, 0, 0], [0; SIZE], [0; SIZE], [0; SIZE]], 500);
assert!(game.slide(Direction::Left));
assert_eq!(game.score(), 4);
game.restart();
assert_eq!(game.score(), 0);
assert_eq!(game.best(), 500);
assert_eq!(game.moves(), 0);
assert!(!game.can_undo());
assert_eq!(game.grid().iter().flatten().filter(|&&v| v != 0).count(), 2);
}
#[test]
fn spawning_only_ever_produces_twos_and_fours() {
let mut game = Game::with_seed(2024, 0);
for step in 0..400 {
let dir = Direction::ALL[step % Direction::ALL.len()];
if game.status() != Status::Playing {
break;
}
game.slide(dir);
assert!(
game.grid()
.iter()
.flatten()
.all(|&v| v == 0 || v.is_power_of_two()),
"every tile must be a power of two, got {:?}",
game.grid()
);
}
}
#[test]
fn score_never_exceeds_a_sane_bound() {
let mut game = Game::with_seed(99, 0);
for step in 0..1000 {
if game.status() != Status::Playing {
game.restart();
}
game.slide(Direction::ALL[step % 4]);
}
assert!(game.max_tile() <= 1 << 20);
}
}