hw(AT/3): Split into files, add tests

Current performance is at about 5-10% failure rate

7 files changed, 373 insertions, 259 deletions

diff --git a/Year 4/Artificial Intelligence/hw03/src/chromosome.rs b/Year 4/Artificial Intelligence/hw03/src/chromosome.rs
new file mode 100644
index 0000000..27219a9
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/src/chromosome.rs
@@ -0,0 +1,143 @@
+use rand::{thread_rng, Rng};
+use crate::Gene;
+
+#[derive(Clone, PartialEq, Debug)]
+pub struct Chromosome {
+    pub genes: Vec<usize>,
+    pub fitness: f64,
+}
+
+impl Chromosome {
+    // map: Container for all genes; genes[i] is the index inside map
+    pub fn new(genes: Vec<usize>, map: &Vec<Gene>) -> Chromosome {
+        let mut ret = Chromosome {
+            genes,
+            fitness: 0.0,
+        };
+        ret.evaluate_fitness(map);
+        ret
+    }
+
+    pub 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]]);
+        }
+    }
+
+    const MUTATION_PROBABILITY: f64 = 0.01;
+
+    pub 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()));
+        self.genes.swap(i, j);
+
+        self.evaluate_fitness(map);
+    }
+
+    // self & other - parents
+    // Single-point crossover
+    pub fn crossover_with(&self, other: &Self, map: &Vec<Gene>) -> Vec<Chromosome> {
+        assert!(!other.genes.is_empty(), "Crossing over with chromosome without genes!");
+
+        let i = if other.genes.len() == 1 {
+            1
+        }
+        else {
+            thread_rng().gen_range(1..other.genes.len())
+        };
+
+        self.crossover_with_point(other, map, i)
+    }
+
+    fn crossover_with_point(&self, other: &Self, map: &Vec<Gene>, i: usize) -> Vec<Chromosome> {
+        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),
+        ]
+    }
+}
+
+#[test]
+fn test_evaluate_fitness() {
+    let map = vec![
+        Gene { x: 4.0, y: 1.0, name: "".to_string() },
+        Gene { x: 3.0, y: 0.0, name: "".to_string() },
+        Gene { x: 2.0, y: 5.0, name: "".to_string() },
+    ];
+    let g = Chromosome::new(vec![0, 1, 2], &map);
+    assert_eq!(format!("{:.3}", g.fitness), "6.513", "Bad evaluate_fitness, incorrect calculation!");
+}
+
+#[test]
+fn test_mutate() {
+    let map = vec![
+        Gene { x: 4.0, y: 1.0, name: "".to_string() },
+        Gene { x: 3.0, y: 0.0, name: "".to_string() },
+        Gene { x: 2.0, y: 5.0, name: "".to_string() },
+    ];
+    let mut g = Chromosome::new(vec![0, 1, 2], &map);
+    'test: {
+        for _ in 0..10000 {
+            g.mutate(&map);
+            if format!("{:.3}", g.fitness) != "6.513" {
+                break 'test;
+            }
+        }
+        assert!(false, "Bad mutate, never swapped genes");
+    }
+}
+
+#[test]
+fn test_single_point_crossover() {
+    let map = vec![
+        Gene { x: 4.0, y: 1.0, name: "".to_string() },
+        Gene { x: 3.0, y: 0.0, name: "".to_string() },
+        Gene { x: 2.0, y: 5.0, name: "".to_string() },
+    ];
+    let g1 = Chromosome::new(vec![0, 1], &map);
+    let g2 = Chromosome::new(vec![2, 1], &map);
+    let crossed = g1.crossover_with(&g2, &map);
+
+    let g1s = Chromosome::new(vec![0, 2], &map);
+    let g2s = Chromosome::new(vec![2, 0], &map);
+    assert_eq!(crossed[0], g1s, "Bad crossover (2 genes)!");
+    assert_eq!(crossed[1], g2s, "Bad crossover (2 genes)!");
+
+    let map = vec![
+        Gene { x: 4.0, y: 1.0, name: "".to_string() },
+        Gene { x: 3.0, y: 0.0, name: "".to_string() },
+        Gene { x: 2.0, y: 5.0, name: "".to_string() },
+        Gene { x: 8.0, y: 4.0, name: "".to_string() },
+        Gene { x: 7.0, y: 1.0, name: "".to_string() },
+    ];
+    let g1 = Chromosome::new(vec![0, 1, 2, 3, 4], &map);
+    let g2 = Chromosome::new(vec![4, 3, 2, 1, 0], &map);
+
+    let crossed = g1.crossover_with_point(&g2, &map, 3);
+
+    let g1s = Chromosome::new(vec![0, 1, 2, 4, 3], &map);
+    let g2s = Chromosome::new(vec![4, 3, 2, 0, 1], &map);
+    assert_eq!(crossed[0], g1s, "Bad crossover (5 genes)!");
+    assert_eq!(crossed[1], g2s, "Bad crossover (5 genes)!");
+}
diff --git a/Year 4/Artificial Intelligence/hw03/src/ex1.rs b/Year 4/Artificial Intelligence/hw03/src/ex1.rs
deleted file mode 100644
index 3f2a35e..0000000
--- a/Year 4/Artificial Intelligence/hw03/src/ex1.rs
+++ /dev/null
@@ -1,257 +0,0 @@
-#![allow(non_snake_case)]
-use std::fmt;
-use text_io::{read};
-use rand::{Rng, rngs::ThreadRng, 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()));
-        self.genes.swap(i, j);
-
-        self.evaluate_fitness(map);
-    }
-}
-
-#[derive(Debug)]
-struct Generation {
-    t: usize,
-    map: Vec<Gene>,
-
-    population: Vec<Chromosome>,
-}
-
-impl Generation {
-    const POPULATION_SIZE: usize = 700;
-
-    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_from_random(cities: usize) -> Generation {
-        let mut rng = thread_rng();
-        let map = (0..cities)
-            .map(|_| Gene {
-                x: rng.gen::<f64>() * 10.0_f64.powi(rng.gen_range(0..5)),
-                y: rng.gen::<f64>() * 10.0_f64.powi(rng.gen_range(0..5)),
-                name: String::new() })
-            .collect();
-        Self::new_from_map(map)
-    }
-
-    const TOURNAMENT_SIZE: usize = 5;
-
-    fn select(&self, rng: &mut ThreadRng) -> usize {
-        let mut tournament: Vec<usize> = Vec::new();
-        for _ in 0..Self::TOURNAMENT_SIZE {
-            tournament.push(rng.gen_range(0..self.population.len()));
-        }
-
-        tournament
-            .into_iter()
-            .min_by(|a, b| self.population[*a].fitness.partial_cmp(&self.population[*b].fitness).unwrap())
-            .unwrap()
-    }
-
-    fn selection_crossover(&mut self) {
-        let mut rng = thread_rng();
-
-        let mut new_generation: Vec<Chromosome> = Vec::new();
-        while new_generation.len() < self.population.len() {
-            let parent1 = self.select(&mut rng);
-            let parent2 = self.select(&mut rng);
-            if parent1 == parent2 { continue; }
-
-            let mut children = self.population[parent1].crossover_with(&self.population[parent2], &self.map);
-            new_generation.append(&mut children);
-        }
-        self.population = new_generation;
-    }
-
-    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 = 250;
-
-    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()
-    }
-}
-
-impl fmt::Display for Generation {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        let best = self.population
-            .iter()
-            .min_by(|a, b| a.fitness.partial_cmp(&b.fitness).unwrap())
-            .unwrap();
-        for cityi in &best.genes[..best.genes.len()-1] {
-            let curr = &self.map[*cityi];
-            if curr.name.is_empty() {
-                write!(f, "({},{}) -> ", curr.x, curr.y)?;
-            }
-            else {
-                write!(f, "{} -> ", curr.name)?;
-            }
-        }
-
-        let last = &self.map[*best.genes.last().unwrap()];
-        if last.name.is_empty() {
-            writeln!(f, "({},{})", last.x, last.y)?;
-        }
-        else {
-            writeln!(f, "{}", last.name)?;
-        }
-
-        writeln!(f, "{}", best.fitness)
-    }
-}
-
-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_from_random(N);
-    }
-    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.best_fitness());
-    let mut i = 0;
-
-    while ! G.terminated() {
-        if i < 8 {
-            println!("{}", G.best_fitness());
-            i += 1;
-        }
-        G.selection_crossover();
-        G.mutate();
-        G = G.next_generation();
-    }
-
-    println!("");
-    println!("{}", G);
-}
diff --git a/Year 4/Artificial Intelligence/hw03/src/gene.rs b/Year 4/Artificial Intelligence/hw03/src/gene.rs
new file mode 100644
index 0000000..25f583e
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/src/gene.rs
@@ -0,0 +1,20 @@
+#[derive(Debug, Clone)]
+pub struct Gene {
+    pub x: f64,
+    pub y: f64,
+    pub name: String,
+}
+
+impl Gene {
+    // Eucledian distance between two points
+    pub fn dist(&self, other: &Self) -> f64 {
+        ((self.x - other.x).powi(2) + (self.y - other.y).powi(2)).sqrt()
+    }
+}
+
+#[test]
+fn test_dist() {
+    let g1 = Gene { x: 4.0, y: 1.0, name: "".to_string() };
+    let g2 = Gene { x: 3.0, y: 0.0, name: "".to_string() };
+    assert_eq!(format!("{:.3}", g1.dist(&g2)), "1.414");
+}
diff --git a/Year 4/Artificial Intelligence/hw03/src/generation.rs b/Year 4/Artificial Intelligence/hw03/src/generation.rs
new file mode 100644
index 0000000..29bce90
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/src/generation.rs
@@ -0,0 +1,99 @@
+use rand::{thread_rng, Rng, rngs::ThreadRng, seq::SliceRandom};
+use crate::gene::Gene;
+use crate::chromosome::Chromosome;
+
+#[derive(Debug)]
+pub struct Generation {
+    pub t: usize,
+    pub map: Vec<Gene>,
+
+    pub population: Vec<Chromosome>,
+}
+
+impl Generation {
+    const POPULATION_SIZE: usize = 4000;
+    const MAX_GENERATIONS: usize = 200;
+    const TOURNAMENT_SIZE: usize = 5;
+
+    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
+    }
+
+    pub fn new_from_map(map: Vec<Gene>) -> Generation {
+        Generation {
+            t: 0,
+            population: Self::new_population(&map),
+            map,
+        }
+    }
+
+    pub fn new_from_random(cities: usize) -> Generation {
+        let mut rng = thread_rng();
+        let map = (0..cities)
+            .map(|_| Gene {
+                x: rng.gen::<f64>() * 10.0_f64.powi(rng.gen_range(0..5)),
+                y: rng.gen::<f64>() * 10.0_f64.powi(rng.gen_range(0..5)),
+                name: String::new() })
+            .collect();
+        Self::new_from_map(map)
+    }
+
+    pub fn select(&self, rng: &mut ThreadRng) -> usize {
+        let mut tournament: Vec<usize> = Vec::new();
+        for _ in 0..Self::TOURNAMENT_SIZE {
+            tournament.push(rng.gen_range(0..self.population.len()));
+        }
+
+        tournament
+            .into_iter()
+            .min_by(|a, b| self.population[*a].fitness.partial_cmp(&self.population[*b].fitness).unwrap())
+            .unwrap()
+    }
+
+    pub fn selection_crossover(&mut self) {
+        let mut rng = thread_rng();
+
+        let mut new_generation: Vec<Chromosome> = Vec::new();
+        while new_generation.len() < self.population.len() {
+            let parent1 = self.select(&mut rng);
+            let parent2 = self.select(&mut rng);
+            if parent1 == parent2 { continue; }
+
+            let mut children = self.population[parent1].crossover_with(&self.population[parent2], &self.map);
+            new_generation.append(&mut children);
+        }
+        self.population = new_generation;
+    }
+
+    pub fn mutate(&mut self) {
+        for p in &mut self.population {
+            p.mutate(&self.map);
+        }
+    }
+
+    pub fn next_generation(mut self) -> Generation {
+        self.t += 1;
+        self
+    }
+
+    pub fn terminated(&self) -> bool {
+        self.t == Self::MAX_GENERATIONS || self.population[1..].iter().all(|x| *x == self.population[0])
+    }
+
+    pub fn best_fitness(&self) -> f64 {
+        self.population
+            .iter()
+            .map(|x| x.fitness)
+            .min_by(|a, b| a.partial_cmp(b).unwrap())
+            .unwrap()
+    }
+}
diff --git a/Year 4/Artificial Intelligence/hw03/src/main.rs b/Year 4/Artificial Intelligence/hw03/src/main.rs
index e43d43f..f09a07e 100644
--- a/Year 4/Artificial Intelligence/hw03/src/main.rs
+++ b/Year 4/Artificial Intelligence/hw03/src/main.rs
@@ -1,5 +1,90 @@
-mod ex1;
+#![allow(non_snake_case)]
+use std::fmt;
+use text_io::{read};
+
+mod generation;
+use generation::Generation;
+mod gene;
+use gene::Gene;
+mod chromosome;
+
+impl fmt::Display for Generation {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        let best = self.population
+            .iter()
+            .min_by(|a, b| a.fitness.partial_cmp(&b.fitness).unwrap())
+            .unwrap();
+        for cityi in &best.genes[..best.genes.len()-1] {
+            let curr = &self.map[*cityi];
+            if curr.name.is_empty() {
+                write!(f, "({},{}) -> ", curr.x, curr.y)?;
+            }
+            else {
+                write!(f, "{} -> ", curr.name)?;
+            }
+        }
+
+        let last = &self.map[*best.genes.last().unwrap()];
+        if last.name.is_empty() {
+            writeln!(f, "({},{})", last.x, last.y)?;
+        }
+        else {
+            writeln!(f, "{}", last.name)?;
+        }
+
+        writeln!(f, "{}", best.fitness)
+    }
+}
 
 fn main() {
-    ex1::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_from_random(N);
+    }
+    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.best_fitness());
+    let mut i = 0;
+
+    while ! G.terminated() {
+        if i < 8 {
+            // println!("{}", G.best_fitness());
+            i += 1;
+        }
+        G.selection_crossover();
+        G.mutate();
+        G = G.next_generation();
+    }
+
+    // println!("");
+    // println!("{}", G);
+    let best = G.population
+        .iter()
+        .min_by(|a, b| a.fitness.partial_cmp(&b.fitness).unwrap())
+        .unwrap();
+    println!("{} {}", best.genes.first().unwrap(), best.genes.last().unwrap());
 }
diff --git a/Year 4/Artificial Intelligence/hw03/uk12_name.csv b/Year 4/Artificial Intelligence/hw03/uk12_name.csv
new file mode 100644
index 0000000..1088781
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/uk12_name.csv
@@ -0,0 +1,12 @@
+Aberystwyth
+Brighton
+Edinburgh
+Exeter
+Glasgow
+Inverness
+Liverpool
+London
+Newcastle
+Nottingham
+Oxford
+Stratford
\ No newline at end of file
diff --git a/Year 4/Artificial Intelligence/hw03/uk12_xy.csv b/Year 4/Artificial Intelligence/hw03/uk12_xy.csv
new file mode 100644
index 0000000..8651652
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw03/uk12_xy.csv
@@ -0,0 +1,12 @@
+0.190032E-03,-0.285946E-03
+383.458,-0.608756E-03
+-27.0206,-282.758
+335.751,-269.577
+69.4331,-246.780
+168.521,31.4012
+320.350,-160.900
+179.933,-318.031
+492.671,-131.563
+112.198,-110.561
+306.320,-108.090
+217.343,-447.089
\ No newline at end of file