sokoban-elements 0.2.1

use std::collections::{HashMap, HashSet};

use sokoban_elements::{GameBoard, MirrorAxis, Rotation, Tessellation, TileKind, TileShape};

const ALL: [Tessellation; 4] = [
    Tessellation::Sokoban,
    Tessellation::Hexoban,
    Tessellation::Trioban,
    Tessellation::Octoban,
];

fn neighbors(t: Tessellation, x: usize, y: usize, w: usize, h: usize) -> HashSet<(usize, usize)> {
    t.known_directions()
        .iter()
        .filter_map(|d| t.neighbor(x, y, *d, w, h))
        .collect()
}

/// Verify `map` is a geometric symmetry: injective, and the neighbourhood of every mapped cell,
/// restricted to the image, is exactly the image of that cell's neighbourhood.
fn check(
    t: Tessellation, w: usize, h: usize, w2: usize, h2: usize,
    map: &dyn Fn(usize, usize) -> (usize, usize),
) -> Result<(), String> {
    let mut image: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    for y in 0..h {
        for x in 0..w {
            let p = map(x, y);
            if p.0 >= w2 || p.1 >= h2 {
                return Err(format!("({x},{y}) -> {p:?} outside {w2}x{h2}"));
            }
            if let Some(old) = image.insert(p, (x, y)) {
                return Err(format!("not injective: {old:?} and ({x},{y}) both -> {p:?}"));
            }
        }
    }
    let img: HashSet<(usize, usize)> = image.keys().copied().collect();

    for y in 0..h {
        for x in 0..w {
            let src = neighbors(t, x, y, w, h);
            let mapped: HashSet<(usize, usize)> = src.iter().map(|(a, b)| map(*a, *b)).collect();
            let p = map(x, y);
            let dst: HashSet<(usize, usize)> = neighbors(t, p.0, p.1, w2, h2)
                .into_iter()
                .filter(|q| img.contains(q))
                .collect();
            if mapped != dst {
                let lost: Vec<_> = mapped.difference(&dst).collect();
                let gained: Vec<_> = dst.difference(&mapped).collect();
                return Err(format!(
                    "({x},{y})->{p:?}: lost neighbours {lost:?}, gained {gained:?}"
                ));
            }
        }
    }
    Ok(())
}

fn report(label: &str, r: Result<(), String>) {
    match r {
        Ok(()) => println!("  OK    {label}"),
        Err(e) => println!("  BROKE {label}  --  {e}"),
    }
}

// ---------------------------------------------------------------- part A: the existing mirrors

fn part_a() {
    println!("\n=== A. naive index flips (what BoardResizer's defaults do) ===");
    for t in ALL {
        for (w, h) in [(5usize, 5usize), (4, 5), (5, 4), (4, 4)] {
            report(
                &format!("{t:?} {w}x{h} reverse_columns  (x,y)->(w-1-x,y)"),
                check(t, w, h, w, h, &|x, y| (w - 1 - x, y)),
            );
            report(
                &format!("{t:?} {w}x{h} reverse_rows     (x,y)->(x,h-1-y)"),
                check(t, w, h, w, h, &|x, y| (x, h - 1 - y)),
            );
        }
    }
}

// ------------------------------------------------- part B: 90 degrees, square & truncated square

fn part_b() {
    println!("\n=== B. 90 degrees, Sokoban and Octoban ===");
    for t in [Tessellation::Sokoban, Tessellation::Octoban] {
        for (w, h) in [(5usize, 5usize), (4, 5), (5, 4), (4, 4)] {
            report(
                &format!("{t:?} {w}x{h} rot90 plain      (x,y)->(h-1-y,x)"),
                check(t, w, h, h, w, &|x, y| (h - 1 - y, x)),
            );
            // parity-fixed: shift one column right when h is even, board grows by one column
            let (w2, dx) = if h % 2 == 0 { (h + 1, 1) } else { (h, 0) };
            report(
                &format!("{t:?} {w}x{h} rot90 parity-fix (x,y)->(h-1-y+{dx},x)"),
                check(t, w, h, w2, w, &|x, y| (h - 1 - y + dx, x)),
            );
        }
    }
}

