hw(AI/2): Separate into files, test attacks, fix attacks, fix clear, add assertions, add example board

4 files changed, 237 insertions, 175 deletions

diff --git a/Year 4/Artificial Intelligence/hw02/src/alg.rs b/Year 4/Artificial Intelligence/hw02/src/alg.rs
new file mode 100644
index 0000000..2ee321f
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw02/src/alg.rs
@@ -0,0 +1,62 @@
+use super::Puzzle;
+use rand::Rng;
+
+impl Puzzle {
+    fn has_conflicts(&self) -> bool {
+        for i in 0..self.N {
+            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_horse(&mut self) {
+        self.clear();
+
+        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;
+        }
+    }
+
+    fn init_rand(&mut self) {
+        self.clear();
+
+        self.in_col[0] = self.rng.gen_range(0..self.N);
+        self.update(0, 1);
+
+        for col in 1..self.N {
+            self.in_col[col] = self.min_col_row(col);
+            self.update(col, 1);
+        }
+    }
+
+    pub fn solve(&mut self) {
+        self.init_horse();
+        loop {
+            for _ in 0..2 * self.N {
+                let col = self.max_queen_col();
+                if col == self.N { return; }
+
+                let row = self.min_col_row(col);
+                self.move_queen(col, row);
+            }
+            if !self.has_conflicts() {
+                break;
+            }
+            self.init_rand();
+        }
+    }
+}
diff --git a/Year 4/Artificial Intelligence/hw02/src/cell.rs b/Year 4/Artificial Intelligence/hw02/src/cell.rs
new file mode 100644
index 0000000..9b36199
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw02/src/cell.rs
@@ -0,0 +1,74 @@
+use super::Puzzle;
+use rand::Rng;
+
+impl Puzzle {
+    pub fn max_queen_col(&mut self) -> usize {
+        if self.max_attack == 3 {
+            return self.N;
+        }
+
+        if self.max_queens.len() > 1 {
+            return self.max_queens[self.rng.gen_range(0..self.max_queens.len())];
+        }
+        return self.max_queens[0];
+    }
+
+    pub fn min_col_row(&mut self, colI: usize) -> usize {
+        let (mut min_row, mut min_ind) = (i32::MAX, Vec::new());
+        for row in 0..self.N {
+            let attacks = self.attacks(colI, row);
+
+            if attacks < min_row {
+                min_row = attacks;
+                min_ind.clear();
+            }
+            if attacks == min_row {
+                min_ind.push(row);
+            }
+        }
+
+        if min_ind.len() > 1 {
+            return min_ind[self.rng.gen_range(0..min_ind.len())];
+        }
+        return min_ind[0];
+    }
+
+    pub fn update(&mut self, colI: usize, val: i32) {
+        let old_attack = self.attacks(colI, self.in_col[colI]);
+
+        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;
+
+        if val < 0 {
+            if old_attack != self.max_attack { return; }
+
+            for i in 0..self.max_queens.len() {
+                if self.max_queens[i] == colI {
+                    self.max_queens.remove(i);
+                    return;
+                }
+            }
+            unreachable!();
+        }
+
+        let current_attack = self.attacks(colI, self.in_col[colI]);
+
+        if self.max_attack < current_attack {
+            self.max_queens.clear();
+            self.max_queens.push(colI);
+            self.max_attack = current_attack;
+        }
+        if self.max_attack == current_attack {
+            self.max_queens.push(colI);
+        }
+    }
+
+    pub fn move_queen(&mut self, colI: usize, rowI: usize) {
+        if rowI == self.in_col[colI] { return; }
+
+        self.update(colI, -1);
+        self.in_col[colI] = rowI;
+        self.update(colI, 1);
+    }
+}
diff --git a/Year 4/Artificial Intelligence/hw02/src/helper.rs b/Year 4/Artificial Intelligence/hw02/src/helper.rs
new file mode 100644
index 0000000..478e400
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw02/src/helper.rs
@@ -0,0 +1,91 @@
+use super::{ Puzzle, MAXN };
+
+impl Puzzle {
+    pub fn new(N: usize) -> Puzzle {
+        Puzzle {
+            in_col:  [0; MAXN],
+            per_row: [0; MAXN],
+            per_d1:  [0; 2 * MAXN - 1],
+            per_d2:  [0; 2 * MAXN - 1],
+
+            max_attack: 0,
+            max_queens: Vec::with_capacity(N),
+
+            N: N,
+            rng: rand::thread_rng(),
+        }
+    }
+
+    pub fn clear(&mut self) {
+        for i in 0..2 * self.N - 1 {
+            if i < self.N {
+                self.in_col[i] = 0;
+                self.per_row[i] = 0;
+            }
+            else if i < MAXN {
+                assert_eq!(self.in_col[i], 0);
+                assert_eq!(self.per_row[i], 0);
+            }
+            self.per_d1[i] = 0;
+            self.per_d2[i] = 0;
+        }
+        self.max_attack = 0;
+        self.max_queens.clear();
+    }
+
+    pub fn attacks(&self, col: usize, row: usize) -> i32 {
+        assert!(col < self.N && row < self.N);
+
+        1 +                 // Always a queen on a column
+        self.per_row[row] + // Queens on the row
+        self.per_d1[col + self.N - 1 - row] +
+        self.per_d2[col + row]
+        - 3 * ((self.in_col[col] == row) as i32)
+        // If we're in the cell with a queen, remove repeated counts of it
+    }
+
+    // | |*| | |
+    // | | |*| |
+    // | | | |*|
+    // |*| | | |
+    pub fn example1() -> Puzzle {
+        let mut r = Puzzle::new(4);
+        r.in_col[0] = 3;
+        r.in_col[1] = 0;
+        r.in_col[2] = 1;
+        r.in_col[3] = 2;
+        r.per_row[0] = 1; r.per_row[1] = 1; r.per_row[2] = 1; r.per_row[3] = 1;
+
+        r.per_d1[0] = 1;
+        r.per_d1[4] = 3;
+
+        r.per_d2[1] = 1;
+        r.per_d2[3] = 2;
+        r.per_d2[5] = 1;
+        r
+    }
+}
+
+#[test]
+fn test_attacks() {
+    let e1 = Puzzle::example1();
+    assert_eq!(e1.attacks(0, 0), 2); // top-left
+    assert_eq!(e1.attacks(0, 1), 3); // below top-left
+    assert_eq!(e1.attacks(0, 2), 2);
+    assert_eq!(e1.attacks(0, 3), 2);
+
+    assert_eq!(e1.attacks(1, 0), 3); // right of top-left
+    assert_eq!(e1.attacks(1, 1), 2);
+    assert_eq!(e1.attacks(1, 2), 4);
+    assert_eq!(e1.attacks(1, 3), 2);
+
+    assert_eq!(e1.attacks(2, 0), 2);
+    assert_eq!(e1.attacks(2, 1), 4);
+    assert_eq!(e1.attacks(2, 2), 2);
+    assert_eq!(e1.attacks(2, 3), 3);
+
+    assert_eq!(e1.attacks(3, 0), 4);
+    assert_eq!(e1.attacks(3, 1), 2);
+    assert_eq!(e1.attacks(3, 2), 3);
+    assert_eq!(e1.attacks(3, 3), 2);
+}
diff --git a/Year 4/Artificial Intelligence/hw02/src/main.rs b/Year 4/Artificial Intelligence/hw02/src/main.rs
index f36f5c6..2de0630 100644
--- a/Year 4/Artificial Intelligence/hw02/src/main.rs
+++ b/Year 4/Artificial Intelligence/hw02/src/main.rs
@@ -1,16 +1,16 @@
 #![allow(non_snake_case)]
 use text_io::read;
-use rand::{Rng, rngs::ThreadRng};
+use rand::rngs::ThreadRng;
 use std::fmt::{Display, Formatter, Result};
 use std::time::Instant;
 
-const MAXN: usize = 10000;
+pub const MAXN: usize = 10010;
 
-struct Puzzle {
-    in_col:  [usize; MAXN],
-    per_row: [i32; MAXN],
-    per_d1:  [i32; 2 * MAXN - 1],
-    per_d2:  [i32; 2 * MAXN - 1],
+pub struct Puzzle {
+    in_col:  [usize; MAXN],       // Позиция в колона
+    per_row: [i32; MAXN],         // Бройка на ред
+    per_d1:  [i32; 2 * MAXN - 1], // Бройка на главен диагонал
+    per_d2:  [i32; 2 * MAXN - 1], // Бройка на втори диагонал
 
     max_attack: i32,
     max_queens: Vec<usize>,
@@ -19,174 +19,9 @@ struct Puzzle {
     rng: ThreadRng,
 }
 
-impl Puzzle {
-    /* Helper */
-
-    pub fn new(N: usize) -> Puzzle {
-        Puzzle {
-            in_col:  [0; MAXN],
-            per_row: [0; MAXN],
-            per_d1:  [0; 2 * MAXN - 1],
-            per_d2:  [0; 2 * MAXN - 1],
-
-            max_attack: 0,
-            max_queens: Vec::with_capacity(N),
-
-            N: N,
-            rng: rand::thread_rng(),
-        }
-    }
-
-    fn attacks(&self, col: usize, row: usize) -> i32 {
-        self.per_row[row] +
-        self.per_d1[col + self.N - 1 - row] +
-        self.per_d2[col + row]
-    }
-
-    fn clear(&mut self) {
-        self.max_attack = 0;
-        self.max_queens.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;
-            }
-        }
-    }
-
-    /* Cells */
-
-    fn max_queen_col(&mut self) -> usize {
-        if self.max_attack == 3 {
-            return self.N;
-        }
-
-        if self.max_queens.len() > 1 {
-            return self.max_queens[self.rng.gen_range(0..self.max_queens.len())];
-        }
-        return self.max_queens[0];
-    }
-
-    fn min_col_row(&mut self, colI: usize) -> usize {
-        let (mut min_row, mut min_ind) = (i32::MAX, Vec::new());
-        for row in 0..self.N {
-            let attacks = self.attacks(colI, row);
-
-            if attacks < min_row {
-                min_row = attacks;
-                min_ind.clear();
-            }
-            if attacks == min_row {
-                min_ind.push(row);
-            }
-        }
-
-        if min_ind.len() > 1 {
-            return min_ind[self.rng.gen_range(0..min_ind.len())];
-        }
-        return min_ind[0];
-    }
-
-    fn update(&mut self, colI: usize, val: i32) {
-        let old_attack = self.attacks(colI, self.in_col[colI]);
-
-        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;
-
-        if val < 0 {
-            if old_attack != self.max_attack { return; }
-
-            for i in 0..self.max_queens.len() {
-                if self.max_queens[i] == colI {
-                    self.max_queens.remove(i);
-                    return;
-                }
-            }
-            unreachable!();
-        }
-
-        let current_attack = self.attacks(colI, self.in_col[colI]);
-
-        if self.max_attack < current_attack {
-            self.max_queens.clear();
-            self.max_queens.push(colI);
-            self.max_attack = current_attack;
-        }
-        if self.max_attack == current_attack {
-            self.max_queens.push(colI);
-        }
-    }
-
-    fn move_queen(&mut self, colI: usize, rowI: usize) {
-        if rowI == self.in_col[colI] { return; }
-
-        self.update(colI, -1);
-        self.in_col[colI] = rowI;
-        self.update(colI, 1);
-    }
-
-    /* Algorithm */
-
-    fn has_conflicts(&self) -> bool {
-        for i in 0..self.N {
-            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_horse(&mut self) {
-        self.clear();
-
-        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;
-        }
-    }
-
-    fn init_rand(&mut self) {
-        self.clear();
-
-        self.in_col[0] = self.rng.gen_range(0..self.N);
-        self.update(0, 1);
-
-        for col in 1..self.N {
-            self.in_col[col] = self.min_col_row(col);
-            self.update(col, 1);
-        }
-    }
-
-    pub fn solve(&mut self) {
-        self.init_horse();
-        loop {
-            for _ in 0..2 * self.N {
-                let col = self.max_queen_col();
-                if col == self.N { return; }
-
-                let row = self.min_col_row(col);
-                self.move_queen(col, row);
-            }
-            if !self.has_conflicts() {
-                break;
-            }
-            self.init_rand();
-        }
-    }
-}
+mod helper;
+mod cell;
+mod alg;
 
 impl Display for Puzzle {
     fn fmt(&self, f: &mut Formatter) -> Result {