From c22cbdc401d067cd6cc55c5194255ccc8bd3c71b Mon Sep 17 00:00:00 2001 From: Dennis Kobert Date: Sun, 22 Dec 2019 04:39:00 +0100 Subject: Implement brute force solver --- .gitignore | 3 ++ Cargo.toml | 1 + src/main.rs | 6 ++-- src/solvers.rs | 109 ++++++++++++++++++++++++++++++++++++++++++--------------- 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::::new(4); + let mut solver = solvers::Solver::::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 { pub w: u32, /// Use to store already used blocks as a bitmask solve_stack: Vec>, + permutations: Vec>, } // used during row creation, will get deprecated @@ -74,24 +76,24 @@ pub struct SaveState { /// 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 std::cmp::Ord for SaveState { fn cmp(&self, other: &Self) -> std::cmp::Ordering { - self.index.cmp(&other.index) + self.sum.cmp(&other.sum) } } impl std::cmp::PartialOrd for SaveState { fn partial_cmp(&self, other: &Self) -> Option { - Some(self.index.cmp(&other.index)) + Some(self.sum.cmp(&other.sum)) } } impl std::cmp::PartialEq for SaveState { fn eq(&self, other: &Self) -> bool { - self.index.eq(&other.index) + self.sum.eq(&other.sum) } } @@ -99,7 +101,7 @@ impl SaveState { pub fn new() -> Self { Self { bitmask: T::zero(), - index: 0, + sum: 0, row: unsafe { COUNT += 1; COUNT @@ -107,23 +109,26 @@ impl SaveState { } } + #[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 Solver { 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 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::>()).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] { + if state.bitmask != T::from(1 << self.n).unwrap() { + return false; + } + } + true } } -- cgit v1.2.3-54-g00ecf