// ------------------------------------------------------------------ part C: 60 degrees, Hexoban

fn oddr_to_cube(col: i64, row: i64) -> (i64, i64, i64) {
    let q = col - (row - row.rem_euclid(2)) / 2;
    (q, -q - row, row)
}

fn cube_to_oddr(c: (i64, i64, i64)) -> (i64, i64) {
    let row = c.2;
    (c.0 + (row - row.rem_euclid(2)) / 2, row)
}

fn rot60_cube(c: (i64, i64, i64)) -> (i64, i64, i64) { (-c.2, -c.0, -c.1) }

fn part_c() {
    println!("\n=== C. 60 degrees, Hexoban (odd-r offset -> cube -> rotate -> offset) ===");
    let t = Tessellation::Hexoban;
    for (w, h) in [(5usize, 5usize), (4, 5), (5, 4), (4, 4), (7, 3)] {
        let raw: Vec<(i64, i64)> = (0..h as i64)
            .flat_map(|y| (0..w as i64).map(move |x| cube_to_oddr(rot60_cube(oddr_to_cube(x, y)))))
            .collect();

        let min_row = raw.iter().map(|c| c.1).min().unwrap();
        // a vertical shift by an odd number of rows is not expressible in offset coordinates:
        // it would need every hex moved by half a tile. Round the anchor to an even shift.
        let dy = -min_row + (-min_row).rem_euclid(2);
        let min_col = raw.iter().map(|c| c.0).min().unwrap();
        let dx = -min_col;

        let shifted: Vec<(i64, i64)> = raw.iter().map(|c| (c.0 + dx, c.1 + dy)).collect();
        let w2 = (shifted.iter().map(|c| c.0).max().unwrap() + 1) as usize;
        let h2 = (shifted.iter().map(|c| c.1).max().unwrap() + 1) as usize;

        let f = |x: usize, y: usize| {
            let c = cube_to_oddr(rot60_cube(oddr_to_cube(x as i64, y as i64)));
            ((c.0 + dx) as usize, (c.1 + dy) as usize)
        };
        report(
            &format!("Hexoban {w}x{h} rot60 -> {w2}x{h2} (row shift {dy}, col shift {dx})"),
            check(t, w, h, w2, h2, &f),
        );
    }
}

// ------------------------------------------------------------------ part D: 60 degrees, Trioban

const ROW_H: f64 = 0.866_025_403_784_438_6; // sqrt(3)/2

fn tri_centroid(x: i64, y: i64) -> (f64, f64) {
    let down = tri_is_down(x, y);
    let px = x as f64 * 0.5 + 0.5;
    let py = y as f64 * ROW_H + if down { ROW_H / 3.0 } else { 2.0 * ROW_H / 3.0 };
    (px, py)
}

fn tri_is_down(x: i64, y: i64) -> bool { (x + y).rem_euclid(2) == 0 }

fn tri_from_centroid(px: f64, py: f64) -> Option<(i64, i64)> {
    let row = (py / ROW_H).floor();
    let frac = py / ROW_H - row;
    let down = if (frac - 1.0 / 3.0).abs() < 1e-6 {
        true
    } else if (frac - 2.0 / 3.0).abs() < 1e-6 {
        false
    } else {
        return None; // rotated centroid did not land on a lattice centroid
    };
    let x = ((px - 0.5) * 2.0).round();
    if ((px - 0.5) * 2.0 - x).abs() > 1e-6 {
        return None;
    }
    let (x, y) = (x as i64, row as i64);
    if tri_is_down(x, y) != down {
        return None; // orientation disagrees with the parity rule -> not representable
    }
    Some((x, y))
}

