research-walks.rs

1use mrlycore::errors::Result;2use mrlycore::{Color, Rng};3use mrlyfig::{ink, plot, save, Board, Frame};4use mrlymath::two::designs;5use mrlymath::two::Cell2d;6use std::collections::VecDeque;78const LEVEL: usize = 4;9const STEPS: usize = 20000;10const SEED: u64 = 7;1112fn sites(cell: &Cell2d) -> (usize, Vec<bool>) {13    let side = cell.width();14    let types = cell.types();15    let mut mask = vec![false; side * side];16    for row in 0..side {17        for col in 0..side {18            mask[row * side + col] = types.get(&[row, col]) != 0;19        }20    }21    (side, mask)22}2324fn around(side: usize, at: usize) -> Vec<usize> {25    let (row, col) = (at / side, at % side);26    let mut out = Vec::with_capacity(4);27    if row > 0 {28        out.push(at - side);29    }30    if row + 1 < side {31        out.push(at + side);32    }33    if col > 0 {34        out.push(at - 1);35    }36    if col + 1 < side {37        out.push(at + 1);38    }39    out40}4142fn giant(side: usize, mask: &[bool]) -> Vec<usize> {43    let mut seen = vec![false; mask.len()];44    let mut best = Vec::new();45    for start in 0..mask.len() {46        if !mask[start] || seen[start] {47            continue;48        }49        let mut part = Vec::new();50        let mut queue = VecDeque::from([start]);51        seen[start] = true;52        while let Some(at) = queue.pop_front() {53            part.push(at);54            for next in around(side, at) {55                if mask[next] && !seen[next] {56                    seen[next] = true;57                    queue.push_back(next);58                }59            }60        }61        if part.len() > best.len() {62            best = part;63        }64    }65    best66}6768fn middle(side: usize, part: &[usize]) -> usize {69    let mid = (side as f64 - 1.0) / 2.0;70    *part71        .iter()72        .min_by(|a, b| {73            let reach = |at: &usize| {74                let (row, col) = ((at / side) as f64, (at % side) as f64);75                (row - mid).hypot(col - mid)76            };77            reach(a).partial_cmp(&reach(b)).unwrap()78        })79        .unwrap()80}8182fn walk(side: usize, mask: &[bool], start: usize, seed: u64) -> Vec<usize> {83    let mut rng = Rng::new(seed);84    let mut at = start;85    let mut path = vec![at];86    for _ in 0..STEPS {87        let (row, col) = (at / side, at % side);88        let next = match rng.below(4) {89            0 if row > 0 => at - side,90            1 if row + 1 < side => at + side,91            2 if col > 0 => at - 1,92            3 if col + 1 < side => at + 1,93            _ => at,94        };95        if next != at && mask[next] {96            at = next;97            path.push(at);98        }99    }100    path101}102103fn panel(board: &mut Board, area: Frame, code: u128, color: Color) -> Result<usize> {104    let cell = designs::create(code, 3, LEVEL, 0, 3)?;105    let (side, mask) = sites(&cell);106    let step = area.w / side as f64;107    let dot = step * 0.7;108    for (at, on) in mask.iter().enumerate() {109        if *on {110            let (row, col) = (at / side, at % side);111            board.rect(112                area.x + col as f64 * step + (step - dot) / 2.0,113                area.y + row as f64 * step + (step - dot) / 2.0,114                dot,115                dot,116                ink::fade(ink::dim(), 0.55),117            );118        }119    }120    let part = giant(side, &mask);121    let trail = walk(side, &mask, middle(side, &part), SEED);122    let mut seen = vec![false; mask.len()];123    for at in trail {124        if seen[at] {125            continue;126        }127        seen[at] = true;128        let (row, col) = (at / side, at % side);129        board.rect(130            area.x + col as f64 * step,131            area.y + row as f64 * step,132            step,133            step,134            color,135        );136    }137    Ok(mask.iter().filter(|f| **f).count())138}139140fn main() -> Result<()> {141    let mut board = Board::square();142    let frame = board.frame(0.08);143    let half = frame.w / 2.0;144    let first = Frame::new(frame.x, frame.y, half, half).inset(8.0);145    let second = Frame::new(frame.x + half, frame.y + half, half, half).inset(8.0);146    for area in [first, second] {147        plot::axis(&mut board, area, ink::line());148    }149    let a = panel(&mut board, first.inset(10.0), 127, ink::blue())?;150    let b = panel(&mut board, second.inset(10.0), 239, ink::orange())?;151    assert_eq!(a, 7usize.pow(LEVEL as u32));152    assert_eq!(b, a);153    save("research-walks", &board)?;154    Ok(())155}