From db991f36810a460a152c60c9f284c93dd5bdf8db Mon Sep 17 00:00:00 2001
From: natrixaeria <upezu@student.kit.edu>
Date: Thu, 16 Jan 2020 18:04:43 +0100
Subject: Add bwinf solver and n=52 wall

---
 src/solvers/bwinf.rs | 200 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 200 insertions(+)
 create mode 100644 src/solvers/bwinf.rs

(limited to 'src/solvers/bwinf.rs')

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();
+}*/
-- 
cgit v1.2.3-54-g00ecf