hw(4/AI): Add slow solution

4 files changed, 348 insertions, 0 deletions

diff --git a/Year 4/Artificial Intelligence/hw02/Cargo.lock b/Year 4/Artificial Intelligence/hw02/Cargo.lock
new file mode 100644
index 0000000..b9ef3c0
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw02/Cargo.lock
@@ -0,0 +1,147 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "byteorder"
+version = "1.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1fd0f2584146f6f2ef48085050886acf353beff7305ebd1ae69500e27c67f64b"
+
+[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "getrandom"
+version = "0.2.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c4567c8db10ae91089c99af84c68c38da3ec2f087c3f82960bcdbf3656b6f4d7"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi",
+]
+
+[[package]]
+name = "hw02"
+version = "0.1.0"
+dependencies = [
+ "rand",
+ "text_io",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.162"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "18d287de67fe55fd7e1581fe933d965a5a9477b38e949cfa9f8574ef01506398"
+
+[[package]]
+name = "ppv-lite86"
+version = "0.2.20"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "77957b295656769bb8ad2b6a6b09d897d94f05c41b069aede1fcdaa675eaea04"
+dependencies = [
+ "zerocopy",
+]
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.89"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f139b0662de085916d1fb67d2b4169d1addddda1919e696f3252b740b629986e"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.37"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b5b9d34b8991d19d98081b46eacdd8eb58c6f2b201139f7c5f643cc155a633af"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "rand"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
+name = "syn"
+version = "2.0.87"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "25aa4ce346d03a6dcd68dd8b4010bcb74e54e62c90c573f394c46eae99aba32d"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
+[[package]]
+name = "text_io"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d5f0c8eb2ad70c12a6a69508f499b3051c924f4b1cfeae85bfad96e6bc5bba46"
+
+[[package]]
+name = "unicode-ident"
+version = "1.0.13"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e91b56cd4cadaeb79bbf1a5645f6b4f8dc5bde8834ad5894a8db35fda9efa1fe"
+
+[[package]]
+name = "wasi"
+version = "0.11.0+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423"
+
+[[package]]
+name = "zerocopy"
+version = "0.7.35"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1b9b4fd18abc82b8136838da5d50bae7bdea537c574d8dc1a34ed098d6c166f0"
+dependencies = [
+ "byteorder",
+ "zerocopy-derive",
+]
+
+[[package]]
+name = "zerocopy-derive"
+version = "0.7.35"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fa4f8080344d4671fb4e831a13ad1e68092748387dfc4f55e356242fae12ce3e"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
diff --git a/Year 4/Artificial Intelligence/hw02/Cargo.toml b/Year 4/Artificial Intelligence/hw02/Cargo.toml
new file mode 100644
index 0000000..8520bee
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw02/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "hw02"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+rand = "0.8.5"
+text_io = "0.1.12"
diff --git a/Year 4/Artificial Intelligence/hw02/src/main.rs b/Year 4/Artificial Intelligence/hw02/src/main.rs
new file mode 100644
index 0000000..8fd19a2
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw02/src/main.rs
@@ -0,0 +1,182 @@
+#![allow(non_snake_case)]
+use text_io::read;
+use rand::{Rng, rngs::ThreadRng};
+use std::fmt::{Display, Formatter, Result};
+
+#[derive(Clone)]
+struct Queen {
+    is: bool,
+    attacks: i32,
+}
+
+struct Puzzle {
+    board: Vec<Vec<Queen>>,
+    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),
+            N: N,
+            rng: rand::thread_rng(),
+        }
+    }
+
+    fn max_col(&mut self) -> usize {
+        let (mut maxAttacks, mut maxInds) = (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();
+            }
+            if maxAttacks == maxRowAttacks {
+                maxInds.push(col);
+            }
+        }
+
+        if maxInds.len() == 1 {
+            return maxInds[0];
+        }
+        return maxInds[self.rng.gen_range(0..maxInds.len())];
+    }
+    fn min_col_row(&mut self, colI: usize) -> usize {
+        let (mut minAttacks, mut minInds) = (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();
+            }
+            if self.board[colI][row].attacks == minAttacks {
+                minInds.push(row);
+            }
+        }
+
+        if minInds.len() == 1 {
+            return minInds[0];
+        }
+        return minInds[self.rng.gen_range(0..minInds.len())];
+    }
+
+    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 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 queenRow == rowI { return; }
+        self.remove_queen(colI, queenRow);
+        self.place_queen(colI, rowI);
+    }
+
+    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;
+                }
+            }
+        }
+        return false;
+    }
+
+    fn init(&mut self) {
+        self.board = Self::clean_board(self.N);
+        for col in 0..self.N {
+            let r = self.min_col_row(col);
+            self.place_queen(col, r);
+        }
+    }
+    pub fn solve(&mut self) {
+        loop {
+            self.init();
+            for _ in 0..self.N*self.N {
+                let col = self.max_col();
+                let row = self.min_col_row(col);
+                self.move_queen(col, row);
+            }
+            if !self.has_conflicts() {
+                break;
+            }
+        }
+    }
+
+    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 {
+                    write!(f, "*")?;
+                }
+                else {
+                    write!(f, "_")?;
+                }
+                if col < self.N - 1 {
+                    write!(f, " ")?;
+                }
+            }
+            writeln!(f, "")?;
+        }
+        Ok(())
+    }
+}
+
+fn main() {
+    let N: usize = read!();
+    let mut task = Puzzle::new(N);
+    task.solve();
+    println!("{}", task);
+}
diff --git a/Year 4/Artificial Intelligence/shell.nix b/Year 4/Artificial Intelligence/shell.nix
new file mode 100644
index 0000000..5fe3be2
--- /dev/null
+++ b/Year 4/Artificial Intelligence/shell.nix
@@ -0,0 +1,9 @@
+let
+  nixpkgs = fetchTarball "https://github.com/NixOS/nixpkgs/tarball/nixos-24.05";
+  pkgs = import nixpkgs { config = {}; overlays = []; };
+in
+pkgs.mkShellNoCC {
+  packages = with pkgs; [
+    cargo
+  ];
+}