Last active
January 24, 2026 01:05
-
-
Save rrbutani/9277a38bf63c9b754640164555925ecb to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //! for a given `N`, how many unique shapes of `N` contiguous minos (all connected via at least one | |
| //! of the four cardinal directions) are possible? | |
| //! | |
| //! a shape is unique if no translation or rotation of a shape makes it the same as another shape | |
| use std::{collections::HashSet, fmt}; | |
| #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |
| struct Coord<const N: usize> { | |
| x: u8, // 0 <= x < N | |
| y: u8, // 0 <= y < N | |
| } | |
| impl<const N: usize> Coord<N> { | |
| const CENTER: Self = { | |
| assert!(N <= u8::MAX as usize); | |
| // for odd `N` this is easy: just `N // 2` which works out to be the index of the middle | |
| // coordinate | |
| // | |
| // for even `N`, less obvious; arbitrarily picking `N // 2` as well (left of "center") | |
| let middle = N as u8 / 2; | |
| Coord { | |
| x: middle, | |
| y: middle, | |
| } | |
| }; | |
| } | |
| #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |
| enum Direction { | |
| /// rotate: 0º | |
| North, | |
| /// rotate: +90º, -270º | |
| East, | |
| /// rotate: ±180º | |
| South, | |
| /// rotate: +270º, -90º | |
| West, | |
| } | |
| impl Direction { | |
| const ALL: [Self; 4] = { | |
| use Direction::*; | |
| [North, East, South, West] | |
| }; | |
| fn as_offset(self) -> (i8, i8) { | |
| use Direction::*; | |
| let (dx, dy) = match self { | |
| North => (0, -1), | |
| East => (1, 0), | |
| South => (0, 1), | |
| West => (-1, 0), | |
| }; | |
| (dx, dy) | |
| } | |
| } | |
| impl<const N: usize> Coord<N> { | |
| fn translate(self, (dx, dy): (i8, i8)) -> Option<Self> { | |
| Some(Coord { | |
| x: self.x.checked_add_signed(dx).filter(|&x| (x as usize) < N)?, | |
| y: self.y.checked_add_signed(dy).filter(|&y| (y as usize) < N)?, | |
| }) | |
| } | |
| fn rotate(self, rot: Direction) -> Option<Self> { | |
| use Direction::*; | |
| let Coord { x, y } = self; | |
| let Coord { x: cx, y: cy } = Self::CENTER; | |
| // relative to center: | |
| let (dx, dy) = { | |
| let (x, y, cx, cy) = (x as i8, y as i8, cx as i8, cy as i8); | |
| (x - cx, y - cy) | |
| }; | |
| let (new_dx, new_dy) = match rot { | |
| North => (dx, dy), | |
| East => (-dy, dx), | |
| South => (-dx, -dy), | |
| West => (dy, -dx), | |
| }; | |
| Some(Coord { | |
| x: cx.checked_add_signed(new_dx).filter(|&x| (x as usize) < N)?, | |
| y: cy.checked_add_signed(new_dy).filter(|&y| (y as usize) < N)?, | |
| }) | |
| } | |
| } | |
| #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |
| struct Shape<const N: usize> { | |
| minos: [Coord<N>; N], // functionally a Set; must be in sorted order | |
| } | |
| impl<const N: usize> Shape<N> { | |
| fn new(mut coords: [Coord<N>; N]) -> Self { | |
| coords.sort(); | |
| coords | |
| .windows(2) | |
| .for_each(|pair| assert_ne!(pair[0], pair[1], "should be a set!")); | |
| coords.iter().for_each(|Coord { x, y }| { | |
| debug_assert!(*x < (N as u8) && *y < (N as u8), "{x}, {y} ({N})"); | |
| }); | |
| Shape { minos: coords } | |
| } | |
| fn translate(self, offset: (i8, i8)) -> Option<Self> { | |
| let Shape { mut minos } = self; | |
| for coord in &mut minos { | |
| *coord = coord.translate(offset)?; | |
| } | |
| Some(Self::new(minos)) | |
| } | |
| fn rotate(self, rot: Direction) -> Option<Self> { | |
| let Shape { mut minos } = self; | |
| for coord in &mut minos { | |
| *coord = coord.rotate(rot)?; | |
| } | |
| Some(Self::new(minos)) | |
| } | |
| fn all_translations_and_rotations(self) -> impl Iterator<Item = Shape<N>> { | |
| let n: i8 = N.try_into().unwrap(); | |
| let n = n - 1; | |
| // #[cfg(debug_assertions)] | |
| let mut seen = HashSet::<Shape<N>>::with_capacity(N * N * 4 / 2); | |
| (-n..=n) | |
| .flat_map(move |dx| (-n..=n).map(move |dy| (dx, dy))) | |
| .flat_map(|(dx, dy)| { | |
| Direction::ALL | |
| .into_iter() | |
| .map(move |rot| ((dx, dy), rot)) | |
| }) | |
| .filter_map(move |(offs, rot)| { | |
| self.translate(offs)?.rotate(rot) | |
| }) | |
| // .inspect(move |shape| { | |
| // #[cfg(debug_assertions)] | |
| // assert!(seen.insert(*shape), "{shape:?}"); | |
| // }) | |
| .filter(move |shape| seen.insert(*shape)) | |
| } | |
| } | |
| // grid shape? | |
| // | |
| // really I think it's a "tilted" square? | |
| /* | |
| 1: | |
| █ | |
| 2: | |
| █ | |
| ██ | |
| å | |
| 3: | |
| █ | |
| ███ | |
| █ | |
| 4: | |
| █ | |
| ██ | |
| ████ | |
| ██ | |
| 5: | |
| █ | |
| ███ | |
| █████ | |
| ███ | |
| █ | |
| */ | |
| // | |
| // but to keep things simple for now we'll just do the full N x N grid | |
| // how many possible grid states? | |
| // | |
| // ignoring contiguity requirements, N^2 choose N | |
| // | |
| // not gonna bother to model this as a flat array for now; we'll just use a big map... | |
| impl<const N: usize> fmt::Display for Shape<N> { | |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
| let mut out = [[' '; N]; N]; | |
| for Coord { x, y } in self.minos { | |
| out[y as usize][x as usize] = '█'; | |
| } | |
| for row in out { | |
| for cell in row { | |
| cell.fmt(f)?; | |
| } | |
| '\n'.fmt(f)?; | |
| } | |
| Ok(()) | |
| } | |
| } | |
| struct Search<const N: usize> { | |
| // can only have shapes that are not equivalent under translation/rotation | |
| // | |
| // upon insertion to `unique`, all valid (fits in grid) translations/rotations of a shape should | |
| // be checked against/added to `claimed` | |
| unique: HashSet<Shape<N>>, | |
| claimed: HashSet<Shape<N>>, | |
| } | |
| impl<const N: usize> Search<N> { | |
| fn dfs_inner( | |
| &mut self, | |
| prev_placed: &mut HashSet<Coord<N>>, | |
| minos: &mut [Coord<N>; N], | |
| depth: usize, // 0 .. N | |
| new: Coord<N>, | |
| ) { | |
| debug_assert_eq!(prev_placed.len(), depth); | |
| debug_assert!(depth < N); | |
| // attempt to add `new` to the list of minos for the shape: | |
| if !prev_placed.insert(new) { | |
| return; // duplicate! | |
| } | |
| minos[depth] = new; | |
| // then, spider outwards and continue the search | |
| let new_depth = depth + 1; | |
| // unless we've hit `N`: | |
| if new_depth == N { | |
| // attempt to add to unique: | |
| let shape = Shape::new(*minos); | |
| let mut any_claimed = false; | |
| let unique = shape.all_translations_and_rotations().all(|alias| { | |
| let new = self.claimed.insert(alias); | |
| if new { any_claimed = true; } | |
| new | |
| }); | |
| if !unique && any_claimed { | |
| // unreachable!() | |
| // square grid, should never be reachable? idk | |
| } | |
| if unique { | |
| self.unique.insert(shape); | |
| } | |
| } else { | |
| // // if we haven't hit `N`, continue in the four directions: | |
| // for dir in Direction::ALL { | |
| // if let Some(new) = new.translate(dir.as_offset()) { | |
| // self.dfs_inner(prev_placed, minos, new_depth, new); | |
| // } | |
| // } | |
| // if we haven't hit `N`, continue in the four directions from each of the coords so | |
| // far (inefficient, silly): | |
| let coords = *minos; | |
| for base in &coords[0..=depth] { | |
| for dir in Direction::ALL { | |
| if let Some(new) = base.translate(dir.as_offset()) { | |
| self.dfs_inner(prev_placed, minos, new_depth, new); | |
| } | |
| } | |
| } | |
| } | |
| let removed = prev_placed.remove(&new); | |
| debug_assert!(removed); | |
| } | |
| fn dfs() -> HashSet<Shape<N>> { | |
| let mut search = Self { | |
| unique: HashSet::new(), | |
| claimed: HashSet::new(), | |
| }; | |
| search.dfs_inner(&mut HashSet::new(), &mut [Coord::<N>::CENTER; N], 0, Coord::<N>::CENTER); | |
| search.unique | |
| } | |
| } | |
| fn main() { | |
| for (idx, shape) in Search::<4>::dfs().iter().enumerate() { | |
| eprintln!("{}:\n{shape}", idx + 1); | |
| } | |
| } | |
| // edit: there's stuff about this! https://en.wikipedia.org/wiki/Polyomino | |
| // | |
| // "one-sided" unique (i.e. no reflection) is what we're doing here | |
| // https://oeis.org/A000988 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use nix -p cargo rustc rust-analyzer rustfmt clippy |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /.direnv | |
| /target |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| [package] | |
| name = "minos" | |
| version = "0.1.0" | |
| edition = "2024" | |
| [[bin]] | |
| name = "minos" | |
| path = "..minos.rs" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment