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 --- Cargo.toml | 7 ++ log_parser.py | 5 +- src/main.rs | 14 ++- src/solvers/check.cl | 4 + src/solvers/incremental_block.rs | 45 ++++---- src/solvers/intuitive.rs | 231 ++++++++++++--------------------------- src/solvers/mod.rs | 4 +- src/solvers/ocl.rs | 29 +++++ 8 files changed, 147 insertions(+), 192 deletions(-) create mode 100644 src/solvers/check.cl create mode 100644 src/solvers/ocl.rs 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 ", "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>, } @@ -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 { - 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 { +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 } } 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::()?; + + 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(()) +} -- cgit v1.2.3-54-g00ecf