census.rs
11.4 kB · rust · 383 lines
1use crate::tile::{kron, mask_tile, separable, split, unpack, Tile};2use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};34pub fn codes(base: usize) -> Vec<u32> {5 let total = 1u32 << (base * base);6 (1..total).collect()7}89pub struct SideFour {10 pub products: usize,11 pub distinct: usize,12 pub max_preimage: usize,13 pub by_product: HashSet<u64>,14 pub by_block: HashSet<u64>,15}1617pub fn side_four() -> SideFour {18 let mut counts: HashMap<u64, usize> = HashMap::new();19 let mut products = 0usize;20 for a in codes(2) {21 let outer = mask_tile(a as u64, 2);22 for b in codes(2) {23 let inner = mask_tile(b as u64, 2);24 let whole = kron(&outer, &inner);25 *counts.entry(whole.pack()).or_insert(0) += 1;26 products += 1;27 }28 }29 let by_product: HashSet<u64> = counts.keys().copied().collect();30 let max_preimage = counts.values().copied().max().unwrap_or(0);31 let distinct = by_product.len();32 let mut by_block: HashSet<u64> = HashSet::new();33 for mask in 1u64..1 << 16 {34 let tile = mask_tile(mask, 4);35 if split(&tile, 2).is_some() {36 by_block.insert(mask);37 }38 }39 SideFour {40 products,41 distinct,42 max_preimage,43 by_product,44 by_block,45 }46}4748pub struct SideSix {49 pub image23: HashMap<u64, (u32, u32)>,50 pub image32: HashMap<u64, (u32, u32)>,51 pub collisions23: usize,52 pub collisions32: usize,53 pub cross: Vec<u64>,54 pub reducible: Vec<u64>,55}5657pub fn side_six() -> SideSix {58 let mut image23: HashMap<u64, (u32, u32)> = HashMap::new();59 let mut collisions23 = 0usize;60 for a in codes(2) {61 let outer = mask_tile(a as u64, 2);62 for b in codes(3) {63 let inner = mask_tile(b as u64, 3);64 let key = kron(&outer, &inner).pack();65 if image23.insert(key, (a, b)).is_some() {66 collisions23 += 1;67 }68 }69 }70 let mut image32: HashMap<u64, (u32, u32)> = HashMap::new();71 let mut collisions32 = 0usize;72 for a in codes(3) {73 let outer = mask_tile(a as u64, 3);74 for b in codes(2) {75 let inner = mask_tile(b as u64, 2);76 let key = kron(&outer, &inner).pack();77 if image32.insert(key, (a, b)).is_some() {78 collisions32 += 1;79 }80 }81 }82 let mut cross: Vec<u64> = image2383 .keys()84 .copied()85 .filter(|key| image32.contains_key(key))86 .collect();87 cross.sort_unstable();88 let mut union: BTreeSet<u64> = image23.keys().copied().collect();89 union.extend(image32.keys().copied());90 let reducible: Vec<u64> = union.into_iter().collect();91 SideSix {92 image23,93 image32,94 collisions23,95 collisions32,96 cross,97 reducible,98 }99}100101pub struct CrossAnatomy {102 pub separable: usize,103 pub non_separable: usize,104 pub commuting: usize,105 pub rewriting: usize,106 pub non_separable_non_commuting: usize,107 pub non_separable_commuting: Vec<(u32, u32)>,108 pub fills: BTreeMap<usize, usize>,109 pub fills_non_separable: BTreeMap<usize, usize>,110 pub outer_fills: BTreeMap<(usize, usize), usize>,111 pub one_cell_any: BTreeMap<usize, usize>,112 pub one_cell_any_non_separable: BTreeMap<usize, usize>,113 pub one_cell_outer: BTreeMap<usize, usize>,114 pub one_cell_outer_non_separable: BTreeMap<usize, usize>,115 pub commuting_pairs: Vec<(u32, u32)>,116 pub separable_set: HashSet<u64>,117 pub set_non_commuting: HashSet<u64>,118 pub set_one_any: HashSet<u64>,119 pub set_one_outer: HashSet<u64>,120}121122pub fn cross_anatomy(six: &SideSix) -> CrossAnatomy {123 let mut out = CrossAnatomy {124 separable: 0,125 non_separable: 0,126 commuting: 0,127 rewriting: 0,128 non_separable_non_commuting: 0,129 non_separable_commuting: Vec::new(),130 fills: BTreeMap::new(),131 fills_non_separable: BTreeMap::new(),132 outer_fills: BTreeMap::new(),133 one_cell_any: BTreeMap::new(),134 one_cell_any_non_separable: BTreeMap::new(),135 one_cell_outer: BTreeMap::new(),136 one_cell_outer_non_separable: BTreeMap::new(),137 commuting_pairs: Vec::new(),138 separable_set: HashSet::new(),139 set_non_commuting: HashSet::new(),140 set_one_any: HashSet::new(),141 set_one_outer: HashSet::new(),142 };143 for key in &six.cross {144 let tile = unpack(*key, 6);145 let (a2, b3) = six.image23[key];146 let (x3, y2) = six.image32[key];147 let flat = separable(&tile);148 let commutes = a2 == y2 && b3 == x3;149 let fill_a2 = mask_tile(a2 as u64, 2).fill();150 let fill_b3 = mask_tile(b3 as u64, 3).fill();151 let fill_x3 = mask_tile(x3 as u64, 3).fill();152 let fill_y2 = mask_tile(y2 as u64, 2).fill();153 if flat {154 out.separable += 1;155 out.separable_set.insert(*key);156 } else {157 out.non_separable += 1;158 }159 if commutes {160 out.commuting += 1;161 out.commuting_pairs.push((a2, b3));162 } else {163 out.rewriting += 1;164 }165 if !flat && !commutes {166 out.non_separable_non_commuting += 1;167 }168 if !flat && commutes {169 out.non_separable_commuting.push((a2, b3));170 }171 *out.fills.entry(tile.fill()).or_insert(0) += 1;172 if !flat {173 *out.fills_non_separable.entry(tile.fill()).or_insert(0) += 1;174 let low = fill_a2.min(fill_x3);175 let high = fill_a2.max(fill_x3);176 *out.outer_fills.entry((low, high)).or_insert(0) += 1;177 }178 let any =179 usize::from(fill_a2 == 1 || fill_b3 == 1) + usize::from(fill_x3 == 1 || fill_y2 == 1);180 let outer = usize::from(fill_a2 == 1) + usize::from(fill_x3 == 1);181 *out.one_cell_any.entry(any).or_insert(0) += 1;182 *out.one_cell_outer.entry(outer).or_insert(0) += 1;183 if !flat {184 *out.one_cell_any_non_separable.entry(any).or_insert(0) += 1;185 *out.one_cell_outer_non_separable.entry(outer).or_insert(0) += 1;186 if !commutes {187 out.set_non_commuting.insert(*key);188 }189 if any > 0 {190 out.set_one_any.insert(*key);191 }192 if outer > 0 {193 out.set_one_outer.insert(*key);194 }195 }196 }197 out.commuting_pairs.sort_unstable();198 out.non_separable_commuting.sort_unstable();199 out200}201202pub fn two_radix_lines() -> Vec<Vec<usize>> {203 let mut out: Vec<Vec<usize>> = Vec::new();204 for mask in 1u128..1 << 6 {205 let up = crate::tile::line_split(mask, 6, 2).is_some();206 let down = crate::tile::line_split(mask, 6, 3).is_some();207 if up && down {208 out.push((0..6).filter(|i| (mask >> i) & 1 == 1).collect());209 }210 }211 out212}213214pub fn rectangle_set() -> HashSet<u64> {215 let lines: Vec<u128> = (1u128..1 << 6)216 .filter(|mask| {217 crate::tile::line_split(*mask, 6, 2).is_some()218 && crate::tile::line_split(*mask, 6, 3).is_some()219 })220 .collect();221 let mut out = HashSet::new();222 for rows in &lines {223 for cols in &lines {224 let mut tile = Tile::new(6);225 for r in 0..6 {226 if (rows >> r) & 1 == 0 {227 continue;228 }229 for c in 0..6 {230 if (cols >> c) & 1 == 1 {231 tile.set(r, c);232 }233 }234 }235 out.insert(tile.pack());236 }237 }238 out239}240241pub struct SideEight {242 pub image24: usize,243 pub image42: usize,244 pub intersection: usize,245 pub triples_match: bool,246}247248pub fn side_eight() -> SideEight {249 let small: Vec<Tile> = codes(2)250 .into_iter()251 .map(|c| mask_tile(c as u64, 2))252 .collect();253 let mut image24: HashSet<u64> = HashSet::new();254 let mut image42: HashSet<u64> = HashSet::new();255 for mask in 1u64..1 << 16 {256 let big = mask_tile(mask, 4);257 for tile in &small {258 image24.insert(kron(tile, &big).pack());259 image42.insert(kron(&big, tile).pack());260 }261 }262 let intersection: HashSet<u64> = image24.intersection(&image42).copied().collect();263 let mut triples: HashSet<u64> = HashSet::new();264 for x in &small {265 for y in &small {266 for z in &small {267 triples.insert(kron(&kron(x, y), z).pack());268 }269 }270 }271 SideEight {272 image24: image24.len(),273 image42: image42.len(),274 intersection: intersection.len(),275 triples_match: triples == intersection,276 }277}278279pub struct SideNine {280 pub products: usize,281 pub distinct: usize,282 pub collisions: usize,283}284285pub fn side_nine() -> SideNine {286 let mut seen: HashSet<u128> = HashSet::new();287 let mut products = 0usize;288 let mut collisions = 0usize;289 let tiles: Vec<Tile> = codes(3)290 .into_iter()291 .map(|c| mask_tile(c as u64, 3))292 .collect();293 for outer in &tiles {294 for inner in &tiles {295 let whole = kron(outer, inner);296 let mut key = 0u128;297 for (index, cell) in whole.cells.iter().enumerate() {298 if *cell {299 key |= 1u128 << index;300 }301 }302 products += 1;303 if !seen.insert(key) {304 collisions += 1;305 }306 }307 }308 SideNine {309 products,310 distinct: seen.len(),311 collisions,312 }313}314315pub struct WordTwelve {316 pub per_shape: usize,317 pub distinct: [usize; 3],318 pub pairs: [usize; 3],319 pub triple: usize,320 pub union: usize,321 pub witness_shapes: [bool; 3],322}323324pub fn word_twelve(witness: &Tile) -> WordTwelve {325 let two: Vec<Tile> = codes(2)326 .into_iter()327 .map(|c| mask_tile(c as u64, 2))328 .collect();329 let three: Vec<Tile> = codes(3)330 .into_iter()331 .map(|c| mask_tile(c as u64, 3))332 .collect();333 let mut sets: Vec<HashSet<[u64; 3]>> = Vec::new();334 let shapes: [[usize; 3]; 3] = [[2, 2, 3], [2, 3, 2], [3, 2, 2]];335 let mut per_shape = 0usize;336 for shape in shapes {337 let mut set: HashSet<[u64; 3]> = HashSet::new();338 let mut count = 0usize;339 let pick = |side: usize| -> &Vec<Tile> {340 if side == 2 {341 &two342 } else {343 &three344 }345 };346 for a in pick(shape[0]) {347 for b in pick(shape[1]) {348 let left = kron(a, b);349 for c in pick(shape[2]) {350 set.insert(kron(&left, c).key());351 count += 1;352 }353 }354 }355 per_shape = count;356 sets.push(set);357 }358 let distinct = [sets[0].len(), sets[1].len(), sets[2].len()];359 let pairs = [360 sets[0].intersection(&sets[1]).count(),361 sets[1].intersection(&sets[2]).count(),362 sets[0].intersection(&sets[2]).count(),363 ];364 let triple = sets[0]365 .iter()366 .filter(|key| sets[1].contains(*key) && sets[2].contains(*key))367 .count();368 let union = distinct[0] + distinct[1] + distinct[2] - pairs[0] - pairs[1] - pairs[2] + triple;369 let key = witness.key();370 let witness_shapes = [371 sets[0].contains(&key),372 sets[1].contains(&key),373 sets[2].contains(&key),374 ];375 WordTwelve {376 per_shape,377 distinct,378 pairs,379 triple,380 union,381 witness_shapes,382 }383}