Rework intuitive solver to consider all solutions

8 files changed, 147 insertions, 192 deletions

diff --git a/Cargo.toml b/Cargo.toml
index b5332fa..45650fb 100755
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -5,7 +5,14 @@ authors = ["Dennis Kobert <dennis@kobert.dev>",
            "Jan Zwerschke"]
 edition = "2018"
 
+[features]
+
+gpu = ["ocl"]
 
 [dependencies]
 num = "0.2"
+rayon = "1.3"
 permutohedron = "0.2"
+permutation_way = { git = "https://github.com/corentinway/permutation_way_rs" }
+
+ocl = { version = "0.19",  optional = true}
diff --git a/log_parser.py b/log_parser.py
index f27e2b2..cfd7204 100644
--- a/log_parser.py
+++ b/log_parser.py
@@ -1,5 +1,5 @@
 sym = '◙'.encode('utf-8')
-f = open('log_6', 'rb')
+f = open('data/log_6', 'rb')
 
 lines = []
 for line in f:
@@ -48,6 +48,7 @@ def for_stone(s):
 all_counts = [for_stone(i + 1) for i in range(n)]
 
 for sz, counts in enumerate(all_counts):
-    for xpos, count in sorted(counts.items(), key=lambda i: -i[1]):
+    for xpos, count in counts.items(): #//in sorted(counts.items(), key=lambda i: -i[1]):
         sz + 1, xpos, count
         print(f'{sz + 1} {xpos} {count}')
+    print()
diff --git a/src/main.rs b/src/main.rs
index 95a05eb..8a96f05 100755
--- a/src/main.rs
+++ b/src/main.rs
@@ -2,11 +2,13 @@ mod solver;
 mod solvers;
 mod structs;
 
-use solver::Solver;
-
 fn main() {
-    let mut solver = solvers::incremental_block::IncrementalBlockSover::new(4);
-
-    solver.solve().output();
-    //wall.output(solver.n, solver.h);
+    #[cfg(feature = "gpu")]
+    solvers::ocl::trivial();
+    #[cfg(not(feature = "gpu"))]
+    //let mut solver = solvers::incremental_block::IncrementalBlockSover::new(4);
+    {
+        let mut solver = solvers::intuitive::NormalSolver::new(8);
+        solver.solve();
+    }
 }
diff --git a/src/solvers/check.cl b/src/solvers/check.cl
new file mode 100644
index 0000000..d0ab4f0
--- /dev/null
+++ b/src/solvers/check.cl
@@ -0,0 +1,4 @@
+__kernel void check(__global int* permutations, __global int* checks, int n) {
+            buffer[get_global_id(0)] += scalar;
+}
+
diff --git a/src/solvers/incremental_block.rs b/src/solvers/incremental_block.rs
index d4ebb81..19f8f76 100644
--- a/src/solvers/incremental_block.rs
+++ b/src/solvers/incremental_block.rs
@@ -1,9 +1,11 @@
-use std::iter::repeat;
-use crate::solver::{Solver, wall_stats};
+use crate::solver::{wall_stats, Solver};
 use crate::structs::StoneWall;
+use std::iter::repeat;
 
 pub struct IncrementalBlockSover {
-    n: u32, h: u32, w: u32,
+    n: u32,
+    h: u32,
+    w: u32,
     rows: Vec<Vec<(u32, u32)>>,
 }
 
@@ -34,12 +36,15 @@ impl<'s> SubSolver<'s> {
         if row_existence.iter().all(|&x| x) {
             Some(Self {
                 count: index,
-                start, solver,
+                start,
+                solver,
                 heights: Vec::with_capacity(index as usize),
                 pos: vec![0; gap_possibilities.len()],
                 gap_possibilities,
             })
-        } else { None }
+        } else {
+            None
+        }
     }
 
     fn increment_at(&mut self, n: u32) -> bool {
@@ -60,9 +65,7 @@ impl<'s> Iterator for SubSolver<'s> {
     type Item = ();
 
     fn next(&mut self) -> Option<Self::Item> {
-        for (i, p) in self.pos.iter().enumerate().rev() {
-            t
-        }
+        for (i, p) in self.pos.iter().enumerate().rev() {}
         None
     }
 }
@@ -71,11 +74,11 @@ impl IncrementalBlockSover {
     fn generate_first_row(&mut self) {
         let mut sum = 0;
         self.rows[0] = (1..=self.n)
-                .map(|n| {
-                    sum += n;
-                    (sum - n, n)
-                })
-                .collect();
+            .map(|n| {
+                sum += n;
+                (sum - n, n)
+            })
+            .collect();
     }
 
     fn get_wall(&self) -> StoneWall {
@@ -89,15 +92,14 @@ impl IncrementalBlockSover {
     }
 
     fn visited(&self, row: u32, stone: u32) -> bool {
-        self.rows[row as usize].iter()
+        self.rows[row as usize]
+            .iter()
             .position(|&(_, s)| s == stone)
             .is_some()
     }
 
     fn row_size(&self, row: u32) -> u32 {
-        self.rows[row as usize]
-            .last()
-            .map_or(0, |&(i, s)| i + s)
+        self.rows[row as usize].last().map_or(0, |&(i, s)| i + s)
     }
 }
 
@@ -105,10 +107,12 @@ impl Solver for IncrementalBlockSover {
     fn new(n: u32) -> Self {
         let (h, w) = wall_stats(n);
         Self {
-            n, h, w,
+            n,
+            h,
+            w,
             rows: repeat(Vec::with_capacity(h as usize))
-                   .take(h as usize)
-                   .collect()
+                .take(h as usize)
+                .collect(),
         }
     }
 
@@ -130,4 +134,3 @@ impl Solver for IncrementalBlockSover {
         self.w
     }
 }
-
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
     }
 }
diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs
index 4fc1330..9dc210b 100755
--- a/src/solvers/mod.rs
+++ b/src/solvers/mod.rs
@@ -1,2 +1,4 @@
+//pub mod incremental_block;
 pub mod intuitive;
-pub mod incremental_block;
+#[cfg(feature = "gpu")]
+pub mod ocl;
diff --git a/src/solvers/ocl.rs b/src/solvers/ocl.rs
new file mode 100644
index 0000000..7c6bb16
--- /dev/null
+++ b/src/solvers/ocl.rs
@@ -0,0 +1,29 @@
+use ocl::ProQue;
+
+pub fn trivial() -> ocl::Result<()> {
+    let src = r#"
+        __kernel void add(__global float* buffer, float scalar) {
+            buffer[get_global_id(0)] += scalar;
+        }
+    "#;
+
+    let pro_que = ProQue::builder().src(src).dims(1 << 20).build()?;
+
+    let buffer = pro_que.create_buffer::<f32>()?;
+
+    let kernel = pro_que
+        .kernel_builder("add")
+        .arg(&buffer)
+        .arg(10.0f32)
+        .build()?;
+
+    unsafe {
+        kernel.enq()?;
+    }
+
+    let mut vec = vec![0.0f32; buffer.len()];
+    buffer.read(&mut vec).enq()?;
+
+    println!("The value at index [{}] is now '{}'!", 200007, vec[200007]);
+    Ok(())
+}