summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/main.rs6
-rw-r--r--src/solvers.rs109
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
}
}