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;