hw(4/AI): Faster implementation

1 files changed, 97 insertions, 96 deletions

diff --git a/Year 4/Artificial Intelligence/hw02/src/main.rs b/Year 4/Artificial Intelligence/hw02/src/main.rs
index 8fd19a2..0d2ec11 100644
--- a/Year 4/Artificial Intelligence/hw02/src/main.rs
+++ b/Year 4/Artificial Intelligence/hw02/src/main.rs
@@ -2,136 +2,136 @@
 use text_io::read;
 use rand::{Rng, rngs::ThreadRng};
 use std::fmt::{Display, Formatter, Result};
-
-#[derive(Clone)]
-struct Queen {
-    is: bool,
-    attacks: i32,
-}
+use std::time::Instant;
 
 struct Puzzle {
-    board: Vec<Vec<Queen>>,
-    N: usize,
+    in_col: Vec<usize>,
+    per_row: Vec<i32>,
+    per_d1: Vec<i32>,
+    per_d2: Vec<i32>,
 
+    N: usize,
     rng: ThreadRng,
 }
 
 impl Puzzle {
-    fn clean_board(N: usize) -> Vec<Vec<Queen>> {
-        vec![vec![Queen { is: false, attacks: 0 }; N]; N]
-    }
     pub fn new(N: usize) -> Puzzle {
         Puzzle {
-            board: Puzzle::clean_board(N),
+            in_col:  vec![0; N],
+            per_row: vec![0; N],
+            per_d1:  vec![0; 2 * N - 1],
+            per_d2:  vec![0; 2 * N - 1],
             N: N,
             rng: rand::thread_rng(),
         }
     }
 
-    fn max_col(&mut self) -> usize {
-        let (mut maxAttacks, mut maxInds) = (0, Vec::new());
+    fn max_queen_col(&mut self) -> usize {
+        let (mut max_attacks, mut ind) = (0, Vec::new());
         for col in 0..self.N {
-            let mut maxRowAttacks = 0;
-            for row in 0..self.N {
-                if maxRowAttacks < self.board[col][row].attacks {
-                    maxRowAttacks = self.board[col][row].attacks;
-                }
-            }
-            if maxAttacks < maxRowAttacks {
-                maxAttacks = maxRowAttacks;
-                maxInds.clear();
+            let attacks = self.per_row[self.in_col[col]] +
+                          self.per_d1[col + self.N - 1 - self.in_col[col]] +
+                          self.per_d2[col + self.in_col[col]];
+
+            if max_attacks < attacks {
+                max_attacks = attacks;
+                ind.clear();
             }
-            if maxAttacks == maxRowAttacks {
-                maxInds.push(col);
+            if max_attacks == attacks {
+                ind.push(col);
             }
         }
 
-        if maxInds.len() == 1 {
-            return maxInds[0];
+        if ind.len() > 1 {
+            return ind[self.rng.gen_range(0..ind.len())];
         }
-        return maxInds[self.rng.gen_range(0..maxInds.len())];
+        return ind[0];
     }
+
     fn min_col_row(&mut self, colI: usize) -> usize {
-        let (mut minAttacks, mut minInds) = (i32::MAX, Vec::new());
+        let (mut min_row, mut min_ind) = (i32::MAX, Vec::new());
         for row in 0..self.N {
-            if self.board[colI][row].attacks < minAttacks {
-                minAttacks = self.board[colI][row].attacks;
-                minInds.clear();
+            let attacks = self.per_row[row] +
+                          self.per_d1[colI + self.N - 1 - row] +
+                          self.per_d2[colI + row];
+
+            if attacks < min_row {
+                min_row = attacks;
+                min_ind.clear();
             }
-            if self.board[colI][row].attacks == minAttacks {
-                minInds.push(row);
+            if attacks == min_row {
+                min_ind.push(row);
             }
         }
 
-        if minInds.len() == 1 {
-            return minInds[0];
+        if min_ind.len() > 1 {
+            return min_ind[self.rng.gen_range(0..min_ind.len())];
         }
-        return minInds[self.rng.gen_range(0..minInds.len())];
+        return min_ind[0];
     }
 
-    fn modify(&mut self, place: bool, colI: usize, rowI: usize) {
-        if place == self.board[colI][rowI].is { panic!("Cannot {} modify", place); }
-
-        self.board[colI][rowI].is = place;
-        let change = if place { 1 } else { -1 };
-        self.board[colI][rowI].attacks += change;
-
-        for offset in 1..self.N {
-            let (l, r, u, d) = (0 <= colI as i32 - offset as i32, colI + offset < self.N,
-                                0 <= rowI as i32 - offset as i32, rowI + offset < self.N);
-            if l { self.board[colI - offset][rowI].attacks += change; }
-            if r { self.board[colI + offset][rowI].attacks += change; }
-            if u { self.board[colI][rowI - offset].attacks += change; }
-            if d { self.board[colI][rowI + offset].attacks += change; }
-            if l && u { self.board[colI - offset][rowI - offset].attacks += change; }
-            if l && d { self.board[colI - offset][rowI + offset].attacks += change; }
-            if r && u { self.board[colI + offset][rowI - offset].attacks += change; }
-            if r && d { self.board[colI + offset][rowI + offset].attacks += change; }
-        }
-    }
-    fn place_queen(&mut self, colI: usize, rowI: usize) {
-        self.modify(true, colI, rowI);
-    }
-    fn remove_queen(&mut self, colI: usize, rowI: usize) {
-        self.modify(false, colI, rowI);
+    fn update(&mut self, colI: usize, val: i32) {
+        self.per_row[self.in_col[colI]] += val;
+        self.per_d1[colI + self.N - 1 - self.in_col[colI]] += val;
+        self.per_d2[colI + self.in_col[colI]] += val;
     }
     fn move_queen(&mut self, colI: usize, rowI: usize) {
-        let mut queenRow = 0;
-        for i in 0..self.N {
-            if self.board[colI][i].is {
-                queenRow = i;
-                break;
-            }
-        }
+        if rowI == self.in_col[colI] { return; }
 
-        if queenRow == rowI { return; }
-        self.remove_queen(colI, queenRow);
-        self.place_queen(colI, rowI);
+        self.update(colI, -1);
+        self.in_col[colI] = rowI;
+        self.update(colI, 1);
     }
 
     fn has_conflicts(&self) -> bool {
         for i in 0..self.N {
-            for j in 0..self.N {
-                if self.board[i][j].is && self.board[i][j].attacks > 1 {
-                    return true;
-                }
-            }
+            if self.per_row[i] > 1 { return true; }
+        }
+        for i in 0..2 * self.N - 1 {
+            if self.per_d1[i] > 1 || self.per_d2[i] > 1 { return true; }
         }
         return false;
     }
 
     fn init(&mut self) {
-        self.board = Self::clean_board(self.N);
+        // Clear
+        for i in 0..2 * self.N - 1 {
+            self.per_d1[i] = 0;
+            self.per_d2[i] = 0;
+            if i < self.N {
+                self.per_row[i] = 0;
+            }
+        }
+
         for col in 0..self.N {
-            let r = self.min_col_row(col);
-            self.place_queen(col, r);
+            let row = self.min_col_row(col);
+            self.in_col[col] = row;
+            self.update(col, 1);
         }
+        return;
+
+        // Horse
+        // let (mut col, mut row) = (1, 0);
+        // for _ in 0..self.N / 2 {
+        //     self.in_col[col] = row;
+        //     self.update(col, 1);
+        //     col += 2;
+        //     row += 1;
+        // }
+        // let (mut col, mut row) = (0, self.N / 2);
+        // for _ in 0..self.N / 2 {
+        //     self.in_col[col] = row;
+        //     self.update(col, 1);
+        //     col += 2;
+        //     row += 1;
+        // }
     }
+
     pub fn solve(&mut self) {
         loop {
             self.init();
-            for _ in 0..self.N*self.N {
-                let col = self.max_col();
+            for _ in 0..self.N {
+                let col = self.max_queen_col();
                 let row = self.min_col_row(col);
                 self.move_queen(col, row);
             }
@@ -140,25 +140,13 @@ impl Puzzle {
             }
         }
     }
-
-    fn print_marks(&self) {
-        for row in 0..self.N {
-            for col in 0..self.N {
-                print!("{}", self.board[col][row].attacks);
-                if col < self.N - 1 {
-                    print!(" ");
-                }
-            }
-            println!("");
-        }
-    }
 }
 
 impl Display for Puzzle {
     fn fmt(&self, f: &mut Formatter) -> Result {
         for row in 0..self.N {
             for col in 0..self.N {
-                if self.board[col][row].is {
+                if self.in_col[col] == row {
                     write!(f, "*")?;
                 }
                 else {
@@ -176,7 +164,20 @@ impl Display for Puzzle {
 
 fn main() {
     let N: usize = read!();
+    if N < 4 {
+        println!("-1");
+        return;
+    }
     let mut task = Puzzle::new(N);
+
+    let start = Instant::now();
     task.solve();
-    println!("{}", task);
+    let elapsed = start.elapsed();
+
+    if N > 100 {
+        println!("{:.2}", elapsed.as_secs_f64());
+    }
+    else {
+        println!("{}", task);
+    }
 }