diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.rs | 6 | ||||
| -rw-r--r-- | src/solvers.rs | 109 |
2 files changed, 83 insertions, 32 deletions
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::<u32>::new(4); + let mut solver = solvers::Solver::<u32>::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<T: num::PrimInt> { pub w: u32, /// Use to store already used blocks as a bitmask solve_stack: Vec<SaveState<T>>, + permutations: Vec<Vec<u32>>, } // used during row creation, will get deprecated @@ -74,24 +76,24 @@ pub struct SaveState<T: num::PrimInt> { /// 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<T: num::PrimInt> std::cmp::Ord for SaveState<T> { fn cmp(&self, other: &Self) -> std::cmp::Ordering { - self.index.cmp(&other.index) + self.sum.cmp(&other.sum) } } impl<T: num::PrimInt> std::cmp::PartialOrd for SaveState<T> { fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { - Some(self.index.cmp(&other.index)) + Some(self.sum.cmp(&other.sum)) } } impl<T: num::PrimInt> std::cmp::PartialEq for SaveState<T> { fn eq(&self, other: &Self) -> bool { - self.index.eq(&other.index) + self.sum.eq(&other.sum) } } @@ -99,7 +101,7 @@ impl<T: num::PrimInt> SaveState<T> { pub fn new() -> Self { Self { bitmask: T::zero(), - index: 0, + sum: 0, row: unsafe { COUNT += 1; COUNT @@ -107,23 +109,26 @@ impl<T: num::PrimInt> SaveState<T> { } } + #[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<T: num::PrimInt> Solver<T> { 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 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::<Vec<u32>>()).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<T>] { + if state.bitmask != T::from(1 << self.n).unwrap() { + return false; + } + } + true } } |