1 files changed, 69 insertions, 162 deletions

diff --git a/src/solvers/intuitive.rs b/src/solvers/intuitive.rs
index 9521ffc..6fea69d 100755
--- a/src/solvers/intuitive.rs
+++ b/src/solvers/intuitive.rs
@@ -1,100 +1,50 @@
-use crate::solver::Solver;
-use crate::structs::GapHeights;
-use std::os::raw::c_ushort;
+use rayon::prelude::*;
 
 /// Solve for a given N and return the resulting wall
-pub struct NormalSolver<T: num::PrimInt> {
+pub struct NormalSolver {
     pub n: u32,
     /// calculated height [might not be correct!]
     pub h: u32,
     /// width
     pub w: u32,
+    pub chunk: u32,
+    pub mask: u64,
     /// Use to store already used blocks as a bitmask
-    solve_stack: Vec<SaveState<T>>,
     permutations: Vec<Vec<u32>>,
+    masks: Vec<u64>,
 }
 
-// used during row creation, will get deprecated
-static mut COUNT: u32 = 0;
 static mut TRIES: u32 = 0;
 static mut SOLUTIONS: 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, n: u32) -> bool {
-        if gap - self.sum > n {
-            //println!("{}", gap - self.sum);
-            return false;
-        }
-        self.get_bit(gap - self.sum) == T::zero()
-    }
-
-    #[allow(dead_code)]
-    pub unsafe fn bridge_gap(&mut self, gap: u32) {
-        self.set_bit(gap - self.sum);
-        self.sum = gap;
-    }
-}
-
-impl<T: num::PrimInt> NormalSolver<T> {
+impl NormalSolver {
     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 chunk = n_f as u32 / n;
         let mut permutations = Vec::with_capacity(n_f);
-        //println!("Generating permutations");
-        for data in heap {
+        let mut masks: Vec<u64> = vec![0; n_f];
+        println!("Generating permutations");
+        for (j, data) in heap.enumerate() {
             permutations.push(data.clone());
-        }
-        /*use permutohedron::LexicalPermutation;
-        loop {
-            permutations.push(heap.to_vec());
-            if !heap.next_permutation() {
-                break;
+            let mut sum = 0;
+            for stone in permutations[j].iter().take(n as usize - 1) {
+                //.take(n as usize - 1) {
+                sum += stone;
+                masks[j] |= 1 << sum;
             }
-        }*/
-
+        }
         Self {
             n,
             h,
             w,
-            solve_stack: vec![SaveState::new(); h as usize],
+            chunk,
+            mask: (1 << w) - 2,
             permutations,
+            masks,
         }
     }
 
@@ -102,120 +52,77 @@ impl<T: num::PrimInt> NormalSolver<T> {
         for (n, i) in self.permutations.iter().enumerate() {
             let tmp: Vec<u32> = i.iter().map(|x| *x).collect();
             //println!("perm {}: {:?}", n, tmp);
+            //println!("perm {}: {:?}", n, self.masks[n]);
         }
-        //println!("calculate results");
+        println!("calculate results");
         self.permute(
             permutohedron::factorial(self.n as usize),
             0,
-            ((0..(self.h - 1)).collect::<Vec<u32>>()).as_ref(),
+            0,
+            ((0..(self.h - 1))
+                .map(|x| x * self.chunk)
+                .collect::<Vec<u32>>())
+            .as_ref(),
         );
         unsafe { println!("tries: {}\nsolutions: {}", TRIES, SOLUTIONS) }
     }
 
-    fn permute(&mut self, up: usize, index: usize, numbers: &[u32]) {
-        let chunk = self.permutations.len() / self.h as usize;
-        if index as usize == numbers.len() - 1 && false {
-            let mut new_num = Vec::from(numbers);
-            if self.n == 6 {
-                new_num[2] = 680;
-            }
-            if self.n == 8 {
-                new_num[3] = 38728;
-                //new_num[3] = 36719;
+    fn permute(&self, up: usize, index: usize, curr_mask: u64, numbers: &[u32]) {
+        if index as usize == numbers.len() {
+            //println!("checking {:?}", numbers);
+            unsafe {
+                TRIES += 1;
             }
-
-            if self.check_perm(&new_num) {
-                for i in new_num {
-                    println!("{}\t{}", numbers[0], i);
+            let mut tmask: u64 = 0;
+            let mut sum = 0;
+            let mut stones = 0;
+            for i in 1..=(self.w + 1) {
+                if curr_mask & (1 << i) == 0 {
+                    stones += 1;
+                    tmask |= 1 << (i - sum);
+                    sum = i;
                 }
             }
-            return;
-        }
-        if index as usize == numbers.len() {
-            //println!("checking {:?}", numbers);
-            if self.check_perm(&numbers) {
+            if tmask == (1 << (self.n + 1)) - 2 && stones == self.n {
                 //println!("success");
+                unsafe {
+                    SOLUTIONS += 1;
+                }
                 for i in numbers {
-                    println!("{},{}", numbers[0], i);
+                    println!("{}\t{}", numbers[0], i);
                 }
             }
             return;
         }
         let mut new_num = Vec::from(numbers);
-        for i in numbers[index as usize] as usize..((index + 1) * chunk) {
-            for n in (index + 1)..numbers.len() {
-                new_num[n] = (n * chunk) as u32;
-            }
-            self.permute(up, index + 1, &new_num);
-            new_num[index] += 1;
-        }
-    }
-
-    fn check_perm(&mut self, nums: &[u32]) -> bool {
-        //for i in nums {
-        //    println!("{},{}", nums[0], i);
-        //}
-        unsafe {
-            TRIES += 1;
-        }
-        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.n - 1 - (self.n & 1)) as usize].iter()
-            {
-                sum += *n as usize;
-                if sums[sum - 1] != self.w {
-                    return false;
-                }
-                sums[sum - 1] = i as u32;
+        let start = numbers[index as usize] / self.chunk;
+        for i in start..self.n - (self.h - 1 - index as u32) {
+            for n in 1..(numbers.len() - index) {
+                new_num[n + index] = (n as u32 + i) * self.chunk;
             }
-        }
-        let mut test = SaveState::<u64>::new();
-        for i in 0..sums.len() {
-            if sums[i] == self.w {
-                if !test.bridges_gap(i as u32, self.n) {
-                    return false;
+            if index == 0 {
+                (0..self.chunk).into_par_iter().for_each(|j| {
+                    let mut new_num = new_num.clone();
+                    let tmp = i * self.chunk + j;
+                    new_num[index] = tmp;
+                    self.permute(
+                        up,
+                        index + 1,
+                        curr_mask | self.masks[tmp as usize],
+                        &new_num,
+                    );
+                });
+            } else {
+                for j in 0..self.chunk {
+                    new_num[index] = i * self.chunk + j;
+                    self.permute(
+                        up,
+                        index + 1,
+                        curr_mask | self.masks[new_num[index] as usize],
+                        &new_num,
+                    );
                 }
-                unsafe {
-                    test.bridge_gap(i as u32);
-                }
-            }
-        }
-        //println!("{:?}", sums);
-        let vec = sums
-            .iter()
-            .map(|x| if *x != self.w { *x as u32 } else { self.h - 1 })
-            .collect();
-        //println!("{:?}", vec);
-        let vec = GapHeights::from_heights(vec); //.output(self.n, self.h);
-
-        //if !self.check_gaps(&vec) {
-        //    return false;
-        //}
-        //println!("success");
-        unsafe {
-            SOLUTIONS += 1;
-        }
-        //vec.as_stone_wall(self.n).output();
-        true
-    }
-
-    #[allow(dead_code)]
-    fn check_gaps(&mut self, wall: &GapHeights) -> bool {
-        self.solve_stack = vec![SaveState::new(); self.h as usize];
-        for (i, r) in wall.iter().enumerate() {
-            let stone = (i + 1) as u32 - self.solve_stack[r as usize].sum;
-            if stone > self.n {
-                return false;
-            }
-            self.solve_stack[r as usize].set_bit(stone);
-            self.solve_stack[r as usize].sum = i as u32;
-        }
-        for state in self.solve_stack.as_ref() as &[SaveState<T>] {
-            if state.bitmask != T::from(1 << self.n).unwrap() {
-                return false;
             }
         }
-        true
     }
 }