From 0bb7242309483725f782d63593ae0d2d3da8b984 Mon Sep 17 00:00:00 2001
From: natrixaeria <upezu@student.kit.edu>
Date: Mon, 20 Jan 2020 15:07:38 +0100
Subject: Add optimized sorting preferences to bwinf solver

---
 src/main.rs          |  2 +-
 src/solvers/bwinf.rs | 38 +++++++++++++++++++-------------------
 2 files changed, 20 insertions(+), 20 deletions(-)

diff --git a/src/main.rs b/src/main.rs
index 1c92050..605bafc 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -3,7 +3,7 @@ mod solvers;
 mod structs;
 use crate::solvers::{IteratorSolver, Solver};
 
-pub static N: u32 = 30;
+pub static N: u32 = 40;
 fn main() {
     let clock = std::time::Instant::now();
 
diff --git a/src/solvers/bwinf.rs b/src/solvers/bwinf.rs
index dbcbea9..f8f2188 100644
--- a/src/solvers/bwinf.rs
+++ b/src/solvers/bwinf.rs
@@ -39,10 +39,10 @@ impl Row {
         }
     }
 
-    fn update(&mut self, x: u32) -> bool {
+    fn update(&mut self, x: u32) -> Option<u32> {
         let stone_len = x - self.width;
         if stone_len > self.n || !self.palette[(stone_len - 1) as usize] {
-            return false;
+            return None;
         }
         self.width = x;
         self.palette[(stone_len - 1) as usize] = false;
@@ -55,7 +55,7 @@ impl Row {
         } else {
             self.max_reachable += stone_len
         }
-        true
+        Some(stone_len)
     }
 
     fn undo_update(&mut self) {
@@ -100,7 +100,8 @@ pub struct BwinfSolver {
     x: u32,
     min_max_reachable: u32,
     max_reached: u32,
-    steps: u64
+    steps: u64,
+    stone_counts: Vec<u64>,
 }
 
 impl Solver for BwinfSolver {
@@ -115,6 +116,7 @@ impl Solver for BwinfSolver {
             min_max_reachable: n,
             max_reached: 0,
             steps: 0,
+            stone_counts: vec![0; n as usize]
         }
     }
 
@@ -140,6 +142,8 @@ impl BwinfSolver {
         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;
+        let mut stone_counts = vec![1; h as usize];
+        stone_counts.append(&mut vec![0; (n - h) as usize]);
         Self {
             n,
             h,
@@ -149,6 +153,7 @@ impl BwinfSolver {
             min_max_reachable: 1 + n,
             max_reached: n,
             steps: 0,
+            stone_counts
         }
     }
 
@@ -158,25 +163,18 @@ impl BwinfSolver {
         }
     }
 
-    fn order_key(&self, index: u32) -> (i32, i32) {
+    fn order_key(&self, index: u32) -> (u64, usize, 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)
-        (index, 0)
+        (self.stone_counts[(self.x - row.width - 1) as usize] as u64,
+         row.stones.len() as usize,
+         -(row.width as i32))
     }
 
     fn order(&self) -> Vec<u32> {
-        (0..self.h).collect()
-        /*let mut v: Vec<u32> = (0..self.h).collect();
-        let b = self.b;
+        //(0..self.h).collect()
+        let mut v: Vec<u32> = (0..self.h).collect();
         v.sort_unstable_by_key(|&row| self.order_key(row));
-        v*/
+        v
     }
 
     fn solve_recursive(&mut self) -> bool {
@@ -196,7 +194,8 @@ impl BwinfSolver {
                 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 let Some(stone) = self.rows[row_index as usize].update(self.x) {
+                self.stone_counts[stone as usize - 1] += 1;
                 if max_reachable == self.min_max_reachable {
                     self.min_max_reachable =
                         self.rows.iter().map(|v| v.max_reachable).min().unwrap();
@@ -210,6 +209,7 @@ impl BwinfSolver {
                 }
                 self.min_max_reachable = min_max_reachable;
                 self.rows[row_index as usize].undo_update();
+                self.stone_counts[stone as usize - 1] -= 1;
             }
         }
         false
-- 
cgit v1.2.3-54-g00ecf