wiki-rep-tiles.rs

1use figures::{ink, save, Board};2use mrlyrs::core::error::Result;3use std::collections::HashSet;45const DEPTH: usize = 3;6const GAPS: [f64; DEPTH] = [16.0, 8.0, 3.0];7const SPHINX: [[(i64, i64); 3]; 6] = [8    [(0, 0), (1, 0), (0, 1)],9    [(1, 0), (2, 0), (1, 1)],10    [(2, 0), (3, 0), (2, 1)],11    [(1, 0), (0, 1), (1, 1)],12    [(2, 0), (1, 1), (2, 1)],13    [(0, 1), (1, 1), (0, 2)],14];15const OUTLINE: [(i64, i64); 5] = [(0, 0), (3, 0), (2, 1), (1, 1), (0, 2)];16const ID: Mat = [[1, 0], [0, 1]];17const TURN: Mat = [[0, -1], [1, 1]];18const MIRROR: Mat = [[1, 1], [0, -1]];1920type Mat = [[i64; 2]; 2];21type Point = (i64, i64);2223#[derive(Clone, Copy)]24struct Tile {25    m: Mat,26    t: Point,27}2829fn mul(a: Mat, b: Mat) -> Mat {30    let cell = |i: usize, j: usize| a[i][0] * b[0][j] + a[i][1] * b[1][j];31    [[cell(0, 0), cell(0, 1)], [cell(1, 0), cell(1, 1)]]32}3334fn apply(m: Mat, p: Point) -> Point {35    (m[0][0] * p.0 + m[0][1] * p.1, m[1][0] * p.0 + m[1][1] * p.1)36}3738fn det(m: Mat) -> i64 {39    m[0][0] * m[1][1] - m[0][1] * m[1][0]40}4142fn place(tile: Tile, p: Point) -> Point {43    let q = apply(tile.m, p);44    (q.0 + tile.t.0, q.1 + tile.t.1)45}4647fn key(tri: [Point; 3]) -> Point {48    (49        tri[0].0 + tri[1].0 + tri[2].0,50        tri[0].1 + tri[1].1 + tri[2].1,51    )52}5354fn split(tri: [Point; 3]) -> [[Point; 3]; 4] {55    let [p, q, r] = tri;56    let two = |a: Point| (2 * a.0, 2 * a.1);57    let sum = |a: Point, b: Point| (a.0 + b.0, a.1 + b.1);58    let (pq, qr, pr) = (sum(p, q), sum(q, r), sum(p, r));59    [60        [two(p), pq, pr],61        [two(q), pq, qr],62        [two(r), pr, qr],63        [pq, qr, pr],64    ]65}6667fn cells(tile: Tile) -> Vec<Point> {68    SPHINX69        .iter()70        .map(|tri| key(tri.map(|p| place(tile, p))))71        .collect()72}7374fn cover(75    target: &HashSet<Point>,76    pieces: &[(Tile, Vec<Point>)],77    used: &mut Vec<usize>,78    found: &mut Vec<Vec<usize>>,79) {80    let covered: HashSet<Point> = used81        .iter()82        .flat_map(|&i| pieces[i].1.iter().copied())83        .collect();84    let Some(&first) = target.iter().filter(|c| !covered.contains(c)).min() else {85        found.push(used.clone());86        return;87    };88    for (i, (_, keys)) in pieces.iter().enumerate() {89        if keys.contains(&first) && keys.iter().all(|k| !covered.contains(k)) {90            used.push(i);91            cover(target, pieces, used, found);92            used.pop();93        }94    }95}9697fn main() -> Result<()> {98    let doubled: HashSet<Point> = SPHINX.iter().flat_map(|&tri| split(tri)).map(key).collect();99    assert_eq!(doubled.len(), 24);100    let mut pieces = Vec::new();101    for flip in [ID, MIRROR] {102        let mut m = flip;103        for _ in 0..6 {104            for a in -8..=8 {105                for b in -8..=8 {106                    let tile = Tile { m, t: (a, b) };107                    let keys = cells(tile);108                    if keys.iter().all(|k| doubled.contains(k)) {109                        pieces.push((tile, keys));110                    }111                }112            }113            m = mul(TURN, m);114        }115    }116    let mut found = Vec::new();117    cover(&doubled, &pieces, &mut Vec::new(), &mut found);118    assert_eq!(found.len(), 1);119    let rule: Vec<Tile> = found[0].iter().map(|&i| pieces[i].0).collect();120    assert_eq!(rule.len(), 4);121    assert_eq!(rule.iter().filter(|c| det(c.m) < 0).count(), 3);122123    let mut levels = vec![vec![Tile { m: ID, t: (0, 0) }]];124    for _ in 0..DEPTH {125        let next: Vec<Tile> = levels126            .last()127            .unwrap()128            .iter()129            .flat_map(|p| {130                rule.iter().map(move |c| {131                    let shift = apply(p.m, c.t);132                    Tile {133                        m: mul(p.m, c.m),134                        t: (shift.0 + 2 * p.t.0, shift.1 + 2 * p.t.1),135                    }136                })137            })138            .collect();139        levels.push(next);140    }141    let counts: Vec<usize> = levels.iter().map(Vec::len).collect();142    assert_eq!(counts, vec![1, 4, 16, 64]);143    let leaves = &levels[DEPTH];144    let direct = leaves.iter().filter(|c| det(c.m) > 0).count();145    assert_eq!((direct, leaves.len() - direct), (28, 36));146    let mut fine: Vec<[Point; 3]> = SPHINX.to_vec();147    for _ in 0..DEPTH {148        fine = fine.into_iter().flat_map(split).collect();149    }150    let fine: HashSet<Point> = fine.into_iter().map(key).collect();151    let mut laid = HashSet::new();152    for c in leaves {153        for k in cells(*c) {154            assert!(laid.insert(k));155        }156    }157    assert_eq!(laid.len(), 6 * 64);158    assert_eq!(laid, fine);159160    let mut board = Board::square();161    let frame = board.frame(0.08);162    let rise = 3f64.sqrt() / 2.0;163    let px = frame.w / 3.0;164    let top = frame.y + (frame.h - 2.0 * rise * px) / 2.0;165    let outline = |tile: &Tile, depth: usize| -> Vec<(f64, f64)> {166        let scale = (1 << depth) as f64;167        OUTLINE168            .iter()169            .map(|&p| {170                let (a, b) = place(*tile, p);171                let (a, b) = (a as f64 / scale, b as f64 / scale);172                (173                    frame.x + (a + b / 2.0) * px,174                    top + (2.0 * rise - b * rise) * px,175                )176            })177            .collect()178    };179    for c in leaves {180        let color = if det(c.m) > 0 {181            ink::blue()182        } else {183            ink::orange()184        };185        board.polygon(&outline(c, DEPTH), color);186    }187    for depth in (1..=DEPTH).rev() {188        for c in &levels[depth] {189            let mut ring = outline(c, depth);190            ring.push(ring[0]);191            board.polyline(&ring, GAPS[depth - 1], ink::ground());192        }193    }194    save("wiki-rep-tiles", &board)?;195    Ok(())196}