wiki-domino-tilings.rs

1use figures::{ink, save, Board, Grid};2use mrlyrs::core::error::Result;3use mrlyrs::core::Rng;4use std::collections::{HashMap, HashSet};56const ORDER: i64 = 32;7const SEED: u64 = 5;8const DOMINOES: usize = 1056;910#[derive(Clone, Copy, PartialEq, Eq, Hash)]11struct Domino {12    x: i64,13    y: i64,14    flat: bool,15}1617fn inside(order: i64, x: i64, y: i64) -> bool {18    (2 * x + 1).abs() + (2 * y + 1).abs() <= 2 * order19}2021fn cells(d: Domino) -> [(i64, i64); 2] {22    if d.flat {23        [(d.x, d.y), (d.x + 1, d.y)]24    } else {25        [(d.x, d.y), (d.x, d.y + 1)]26    }27}2829fn leads(order: i64, x: i64, y: i64) -> bool {30    (x + y + order).rem_euclid(2) == 031}3233fn shuffle(order: i64, tiles: &[Domino], rng: &mut Rng) -> Vec<Domino> {34    let laid: HashSet<Domino> = tiles.iter().copied().collect();35    let mut doomed = HashSet::new();36    for &d in tiles {37        if leads(order, d.x, d.y) {38            let facing = if d.flat {39                Domino { y: d.y + 1, ..d }40            } else {41                Domino { x: d.x + 1, ..d }42            };43            if laid.contains(&facing) {44                doomed.insert(d);45                doomed.insert(facing);46            }47        }48    }49    let mut next: Vec<Domino> = tiles50        .iter()51        .filter(|d| !doomed.contains(d))52        .map(|&d| {53            let step = if leads(order, d.x, d.y) { 1 } else { -1 };54            if d.flat {55                Domino { y: d.y + step, ..d }56            } else {57                Domino { x: d.x + step, ..d }58            }59        })60        .collect();61    let grown = order + 1;62    let mut taken = HashSet::new();63    for &d in &next {64        for (x, y) in cells(d) {65            assert!(inside(grown, x, y));66            assert!(taken.insert((x, y)));67        }68    }69    for y in (-grown..grown).rev() {70        for x in -grown..grown {71            if !inside(grown, x, y) || taken.contains(&(x, y)) {72                continue;73            }74            assert!(leads(grown, x, y));75            for (u, v) in [(x, y), (x + 1, y), (x, y - 1), (x + 1, y - 1)] {76                assert!(inside(grown, u, v));77                assert!(taken.insert((u, v)));78            }79            if rng.boolean() {80                next.push(Domino { x, y, flat: true });81                next.push(Domino {82                    x,83                    y: y - 1,84                    flat: true,85                });86            } else {87                next.push(Domino {88                    x,89                    y: y - 1,90                    flat: false,91                });92                next.push(Domino {93                    x: x + 1,94                    y: y - 1,95                    flat: false,96                });97            }98        }99    }100    next101}102103fn count(rows: &[Vec<bool>]) -> u64 {104    let width = rows[0].len();105    let mut states: HashMap<u64, u64> = HashMap::from([(0, 1)]);106    for row in rows {107        let mut next = HashMap::new();108        for (&mask, &ways) in &states {109            let mut stack = vec![(0, mask, 0u64)];110            while let Some((i, held, below)) = stack.pop() {111                if i == width {112                    *next.entry(below).or_insert(0) += ways;113                    continue;114                }115                let bit = 1u64 << i;116                if held & bit != 0 {117                    if row[i] {118                        stack.push((i + 1, held, below));119                    }120                    continue;121                }122                if !row[i] {123                    stack.push((i + 1, held, below));124                    continue;125                }126                stack.push((i + 1, held, below | bit));127                if i + 1 < width && row[i + 1] && held & (bit << 1) == 0 {128                    stack.push((i + 2, held, below));129                }130            }131        }132        states = next;133    }134    states.get(&0).copied().unwrap_or(0)135}136137fn aztec(order: i64) -> Vec<Vec<bool>> {138    (-order..order)139        .map(|y| (-order..order).map(|x| inside(order, x, y)).collect())140        .collect()141}142143fn main() -> Result<()> {144    for order in 1..=6 {145        assert_eq!(count(&aztec(order)), 1 << (order * (order + 1) / 2));146    }147    let fibonacci: Vec<u64> = (1..=10).map(|n| count(&vec![vec![true; 2]; n])).collect();148    assert_eq!(fibonacci, vec![1, 2, 3, 5, 8, 13, 21, 34, 55, 89]);149    assert_eq!(count(&vec![vec![true; 8]; 8]), 12_988_816);150151    let mut rng = Rng::new(SEED);152    let mut tiles = Vec::new();153    for order in 0..ORDER {154        tiles = shuffle(order, &tiles, &mut rng);155    }156    assert_eq!((ORDER * (ORDER + 1)) as usize, DOMINOES);157    assert_eq!(tiles.len(), DOMINOES);158    let region: usize = aztec(ORDER).iter().flatten().filter(|&&on| on).count();159    assert_eq!(region, 2 * DOMINOES);160    let covered: HashSet<(i64, i64)> = tiles.iter().flat_map(|&d| cells(d)).collect();161    assert_eq!(covered.len(), region);162    assert!(tiles.iter().filter(|d| !d.flat).count().is_multiple_of(2));163164    let mut board = Board::square();165    let side = 2 * ORDER as usize;166    let grid = Grid::new(board.frame(0.08), side, side, 0.0);167    let unit = grid.frame.w / side as f64;168    let pad = unit * 0.1;169    for &d in &tiles {170        let [(ax, ay), (bx, by)] = cells(d);171        let corner = |x: i64, y: i64| grid.cell((x + ORDER) as usize, (ORDER - 1 - y) as usize);172        let (x0, y0, _, _) = corner(ax.min(bx), ay.max(by));173        let (x1, y1, w1, h1) = corner(ax.max(bx), ay.min(by));174        let (w, h) = (x1 + w1 - x0, y1 + h1 - y0);175        let color = if d.flat { ink::blue() } else { ink::yellow() };176        board.round_rect(177            x0 + pad,178            y0 + pad,179            w - 2.0 * pad,180            h - 2.0 * pad,181            (unit - 2.0 * pad) * 0.3,182            color,183        );184    }185    save("wiki-domino-tilings", &board)?;186    Ok(())187}