fn part_d() {
    println!("\n=== D. 60 degrees, Trioban (rotate centroids, snap back onto the lattice) ===");
    // sanity: does the parity rule agree with the geometry the crate reports?
    for y in 0..4i64 {
        for x in 0..4i64 {
            let expect = if tri_is_down(x, y) {
                TileShape::TriangleDown
            } else {
                TileShape::TriangleUp
            };
            assert_eq!(
                Tessellation::Trioban.tile_shape_from_pos(x as usize, y as usize),
                expect
            );
        }
    }

    let (c, s) = (0.5f64, ROW_H); // cos 60, sin 60
    let rot = |x: i64, y: i64| {
        let (px, py) = tri_centroid(x, y);
        tri_from_centroid(px * c - py * s, px * s + py * c)
    };

    for (w, h) in [(5usize, 5usize), (4, 5), (5, 4), (4, 4), (6, 3)] {
        let raw: Vec<Option<(i64, i64)>> = (0..h as i64)
            .flat_map(|y| (0..w as i64).map(move |x| rot(x, y)))
            .collect();
        if raw.iter().any(|c| c.is_none()) {
            println!("  BROKE Trioban {w}x{h} rot60 -- some cell did not land on the lattice");
            continue;
        }
        let raw: Vec<(i64, i64)> = raw.into_iter().map(|c| c.unwrap()).collect();

        let min_x = raw.iter().map(|c| c.0).min().unwrap();
        let min_y = raw.iter().map(|c| c.1).min().unwrap();
        // shape is parity(x+y), so only translations with dx+dy even preserve orientations
        let (mut dx, dy) = (-min_x, -min_y);
        if (dx + dy).rem_euclid(2) != 0 {
            dx += 1;
        }
        let shifted: Vec<(i64, i64)> = raw.iter().map(|c| (c.0 + dx, c.1 + dy)).collect();
        let w2 = (shifted.iter().map(|c| c.0).max().unwrap() + 1) as usize;
        let h2 = (shifted.iter().map(|c| c.1).max().unwrap() + 1) as usize;

        let f = |x: usize, y: usize| {
            let c = rot(x as i64, y as i64).unwrap();
            ((c.0 + dx) as usize, (c.1 + dy) as usize)
        };
        report(
            &format!("Trioban {w}x{h} rot60 -> {w2}x{h2} (shift {dx},{dy})"),
            check(Tessellation::Trioban, w, h, w2, h2, &f),
        );
    }
}

fn main() {
    part_a();
    part_b();
    part_c();
    part_d();
    verify_tri_int();
    part_e();
    part_f();
}

#[derive(Debug, Copy, Clone)]
enum PublicTransform {
    MirrorHorizontal,
    MirrorVertical,
    RotateClockwise,
    RotateCounterClockwise,
}

fn transformed_public(mut board: GameBoard, transform: PublicTransform) -> GameBoard {
    match transform {
        PublicTransform::MirrorHorizontal => board.mirror(MirrorAxis::Horizontal),
        PublicTransform::MirrorVertical => board.mirror(MirrorAxis::Vertical),
        PublicTransform::RotateClockwise => board.rotate(Rotation::Clockwise),
        PublicTransform::RotateCounterClockwise => board.rotate(Rotation::CounterClockwise),
    }
    board
}

fn part_f() {
    println!("\n=== F. finished GameBoard public API ===");
    let transforms = [
        PublicTransform::MirrorHorizontal,
        PublicTransform::MirrorVertical,
        PublicTransform::RotateClockwise,
        PublicTransform::RotateCounterClockwise,
    ];

    for tessellation in ALL {
        for (width, height) in [(4usize, 4usize), (4, 5), (5, 4), (5, 5), (7, 3), (1, 5)] {
            for transform in transforms {
                let mut positions = HashMap::new();
                let mut transformed_size = None;
                for y in 0..height {
                    for x in 0..width {
                        let mut tiles = vec![TileKind::Floor; width * height];
                        tiles[y * width + x] = TileKind::Wall;
                        let board =
                            GameBoard::parsed_from_tiles(&tiles, width, height, tessellation)
                                .unwrap();
                        let board = transformed_public(board, transform);
                        transformed_size = Some((board.width(), board.height()));
                        let mapped = board
                            .iter()
                            .find_map(|(position, tile)| {
                                (tile == TileKind::Wall).then_some(position)
                            })
                            .unwrap();
                        positions.insert((x, y), mapped);
                    }
                }

                let (new_width, new_height) = transformed_size.unwrap();
                report(
                    &format!(
                        "{tessellation:?} {width}x{height} {transform:?} -> \
                         {new_width}x{new_height}"
                    ),
                    check(tessellation, width, height, new_width, new_height, &|x, y| {
                        positions[&(x, y)]
                    }),
                );
            }
        }
    }
}

