tile.rs

1use std::collections::BTreeSet;23#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]4pub struct Tile {5    pub side: usize,6    pub cells: Vec<bool>,7}89impl Tile {10    pub fn new(side: usize) -> Tile {11        Tile {12            side,13            cells: vec![false; side * side],14        }15    }1617    pub fn at(&self, r: usize, c: usize) -> bool {18        self.cells[r * self.side + c]19    }2021    pub fn set(&mut self, r: usize, c: usize) {22        let side = self.side;23        self.cells[r * side + c] = true;24    }2526    pub fn fill(&self) -> usize {27        self.cells.iter().filter(|cell| **cell).count()28    }2930    pub fn empty(&self) -> bool {31        !self.cells.iter().any(|cell| *cell)32    }3334    pub fn pack(&self) -> u64 {35        let mut key = 0u64;36        for (index, cell) in self.cells.iter().enumerate() {37            if *cell {38                key |= 1u64 << index;39            }40        }41        key42    }4344    pub fn key(&self) -> [u64; 3] {45        let mut key = [0u64; 3];46        for (index, cell) in self.cells.iter().enumerate() {47            if *cell {48                key[index / 64] |= 1u64 << (index % 64);49            }50        }51        key52    }5354    pub fn support(&self) -> Vec<(usize, usize)> {55        let mut out = Vec::new();56        for r in 0..self.side {57            for c in 0..self.side {58                if self.at(r, c) {59                    out.push((r, c));60                }61            }62        }63        out64    }6566    pub fn text(&self) -> String {67        let cells: Vec<String> = self68            .support()69            .iter()70            .map(|(r, c)| format!("({r},{c})"))71            .collect();72        format!("[{}]{{{}}}", self.side, cells.join(","))73    }74}7576pub fn mask_tile(mask: u64, side: usize) -> Tile {77    let mut tile = Tile::new(side);78    for index in 0..side * side {79        if (mask >> index) & 1 == 1 {80            tile.set(index / side, index % side);81        }82    }83    tile84}8586pub fn unpack(key: u64, side: usize) -> Tile {87    mask_tile(key, side)88}8990pub fn kron(outer: &Tile, inner: &Tile) -> Tile {91    let side = outer.side * inner.side;92    let mut out = Tile::new(side);93    let n = inner.side;94    for i in 0..outer.side {95        for j in 0..outer.side {96            if !outer.at(i, j) {97                continue;98            }99            for p in 0..n {100                for q in 0..n {101                    if inner.at(p, q) {102                        out.set(i * n + p, j * n + q);103                    }104                }105            }106        }107    }108    out109}110111pub fn divisors(n: usize) -> Vec<usize> {112    (1..=n).filter(|d| n % d == 0).collect()113}114115pub fn split(tile: &Tile, d: usize) -> Option<(Tile, Tile)> {116    if tile.side % d != 0 {117        return None;118    }119    let n = tile.side / d;120    let mut outer = Tile::new(d);121    let mut inner: Option<Tile> = None;122    for i in 0..d {123        for j in 0..d {124            let mut block = Tile::new(n);125            let mut live = false;126            for p in 0..n {127                for q in 0..n {128                    if tile.at(i * n + p, j * n + q) {129                        block.set(p, q);130                        live = true;131                    }132                }133            }134            if !live {135                continue;136            }137            outer.set(i, j);138            match &inner {139                None => inner = Some(block),140                Some(first) => {141                    if *first != block {142                        return None;143                    }144                }145            }146        }147    }148    inner.map(|block| (outer, block))149}150151pub fn cuts(tile: &Tile) -> Vec<usize> {152    divisors(tile.side)153        .into_iter()154        .filter(|d| split(tile, *d).is_some())155        .collect()156}157158pub fn irreducible(tile: &Tile) -> bool {159    if tile.side < 2 || tile.empty() {160        return false;161    }162    !divisors(tile.side)163        .into_iter()164        .any(|d| d > 1 && d < tile.side && split(tile, d).is_some())165}166167pub fn separable(tile: &Tile) -> bool {168    let mut rows = BTreeSet::new();169    let mut cols = BTreeSet::new();170    for (r, c) in tile.support() {171        rows.insert(r);172        cols.insert(c);173    }174    rows.len() * cols.len() == tile.fill()175}176177pub fn factorisations(tile: &Tile) -> Vec<Vec<Tile>> {178    let mut out: Vec<Vec<Tile>> = Vec::new();179    let mut found = false;180    for d in divisors(tile.side) {181        if d == 1 || d == tile.side {182            continue;183        }184        if let Some((outer, inner)) = split(tile, d) {185            found = true;186            for left in factorisations(&outer) {187                for right in factorisations(&inner) {188                    let mut whole = left.clone();189                    whole.extend(right.iter().cloned());190                    if !out.contains(&whole) {191                        out.push(whole);192                    }193                }194            }195        }196    }197    if !found {198        out.push(vec![tile.clone()]);199    }200    out201}202203pub fn profile(word: &[Tile]) -> Vec<usize> {204    word.iter().map(|tile| tile.side).collect()205}206207pub fn chain(word: &[Tile]) -> Vec<usize> {208    let mut out = vec![1usize];209    let mut run = 1usize;210    for tile in word {211        run *= tile.side;212        out.push(run);213    }214    out215}216217pub fn totally_ordered(set: &BTreeSet<usize>) -> bool {218    let list: Vec<usize> = set.iter().copied().collect();219    for i in 0..list.len() {220        for j in i + 1..list.len() {221            if list[j] % list[i] != 0 {222                return false;223            }224        }225    }226    true227}228229pub fn incomparable(list: &[usize]) -> bool {230    for i in 0..list.len() {231        for j in i + 1..list.len() {232            if list[j] % list[i] != 0 && list[i] % list[j] != 0 {233                return true;234            }235        }236    }237    false238}239240pub fn gcd(a: usize, b: usize) -> usize {241    if b == 0 {242        a243    } else {244        gcd(b, a % b)245    }246}247248pub fn lcm(a: usize, b: usize) -> usize {249    a / gcd(a, b) * b250}251252pub fn line_kron(outer: u128, outer_side: usize, inner: u128, inner_side: usize) -> u128 {253    let mut out = 0u128;254    for i in 0..outer_side {255        if (outer >> i) & 1 == 0 {256            continue;257        }258        for p in 0..inner_side {259            if (inner >> p) & 1 == 1 {260                out |= 1u128 << (i * inner_side + p);261            }262        }263    }264    out265}266267pub fn line_split(mask: u128, side: usize, d: usize) -> Option<(u128, u128)> {268    if side % d != 0 {269        return None;270    }271    let n = side / d;272    let full = if n >= 128 {273        u128::MAX274    } else {275        (1u128 << n) - 1276    };277    let mut outer = 0u128;278    let mut inner: Option<u128> = None;279    for i in 0..d {280        let block = (mask >> (i * n)) & full;281        if block == 0 {282            continue;283        }284        outer |= 1u128 << i;285        match inner {286            None => inner = Some(block),287            Some(first) => {288                if first != block {289                    return None;290                }291            }292        }293    }294    inner.map(|block| (outer, block))295}296297pub fn line_cuts(mask: u128, side: usize) -> Vec<usize> {298    divisors(side)299        .into_iter()300        .filter(|d| line_split(mask, side, *d).is_some())301        .collect()302}303304pub fn line_reducible(mask: u128, side: usize) -> bool {305    divisors(side)306        .into_iter()307        .any(|d| d > 1 && d < side && line_split(mask, side, d).is_some())308}309310pub fn line_text(mask: u128, side: usize) -> String {311    let cells: Vec<String> = (0..side)312        .filter(|i| (mask >> i) & 1 == 1)313        .map(|i| format!("{i}"))314        .collect();315    format!("{{{}}}", cells.join(","))316}