word.rs

1pub const CODES: [u8; 15] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];2pub const LIBRARY: [u8; 10] = [3, 5, 6, 7, 9, 10, 11, 12, 13, 14];34pub fn corners(code: u8) -> Vec<(usize, usize)> {5    (0..4usize)6        .filter(|i| (code >> i) & 1 == 1)7        .map(|i| (i / 2, i % 2))8        .collect()9}1011pub struct Grid {12    pub side: usize,13    pub cells: Vec<bool>,14}1516pub fn render(word: &[u8]) -> Grid {17    let mut side = 1usize;18    let mut cells = vec![true];19    for &code in word {20        let next = side * 2;21        let mut out = vec![false; next * next];22        let filled = corners(code);23        for r in 0..side {24            for c in 0..side {25                if cells[r * side + c] {26                    for &(a, b) in &filled {27                        out[(2 * r + a) * next + 2 * c + b] = true;28                    }29                }30            }31        }32        side = next;33        cells = out;34    }35    Grid { side, cells }36}3738impl Grid {39    pub fn at(&self, r: usize, c: usize) -> bool {40        self.cells[r * self.side + c]41    }4243    pub fn fill(&self) -> u64 {44        self.cells.iter().filter(|c| **c).count() as u6445    }4647    pub fn diagonal(&self) -> u64 {48        (0..self.side).filter(|&i| self.at(i, i)).count() as u6449    }5051    pub fn adjacent(&self) -> u64 {52        let mut count = 0u64;53        for r in 0..self.side {54            for c in 0..self.side {55                if !self.at(r, c) {56                    continue;57                }58                if r + 1 < self.side && self.at(r + 1, c) {59                    count += 1;60                }61                if c + 1 < self.side && self.at(r, c + 1) {62                    count += 1;63                }64            }65        }66        count67    }6869    pub fn quads(&self) -> u64 {70        let mut count = 0u64;71        for r in 0..self.side.saturating_sub(1) {72            for c in 0..self.side.saturating_sub(1) {73                if self.at(r, c) && self.at(r + 1, c) && self.at(r, c + 1) && self.at(r + 1, c + 1)74                {75                    count += 1;76                }77            }78        }79        count80    }8182    pub fn interior(&self) -> u64 {83        let mut count = 0u64;84        for r in 0..self.side {85            for c in 0..self.side {86                if !self.at(r, c) {87                    continue;88                }89                let inside = r > 090                    && c > 091                    && r + 1 < self.side92                    && c + 1 < self.side93                    && self.at(r - 1, c)94                    && self.at(r + 1, c)95                    && self.at(r, c - 1)96                    && self.at(r, c + 1);97                if inside {98                    count += 1;99                }100            }101        }102        count103    }104105    pub fn boundary(&self) -> u64 {106        self.fill() - self.interior()107    }108109    pub fn perimeter(&self) -> u64 {110        4 * self.fill() - 2 * self.adjacent()111    }112113    pub fn euler(&self) -> i64 {114        self.fill() as i64 - self.adjacent() as i64 + self.quads() as i64115    }116117    pub fn labels(&self) -> (Vec<i64>, u64) {118        let mut label = vec![-1i64; self.cells.len()];119        let mut count = 0i64;120        let mut stack: Vec<usize> = Vec::new();121        for start in 0..self.cells.len() {122            if !self.cells[start] || label[start] >= 0 {123                continue;124            }125            label[start] = count;126            stack.push(start);127            while let Some(at) = stack.pop() {128                let r = at / self.side;129                let c = at % self.side;130                let push = |rr: usize, cc: usize, label: &mut Vec<i64>, stack: &mut Vec<usize>| {131                    let next = rr * self.side + cc;132                    if self.cells[next] && label[next] < 0 {133                        label[next] = count;134                        stack.push(next);135                    }136                };137                if r > 0 {138                    push(r - 1, c, &mut label, &mut stack);139                }140                if r + 1 < self.side {141                    push(r + 1, c, &mut label, &mut stack);142                }143                if c > 0 {144                    push(r, c - 1, &mut label, &mut stack);145                }146                if c + 1 < self.side {147                    push(r, c + 1, &mut label, &mut stack);148                }149            }150            count += 1;151        }152        (label, count as u64)153    }154155    pub fn components(&self) -> u64 {156        self.labels().1157    }158159    pub fn holes(&self) -> u64 {160        let mut seen = vec![false; self.cells.len()];161        let mut stack: Vec<usize> = Vec::new();162        let open = |at: usize, seen: &mut Vec<bool>, stack: &mut Vec<usize>| {163            if !self.cells[at] && !seen[at] {164                seen[at] = true;165                stack.push(at);166            }167        };168        for i in 0..self.side {169            open(i, &mut seen, &mut stack);170            open((self.side - 1) * self.side + i, &mut seen, &mut stack);171            open(i * self.side, &mut seen, &mut stack);172            open(i * self.side + self.side - 1, &mut seen, &mut stack);173        }174        while let Some(at) = stack.pop() {175            let r = at / self.side;176            let c = at % self.side;177            let step = |rr: usize, cc: usize, seen: &mut Vec<bool>, stack: &mut Vec<usize>| {178                let next = rr * self.side + cc;179                if !self.cells[next] && !seen[next] {180                    seen[next] = true;181                    stack.push(next);182                }183            };184            if r > 0 {185                step(r - 1, c, &mut seen, &mut stack);186            }187            if r + 1 < self.side {188                step(r + 1, c, &mut seen, &mut stack);189            }190            if c > 0 {191                step(r, c - 1, &mut seen, &mut stack);192            }193            if c + 1 < self.side {194                step(r, c + 1, &mut seen, &mut stack);195            }196        }197        let mut count = 0u64;198        for start in 0..self.cells.len() {199            if self.cells[start] || seen[start] {200                continue;201            }202            count += 1;203            seen[start] = true;204            stack.push(start);205            while let Some(at) = stack.pop() {206                let r = at / self.side;207                let c = at % self.side;208                let step = |rr: usize, cc: usize, seen: &mut Vec<bool>, stack: &mut Vec<usize>| {209                    let next = rr * self.side + cc;210                    if !self.cells[next] && !seen[next] {211                        seen[next] = true;212                        stack.push(next);213                    }214                };215                if r > 0 {216                    step(r - 1, c, &mut seen, &mut stack);217                }218                if r + 1 < self.side {219                    step(r + 1, c, &mut seen, &mut stack);220                }221                if c > 0 {222                    step(r, c - 1, &mut seen, &mut stack);223                }224                if c + 1 < self.side {225                    step(r, c + 1, &mut seen, &mut stack);226                }227            }228        }229        count230    }231232    pub fn profile(&self) -> Vec<u64> {233        let mut out = vec![0u64; 2 * self.side - 1];234        for r in 0..self.side {235            for c in 0..self.side {236                if self.at(r, c) {237                    out[r + c] += 1;238                }239            }240        }241        out242    }243244    pub fn contacts(&self) -> (u64, u64) {245        let rows = (0..self.side)246            .filter(|&r| self.at(r, 0) && self.at(r, self.side - 1))247            .count() as u64;248        let cols = (0..self.side)249            .filter(|&c| self.at(0, c) && self.at(self.side - 1, c))250            .count() as u64;251        (rows, cols)252    }253254    pub fn merging(&self) -> u64 {255        let (label, _) = self.labels();256        let mut touched: Vec<i64> = Vec::new();257        let mark = |at: usize, touched: &mut Vec<i64>| {258            if label[at] >= 0 && !touched.contains(&label[at]) {259                touched.push(label[at]);260            }261        };262        for r in 0..self.side {263            if self.at(r, 0) && self.at(r, self.side - 1) {264                mark(r * self.side, &mut touched);265                mark(r * self.side + self.side - 1, &mut touched);266            }267        }268        for c in 0..self.side {269            if self.at(0, c) && self.at(self.side - 1, c) {270                mark(c, &mut touched);271                mark((self.side - 1) * self.side + c, &mut touched);272            }273        }274        touched.len() as u64275    }276}277278#[derive(Clone, PartialEq, Eq)]279pub struct Obs {280    pub fill: u64,281    pub diagonal: u64,282    pub boundary: u64,283    pub perimeter: u64,284    pub components: u64,285    pub euler: i64,286    pub holes: u64,287    pub profile: Vec<u64>,288}289290pub fn observe(word: &[u8]) -> Obs {291    let grid = render(word);292    Obs {293        fill: grid.fill(),294        diagonal: grid.diagonal(),295        boundary: grid.boundary(),296        perimeter: grid.perimeter(),297        components: grid.components(),298        euler: grid.euler(),299        holes: grid.holes(),300        profile: grid.profile(),301    }302}303304pub const SERIES: [&str; 4] = ["components", "Euler characteristic", "boundary", "holes"];305306pub fn series_value(obs: &Obs, which: usize) -> i64 {307    match which {308        0 => obs.components as i64,309        1 => obs.euler,310        2 => obs.boundary as i64,311        _ => obs.holes as i64,312    }313}314315pub fn spell(word: &[u8]) -> String {316    if word.is_empty() {317        return "e".to_string();318    }319    if word.len() == 1 {320        return format!("{}", word[0]);321    }322    let inner: Vec<String> = word.iter().map(|c| format!("{c}")).collect();323    format!("({})", inner.join(","))324}