hw(1/AI): Add failed attemt at implementing it in Rust

4 files changed, 186 insertions, 0 deletions

diff --git a/Year 4/Artificial Intelligence/ENDME/Cargo.lock b/Year 4/Artificial Intelligence/ENDME/Cargo.lock
new file mode 100644
index 0000000..a2a9baa
--- /dev/null
+++ b/Year 4/Artificial Intelligence/ENDME/Cargo.lock
@@ -0,0 +1,16 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "hw01"
+version = "0.1.0"
+dependencies = [
+ "text_io",
+]
+
+[[package]]
+name = "text_io"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d5f0c8eb2ad70c12a6a69508f499b3051c924f4b1cfeae85bfad96e6bc5bba46"
diff --git a/Year 4/Artificial Intelligence/ENDME/Cargo.toml b/Year 4/Artificial Intelligence/ENDME/Cargo.toml
new file mode 100644
index 0000000..6a6483e
--- /dev/null
+++ b/Year 4/Artificial Intelligence/ENDME/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "hw01"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+text_io = "0.1.12"
diff --git a/Year 4/Artificial Intelligence/ENDME/src/graph.rs b/Year 4/Artificial Intelligence/ENDME/src/graph.rs
new file mode 100644
index 0000000..1a536b5
--- /dev/null
+++ b/Year 4/Artificial Intelligence/ENDME/src/graph.rs
@@ -0,0 +1,134 @@
+use std::mem::swap;
+use std::collections::VecDeque;
+
+#[derive(PartialEq, Clone)]
+struct Board {
+    arr: Vec<Vec<u32>>,
+    zero: (usize, usize),
+}
+
+impl Board {
+    fn find_zero(board: &Vec<Vec<u32>>) -> (usize, usize) {
+        for i in 0..board.len() {
+            for j in 0..board[i].len() {
+                if board[i][j] == 0 {
+                    return (i, j);
+                }
+            }
+        }
+        panic!("Couldn't find a zero inside {:?}", board);
+    }
+
+    fn new(board: Vec<Vec<u32>>) -> Board {
+        Board {
+            zero: Self::find_zero(&board),
+            arr: board,
+        }
+    }
+
+    fn can_move_zero(&self, direction: u32) -> bool {
+        match direction {
+            0 => self.zero.1 > 0,
+            1 => self.zero.1 < self.arr[self.zero.0].len() - 1,
+            2 => self.zero.0 > 0,
+            3 => self.zero.0 < self.arr.len() - 1,
+            _ => panic!("Unknown direction {}", direction),
+        }
+    }
+
+    fn dir_to_str(direction: u32) -> String {
+        match direction {
+            0 => "left".to_string(),
+            1 => "right".to_string(),
+            2 => "up".to_string(),
+            3 => "down".to_string(),
+            _ => panic!("Unknown direction {}", direction),
+        }
+    }
+
+    fn move_zero(&mut self, direction: u32) {
+        match direction {
+            0 => {
+                let (left, right) = self.arr[self.zero.0].split_at_mut(self.zero.1);
+                swap(&mut left[self.zero.1 - 1], &mut right[0]);
+                self.zero.1 -= 1;
+            },
+            1 => {
+                let (left, right) = self.arr[self.zero.0].split_at_mut(self.zero.1 + 1);
+                swap(&mut left[self.zero.1 - 1], &mut right[0]);
+                self.zero.1 += 1;
+            },
+            2 => {
+                let (top, bottom) = self.arr.split_at_mut(self.zero.0);
+                swap(&mut top[self.zero.0 - 1][self.zero.1], &mut bottom[0][self.zero.1]);
+                self.zero.0 -= 1;
+            },
+            3 => {
+                let (top, bottom) = self.arr.split_at_mut(self.zero.0 + 1);
+                swap(&mut top[self.zero.0 - 1][self.zero.1], &mut bottom[0][self.zero.1]);
+                self.zero.0 += 1;
+            },
+            _ => panic!("Unknown direction {}", direction),
+        }
+    }
+}
+
+#[derive(Clone)]
+struct GraphNode {
+    board: Board,
+    adj: Vec<GraphNode>,
+    dist: u32,
+    path: Vec<String>,
+}
+
+impl PartialEq for GraphNode {
+    fn eq(&self, other: &Self) -> bool {
+        self.board == other.board
+    }
+}
+impl Eq for GraphNode {}
+
+impl GraphNode {
+    fn new(board: Vec<Vec<u32>>, dist: u32, path: Vec<String>) -> GraphNode {
+        GraphNode {
+            board: Board::new(board),
+            adj: Vec::new(),
+            dist: dist,
+            path: path
+        }
+    }
+}
+
+pub struct Graph {
+    root: GraphNode,
+}
+
+impl Graph {
+    pub fn new(root_board: Vec<Vec<u32>>, goal: u32) -> Graph {
+        let mut G = Graph { root: GraphNode::new(root_board, 0, Vec::new()) };
+        let mut queue: VecDeque<&mut GraphNode> = VecDeque::new();
+        queue.push_back(&mut G.root);
+
+        let mut all_nodes: Vec<&GraphNode> = Vec::new();
+
+        while !queue.is_empty() {
+            let curr: &mut GraphNode = queue.pop_front().unwrap();
+            for direction in 0..4 {
+                if ! curr.board.can_move_zero(direction) { continue; }
+
+                let mut newnode: GraphNode = curr.clone().to_owned();
+                newnode.board.move_zero(direction);
+                newnode.path.push(Board::dir_to_str(direction));
+                // TODO: update distance
+
+                if all_nodes.iter().any(|&x| *x == newnode) { continue; }
+                curr.adj.push(newnode);
+
+                queue.push_back(curr.adj.last_mut().unwrap());
+                // all_nodes.push(curr.adj.last().unwrap());
+            }
+        }
+
+        G
+    }
+}
diff --git a/Year 4/Artificial Intelligence/ENDME/src/main.rs b/Year 4/Artificial Intelligence/ENDME/src/main.rs
new file mode 100644
index 0000000..58a7196
--- /dev/null
+++ b/Year 4/Artificial Intelligence/ENDME/src/main.rs
@@ -0,0 +1,27 @@
+use text_io::read;
+mod graph;
+use graph::{ Graph };
+
+// Manhattan
+fn h() {
+}
+
+fn dfs() {
+}
+
+fn main() {
+    /* Input */
+    let N: u32 = read!();
+    let I: i32 = read!();
+
+    let size: usize = (N as f64 + 1.0).sqrt() as usize;
+    let mut board: Vec<Vec<u32>> = Vec::new();
+    for i in 0..size {
+        board.push(Vec::new());
+        for j in 0..size {
+            board[i].push(read!());
+        }
+    }
+
+    let G: Graph = Graph::new(board, I as u32);
+}