hw(3/AI): Initial solution

4 files changed, 373 insertions, 0 deletions

diff --git a/Year 4/Artificial Intelligence/hw03/Cargo.lock b/Year 4/Artificial Intelligence/hw03/Cargo.lock
new file mode 100644
index 0000000..6944688
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/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 = "hw03"
+version = "0.1.0"
+dependencies = [
+ "rand",
+ "text_io",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.164"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "433bfe06b8c75da9b2e3fbea6e5329ff87748f0b144ef75306e674c3f6f7c13f"
+
+[[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/hw03/Cargo.toml b/Year 4/Artificial Intelligence/hw03/Cargo.toml
new file mode 100644
index 0000000..58d2a30
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "hw03"
+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/hw03/src/ex1.rs b/Year 4/Artificial Intelligence/hw03/src/ex1.rs
new file mode 100644
index 0000000..5da7c9b
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/src/ex1.rs
@@ -0,0 +1,211 @@
+use text_io::{read};
+use rand::{Rng, thread_rng, seq::SliceRandom};
+
+#[derive(Debug)]
+struct Gene {
+    x: f64,
+    y: f64,
+    name: String,
+}
+
+impl Gene {
+    // Eucledian distance between two points
+    fn dist(&self, other: &Self) -> f64 {
+        ((self.x - other.x).powi(2) + (self.y - other.y).powi(2)).sqrt()
+    }
+}
+
+#[derive(Clone, PartialEq, Debug)]
+struct Chromosome {
+    genes: Vec<usize>,
+    fitness: f64,
+}
+
+impl Chromosome {
+    fn new(genes: Vec<usize>, map: &Vec<Gene>) -> Chromosome {
+        let mut ret = Chromosome {
+            genes,
+            fitness: 0.0,
+        };
+        ret.evaluate_fitness(map);
+        ret
+    }
+
+    fn evaluate_fitness(&mut self, map: &Vec<Gene>) {
+        self.fitness = 0.0;
+        for i in 0..self.genes.len() - 1 {
+            self.fitness += map[self.genes[i]].dist(&map[self.genes[i+1]]);
+        }
+    }
+
+    // self & other - parents
+    // Single-point crossover
+    fn crossover_with(&self, other: &Self, map: &Vec<Gene>) -> Vec<Chromosome> {
+        let i = thread_rng().gen_range(0..other.genes.len());
+
+        let mut child1 = self.genes[..i].to_vec();
+        for elem in &other.genes {
+            if child1.len() == other.genes.len() { break; }
+
+            if ! child1.contains(&elem) {
+                child1.push(*elem);
+            }
+        }
+
+        let mut child2 = other.genes[..i].to_vec();
+        for elem in &self.genes {
+            if child2.len() == self.genes.len() { break; }
+
+            if ! child2.contains(&elem) {
+                child2.push(*elem);
+            }
+        }
+
+        vec![
+            Chromosome::new(child1, map),
+            Chromosome::new(child2, map),
+        ]
+    }
+
+    const MUTATION_PROBABILITY: f64 = 0.1;
+
+    fn mutate(&mut self, map: &Vec<Gene>) {
+        let mut rng = thread_rng();
+        if ! rng.gen_bool(Self::MUTATION_PROBABILITY) { return; }
+
+        let (i, j) = (rng.gen_range(0..self.genes.len()), rng.gen_range(0..self.genes.len()));
+        let temp = self.genes[i].clone();
+        self.genes[i] = self.genes[j];
+        self.genes[j] = temp;
+
+        self.evaluate_fitness(map);
+    }
+}
+
+#[derive(Debug)]
+struct Generation {
+    t: usize,
+    map: Vec<Gene>,
+
+    population: Vec<Chromosome>,
+}
+
+impl Generation {
+    const POPULATION_SIZE: usize = 250;
+
+    fn new_population(map: &Vec<Gene>) -> Vec<Chromosome> {
+        let mut rng = thread_rng();
+
+        let mut perm: Vec<usize> = (0..map.len()).collect();
+        let mut ret: Vec<Chromosome> = Vec::new();
+
+        for _ in 0..Self::POPULATION_SIZE {
+            perm.shuffle(&mut rng);
+            ret.push(Chromosome::new(perm.clone(), map));
+        }
+        ret
+    }
+
+    fn new_from_map(map: Vec<Gene>) -> Generation {
+        Generation {
+            t: 0,
+            population: Self::new_population(&map),
+            map,
+        }
+    }
+
+    fn new() -> Generation {
+        Generation {
+            t: 0,
+            map: Vec::new(),
+            population: Vec::new(),
+        }
+    }
+
+    fn selection_crossover(&mut self) {
+        let mut rng = thread_rng();
+        // Roulette selection
+        let sum_fitness: f64 = self.population.iter().map(|x| x.fitness).sum();
+
+        let mut prev_parent = usize::MAX;
+        for i in 0..self.population.len() {
+            if ! rng.gen_bool(self.population[i].fitness / sum_fitness) { continue; }
+
+            if prev_parent != usize::MAX {
+                let children = self.population[prev_parent].crossover_with(&self.population[i], &self.map);
+                self.population[prev_parent] = children[0].clone();
+                self.population[i]           = children[1].clone();
+                prev_parent = usize::MAX;
+            }
+            else {
+                prev_parent = i;
+            }
+        }
+    }
+
+    fn mutate(&mut self) {
+        for p in &mut self.population {
+            p.mutate(&self.map);
+        }
+    }
+
+    fn next_generation(mut self) -> Generation {
+        self.t += 1;
+        self
+    }
+
+    const MAX_GENERATIONS: usize = 2000;
+
+    fn terminated(&self) -> bool {
+        self.t == Self::MAX_GENERATIONS || self.population[1..].iter().all(|x| *x == self.population[0])
+    }
+
+    fn best_fitness(&self) -> f64 {
+        self.population
+            .iter()
+            .map(|x| x.fitness)
+            .min_by(|a, b| a.partial_cmp(b).unwrap())
+            .unwrap()
+    }
+}
+
+pub fn main() {
+    let mut G: Generation;
+    let input: String = read!();
+    let N = input.parse::<usize>();
+
+    if N.is_ok() {
+        let N = N.unwrap();
+        G = Generation::new();
+    }
+    else {
+        let names: Vec<String> = std::fs::read_to_string([input.clone(), "_name.csv".to_string()].concat())
+            .expect("Couldn't open points file: ..._name.csv")
+            .lines()
+            .map(|x| x.to_string())
+            .collect();
+        let points: Vec<Gene> = std::fs::read_to_string([input, "_xy.csv".to_string()].concat())
+            .expect("Couldn't open points file: ..._xy.csv")
+            .lines()
+            .enumerate()
+            .map(|(i, l)| {
+                let coords: Vec<&str> = l.split(',').collect();
+                Gene {
+                    x: coords[0].parse::<f64>().unwrap(),
+                    y: coords[1].parse::<f64>().unwrap(),
+                    name: names[i].clone(),
+                }
+            })
+            .collect();
+        G = Generation::new_from_map(points);
+        println!("{:?}", G);
+    }
+
+    println!("{}", G.best_fitness());
+    while ! G.terminated() {
+        G.selection_crossover();
+        G.mutate();
+        G = G.next_generation();
+    }
+    println!("{}", G.best_fitness());
+}
diff --git a/Year 4/Artificial Intelligence/hw03/src/main.rs b/Year 4/Artificial Intelligence/hw03/src/main.rs
new file mode 100644
index 0000000..e43d43f
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/src/main.rs
@@ -0,0 +1,5 @@
+mod ex1;
+
+fn main() {
+    ex1::main();
+}