From dd0ed4cfff1a4af2a518aab399e32174175ed0d8 Mon Sep 17 00:00:00 2001 From: natrixaeria Date: Sun, 22 Dec 2019 06:21:32 +0100 Subject: Arrange project structure --- src/main.rs | 4 +- src/solver.rs | 9 ++ src/solvers.rs | 215 ----------------------------------------------- src/solvers/intuitive.rs | 161 +++++++++++++++++++++++++++++++++++ src/solvers/mod.rs | 1 + src/structs.rs | 98 +++++++++++++++++++++ 6 files changed, 272 insertions(+), 216 deletions(-) create mode 100644 src/solver.rs delete mode 100644 src/solvers.rs create mode 100644 src/solvers/intuitive.rs create mode 100644 src/solvers/mod.rs create mode 100644 src/structs.rs diff --git a/src/main.rs b/src/main.rs index bb8b978..a1cdd3b 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,7 +1,9 @@ +mod structs; +mod solver; mod solvers; fn main() { - let mut solver = solvers::Solver::::new(8); + let mut solver = solvers::intuitive::NormalSolver::::new(6); solver.solve(); //wall.output(solver.n, solver.h); diff --git a/src/solver.rs b/src/solver.rs new file mode 100644 index 0000000..c289cd6 --- /dev/null +++ b/src/solver.rs @@ -0,0 +1,9 @@ +use crate::structs::StoneWall; + +pub trait Solver { + fn new(n: u32) -> Self; + fn solve(&mut self) -> StoneWall; + fn n(&self) -> u32; + fn h(&self) -> u32; + fn w(&self) -> u32; +} diff --git a/src/solvers.rs b/src/solvers.rs deleted file mode 100644 index a0845a1..0000000 --- a/src/solvers.rs +++ /dev/null @@ -1,215 +0,0 @@ -pub struct Wall { - heights: Vec, -} - -impl Wall { - pub fn from_heights(heights: Vec) -> Self { - Self { heights } - } - - #[allow(dead_code)] - fn create_empty(w: u32) -> Self { - let heights = if w == 0 { - vec![] - } else if w == 1 { - vec![0] - } else { - let mut v = Vec::with_capacity(w as usize); - v.push(0); - v.push(1); - v - }; - Self { heights } - } - - pub fn calculate_row(&self, r: u32, stones: &mut [u32]) { - let mut len = 1; - let mut i = 0; - for &height in self.heights.iter().chain([r].iter()) { - if height == r { - stones[i] = len; - i += 1; - len = 0; - } - len += 1; - } - } - - pub fn output(&self, n: u32, h: u32) { - let mut stones = vec![0; n as usize]; - let mut toggle = 0; - let colors = [ - "\x1b[31m", "\x1b[32m", "\x1b[33m", "\x1b[34m", "\x1b[35m", "\x1b[36m", - ]; - for row in 0..h { - self.calculate_row(row, &mut stones); - for &len in stones.iter() { - print!("{}", colors[toggle]); - toggle = (toggle + 1) % colors.len(); - for _ in 0..len { - print!("◙"); - } - } - println!("\x1b[m"); - } - } -} - -/// Solve for a given N and return the resulting wall -pub struct Solver { - pub n: u32, - /// calculated height [might not be correct!] - pub h: u32, - /// width - pub w: u32, - /// Use to store already used blocks as a bitmask - solve_stack: Vec>, - permutations: Vec>, -} - -// used during row creation, will get deprecated -static mut COUNT: u32 = 0; - -/// Save the current state for each row -#[derive(Clone, Eq, 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 std::cmp::Ord for SaveState { - fn cmp(&self, other: &Self) -> std::cmp::Ordering { - self.sum.cmp(&other.sum) - } -} -impl std::cmp::PartialOrd for SaveState { - fn partial_cmp(&self, other: &Self) -> Option { - Some(self.sum.cmp(&other.sum)) - } -} -impl std::cmp::PartialEq for SaveState { - fn eq(&self, other: &Self) -> bool { - self.sum.eq(&other.sum) - } -} - -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) -> bool { - self.get_bit(gap - self.sum) == T::zero() - } - - #[allow(dead_code)] - pub fn bridge_gap(mut self, gap: u32) -> Self { - self.set_bit(gap - self.sum); - self.sum = gap; - self - } -} - -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, - } - } - - 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; - } - } - } - - 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 - } -} diff --git a/src/solvers/intuitive.rs b/src/solvers/intuitive.rs new file mode 100644 index 0000000..61ecbdf --- /dev/null +++ b/src/solvers/intuitive.rs @@ -0,0 +1,161 @@ +use crate::solver::Solver; +use crate::structs::GapHeights; + +/// Solve for a given N and return the resulting wall +pub struct NormalSolver { + pub n: u32, + /// calculated height [might not be correct!] + pub h: u32, + /// width + pub w: u32, + /// Use to store already used blocks as a bitmask + solve_stack: Vec>, + permutations: Vec>, +} + +// used during row creation, will get deprecated +static mut COUNT: u32 = 0; + +/// Save the current state for each row +#[derive(Clone, Eq, 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 std::cmp::Ord for SaveState { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + self.sum.cmp(&other.sum) + } +} +impl std::cmp::PartialOrd for SaveState { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.sum.cmp(&other.sum)) + } +} +impl std::cmp::PartialEq for SaveState { + fn eq(&self, other: &Self) -> bool { + self.sum.eq(&other.sum) + } +} + +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) -> bool { + self.get_bit(gap - self.sum) == T::zero() + } + + #[allow(dead_code)] + pub fn bridge_gap(mut self, gap: u32) -> Self { + self.set_bit(gap - self.sum); + self.sum = gap; + self + } +} + +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 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, + } + } + + 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; + } + } + } + + 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; + } + } + GapHeights::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: &GapHeights) -> bool { + for (i, r) in wall.iter().enumerate() { + let stone = (i + 1) as u32 - 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 + } +} diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs new file mode 100644 index 0000000..0b1d716 --- /dev/null +++ b/src/solvers/mod.rs @@ -0,0 +1 @@ +pub mod intuitive; diff --git a/src/structs.rs b/src/structs.rs new file mode 100644 index 0000000..571c79d --- /dev/null +++ b/src/structs.rs @@ -0,0 +1,98 @@ +pub struct StoneWall { + rows: Vec>, +} + +impl StoneWall { + pub fn create_empty(n: u32) -> Self { + let n = n as usize; + let h = n / 2 + 1; + let mut rows = vec![vec![0; n]; h]; + rows.get_mut(0).map(|r| r[0] = 1); + rows.get_mut(1).map(|r| r[1] = 2); + Self { + rows, + } + } +} + +pub struct GapHeights { + heights: Vec, +} + +impl GapHeights { + pub fn from_heights(heights: Vec) -> Self { + Self { heights } + } + + #[allow(dead_code)] + fn create_empty(w: u32) -> Self { + let heights = if w == 0 { + vec![] + } else if w == 1 { + vec![0] + } else { + let mut v = Vec::with_capacity(w as usize); + v.push(0); + v.push(1); + v + }; + Self { heights } + } + + pub fn add_gap(&mut self, height: u32) { + self.add_gap(height) + } + + pub fn calculate_row(&self, r: u32, stones: &mut [u32]) { + let mut len = 1; + let mut i = 0; + for &height in self.heights.iter().chain([r].iter()) { + if height == r { + stones[i] = len; + i += 1; + len = 0; + } + len += 1; + } + } + + pub fn output(&self, n: u32, h: u32) { + let mut stones = vec![0; n as usize]; + let mut toggle = 0; + let colors = [ + "\x1b[31m", "\x1b[32m", "\x1b[33m", "\x1b[34m", "\x1b[35m", "\x1b[36m", + ]; + for row in 0..h { + self.calculate_row(row, &mut stones); + for &len in stones.iter() { + print!("{}", colors[toggle]); + toggle = (toggle + 1) % colors.len(); + for _ in 0..len { + print!("◙"); + } + } + println!("\x1b[m"); + } + } + + pub fn iter<'a>(&'a self) -> GapIter<'a> { + GapIter { + gap_heights: self, + i: 0, + } + } +} + +pub struct GapIter<'a> { + gap_heights: &'a GapHeights, + i: usize, +} + +impl<'a> Iterator for GapIter<'a> { + type Item = u32; + fn next(&mut self) -> Option { + let i = self.i; + self.i += 1; + self.gap_heights.heights.get(i).map(|&x| x) + } +} -- cgit v1.2.3-54-g00ecf From db532edb6b63912f6cce0c5b6445b37686473069 Mon Sep 17 00:00:00 2001 From: natrixaeria Date: Sun, 22 Dec 2019 06:55:48 +0100 Subject: Create stone wall structure --- src/structs.rs | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/src/structs.rs b/src/structs.rs index 571c79d..fdc20f4 100644 --- a/src/structs.rs +++ b/src/structs.rs @@ -13,6 +13,27 @@ impl StoneWall { rows, } } + + pub fn set_stone(&mut self, row: u32, pos: u32, stone: u32) -> Option<()> { + self.rows.get_mut(row as usize).and_then(|v| v.get_mut(pos as usize)) + .map(|v| *v = stone) + } + + pub fn output(&self) { + let colors = [ + [31, 32], + [33, 35], + ]; + for (i, row) in self.rows.iter().enumerate() { + for (j, &stone) in row.iter().enumerate() { + print!("{}", colors[i & 1][j & 1]); + print!("\x1b[{}m{}", + colors[i & 1][j & 1], + "◙".repeat(stone as usize)); + } + println!("\x1b[m"); + } + } } pub struct GapHeights { @@ -81,6 +102,19 @@ impl GapHeights { i: 0, } } + + pub fn as_stone_wall(&self, n: u32) -> StoneWall { + let h = n/2 + 1; + let mut rows = Vec::with_capacity(h as usize); + for i in 0..h { + let mut row = vec![0; n as usize]; + self.calculate_row(i, &mut row); + rows.push(row); + } + StoneWall { + rows + } + } } pub struct GapIter<'a> { -- cgit v1.2.3-54-g00ecf