witness.rs

1use crate::tile::{2    cuts, factorisations, gcd, incomparable, kron, lcm, line_cuts, line_kron, mask_tile, profile,3    unpack, Tile,4};5use std::collections::BTreeSet;67pub fn from_cells(side: usize, cells: &[(usize, usize)]) -> Tile {8    let mut tile = Tile::new(side);9    for (r, c) in cells {10        tile.set(*r, *c);11    }12    tile13}1415pub fn identity(side: usize) -> Tile {16    let cells: Vec<(usize, usize)> = (0..side).map(|i| (i, i)).collect();17    from_cells(side, &cells)18}1920pub fn antidiagonal(side: usize) -> Tile {21    let cells: Vec<(usize, usize)> = (0..side).map(|i| (i, side - 1 - i)).collect();22    from_cells(side, &cells)23}2425pub fn gcd_closed(list: &[usize]) -> bool {26    let set: BTreeSet<usize> = list.iter().copied().collect();27    for a in &set {28        for b in &set {29            if !set.contains(&gcd(*a, *b)) {30                return false;31            }32        }33    }34    true35}3637pub fn lcm_closed(list: &[usize], side: usize) -> bool {38    let set: BTreeSet<usize> = list.iter().copied().collect();39    for a in &set {40        for b in &set {41            let value = lcm(*a, *b);42            if value <= side && !set.contains(&value) {43                return false;44            }45        }46    }47    true48}4950pub struct LineClosure {51    pub gcd_violations: usize,52    pub lcm_violations: usize,53    pub first_lcm: Option<(usize, u128, Vec<usize>)>,54}5556pub fn line_closure(max_side: usize) -> LineClosure {57    let mut out = LineClosure {58        gcd_violations: 0,59        lcm_violations: 0,60        first_lcm: None,61    };62    for side in 1..=max_side {63        for mask in 1u128..1u128 << side {64            let list = line_cuts(mask, side);65            if !gcd_closed(&list) {66                out.gcd_violations += 1;67            }68            if !lcm_closed(&list, side) {69                out.lcm_violations += 1;70                if out.first_lcm.is_none() {71                    out.first_lcm = Some((side, mask, list.clone()));72                }73            }74        }75    }76    out77}7879pub fn line_commuting(m: usize, n: usize) -> Vec<(u128, u128)> {80    let mut out = Vec::new();81    for a in 1u128..1u128 << m {82        for b in 1u128..1u128 << n {83            if line_kron(a, m, b, n) == line_kron(b, n, a, m) {84                out.push((a, b));85            }86        }87    }88    out89}9091pub struct TwelveSweep {92    pub tiles: usize,93    pub gcd_violations: usize,94    pub lcm_violations: usize,95    pub mismatches: usize,96    pub multiple: usize,97    pub unequal_length: usize,98    pub max_factorisations: usize,99}100101pub fn twelve_sweep(six: &[u64]) -> TwelveSweep {102    let small: Vec<Tile> = (1u32..16).map(|c| mask_tile(c as u64, 2)).collect();103    let mut out = TwelveSweep {104        tiles: 0,105        gcd_violations: 0,106        lcm_violations: 0,107        mismatches: 0,108        multiple: 0,109        unequal_length: 0,110        max_factorisations: 0,111    };112    let mut seen: std::collections::HashSet<[u64; 3]> = std::collections::HashSet::new();113    for key in six {114        let inner = unpack(*key, 6);115        for code in &small {116            for whole in [kron(code, &inner), kron(&inner, code)] {117                if !seen.insert(whole.key()) {118                    continue;119                }120                out.tiles += 1;121                let list = cuts(&whole);122                if !gcd_closed(&list) {123                    out.gcd_violations += 1;124                }125                if !lcm_closed(&list, 12) {126                    out.lcm_violations += 1;127                }128                let words = factorisations(&whole);129                out.max_factorisations = out.max_factorisations.max(words.len());130                let many = words.len() > 1;131                if many {132                    out.multiple += 1;133                }134                if many != incomparable(&list) {135                    out.mismatches += 1;136                }137                let lengths: BTreeSet<usize> = words.iter().map(|word| word.len()).collect();138                if lengths.len() > 1 {139                    out.unequal_length += 1;140                }141            }142        }143    }144    out145}146147pub fn profiles_text(tile: &Tile) -> String {148    let mut rows: Vec<String> = factorisations(tile)149        .iter()150        .map(|word| {151            let sides: Vec<String> = profile(word).iter().map(|s| format!("{s}")).collect();152            format!("({})", sides.join(" x "))153        })154        .collect();155    rows.sort();156    rows.join(" ")157}