path: root/src/rectangular.rs

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

use bitvec::{bitvec, order::Lsb0, vec::BitVec};

use crate::CalanderPuzzle;

// clockwise
#[derive(Clone, Copy)]
enum Rotation {
    Rot0,
    Rot1,
    Rot2,
    Rot3,
}

#[derive(Clone, Copy)]
struct Orientation {
    rotation: Rotation,
    flipped: bool
}

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
pub struct Coords {
    row: i32,
    col: i32,
}

impl Coords {
    pub fn new(row: i32, col: i32) -> Self {
        Self { row, col }
    }

    fn orient(self, orientation: Orientation) -> Self {
        let (row, col) = match orientation.rotation {
            Rotation::Rot0 => ( self.row,  self.col),
            Rotation::Rot1 => (-self.col,  self.row),
            Rotation::Rot2 => (-self.row, -self.col),
            Rotation::Rot3 => ( self.col, -self.row),
        };
        if orientation.flipped {
            Self::new(col, row)
        } else {
            Self::new(row, col)
        }
    }

    fn translate(self, offset: Coords) -> Self {
        Self::new(self.row + offset.row, self.col + offset.col)
    }
}

#[derive(Clone, Copy)]
struct BoundingBox {
    min: Coords,
    max: Coords,
}

impl BoundingBox {
    fn new(min: Coords, max: Coords) -> Self {
        Self { min, max }
    }

    fn orient(self, orientation: Orientation) -> Self {
        let (min_row, min_col, max_row, max_col) = match orientation.rotation {
            Rotation::Rot0 => ( self.min.row,  self.min.col,  self.max.row,  self.max.col),
            Rotation::Rot1 => (-self.max.col,  self.min.row, -self.min.col,  self.max.row),
            Rotation::Rot2 => (-self.max.row, -self.max.col, -self.min.row, -self.min.col),
            Rotation::Rot3 => ( self.min.col, -self.max.row,  self.max.col, -self.min.row)
        };
        if orientation.flipped {
            Self::new(Coords::new(min_col, min_row), Coords::new(max_col, max_row))
        } else {
            Self::new(Coords::new(min_row, min_col), Coords::new(max_row, max_col))
        }
    }

    fn translate(self, offset: Coords) -> Self {
        Self::new(self.min.translate(offset), self.max.translate(offset))
    }
}

pub struct Piece {
    units: HashSet<Coords>,
    bounding_box: BoundingBox,
}

impl Piece {
    /// creates a new piece from an iterator of coordinates
    /// returns None if iterator is empty
    pub fn new(units: impl IntoIterator<Item=Coords>) -> Option<Self> {
        let mut unit_set: HashSet<Coords> = HashSet::new();
        let mut coords_min: Option<Coords> = None;
        let mut coords_max: Option<Coords> = None;

        for coords in units {
            coords_min = Some(match coords_min {
                None => coords,
                Some(coords_min) => Coords::new(
                    coords_min.row.min(coords.row),
                    coords_min.col.min(coords.col),
                )
            });
            coords_max = Some(match coords_max {
                None => coords,
                Some(coords_max) => Coords::new(
                    coords_max.row.max(coords.row),
                    coords_max.col.max(coords.col),
                )
            });
            unit_set.insert(coords);
        }

        if unit_set.len() > 0 {
            Some(Self {
                units: unit_set,
                bounding_box: BoundingBox::new(coords_min.unwrap(), coords_max.unwrap()),
            })
        } else {
            None
        }
    }

    fn translated_units(&self, orientation: Orientation, offset: Coords) -> impl IntoIterator<Item=Coords> {
        self.units.iter().copied().map(move |c| {
            c.orient(orientation).translate(offset)
        })
    }
}

pub struct Puzzle {
    board: HashMap<Coords, usize>,
    bounding_box: BoundingBox,
    pieces: Vec<Piece>,
}