#[allow(dead_code)]
fn dump_trioban_map() {
    let (c, s) = (0.5f64, ROW_H);
    println!("\nraw trioban rot60 mapping (x,y,down) -> (x',y')");
    for y in 0..5i64 {
        for x in 0..5i64 {
            let (px, py) = tri_centroid(x, y);
            let m = tri_from_centroid(px * c - py * s, px * s + py * c).unwrap();
            println!("({x},{y},{}) -> {m:?}", tri_is_down(x, y));
        }
    }
}

/// Candidate closed-form integer rotation for Trioban, fitted from the float probe.
fn tri_rot60_int(x: i64, y: i64) -> (i64, i64) {
    let p = y.rem_euclid(2);
    (
        (x - p).div_euclid(2) - (3 * y).div_euclid(2) - 1,
        (x + 1 - p).div_euclid(2) + (y + 1).div_euclid(2),
    )
}

#[allow(dead_code)]
fn verify_tri_int() {
    let (c, s) = (0.5f64, ROW_H);
    let mut bad = 0;
    for y in -20..20i64 {
        for x in -20..20i64 {
            let (px, py) = tri_centroid(x, y);
            let f = tri_from_centroid(px * c - py * s, px * s + py * c).unwrap();
            if f != tri_rot60_int(x, y) {
                if bad < 5 {
                    println!("  MISMATCH ({x},{y}): float {f:?} vs int {:?}", tri_rot60_int(x, y));
                }
                bad += 1;
            }
        }
    }
    println!("\ninteger trioban rot60 formula: {} mismatches over 1600 cells", bad);
}

/// For a rotation `T`, work out how each Direction must be relabelled, and whether that
/// relabelling is uniform over the board or depends on the cell.
fn direction_table(t: Tessellation, name: &str, tr: &dyn Fn(i64, i64) -> (i64, i64)) {
    use std::collections::BTreeMap;
    let (w, h) = (24usize, 24usize);
    let big = 200i64; // work far from any edge, in a huge virtual grid
    let mut table: BTreeMap<String, BTreeMap<String, Vec<(usize, usize)>>> = BTreeMap::new();

    for y in 6..h - 6 {
        for x in 6..w - 6 {
            for d in t.known_directions() {
                let Some(q) = t.neighbor(x, y, *d, w, h) else {
                    continue;
                };
                let p2 = tr(x as i64, y as i64);
                let q2 = tr(q.0 as i64, q.1 as i64);
                let found: Vec<String> = t
                    .known_directions()
                    .iter()
                    .filter(|d2| {
                        t.neighbor((p2.0 + big) as usize, (p2.1 + big) as usize, **d2, 1000, 1000)
                            == Some(((q2.0 + big) as usize, (q2.1 + big) as usize))
                    })
                    .map(|d2| format!("{d2:?}"))
                    .collect();
                table
                    .entry(format!("{d:?}"))
                    .or_default()
                    .entry(found.join("|"))
                    .or_default()
                    .push((x, y));
            }
        }
    }

    println!("\n{name}:");
    for (d, outs) in table {
        let summary: Vec<String> = outs
            .iter()
            .map(|(k, v)| format!("{k} [{} cells]", v.len()))
            .collect();
        println!("  {d:>10} -> {}", summary.join("  ,  "));
    }
}

#[allow(dead_code)]
fn part_e() {
    println!("\n=== E. how directions relabel under rotation ===");
    direction_table(Tessellation::Sokoban, "Sokoban rot90 (x,y)->(-y,x)", &|x, y| (-y, x));
    direction_table(Tessellation::Octoban, "Octoban rot90 (x,y)->(-y,x)", &|x, y| (-y, x));
    direction_table(Tessellation::Hexoban, "Hexoban rot60 (cube)", &|x, y| {
        cube_to_oddr(rot60_cube(oddr_to_cube(x, y)))
    });
    direction_table(Tessellation::Trioban, "Trioban rot60 (integer form)", &|x, y| {
        tri_rot60_int(x, y)
    });
}