diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lib.rs | 16 | ||||
| -rw-r--r-- | src/rectangular.rs | 284 |
2 files changed, 300 insertions, 0 deletions
diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..23a954e --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,16 @@ +pub mod rectangular; + +pub trait CalanderPuzzle { + type Placement; + + // returns a Vec that associates with each piece index, + // a Vec of possible placements of that piece + fn placements(&self, allow_flips: bool) -> Vec<Vec<Self::Placement>>; + + fn solve(&self) { + + } +} + + + diff --git a/src/rectangular.rs b/src/rectangular.rs new file mode 100644 index 0000000..b1c4a23 --- /dev/null +++ b/src/rectangular.rs @@ -0,0 +1,284 @@ +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 + } +} + |