Add bwinf solver and n=52 wall

4 files changed, 257 insertions, 3 deletions

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<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;