diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/main.rs | 9 | ||||
-rw-r--r-- | src/solvers/bwinf.rs | 200 | ||||
-rw-r--r-- | src/solvers/mod.rs | 1 |
3 files changed, 207 insertions, 3 deletions
diff --git a/src/main.rs b/src/main.rs index ee7082d..674d139 100644 --- a/src/main.rs +++ b/src/main.rs @@ -7,9 +7,12 @@ pub static N: u32 = 8; fn main() { //let mut solver = solvers::single::NormalSolver::new(N); //solver.solve(); - let solver = solvers::gpusolver::GpuSolver::new(N); + //let solver = solvers::gpusolver::GpuSolver::new(N); //println!("solver: {:?}", solver); - for (i, solution) in solver.solve().enumerate() { + /*for (i, solution) in solver.solve().enumerate() { println!("{}: {:?}", i, solution); - } + }*/ + let mut wall = solvers::bwinf::Wall::new(26); + wall.solve(); + wall.output() } diff --git a/src/solvers/bwinf.rs b/src/solvers/bwinf.rs new file mode 100644 index 0000000..fcf6876 --- /dev/null +++ b/src/solvers/bwinf.rs @@ -0,0 +1,200 @@ +#[derive(Clone, Debug)] +struct Row { + n: u32, b: u32, + palette: Vec<bool>, + max_stone: u32, + width: u32, + stones: Vec<u32>, + max_reachable: u32 +} + +impl Row { + fn new(n: u32, b: u32) -> Row { + Self { + n, b, + palette: vec![true; n as usize], + max_stone: n, + width: 0, + stones: Vec::with_capacity(n as usize), + max_reachable: n + } + } + + fn with_stone(n: u32, b: u32, s: u32) -> Row { + let mut stones = Vec::with_capacity(n as usize); + stones.push(s); + let max_stone = n - if s == n { 1 } else { 0 }; + Self { + n, b, + palette: (1..=n).map(|i| i != s).collect(), + max_stone: max_stone, + width: s, + stones, + max_reachable: s + max_stone, + } + } + + fn update(&mut self, x: u32) -> bool { + let stone_len = x - self.width; + if stone_len > self.n || !self.palette[(stone_len - 1) as usize] { + return false; + } + self.width = x; + self.palette[(stone_len - 1) as usize] = false; + self.stones.push(stone_len); + if self.max_stone == stone_len { + while !self.palette[(self.max_stone - 1) as usize] { + self.max_stone -= 1; + } + self.max_reachable = x + self.max_stone + } else { + self.max_reachable += stone_len + } + true + } + + fn undo_update(&mut self) { + let stone_len = self.stones.pop().unwrap(); + self.width -= stone_len; + self.palette[(stone_len - 1) as usize] = true; + if stone_len > self.max_stone { + self.max_stone = stone_len; + self.max_reachable = self.width + stone_len + } else { + self.max_reachable -= stone_len + } + } + + fn complete(&mut self) { + self.stones.push(self.b - self.width); + } + + fn output_repeat(&self) { + for (i, &stone) in self.stones.iter().enumerate() { + for _ in 0..stone { + print!("{}", ['-', '*'][i & 1]); + } + } + println!(""); + } + + fn output_numbers(&self) { + for stone in self.stones.iter() { + print!("{:2} ", stone); + } + println!(""); + } +} + +#[derive(Clone, Debug)] +pub struct Wall { + n: u32, h: u32, b: u32, + rows: Vec<Row>, + x: u32, + min_max_reachable: u32, + max_reached: u32, + steps: u32 +} + +impl Wall { + pub fn new(n: u32) -> Self { + let (h, b) = ((n >> 1) + 1, (n * n + n ) >> 1); + Self { + n, h, b, + rows: vec![Row::new(n, b); h as usize], + x: 1, + min_max_reachable: n, + max_reached: 0, + steps: 0 + } + } + + fn new_linear(n: u32) -> Self { + let (h, b) = ((n >> 1) + 1, (n * n + n ) >> 1); + let rows = (1..=h).map(|i| Row::with_stone(n, b, i)).collect(); + let x = h + 1; + Self { + n, h, b, + rows, + x, + min_max_reachable: 1 + n, + max_reached: n, + steps: 0 + } + } + + fn complete(&mut self) { + for row in self.rows.iter_mut() { + row.complete() + } + } + + fn order_key(&self, index: u32) -> (i32, i32) { + let row = self.rows.get(index as usize).unwrap(); + let stones = row.stones.len() as i32; + let width = row.width as i32; + let max_stone = row.max_stone as i32; + let index = index as i32; + //(-max_stone, index) + let perc = (self.x as f32 / (self.b as f32)) * (self.h as f32); + let dif = (perc - (index as f32)).abs().round() as i32; + (-max_stone, dif) + } + + fn order(&self) -> Vec<u32> { + //(0..self.h).collect() + let mut v: Vec<u32> = (0..self.h).collect(); + let b = self.b; + v.sort_unstable_by_key(|&row| self.order_key(row)); + v + } + + pub fn solve(&mut self) -> bool { + self.steps += 1; + // complete if already nearly complete + if self.x == self.b { + self.complete(); + return true; + } + let mut row_empty = false; + let min_max_reachable = self.min_max_reachable; + for row_index in self.order() { + if self.rows[row_index as usize].stones.is_empty() { + if row_empty { + break + } + row_empty = true; + } + let max_reachable = self.rows[row_index as usize].max_reachable; + if self.rows[row_index as usize].update(self.x) { + if max_reachable == self.min_max_reachable { + self.min_max_reachable = self.rows.iter() + .map(|v| v.max_reachable).min() + .unwrap(); + } + if self.min_max_reachable > self.x { + self.x += 1; + if self.solve() { + return true; + } + self.x -= 1; + } + self.min_max_reachable = min_max_reachable; + self.rows[row_index as usize].undo_update(); + } + } + false + } + + pub fn output(&self) { + for row in self.rows.iter() { + row.output_numbers(); + } + } +} + +/*fn main() { + let mut wall = Wall::new(26); + wall.solve(); + wall.output(); +}*/ diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs index de61639..84e9642 100644 --- a/src/solvers/mod.rs +++ b/src/solvers/mod.rs @@ -1,6 +1,7 @@ //pub mod incremental_block; pub mod gpu; pub mod gpusolver; +pub mod bwinf; //pub mod single; //use crate::structs::StoneWall; |