use crate::utils::{build_left_moves_table, build_right_moves_table, get_exponent};
use lazy_static::lazy_static;
use std::fmt::{Debug, Display, Formatter};
use termion::color;
#[derive(Clone, Copy, Default, PartialEq, Eq, Hash)]
pub struct Board {
state: u64,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Direction {
Left,
Right,
Up,
Down,
}
impl Direction {
pub fn all() -> &'static [Direction; 4] {
&[
Direction::Left,
Direction::Right,
Direction::Up,
Direction::Down,
]
}
}
lazy_static! {
static ref LEFT_MOVES_TABLE: Vec<u16> = build_left_moves_table();
static ref RIGHT_MOVES_TABLE: Vec<u16> = build_right_moves_table();
}
impl Board {
pub fn get_value(self, tile_idx: u8) -> u16 {
let exponent = self.get_exponent_value(tile_idx);
if exponent == 0 {
return 0;
}
2 << (exponent - 1) as u16
}
pub fn get_exponent_value(self, tile_idx: u8) -> u8 {
((self.state >> (4 * (15 - tile_idx as u64))) & 0xF) as u8
}
pub fn set_value(self, tile_idx: u8, tile_value: u16) -> Self {
let exponent = get_exponent(tile_value);
self.set_value_by_exponent(tile_idx, exponent)
}
pub fn set_value_by_exponent(self, tile_idx: u8, value_exponent: u64) -> Self {
let bits_shift = ((15 - tile_idx) * 4) as u64;
let clear_mask = !(0xF << bits_shift);
let update_mask = value_exponent << bits_shift;
let new_state = (self.state & clear_mask) | update_mask;
Board { state: new_state }
}
pub fn rows(self) -> [u16; 4] {
let row1 = ((self.state & 0xFFFF_0000_0000_0000) >> 48) as u16;
let row2 = ((self.state & 0x0000_FFFF_0000_0000) >> 32) as u16;
let row3 = ((self.state & 0x0000_0000_FFFF_0000) >> 16) as u16;
let row4 = (self.state & 0x0000_0000_0000_FFFF) as u16;
[row1, row2, row3, row4]
}
pub fn columns(self) -> [u16; 4] {
self.transpose().rows()
}
pub fn max_value(self) -> u16 {
let exponent = self.into_iter().max().unwrap();
1 << exponent as u16
}
pub fn empty_tiles_indices(self) -> impl Iterator<Item = u8> {
self.into_empty_tiles_iter()
}
pub fn count_empty_tiles(self) -> usize {
self.empty_tiles_indices().fold(0, |mut acc, _| {
acc += 1;
acc
})
}
pub fn count_distinct_tiles(self) -> usize {
let mut bitset: u16 = 0;
let mut state = self.state;
while state != 0 {
bitset |= 1 << (state & 0b1111) as u16;
state >>= 4;
}
bitset >>= 1;
let mut count: usize = 0;
while bitset != 0 {
bitset &= bitset - 1;
count += 1;
}
count
}
pub fn move_to(self, direction: Direction) -> Self {
match direction {
Direction::Left => self.into_left(),
Direction::Right => self.into_right(),
Direction::Up => self.into_up(),
Direction::Down => self.into_down(),
}
}
fn transpose(self) -> Self {
let x = self.state;
let a1 = x & 0xF0F0_0F0F_F0F0_0F0F;
let a2 = x & 0x0000_F0F0_0000_F0F0;
let a3 = x & 0x0F0F_0000_0F0F_0000;
let a = a1 | (a2 << 12) | (a3 >> 12);
let b1 = a & 0xFF00_FF00_00FF_00FF;
let b2 = a & 0x00FF_00FF_0000_0000;
let b3 = a & 0x0000_0000_FF00_FF00;
let ret = b1 | (b2 >> 24) | (b3 << 24);
Self { state: ret }
}
fn into_left(self) -> Self {
self.rows()
.iter()
.enumerate()
.fold(Board::default(), |mut acc, (row_idx, row)| {
acc.state |=
(LEFT_MOVES_TABLE[*row as usize] as u64) << (16 * (3 - row_idx) as u64);
acc
})
}
fn into_right(self) -> Self {
self.rows()
.iter()
.enumerate()
.fold(Board::default(), |mut acc, (row_idx, row)| {
acc.state |=
(RIGHT_MOVES_TABLE[*row as usize] as u64) << (16 * (3 - row_idx) as u64);
acc
})
}
fn into_up(self) -> Self {
self.transpose().rows().iter().enumerate().fold(
Board::default(),
|mut acc, (col_idx, col)| {
let up_col = LEFT_MOVES_TABLE[*col as usize] as u64;
let col_shift = 4 * (3 - col_idx) as u64;
acc.state |= (up_col & 0xF000) << (36 + col_shift);
acc.state |= (up_col & 0xF00) << (24 + col_shift);
acc.state |= (up_col & 0xF0) << (12 + col_shift);
acc.state |= (up_col & 0xF) << col_shift;
acc
},
)
}
fn into_down(self) -> Self {
self.transpose().rows().iter().enumerate().fold(
Board::default(),
|mut acc, (col_idx, col)| {
let up_col = RIGHT_MOVES_TABLE[*col as usize] as u64;
let col_shift = 4 * (3 - col_idx) as u64;
acc.state |= (up_col & 0xF000) << (36 + col_shift);
acc.state |= (up_col & 0xF00) << (24 + col_shift);
acc.state |= (up_col & 0xF0) << (12 + col_shift);
acc.state |= (up_col & 0xF) << col_shift;
acc
},
)
}
}
impl IntoIterator for Board {
type Item = u8;
type IntoIter = BoardIntoIterator;
fn into_iter(self) -> Self::IntoIter {
BoardIntoIterator {
state: self.state,
index: 0,
}
}
}
pub struct BoardIntoIterator {
state: u64,
index: u8,
}
impl Iterator for BoardIntoIterator {
type Item = u8;
fn next(&mut self) -> Option<Self::Item> {
match self.index {
16 => None,
_ => {
let exponent = self.state >> 60;
self.state <<= 4;
self.index += 1;
Some(exponent as u8)
}
}
}
}
impl Board {
pub fn into_empty_tiles_iter(self) -> EmptyTilesIterator {
EmptyTilesIterator {
state: self.state,
index: 0,
}
}
}
pub struct EmptyTilesIterator {
state: u64,
index: u8,
}
impl Iterator for EmptyTilesIterator {
type Item = u8;
fn next(&mut self) -> Option<Self::Item> {
loop {
match self.index {
16 => return None,
_ => {
let empty_tile_index = if self.state.leading_zeros() >= 4 {
Some(self.index)
} else {
None
};
self.state <<= 4;
self.index += 1;
if empty_tile_index.is_some() {
return empty_tile_index;
}
}
}
}
}
}
impl From<Vec<u16>> for Board {
fn from(tiles: Vec<u16>) -> Self {
let mut state: u64 = 0;
for tile_value in tiles.into_iter() {
state <<= 4;
state |= get_exponent(tile_value);
}
Self { state }
}
}
impl From<Board> for Vec<u16> {
fn from(board: Board) -> Self {
board
.into_iter()
.map(|tile_exponent| {
if tile_exponent == 0 {
0
} else {
2 << (tile_exponent - 1) as u16
}
})
.collect()
}
}
impl Board {
fn display(self, f: &mut Formatter<'_>, debug: bool) -> Result<(), std::fmt::Error> {
let mut display = String::new();
let line_break = if debug { "\n" } else { "\n\r" };
display.push_str(&*format!(
"{b}╔═══════╦═══════╦═══════╦═══════╗{b}",
b = line_break
));
for (i, tile) in Vec::from(self).into_iter().enumerate() {
if tile == 0 {
display.push_str("║ ");
} else if debug {
display.push_str(&*format!(
"║{prefix}{tile} ",
prefix = get_spaces_prefix(tile),
tile = tile,
));
} else {
display.push_str(&*format!(
"║{prefix}{color}{tile}{reset} ",
prefix = get_spaces_prefix(tile),
color = get_color(tile),
tile = tile,
reset = color::Fg(color::Reset)
));
}
if i % 4 == 3 {
display.push_str(&*format!("║{b}", b = line_break));
if i == 15 {
display.push_str(&*format!(
"╚═══════╩═══════╩═══════╩═══════╝{b}",
b = line_break
));
} else {
display.push_str(&*format!(
"╠═══════╬═══════╬═══════╬═══════╣{b}",
b = line_break
));
}
}
}
write!(f, "{}", display)
}
}
impl Display for Board {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
self.display(f, false)
}
}
impl Debug for Board {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
self.display(f, true)
}
}
fn get_spaces_prefix(tile: u16) -> &'static str {
if tile < 10 {
" "
} else if tile < 100 {
" "
} else if tile < 1000 {
" "
} else if tile < 10000 {
" "
} else {
" "
}
}
fn get_color(tile: u16) -> color::Fg<color::Rgb> {
match tile {
2 => color::Fg(color::Rgb(238, 228, 218)),
4 => color::Fg(color::Rgb(237, 224, 200)),
8 => color::Fg(color::Rgb(242, 177, 121)),
16 => color::Fg(color::Rgb(245, 149, 99)),
32 => color::Fg(color::Rgb(246, 124, 95)),
64 => color::Fg(color::Rgb(246, 94, 59)),
128 => color::Fg(color::Rgb(237, 207, 114)),
256 => color::Fg(color::Rgb(237, 204, 97)),
512 => color::Fg(color::Rgb(237, 200, 80)),
1024 => color::Fg(color::Rgb(237, 197, 63)),
2048 => color::Fg(color::Rgb(237, 194, 46)),
4096 => color::Fg(color::Rgb(129, 214, 154)),
8192 => color::Fg(color::Rgb(129, 214, 154)),
16384 => color::Fg(color::Rgb(129, 214, 154)),
32768 => color::Fg(color::Rgb(129, 214, 154)),
_ => panic!("Invalid tile value: {}", tile),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn should_convert_vec_to_board() {
#[rustfmt::skip]
let vec_board: Vec<u16> = vec![
0, 2, 0, 0,
32768, 0, 0, 2,
0, 0, 16, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board.clone());
let into_vec_board: Vec<u16> = board.into();
assert_eq!(vec_board, into_vec_board);
}
#[test]
fn should_iterate_over_exponents() {
#[rustfmt::skip]
let vec_board: Vec<u16> = vec![
0, 2, 0, 0,
32768, 0, 0, 2,
0, 0, 16, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board.clone());
let exponents: Vec<_> = board.into_iter().collect();
#[rustfmt::skip]
let expected_exponents = vec![
0, 1, 0, 0,
15, 0, 0, 1,
0, 0, 4, 2,
3, 1, 4, 6
];
assert_eq!(expected_exponents, exponents);
}
#[test]
fn should_use_binary_representation() {
#[rustfmt::skip]
let board_values = vec![
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 4, 0,
0, 16, 0, 8
];
let board = Board::from(board_values);
let board_repr: u64 =
2u64.pow(0 + 0) + 2u64.pow(1 + 0) + 2u64.pow(2 + 8) + 2u64.pow(1 + 20);
assert_eq!(board_repr as u64, board.state);
}
#[test]
fn should_get_value() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 4, 0, 2,
2, 0, 4, 0,
4, 2, 0, 512,
16, 8, 32, 32,
]);
assert_eq!(512, board.get_value(11));
}
#[test]
fn should_get_exponent_value() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 4, 0, 2,
2, 0, 4, 0,
4, 2, 0, 512,
16, 8, 32, 32,
]);
assert_eq!(9, board.get_exponent_value(11));
}
#[test]
fn should_get_rows() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 4, 0, 2,
2, 0, 4, 0,
4, 2, 0, 512,
16, 8, 32, 32,
]);
let rows = board.rows();
let expected_rows: [u16; 4] = [0x0201, 0x1020, 0x2109, 0x4355];
assert_eq!(expected_rows, rows);
}
#[test]
fn should_get_columns() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 2, 4, 16,
4, 0, 2, 8,
0, 4, 0, 32,
2, 0, 512, 32,
]);
let columns = board.columns();
let expected_rows: [u16; 4] = [0x0201, 0x1020, 0x2109, 0x4355];
assert_eq!(expected_rows, columns);
}
#[test]
fn should_set_value() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 4, 0, 2,
2, 0, 4, 0,
4, 2, 0, 512,
16, 8, 32, 32,
]);
let board = board.set_value(5, 32).set_value(8, 64);
#[rustfmt::skip]
let expected_board = Board::from(vec![
0, 4, 0, 2,
2, 32, 4, 0,
64, 2, 0, 512,
16, 8, 32, 32,
]);
assert_eq!(expected_board, board);
}
#[test]
fn should_set_value_by_exponent() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 4, 0, 2,
2, 0, 4, 0,
4, 2, 0, 512,
16, 8, 32, 32,
]);
let board = board
.set_value_by_exponent(5, 5)
.set_value_by_exponent(8, 6);
#[rustfmt::skip]
let expected_board = Board::from(vec![
0, 4, 0, 2,
2, 32, 4, 0,
64, 2, 0, 512,
16, 8, 32, 32,
]);
assert_eq!(expected_board, board);
}
#[test]
fn should_move_left() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 0, 0, 2,
2, 2, 4, 0,
4, 2, 8, 512,
16, 16, 32, 32,
]);
let left_board = board.into_left();
#[rustfmt::skip]
let expected_board = Board::from(vec![
2, 0, 0, 0,
4, 4, 0, 0,
4, 2, 8, 512,
32, 64, 0, 0,
]);
assert_eq!(expected_board, left_board);
}
#[test]
fn should_move_right() {
#[rustfmt::skip]
let board = Board::from(vec![
512, 8, 2, 4,
2, 0, 0, 0,
0, 4, 2, 2,
32, 32, 16, 16,
]);
let right_board = board.into_right();
#[rustfmt::skip]
let expected_board = Board::from(vec![
512, 8, 2, 4,
0, 0, 0, 2,
0, 0, 4, 4,
0, 0, 64, 32,
]);
assert_eq!(expected_board, right_board);
}
#[test]
fn should_move_up() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 2, 512, 16,
0, 2, 8, 16,
0, 4, 2, 32,
2, 0, 4, 32,
]);
let up_board = board.into_up();
#[rustfmt::skip]
let expected_board = Board::from(vec![
2, 4, 512, 32,
0, 4, 8, 64,
0, 0, 2, 0,
0, 0, 4, 0,
]);
assert_eq!(expected_board, up_board);
}
#[test]
fn should_move_down() {
#[rustfmt::skip]
let board = Board::from(vec![
2, 0, 512, 32,
0, 4, 8, 32,
0, 2, 2, 16,
0, 2, 4, 16,
]);
let down_board = board.into_down();
#[rustfmt::skip]
let expected_board = Board::from(vec![
0, 0, 512, 0,
0, 0, 8, 0,
0, 4, 2, 64,
2, 4, 4, 32,
]);
assert_eq!(expected_board, down_board);
}
#[test]
fn should_move_with_high_values() {
#[rustfmt::skip]
let board = Board::from(vec![
0, 0, 0, 0,
0, 0, 16384, 0,
0, 0, 16384, 0,
0, 0, 0, 0,
]);
let down_board = board.into_down();
#[rustfmt::skip]
let expected_board = Board::from(vec![
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 32768, 0,
]);
assert_eq!(expected_board, down_board);
}
#[test]
fn should_get_max_value() {
#[rustfmt::skip]
let vec_board = vec![
0, 2, 0, 2048,
0, 256, 0, 512,
0, 0, 1024, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board);
let max_value = board.max_value();
assert_eq!(2048, max_value);
}
#[test]
fn should_get_empty_tiles() {
#[rustfmt::skip]
let vec_board = vec![
0, 2, 0, 2048,
0, 256, 0, 512,
0, 0, 1024, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board);
let empty_tiles: Vec<_> = board.empty_tiles_indices().collect();
assert_eq!(vec![0, 2, 4, 6, 8, 9], empty_tiles);
}
#[test]
fn should_count_empty_tiles() {
#[rustfmt::skip]
let vec_board = vec![
0, 2, 0, 2048,
0, 256, 0, 512,
0, 0, 1024, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board);
let nb_empty_tiles = board.count_empty_tiles();
assert_eq!(6, nb_empty_tiles);
}
#[test]
fn should_count_distinct_tiles() {
#[rustfmt::skip]
let vec_board = vec![
0, 2, 0, 2048,
0, 16, 0, 512,
0, 0, 8, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board);
let distinct_tiles = board.count_distinct_tiles();
assert_eq!(7, distinct_tiles);
}
#[test]
fn should_display_board_for_debug() {
#[rustfmt::skip]
let vec_board = vec![
8192, 32, 16384, 32768,
4096, 256, 0, 512,
2048, 128, 1024, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board);
let display = format!("{:?}", board);
let expected_display = r#"
╔═══════╦═══════╦═══════╦═══════╗
║ 8192 ║ 32 ║ 16384 ║ 32768 ║
╠═══════╬═══════╬═══════╬═══════╣
║ 4096 ║ 256 ║ ║ 512 ║
╠═══════╬═══════╬═══════╬═══════╣
║ 2048 ║ 128 ║ 1024 ║ 4 ║
╠═══════╬═══════╬═══════╬═══════╣
║ 8 ║ 2 ║ 16 ║ 64 ║
╚═══════╩═══════╩═══════╩═══════╝
"#;
assert_eq!(expected_display, display);
}
#[test]
fn should_display_board() {
#[rustfmt::skip]
let vec_board = vec![
8192, 32, 16384, 32768,
4096, 256, 0, 512,
2048, 128, 1024, 4,
8, 2, 16, 64
];
let board = Board::from(vec_board);
format!("{}", board);
}
}