wiki-burnsides-lemma.rs

1use mrlycore::errors::Result;2use mrlyfig::{ink, save, Board};34const CELLS: usize = 4;5const PATTERNS: usize = 16;6const CLASSES: usize = 6;7const FIXED: usize = 48;89fn moves() -> [[usize; CELLS]; 8] {10    let seat = |row: usize, col: usize| 2 * row + col;11    let mut out = [[0usize; CELLS]; 8];12    for row in 0..2 {13        for col in 0..2 {14            let from = seat(row, col);15            out[0][from] = seat(row, col);16            out[1][from] = seat(col, 1 - row);17            out[2][from] = seat(1 - row, 1 - col);18            out[3][from] = seat(1 - col, row);19            out[4][from] = seat(row, 1 - col);20            out[5][from] = seat(1 - row, col);21            out[6][from] = seat(col, row);22            out[7][from] = seat(1 - col, 1 - row);23        }24    }25    out26}2728fn act(mask: usize, plan: &[usize; CELLS]) -> usize {29    (0..CELLS).filter(|&i| mask >> i & 1 == 1).fold(0, |acc, i| acc | 1 << plan[i])30}3132fn main() -> Result<()> {33    let plans = moves();34    let fixed: usize = plans35        .iter()36        .map(|plan| (0..PATTERNS).filter(|&mask| act(mask, plan) == mask).count())37        .sum();38    assert_eq!(fixed, FIXED);39    assert_eq!(fixed / plans.len(), CLASSES);40    let mut seen = [false; PATTERNS];41    let mut classes: Vec<Vec<usize>> = Vec::new();42    for mask in 0..PATTERNS {43        if seen[mask] {44            continue;45        }46        let mut orbit: Vec<usize> = plans.iter().map(|plan| act(mask, plan)).collect();47        orbit.sort_unstable();48        orbit.dedup();49        for &member in &orbit {50            seen[member] = true;51        }52        classes.push(orbit);53    }54    assert_eq!(classes.len(), CLASSES);55    assert_eq!(classes.iter().map(Vec::len).sum::<usize>(), PATTERNS);56    classes.sort_by_key(|orbit| (orbit[0].count_ones(), PATTERNS - orbit.len()));57    let mut board = Board::square();58    let frame = board.frame(0.08);59    let rows = frame.rows(CLASSES);60    let widest = classes.iter().map(Vec::len).max().unwrap_or(1);61    let slot = frame.w / widest as f64;62    let stamp = (slot * 0.62).min(rows[0].h * 0.74);63    let pad = stamp * 0.06;64    for (class, row) in classes.iter().zip(rows.iter()) {65        let run = class.len() as f64 * slot;66        let left = row.x + (row.w - run) / 2.0;67        let top = row.y + (row.h - stamp) / 2.0;68        for (place, &mask) in class.iter().enumerate() {69            let x = left + place as f64 * slot + (slot - stamp) / 2.0;70            let half = (stamp - pad) / 2.0;71            for cell in 0..CELLS {72                let tone = if mask >> cell & 1 == 1 {73                    ink::blue()74                } else {75                    ink::dim()76                };77                board.rect(78                    x + (cell % 2) as f64 * (half + pad),79                    top + (cell / 2) as f64 * (half + pad),80                    half,81                    half,82                    tone,83                );84            }85        }86    }87    save("wiki-burnsides-lemma", &board)?;88    Ok(())89}