impl Puzzle {
    /// creates a new puzzle from an iterator of board coordinates
    /// returns None if iterator is empty
    pub fn new(board: impl IntoIterator<Item=Coords>) -> Option<Self> {
        
        let mut board_map: HashMap<Coords, usize> = HashMap::new();
        let mut coords_min: Option<Coords> = None;
        let mut coords_max: Option<Coords> = None;

        let mut i = 0;
        for coords in board {
            coords_min = Some(match coords_min {
                None => coords,
                Some(coords_min) => Coords::new(
                    coords_min.row.min(coords.row),
                    coords_min.col.min(coords.col),
                )
            });
            coords_max = Some(match coords_max {
                None => coords,
                Some(coords_max) => Coords::new(
                    coords_max.row.max(coords.row),
                    coords_max.col.max(coords.col),
                )
            });
            if !board_map.contains_key(&coords) {
                board_map.insert(coords, i);
                i += 1;
            }
        }

        if board_map.len() > 0 {
            Some(Self {
                board: board_map,
                bounding_box: BoundingBox::new(coords_min.unwrap(), coords_max.unwrap()),
                pieces: Vec::new(),
            })
        } else {
            None
        }
    }

    pub fn pieces(&self) -> std::slice::Iter<'_, Piece> {
        self.pieces.iter()
    }
    
    pub fn with_piece(mut self, piece: Piece) -> Self {
        self.pieces.push(piece);
        self
    }

    pub fn print_placement(&self, placement: &Placement) {
        for row in self.bounding_box.min.row..=self.bounding_box.max.row {
            for col in self.bounding_box.min.col..=self.bounding_box.max.col {
                match self.board.get(&Coords::new(row, col)) {
                    None => {
                        print!(" ");
                    },
                    Some(&index) => {
                        if placement.bitvec[index] {
                            print!("#");
                        } else {
                            print!(".");
                        }
                    }
                }
            }
            println!("");
        }
    }
}

pub struct Placement {
    bitvec: BitVec<u64>,
}

impl Placement {
    fn new(bitvec: BitVec<u64>) -> Self {
        Self { bitvec }
    }
}

impl CalanderPuzzle for Puzzle {
    type Placement = Placement;

    fn placements(&self, allow_flips: bool) -> Vec<Vec<Placement>> {
        // TODO remove identical placements
        let orientations = if allow_flips {
            vec![
                Orientation { rotation: Rotation::Rot0, flipped: false },
                Orientation { rotation: Rotation::Rot1, flipped: false },
                Orientation { rotation: Rotation::Rot2, flipped: false },
                Orientation { rotation: Rotation::Rot3, flipped: false },
                Orientation { rotation: Rotation::Rot0, flipped: true },
                Orientation { rotation: Rotation::Rot1, flipped: true },
                Orientation { rotation: Rotation::Rot2, flipped: true },
                Orientation { rotation: Rotation::Rot3, flipped: true },
            ]
        } else {
            vec![
                Orientation { rotation: Rotation::Rot0, flipped: false },
                Orientation { rotation: Rotation::Rot1, flipped: false },
                Orientation { rotation: Rotation::Rot2, flipped: false },
                Orientation { rotation: Rotation::Rot3, flipped: false },
            ]
        };

        let puzzle_bbox = self.bounding_box;
        
        let mut placements = Vec::new();
        for piece in &self.pieces {
            let mut piece_placements = Vec::new();
            let mut seen_placements = HashSet::<BitVec<u64>>::new();
            
            for orientation in orientations.iter().copied() {
                let piece_bbox = piece.bounding_box.orient(orientation);

                let offset_row_start = puzzle_bbox.min.row - piece_bbox.min.row;
                let offset_row_end = puzzle_bbox.max.row - piece_bbox.max.row;

                let offset_col_start = puzzle_bbox.min.col - piece_bbox.min.col;
                let offset_col_end = puzzle_bbox.max.col - piece_bbox.max.col;
                
                for offset_row in offset_row_start..=offset_row_end {
                    for offset_col in offset_col_start..=offset_col_end {
                        let offset = Coords::new(offset_row, offset_col);

                        let mut bitvec = bitvec![u64, Lsb0; 0; self.board.len()];
                        let mut fits = true;
                        for unit in  piece.translated_units(orientation, offset) {
                            let Some(&index) = self.board.get(&unit) else {
                                fits = false;
                                break;
                            };
                            bitvec.set(index, true);
                        }
                        if fits && !seen_placements.contains(&bitvec) {
                            seen_placements.insert(bitvec.clone());
                            piece_placements.push(Placement::new(bitvec));
                        }
                    }
                }
            }
            placements.push(piece_placements);
        }
        placements
    }
}