diff options
author | natrixaeria <upezu@student.kit.edu> | 2020-01-20 14:02:13 +0100 |
---|---|---|
committer | natrixaeria <upezu@student.kit.edu> | 2020-01-20 14:02:13 +0100 |
commit | 41b495d23cd0772811b424a9a006de8b22de7cb4 (patch) | |
tree | 42ecf3c224b8a12bcd76a75d10ccc2bfce49c363 /src/solvers | |
parent | 093b21afc08787cb17b5ac0b0c133a01aa972837 (diff) | |
parent | 9dbc4eb4c9e7ad8b737eb02702023669ecc812bf (diff) |
Merge branch 'master' of dennis:/var/repos/babel
Diffstat (limited to 'src/solvers')
-rw-r--r-- | src/solvers/bwinf.rs | 60 | ||||
-rw-r--r-- | src/solvers/mod.rs | 4 |
2 files changed, 38 insertions, 26 deletions
diff --git a/src/solvers/bwinf.rs b/src/solvers/bwinf.rs index 8c9624b..dbcbea9 100644 --- a/src/solvers/bwinf.rs +++ b/src/solvers/bwinf.rs @@ -2,23 +2,25 @@ use super::{Solver, FirstSolver}; #[derive(Clone, Debug)] struct Row { - n: u32, b: u32, + n: u32, + b: u32, palette: Vec<bool>, max_stone: u32, width: u32, stones: Vec<u32>, - max_reachable: u32 + max_reachable: u32, } impl Row { fn new(n: u32, b: u32) -> Row { Self { - n, b, + n, + b, palette: vec![true; n as usize], max_stone: n, width: 0, stones: Vec::with_capacity(n as usize), - max_reachable: n + max_reachable: n, } } @@ -27,9 +29,10 @@ impl Row { stones.push(s); let max_stone = n - if s == n { 1 } else { 0 }; Self { - n, b, + n, + b, palette: (1..=n).map(|i| i != s).collect(), - max_stone: max_stone, + max_stone, width: s, stones, max_reachable: s + max_stone, @@ -77,20 +80,22 @@ impl Row { print!("{}", ['-', '*'][i & 1]); } } - println!(""); + println!(); } fn output_numbers(&self) { for stone in self.stones.iter() { print!("{:2} ", stone); } - println!(""); + println!(); } } #[derive(Clone, Debug)] pub struct BwinfSolver { - n: u32, h: u32, b: u32, + n: u32, + h: u32, + b: u32, rows: Vec<Row>, x: u32, min_max_reachable: u32, @@ -102,12 +107,14 @@ impl Solver for BwinfSolver { fn new(n: u32) -> Self { let (h, b) = ((n >> 1) + 1, (n * n + n ) >> 1); Self { - n, h, b, + n, + h, + b, rows: vec![Row::new(n, b); h as usize], x: 1, min_max_reachable: n, max_reached: 0, - steps: 0 + steps: 0, } } @@ -125,17 +132,23 @@ impl Solver for BwinfSolver { } impl BwinfSolver { + pub fn solve(&mut self) { + self.solve_recursive(); + } + fn new_linear(n: u32) -> Self { - let (h, b) = ((n >> 1) + 1, (n * n + n ) >> 1); + 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, + n, + h, + b, rows, x, min_max_reachable: 1 + n, max_reached: n, - steps: 0 + steps: 0, } } @@ -147,8 +160,8 @@ impl BwinfSolver { 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 _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) @@ -159,11 +172,11 @@ impl BwinfSolver { } fn order(&self) -> Vec<u32> { - //(0..self.h).collect() - let mut v: Vec<u32> = (0..self.h).collect(); + (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 + v*/ } fn solve_recursive(&mut self) -> bool { @@ -178,20 +191,19 @@ impl BwinfSolver { for row_index in self.order() { if self.rows[row_index as usize].stones.is_empty() { if row_empty { - break + 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(); + 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() { + if self.solve_recursive() { return true; } self.x -= 1; diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs index 8fdd296..0ea589b 100644 --- a/src/solvers/mod.rs +++ b/src/solvers/mod.rs @@ -17,10 +17,10 @@ pub trait Solver { } pub trait FirstSolver { - fn solve(self) -> RowResult; + fn solve(self) -> gpu::RowResult; } pub trait IteratorSolver: Solver { - type IntoIter: Iterator<Item = RowResult>; + type IntoIter: Iterator<Item = gpu::RowResult>; fn solve(self) -> Self::IntoIter; } |