summaryrefslogtreecommitdiff
path: root/src/solvers
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers')
-rw-r--r--src/solvers/intuitive.rs146
-rw-r--r--src/solvers/mod.rs1
2 files changed, 147 insertions, 0 deletions
diff --git a/src/solvers/intuitive.rs b/src/solvers/intuitive.rs
new file mode 100644
index 0000000..16baa03
--- /dev/null
+++ b/src/solvers/intuitive.rs
@@ -0,0 +1,146 @@
+use crate::solver::Solver;
+use crate::structs::GapHeights;
+
+/// Solve for a given N and return the resulting wall
+pub struct NormalSolver<T: num::PrimInt> {
+ pub n: u32,
+ /// calculated height [might not be correct!]
+ pub h: u32,
+ /// width
+ pub w: u32,
+ /// Use to store already used blocks as a bitmask
+ solve_stack: Vec<SaveState<T>>,
+ permutations: Vec<Vec<u32>>,
+}
+
+// used during row creation, will get deprecated
+static mut COUNT: u32 = 0;
+
+/// Save the current state for each row
+#[derive(Clone, Copy)]
+pub struct SaveState<T: num::PrimInt> {
+ /// Mask of all currently used stones
+ pub bitmask: T,
+ /// sum of all placed stones
+ pub sum: u32,
+ /// the row index
+ pub row: u32,
+}
+
+impl<T: num::PrimInt> SaveState<T> {
+ pub fn new() -> Self {
+ Self {
+ bitmask: T::zero(),
+ sum: 0,
+ row: unsafe {
+ COUNT += 1;
+ COUNT
+ },
+ }
+ }
+
+ #[allow(dead_code)]
+ pub fn set_bit(&mut self, stone: u32) {
+ self.bitmask =
+ self.bitmask | T::from(1 << stone).expect("Stone placing index out of bounds");
+ }
+
+ #[allow(dead_code)]
+ pub fn get_bit(&self, stone: u32) -> T {
+ self.bitmask & T::from(1 << stone).expect("Requested stone index out of bounds")
+ }
+
+ #[allow(dead_code)]
+ pub fn bridges_gap(&self, gap: u32) -> bool {
+ self.get_bit(gap - self.sum) == T::zero()
+ }
+
+ #[allow(dead_code)]
+ pub fn bridge_gap(mut self, gap: u32) -> Self {
+ self.set_bit(gap - self.sum);
+ self.sum = gap;
+ self
+ }
+}
+
+impl<T: num::PrimInt> NormalSolver<T> {
+ pub fn new(n: u32) -> Self {
+ let h = n / 2 + 1;
+ let w = h * (n - 1);
+ let mut heap = (1..=n).collect::<Vec<u32>>();
+ let heap = permutohedron::Heap::new(&mut heap);
+ let n_f = permutohedron::factorial(n as usize);
+ let mut permutations = Vec::with_capacity(n_f);
+ println!("Generating permutations");
+ for data in heap {
+ permutations.push(data.clone());
+ }
+ Self {
+ n,
+ h,
+ w,
+ solve_stack: vec![SaveState::new(); h as usize],
+ permutations,
+ }
+ }
+
+ pub fn solve(&mut self) {
+ //for (n, i) in self.permutations.iter().enumerate() {
+ // println!("perm {}: {:?}", n, i);
+ //}
+ println!("calculate results");
+ self.permute(
+ permutohedron::factorial(self.n as usize),
+ 0,
+ ((0..self.h).collect::<Vec<u32>>()).as_ref(),
+ );
+ }
+
+ fn permute(&mut self, up: usize, index: usize, numbers: &[u32]) {
+ if index as usize == numbers.len() {
+ //println!("checking {:?}", numbers);
+ if self.check_perm(&numbers) {
+ println!("success");
+ }
+ return;
+ }
+ let mut new_num = Vec::from(numbers);
+ for i in numbers[index as usize] as usize..up {
+ self.permute(up, index + 1, &new_num);
+ new_num[index] += 1;
+ for n in (index + 1)..numbers.len() {
+ new_num[n] = (i + 1 + n - index) as u32;
+ }
+ }
+ }
+
+ fn check_perm(&mut self, nums: &[u32]) -> bool {
+ let mut sums = vec![self.w; self.w as usize];
+ for (i, num) in nums.iter().enumerate() {
+ let mut sum = 0;
+ for n in self.permutations[*num as usize][..self.h as usize].iter() {
+ sum += *n as usize;
+ if sums[sum - 1] != self.w {
+ return false;
+ }
+ sums[sum - 1] = i as u32;
+ }
+ }
+ GapHeights::from_heights(sums.iter().map(|x| *x as u32).collect()).output(self.w, self.h);
+ true
+ }
+
+ #[allow(dead_code)]
+ fn check_gaps(&mut self, wall: &GapHeights) -> bool {
+ for (i, r) in wall.iter().enumerate() {
+ let stone = (i + 1) as u32 - self.solve_stack[r as usize].sum;
+ self.solve_stack[r as usize].set_bit(stone);
+ }
+ for state in self.solve_stack.as_ref() as &[SaveState<T>] {
+ if state.bitmask != T::from(1 << self.n).unwrap() {
+ return false;
+ }
+ }
+ true
+ }
+}
diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs
new file mode 100644
index 0000000..0b1d716
--- /dev/null
+++ b/src/solvers/mod.rs
@@ -0,0 +1 @@
+pub mod intuitive;