research-dimers.rs

1use figures::{ink, save, Board};2use mrlyrs::core::error::Result;3use mrlyrs::core::Rng;4use mrlyrs::math::bang::factory;5use mrlyrs::math::bang::Code;67const LEVEL: usize = 3;8const SIDE: usize = 27;9const CELLS: usize = 512;10const SEED: u64 = 3;11const FLIPS: usize = 400_000;12const NONE: usize = usize::MAX;1314fn neighbours(filled: &[bool], cell: usize) -> Vec<usize> {15    let (r, c) = (cell / SIDE, cell % SIDE);16    let mut out = Vec::with_capacity(4);17    if r > 0 {18        out.push(cell - SIDE);19    }20    if c + 1 < SIDE {21        out.push(cell + 1);22    }23    if r + 1 < SIDE {24        out.push(cell + SIDE);25    }26    if c > 0 {27        out.push(cell - 1);28    }29    out.retain(|&n| filled[n]);30    out31}3233fn augment(links: &[Vec<usize>], mate: &mut [usize], seen: &mut [bool], black: usize) -> bool {34    for &white in &links[black] {35        if std::mem::replace(&mut seen[white], true) {36            continue;37        }38        if mate[white] == NONE || augment(links, mate, seen, mate[white]) {39            mate[white] = black;40            mate[black] = white;41            return true;42        }43    }44    false45}4647fn flip(filled: &[bool], mate: &mut [usize], r: usize, c: usize) {48    let a = r * SIDE + c;49    let (b, d, e) = (a + 1, a + SIDE, a + SIDE + 1);50    if ![a, b, d, e].iter().all(|&x| filled[x]) {51        return;52    }53    if mate[a] == b && mate[d] == e {54        (mate[a], mate[d], mate[b], mate[e]) = (d, a, e, b);55    } else if mate[a] == d && mate[b] == e {56        (mate[a], mate[b], mate[d], mate[e]) = (b, a, e, d);57    }58}5960fn main() -> Result<()> {61    let design = factory::create(Code::from(495u128), 3, 2, 3, LEVEL)?;62    assert_eq!(design.shape, vec![SIDE, SIDE]);63    let filled: Vec<bool> = (0..SIDE * SIDE).map(|f| design.at(f) == 1).collect();64    assert_eq!(filled.iter().filter(|&&on| on).count(), CELLS);65    let links: Vec<Vec<usize>> = (0..SIDE * SIDE).map(|i| neighbours(&filled, i)).collect();66    let blacks: Vec<usize> = (0..SIDE * SIDE)67        .filter(|&i| filled[i] && (i / SIDE + i % SIDE).is_multiple_of(2))68        .collect();69    assert_eq!(2 * blacks.len(), CELLS);7071    let mut mate = vec![NONE; SIDE * SIDE];72    for &black in &blacks {73        let mut seen = vec![false; SIDE * SIDE];74        assert!(augment(&links, &mut mate, &mut seen, black));75    }76    let mut rng = Rng::new(SEED);77    for _ in 0..FLIPS {78        flip(&filled, &mut mate, rng.below(SIDE - 1), rng.below(SIDE - 1));79    }80    for cell in 0..SIDE * SIDE {81        if filled[cell] {82            assert!(links[cell].contains(&mate[cell]));83            assert_eq!(mate[mate[cell]], cell);84        } else {85            assert_eq!(mate[cell], NONE);86        }87    }8889    let mut board = Board::square();90    let frame = board.frame(0.08);91    let unit = frame.w / SIDE as f64;92    let pad = unit * 0.11;93    let thick = unit - 2.0 * pad;94    let mut dominoes = 0;95    for &black in &blacks {96        let white = mate[black];97        let (lo, hi) = (black.min(white), black.max(white));98        let flat = hi == lo + 1;99        let (r, c) = (lo / SIDE, lo % SIDE);100        let (x, y) = (frame.x + c as f64 * unit, frame.y + r as f64 * unit);101        let (w, h, color) = if flat {102            (2.0 * unit, unit, ink::blue())103        } else {104            (unit, 2.0 * unit, ink::orange())105        };106        board.round_rect(107            x + pad,108            y + pad,109            w - 2.0 * pad,110            h - 2.0 * pad,111            thick * 0.3,112            color,113        );114        dominoes += 1;115    }116    assert_eq!(2 * dominoes, CELLS);117    save("research-dimers", &board)?;118    Ok(())119}