From 862695a7374bc60368d09a7e695ae0b8aa3b97c2 Mon Sep 17 00:00:00 2001 From: Dennis Kobert Date: Sat, 4 Jan 2020 00:52:36 +0100 Subject: Rework intuitive solver to consider all solutions --- src/solvers/intuitive.rs | 231 ++++++++++++++--------------------------------- 1 file changed, 69 insertions(+), 162 deletions(-) (limited to 'src/solvers/intuitive.rs') 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 { +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>, permutations: Vec>, + masks: Vec, } -// 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 { - /// Mask of all currently used stones - pub bitmask: T, - /// sum of all placed stones - pub sum: u32, - /// the row index - pub row: u32, -} - -impl SaveState { - 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 NormalSolver { +impl NormalSolver { pub fn new(n: u32) -> Self { let h = n / 2 + 1; let w = h * (n - 1); let mut heap = (1..=n).collect::>(); 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 = 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 NormalSolver { for (n, i) in self.permutations.iter().enumerate() { let tmp: Vec = 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::>()).as_ref(), + 0, + ((0..(self.h - 1)) + .map(|x| x * self.chunk) + .collect::>()) + .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::::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] { - if state.bitmask != T::from(1 << self.n).unwrap() { - return false; } } - true } } -- cgit v1.2.3-70-g09d2