initial commit, rectangular grid placement enumeration

5 files changed, 395 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..869df07
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+/target
+Cargo.lock
\ No newline at end of file
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..8d9f9e9
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "calendar-puzzle"
+version = "0.1.0"
+edition = "2024"
+
+[dependencies]
+bitvec = "1.1.1"
diff --git a/examples/puzzle-a-day.rs b/examples/puzzle-a-day.rs
new file mode 100644
index 0000000..6577ede
--- /dev/null
+++ b/examples/puzzle-a-day.rs
@@ -0,0 +1,86 @@
+use calendar_puzzle::{CalanderPuzzle, rectangular::{Coords, Piece, Puzzle}};
+
+fn main() {
+    // construct board coordinates
+    let mut coords = Vec::new();
+    for row in 0..7 {
+        for col in 0..7 {
+            if (row >= 5 && col == 6) || (row == 0 && col >= 3) {
+                continue;
+            }
+            coords.push(Coords::new(row, col))
+        }
+    }
+
+    let puzzle = Puzzle::new(coords).unwrap()
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(0, 1),
+            Coords::new(0, 2),
+            Coords::new(1, 0),
+            Coords::new(1, 1),
+            Coords::new(1, 2),
+        ]).unwrap())
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(0, 1),
+            Coords::new(0, 2),
+            Coords::new(1, 0),
+            Coords::new(1, 1),
+        ]).unwrap())
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(0, 1),
+            Coords::new(0, 2),
+            Coords::new(1, 0),
+            Coords::new(1, 2),
+        ]).unwrap())
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(0, 1),
+            Coords::new(0, 2),
+            Coords::new(0, 3),
+            Coords::new(1, 1),
+        ]).unwrap())
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(0, 1),
+            Coords::new(0, 2),
+            Coords::new(0, 3),
+            Coords::new(1, 0),
+        ]).unwrap())
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(0, 1),
+            Coords::new(0, 2),
+            Coords::new(1, 2),
+            Coords::new(1, 3),
+        ]).unwrap())
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(1, 0),
+            Coords::new(1, 1),
+            Coords::new(1, 2),
+            Coords::new(2, 2),
+        ]).unwrap())
+        .with_piece(Piece::new([
+            Coords::new(0, 0),
+            Coords::new(0, 1),
+            Coords::new(0, 2),
+            Coords::new(1, 0),
+            Coords::new(2, 0),
+        ]).unwrap());
+    
+    let placements = puzzle.placements(true);
+    let placements_no_flip = puzzle.placements(false);
+
+    for (i, _piece) in puzzle.pieces().enumerate() {
+        println!("piece {} has {} placements allowing flips", i, placements[i].len());
+        println!("piece {} has {} placements without flips", i, placements_no_flip[i].len());
+
+        for placement in &placements_no_flip[i] {
+            puzzle.print_placement(placement);
+            println!("");
+        }
+    }
+}
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
+    }
+}
+