paths.rs

1use super::pens::{self, Pen};2use std::collections::BTreeSet;34const STEPS: [(i64, i64); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)];56/// Returns the character's hand-penned strokes from the pen tables, or None outside the font.7pub fn penned(c: char) -> Option<Vec<Vec<(usize, usize)>>> {8    pens::all()9        .into_iter()10        .find(|&(key, _)| key == c)11        .map(|pen| parse(&pen))12}1314/// Returns the character's ordered strokes over its trimmed bitmap, or none for a character outside the font.15pub fn strokes(c: char) -> Vec<Vec<(usize, usize)>> {16    penned(c).unwrap_or_default()17}1819/// Flattens the character's strokes into one cell-by-cell drawing order.20pub fn path(c: char) -> Vec<(usize, usize)> {21    strokes(c).into_iter().flatten().collect()22}2324fn parse((_, strokes): &Pen) -> Vec<Vec<(usize, usize)>> {25    strokes26        .iter()27        .map(|stroke| stroke.split_whitespace().map(cell).collect())28        .collect()29}3031fn cell(token: &str) -> (usize, usize) {32    let digits: Vec<usize> = token33        .chars()34        .map(|d| d.to_digit(10).unwrap() as usize)35        .collect();36    (digits[0], digits[1])37}3839fn lit_of(rows: &[String]) -> BTreeSet<(usize, usize)> {40    let mut lit = BTreeSet::new();41    for (r, row) in rows.iter().enumerate() {42        for (c, ch) in row.chars().enumerate() {43            if ch == '1' {44                lit.insert((r, c));45            }46        }47    }48    lit49}5051fn step(cell: (usize, usize), (dr, dc): (i64, i64)) -> Option<(usize, usize)> {52    let (r, c) = (cell.0 as i64 + dr, cell.1 as i64 + dc);53    (r >= 0 && c >= 0).then_some((r as usize, c as usize))54}5556fn degree(cell: (usize, usize), left: &BTreeSet<(usize, usize)>) -> usize {57    STEPS58        .iter()59        .filter(|&&d| step(cell, d).is_some_and(|n| left.contains(&n)))60        .count()61}6263fn opening(left: &BTreeSet<(usize, usize)>) -> (usize, usize) {64    *left65        .iter()66        .min_by_key(|&&cell| (degree(cell, left) != 1, usize::MAX - cell.0, cell.1))67        .expect("opening is only asked of a non-empty set")68}6970/// Drafts a stroke order for a trimmed bitmap by walking its lit cells: start at a lowest-left free end, keep heading, lift when stuck.71pub fn draft(rows: &[String]) -> Vec<Vec<(usize, usize)>> {72    let mut left = lit_of(rows);73    let mut out = Vec::new();74    while !left.is_empty() {75        let start = opening(&left);76        left.remove(&start);77        let mut stroke = vec![start];78        let mut heading: Option<(i64, i64)> = None;79        loop {80            let cur = *stroke.last().unwrap();81            let ahead = heading82                .and_then(|d| step(cur, d))83                .filter(|n| left.contains(n));84            let next = ahead.or_else(|| {85                STEPS86                    .iter()87                    .find_map(|&d| step(cur, d).filter(|n| left.contains(n)))88            });89            let Some(next) = next else { break };90            heading = Some((next.0 as i64 - cur.0 as i64, next.1 as i64 - cur.1 as i64));91            left.remove(&next);92            stroke.push(next);93        }94        out.push(stroke);95    }96    out97}9899/// Returns the least strokes that can write a trimmed bitmap: the minimum cover of its lit cells by 4-adjacent paths, zero for a blank.100pub fn floor(rows: &[String]) -> usize {101    let cells: Vec<(usize, usize)> = lit_of(rows).into_iter().collect();102    let n = cells.len();103    if n == 0 {104        return 0;105    }106    let index = |cell: (usize, usize)| cells.binary_search(&cell).ok();107    let mut edges = Vec::new();108    for (i, &(r, c)) in cells.iter().enumerate() {109        if let Some(j) = index((r, c + 1)) {110            edges.push((i, j));111        }112        if let Some(j) = index((r + 1, c)) {113            edges.push((i, j));114        }115    }116    let mut deg = vec![0u8; n];117    let mut parent: Vec<usize> = (0..n).collect();118    let mut best = n - draft(rows).len();119    forest(&edges, 0, 0, &mut deg, &mut parent, &mut best);120    n - best121}122123fn root(parent: &[usize], mut v: usize) -> usize {124    while parent[v] != v {125        v = parent[v];126    }127    v128}129130fn forest(131    edges: &[(usize, usize)],132    at: usize,133    taken: usize,134    deg: &mut [u8],135    parent: &mut [usize],136    best: &mut usize,137) {138    *best = (*best).max(taken);139    if at == edges.len() || taken + edges.len() - at <= *best {140        return;141    }142    let (a, b) = edges[at];143    if deg[a] < 2 && deg[b] < 2 {144        let (ra, rb) = (root(parent, a), root(parent, b));145        if ra != rb {146            deg[a] += 1;147            deg[b] += 1;148            parent[ra] = rb;149            forest(edges, at + 1, taken + 1, deg, parent, best);150            parent[ra] = ra;151            deg[a] -= 1;152            deg[b] -= 1;153        }154    }155    forest(edges, at + 1, taken, deg, parent, best);156}157158#[cfg(test)]159mod tests {160    use super::*;161    use crate::{glyph, supported, trim};162163    fn permutes(c: char, walk: &[(usize, usize)]) {164        let rows = trim(&glyph(c).unwrap().rows);165        let seen: BTreeSet<(usize, usize)> = walk.iter().copied().collect();166        assert_eq!(seen.len(), walk.len(), "{c} repeats a cell");167        assert_eq!(seen, lit_of(&rows), "{c} misses or invents a cell");168    }169170    #[test]171    fn every_path_is_a_permutation_of_the_glyph() {172        for c in supported() {173            permutes(c, &path(c));174        }175    }176177    #[test]178    fn every_draft_is_a_permutation_of_the_glyph() {179        for c in supported() {180            let rows = trim(&glyph(c).unwrap().rows);181            let walk: Vec<(usize, usize)> = draft(&rows).into_iter().flatten().collect();182            permutes(c, &walk);183        }184    }185186    #[test]187    fn the_pens_cover_the_font_once_in_order() {188        let keys: Vec<char> = pens::all().into_iter().map(|(c, _)| c).collect();189        assert_eq!(keys, supported(), "the pen tables drifted from the font");190        let distinct: BTreeSet<char> = keys.iter().copied().collect();191        assert_eq!(distinct.len(), keys.len(), "a glyph is penned twice");192        assert_eq!(strokes('M')[0][0], (4, 0));193        assert_eq!(strokes('D').len(), 4);194        assert_eq!(strokes('X').len(), 3);195        assert_eq!(strokes('8').len(), 1);196    }197198    #[test]199    fn no_pen_writes_below_its_floor() {200        for c in supported() {201            let rows = trim(&glyph(c).unwrap().rows);202            let least = floor(&rows);203            assert!(strokes(c).len() >= least, "{c} is penned under its floor");204        }205        let least = |c: char| floor(&trim(&glyph(c).unwrap().rows));206        assert_eq!((least('X'), least('8')), (3, 1));207        assert_eq!((least('#'), least('x'), least('*')), (8, 7, 13));208        assert_eq!((least(' '), least('.'), least('O')), (0, 1, 1));209    }210211    #[test]212    fn strokes_are_four_adjacent_walks() {213        for c in supported() {214            for stroke in strokes(c) {215                for pair in stroke.windows(2) {216                    let (a, b) = (pair[0], pair[1]);217                    let gap = a.0.abs_diff(b.0) + a.1.abs_diff(b.1);218                    assert_eq!(gap, 1, "{c} jumps inside a stroke");219                }220            }221        }222    }223}