research-arcs.rs
4.3 kB · rust · 147 lines
1use figures::{ink, save, Board, Grid};2use mrlyrs::core::error::Result;3use mrlyrs::math::bang::factory;4use mrlyrs::math::bang::Code;5use std::f64::consts::{FRAC_PI_2, PI};67const LEVEL: usize = 3;8const SIDE: usize = 27;9const LOOPS: usize = 50;1011struct Dsu {12 parent: Vec<usize>,13}1415impl Dsu {16 fn new(size: usize) -> Dsu {17 Dsu {18 parent: (0..size).collect(),19 }20 }21 fn find(&mut self, mut i: usize) -> usize {22 while self.parent[i] != i {23 self.parent[i] = self.parent[self.parent[i]];24 i = self.parent[i];25 }26 i27 }28 fn union(&mut self, a: usize, b: usize) -> bool {29 let (ra, rb) = (self.find(a), self.find(b));30 if ra == rb {31 return false;32 }33 self.parent[ra] = rb;34 true35 }36}3738fn across(x: usize, y: usize) -> usize {39 y * SIDE + x40}4142fn upright(x: usize, y: usize) -> usize {43 SIDE * (SIDE + 1) + y * (SIDE + 1) + x44}4546fn arcs(filled: bool, x: usize, y: usize) -> [(usize, usize); 2] {47 let (bottom, top) = (across(x, y), across(x, y + 1));48 let (left, right) = (upright(x, y), upright(x + 1, y));49 if filled {50 [(left, bottom), (right, top)]51 } else {52 [(bottom, right), (left, top)]53 }54}5556fn mirrors(filled: &[bool]) -> usize {57 let w = SIDE + 1;58 let mut dsu = Dsu::new(w * w);59 let mut parts = w * w;60 for y in 0..SIDE {61 for x in 0..SIDE {62 let (a, b) = if filled[y * SIDE + x] {63 (y * w + x + 1, (y + 1) * w + x)64 } else {65 (y * w + x, (y + 1) * w + x + 1)66 };67 if dsu.union(a, b) {68 parts -= 1;69 }70 }71 }72 parts - 2 * SIDE - 173}7475fn main() -> Result<()> {76 let design = factory::create(Code::from(495u128), 3, 2, 3, LEVEL)?;77 assert_eq!(design.shape, vec![SIDE, SIDE]);78 assert_eq!(design.sum(), 8u64.pow(LEVEL as u32));79 let parity = factory::create(Code::from(7u128), 3, 2, 2, LEVEL)?;80 assert_eq!(design.bytes()?, parity.bytes()?);81 let filled: Vec<bool> = (0..SIDE * SIDE).map(|f| design.at(f) == 1).collect();8283 let nodes = 2 * SIDE * (SIDE + 1);84 let mut dsu = Dsu::new(nodes);85 let mut degree = vec![0u8; nodes];86 for y in 0..SIDE {87 for x in 0..SIDE {88 for (a, b) in arcs(filled[y * SIDE + x], x, y) {89 degree[a] += 1;90 degree[b] += 1;91 dsu.union(a, b);92 }93 }94 }95 let mut open = vec![false; nodes];96 let mut root = vec![false; nodes];97 for (node, d) in degree.iter().enumerate() {98 let r = dsu.find(node);99 root[r] = true;100 open[r] |= *d == 1;101 }102 let strands = (0..nodes).filter(|&n| root[n] && open[n]).count();103 let loops = (0..nodes).filter(|&n| root[n] && !open[n]).count();104 assert_eq!(degree.iter().filter(|&&d| d == 1).count(), 4 * SIDE);105 assert_eq!(strands, 2 * SIDE);106 assert_eq!(loops, LOOPS);107 assert_eq!(mirrors(&filled), LOOPS);108109 let mut board = Board::square();110 let frame = board.frame(0.08);111 let cell = frame.w / SIDE as f64;112 let thick = cell * 0.15;113 let radius = cell / 2.0;114 let grid = Grid::new(frame, SIDE, SIDE, 0.0);115 for y in 0..SIDE {116 for x in 0..SIDE {117 if filled[y * SIDE + x] {118 grid.fill(&mut board, x, SIDE - 1 - y, ink::line());119 }120 }121 }122 for y in 0..SIDE {123 for x in 0..SIDE {124 let on = filled[y * SIDE + x];125 let left = frame.x + x as f64 * cell;126 let top = frame.y + (SIDE - 1 - y) as f64 * cell;127 let sweeps = if on {128 [129 ((left, top + cell), (-FRAC_PI_2, 0.0)),130 ((left + cell, top), (FRAC_PI_2, PI)),131 ]132 } else {133 [134 ((left + cell, top + cell), (PI, PI + FRAC_PI_2)),135 ((left, top), (0.0, FRAC_PI_2)),136 ]137 };138 for ((a, _), (centre, angles)) in arcs(on, x, y).into_iter().zip(sweeps) {139 let r = dsu.find(a);140 let color = if open[r] { ink::blue() } else { ink::orange() };141 board.arc(centre, radius, angles, thick, color);142 }143 }144 }145 save("research-arcs", &board)?;146 Ok(())147}