Implement brute force solver

4 files changed, 87 insertions, 32 deletions

diff --git a/.gitignore b/.gitignore
index 088ba6b..2f7cd6f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -8,3 +8,6 @@ Cargo.lock
 
 # These are backup files generated by rustfmt
 **/*.rs.bk
+
+# Ignore IDE Files
+/.idea/
diff --git a/Cargo.toml b/Cargo.toml
index 9d312e3..b5332fa 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,3 +8,4 @@ edition = "2018"
 
 [dependencies]
 num = "0.2"
+permutohedron = "0.2"
diff --git a/src/main.rs b/src/main.rs
index 7da7bd2..bb8b978 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,8 +1,8 @@
 mod solvers;
 
 fn main() {
-    let mut solver = solvers::Solver::<u32>::new(4);
+    let mut solver = solvers::Solver::<u32>::new(8);
 
-    let wall = solver.solve();
-    wall.output(solver.n, solver.h);
+    solver.solve();
+    //wall.output(solver.n, solver.h);
 }
diff --git a/src/solvers.rs b/src/solvers.rs
index a105958..a0845a1 100644
--- a/src/solvers.rs
+++ b/src/solvers.rs
@@ -7,6 +7,7 @@ impl Wall {
         Self { heights }
     }
 
+    #[allow(dead_code)]
     fn create_empty(w: u32) -> Self {
         let heights = if w == 0 {
             vec![]
@@ -63,6 +64,7 @@ pub struct Solver<T: num::PrimInt> {
     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
@@ -74,24 +76,24 @@ pub struct SaveState<T: num::PrimInt> {
     /// Mask of all currently used stones
     pub bitmask: T,
     /// sum of all placed stones
-    pub index: u32,
+    pub sum: u32,
     /// the row index
     pub row: u32,
 }
 
 impl<T: num::PrimInt> std::cmp::Ord for SaveState<T> {
     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-        self.index.cmp(&other.index)
+        self.sum.cmp(&other.sum)
     }
 }
 impl<T: num::PrimInt> std::cmp::PartialOrd for SaveState<T> {
     fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-        Some(self.index.cmp(&other.index))
+        Some(self.sum.cmp(&other.sum))
     }
 }
 impl<T: num::PrimInt> std::cmp::PartialEq for SaveState<T> {
     fn eq(&self, other: &Self) -> bool {
-        self.index.eq(&other.index)
+        self.sum.eq(&other.sum)
     }
 }
 
@@ -99,7 +101,7 @@ impl<T: num::PrimInt> SaveState<T> {
     pub fn new() -> Self {
         Self {
             bitmask: T::zero(),
-            index: 0,
+            sum: 0,
             row: unsafe {
                 COUNT += 1;
                 COUNT
@@ -107,23 +109,26 @@ impl<T: num::PrimInt> SaveState<T> {
         }
     }
 
+    #[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 {
-        println!("{},", stone);
         self.bitmask & T::from(1 << stone).expect("Requested stone index out of bounds")
     }
 
-    pub fn bridges_gap(&self, index: u32) -> bool {
-        self.get_bit(index - self.index) == T::zero()
+    #[allow(dead_code)]
+    pub fn bridges_gap(&self, gap: u32) -> bool {
+        self.get_bit(gap - self.sum) == T::zero()
     }
 
-    pub fn bridge_gap(mut self, index: u32) -> Self {
-        self.set_bit(index - self.index);
-        self.index = index;
+    #[allow(dead_code)]
+    pub fn bridge_gap(mut self, gap: u32) -> Self {
+        self.set_bit(gap - self.sum);
+        self.sum = gap;
         self
     }
 }
@@ -132,33 +137,79 @@ impl<T: num::PrimInt> Solver<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);
+        for data in heap {
+            permutations.push(data.clone());
+        }
         Self {
             n,
             h,
             w,
             solve_stack: vec![SaveState::new(); h as usize],
+            permutations,
         }
     }
 
-    //dummy solver
-    pub fn solve(&mut self) -> Wall {
-        let mut wall = Wall::create_empty(self.w);
-        wall.heights
-            .iter()
-            .take(2)
-            .zip(0..1)
-            .for_each(|(x, i)| self.solve_stack[*x as usize].set_bit(i));
-        for i in 0..(self.n * self.h) {
-            let machine = self
-                .solve_stack
-                .iter()
-                .filter(|x| x.bridges_gap(i + 1))
-                .min()
-                .unwrap()
-                .bridge_gap(i + 1);
-            wall.heights.push(machine.row);
+    pub fn solve(&mut self) {
+        //for (n, i) in self.permutations.iter().enumerate() {
+        //    println!("perm {}: {:?}", n, i);
+        //}
+        self.check_perm(&[3, 16, 23]);
+        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;
+            }
+        }
+    }
 
-        wall
+    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;
+            }
+        }
+        Wall::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: &Wall) -> bool {
+        for (r, i) in wall.heights.iter().zip(1..self.w) {
+            let stone = i - 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
     }
 }