From db991f36810a460a152c60c9f284c93dd5bdf8db Mon Sep 17 00:00:00 2001 From: natrixaeria Date: Thu, 16 Jan 2020 18:04:43 +0100 Subject: Add bwinf solver and n=52 wall --- data/mauer52.txt | 50 +++++++++++++ src/main.rs | 9 ++- src/solvers/bwinf.rs | 200 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/solvers/mod.rs | 1 + 4 files changed, 257 insertions(+), 3 deletions(-) create mode 100644 data/mauer52.txt create mode 100644 src/solvers/bwinf.rs diff --git a/data/mauer52.txt b/data/mauer52.txt new file mode 100644 index 0000000..889d6ef --- /dev/null +++ b/data/mauer52.txt @@ -0,0 +1,50 @@ +bei (1378/1378), 100.0% angekommen + ++========================================+ +|¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦| ++========================================+ + +////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// 1 28 3 6 12 24 48 44 34 10 19 46 35 37 9 7 14 31 33 45 39 15 36 22 40 21 52 51 49 50 41 26 8 47 43 2 42 20 5 4 13 16 17 11 38 30 27 32 29 18 23 25 // +// 2 29 5 10 20 40 24 52 51 47 42 27 1 4 6 13 23 19 14 30 12 18 35 31 50 3 43 46 33 9 21 44 32 48 8 7 36 22 37 26 16 15 11 25 49 45 28 41 39 17 34 38 // +// 3 30 7 14 27 1 5 6 12 26 52 51 48 45 32 16 28 24 23 50 49 46 37 22 47 34 35 42 39 17 43 10 41 11 44 31 4 40 19 38 2 9 25 18 29 13 15 20 36 8 33 21 // +// 4 31 9 18 36 17 34 16 33 14 24 52 51 50 46 37 15 41 20 44 39 13 25 2 5 28 42 29 12 11 22 45 48 40 27 49 8 3 26 30 38 7 32 43 47 1 10 23 35 19 21 6 // +// 5 32 11 22 44 33 24 38 28 52 51 50 47 41 25 49 48 43 35 13 19 46 40 27 9 14 31 45 39 17 15 10 8 12 30 7 18 42 34 1 16 20 21 6 2 23 4 37 36 3 29 26 // +// 6 33 13 28 3 2 4 8 16 35 10 22 48 41 32 12 17 39 29 38 40 19 44 34 18 27 11 26 45 43 14 42 23 21 30 9 5 1 31 46 24 25 36 47 20 51 37 52 50 49 15 7 // +// 7 34 15 30 9 14 28 3 6 8 19 41 26 4 2 13 37 18 22 45 35 16 31 5 17 33 12 23 1 52 51 50 47 38 48 36 25 29 42 49 40 39 44 32 20 46 43 10 24 27 21 11 // +// 8 35 17 34 40 11 14 27 18 13 31 39 50 46 41 20 48 42 28 3 7 10 21 47 37 30 4 1 2 23 22 36 33 12 19 49 52 43 29 5 51 6 9 44 26 45 38 24 25 16 32 15 // +// 9 36 19 38 21 45 40 17 42 25 1 26 23 52 51 49 43 32 14 29 10 2 12 27 22 35 7 6 18 37 20 31 13 28 16 33 50 48 46 34 15 47 5 24 3 30 44 11 8 39 41 4 // +// 10 37 21 42 29 5 17 26 3 2 49 6 7 9 23 48 44 33 8 15 36 38 18 19 39 30 47 52 24 11 20 51 40 35 43 4 13 31 45 50 41 25 46 34 32 12 1 16 27 22 28 14 // +// 11 38 23 46 39 31 1 5 7 30 45 40 19 47 36 21 43 27 4 8 14 29 6 9 17 44 24 52 51 50 49 48 34 3 15 35 42 12 16 32 28 41 10 22 37 13 2 25 20 26 33 18 // +// 12 39 25 50 48 42 29 5 8 15 33 11 28 26 20 52 47 37 16 43 23 51 49 41 36 9 21 44 38 14 32 2 6 40 3 7 22 45 19 1 27 31 17 46 24 35 34 18 4 30 13 10 // +// 13 40 26 32 30 12 28 49 44 34 16 33 8 21 42 25 11 9 24 47 37 20 45 38 15 39 27 6 3 10 7 19 35 29 52 5 14 51 4 41 23 17 2 46 50 18 43 22 31 36 48 1 // +// 14 41 29 7 10 20 43 32 23 34 11 30 5 3 9 15 35 19 37 39 2 4 21 36 17 42 24 46 40 31 12 48 1 13 16 44 25 22 38 18 52 51 6 28 50 47 49 26 33 45 27 8 // +// 15 42 31 11 18 38 20 43 33 14 26 40 41 25 52 28 16 45 30 12 35 1 5 7 17 32 4 8 37 3 34 51 50 46 39 10 23 9 13 6 21 48 27 24 29 36 49 47 44 19 22 2 // +// 16 43 33 15 25 52 51 50 47 42 27 1 2 3 7 12 29 6 8 22 40 26 4 5 28 36 19 34 20 38 31 17 37 45 49 48 30 14 32 10 13 24 23 18 35 21 11 39 44 46 9 41 // +// 17 44 35 37 23 21 45 39 22 46 38 32 11 10 34 20 31 2 3 5 52 8 13 25 4 9 41 1 6 24 27 15 26 40 43 18 49 42 29 19 28 50 51 30 48 12 47 16 14 36 7 33 // +// 18 45 37 19 41 25 12 9 15 36 21 43 20 52 49 46 34 10 27 51 48 50 47 39 30 1 4 5 8 16 33 13 23 44 38 24 42 11 40 26 35 28 14 17 3 6 22 32 2 31 7 29 // +// 19 46 39 23 49 44 35 16 29 4 8 36 3 2 5 10 17 40 22 52 51 47 38 31 9 18 21 45 48 41 24 37 30 1 7 20 32 33 50 42 14 15 13 12 6 27 25 43 26 34 11 28 // +// 20 47 41 27 1 2 4 9 18 36 22 43 28 7 13 25 52 51 50 46 35 16 34 15 30 10 23 44 33 8 38 26 32 3 6 11 19 49 45 37 21 48 12 40 29 24 31 17 14 42 39 5 // +// 21 48 43 31 7 13 30 6 16 27 1 36 41 24 44 45 32 10 29 52 51 49 50 46 25 26 28 2 11 37 12 4 20 47 33 18 34 9 14 38 8 22 35 42 5 15 39 23 19 40 17 3 // +// 22 49 45 36 15 35 11 25 18 12 27 2 10 21 34 38 5 4 13 26 50 48 41 32 6 8 20 42 17 52 51 47 46 24 28 16 1 39 23 37 29 3 7 33 14 40 19 31 44 30 43 9 // +// 23 50 47 42 29 4 8 20 37 17 38 31 24 22 48 44 32 7 40 41 33 28 14 11 25 30 13 43 34 6 15 27 2 18 21 19 12 26 5 52 36 35 10 39 3 46 1 51 49 9 45 16 // +// 24 51 49 46 37 32 10 3 20 31 6 14 29 12 15 34 18 35 13 23 45 38 26 36 39 16 40 19 52 50 42 28 9 21 25 2 17 11 27 1 22 33 41 8 43 7 48 5 47 44 4 30 // +// 25 52 51 50 46 38 19 44 30 11 18 39 28 1 49 13 6 9 22 48 42 29 3 7 12 26 16 10 32 2 5 14 24 34 20 15 17 27 41 47 35 45 21 4 36 23 33 8 40 37 43 31 // +// 26 52 51 50 47 40 24 48 49 43 27 3 7 14 30 1 21 25 2 11 19 33 16 23 32 29 5 8 17 28 4 15 18 39 22 44 46 36 20 38 31 45 41 34 9 10 35 42 12 37 6 13 // +// 27 1 2 4 8 16 32 13 22 47 39 21 52 49 43 30 6 9 17 42 26 11 24 33 15 31 14 18 44 36 41 29 25 3 7 10 23 45 35 34 51 50 48 37 19 46 38 40 28 20 5 12 // +////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +____________________________ + | +Informationen | +____________________________| + | + - n = 52 | + - h = 27 | + - b = 1378 | + - schritte = 557964847 | + | +------------------ | +brauchte 17542.22s | + | +____________________________| \ No newline at end of file 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, + max_stone: u32, + width: u32, + stones: Vec, + 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, + 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 { + //(0..self.h).collect() + let mut v: Vec = (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; -- cgit v1.2.3-54-g00ecf