Initial commit

1 files changed, 109 insertions, 0 deletions

diff --git a/d17/src/main.rs b/d17/src/main.rs
new file mode 100644
index 0000000..bacc9f4
--- /dev/null
+++ b/d17/src/main.rs
@@ -0,0 +1,109 @@
+use std::collections::VecDeque;
+
+use md5;
+
+fn solve_puzzle(passwd: &str) -> Vec<String> {
+    let mut paths = Vec::new();
+
+    // Breadth-first search of all possible paths
+    let start = (String::new(), (0, 0));
+    let mut queue = VecDeque::from([start]);
+    loop {
+        let pp = queue.pop_front();
+        // All paths have finished or got stuck at locked doors
+        if pp.is_none() {
+            break;
+        }
+        // Did we successfully reach the bottom-right corner?
+        let (path, pos) = pp.unwrap();
+        if pos == (3, 3) {
+            paths.push(path.clone());
+            continue;
+        }
+
+        // Doors open based on MD5 hash of `passw' + `path'
+        let data = format!("{}{}", passwd, path);
+        let hash: Vec<char> = format!("{:x}", md5::compute(data)).chars().collect();
+
+        // Which doors are open, i.e. what are the valid next moves?
+        let mut options = Vec::new();
+        let unlock = ['b', 'c', 'd', 'e', 'f'];
+        if unlock.contains(&hash[0]) && pos.1 > 0 {
+            options.push((format!("{}U", path), (pos.0, pos.1 - 1)));
+        }
+        if unlock.contains(&hash[1]) && pos.1 < 3 {
+            options.push((format!("{}D", path), (pos.0, pos.1 + 1)));
+        }
+        if unlock.contains(&hash[2]) && pos.0 > 0 {
+            options.push((format!("{}L", path), (pos.0 - 1, pos.1)));
+        }
+        if unlock.contains(&hash[3]) && pos.0 < 3 {
+            options.push((format!("{}R", path), (pos.0 + 1, pos.1)));
+        }
+
+        // This is a breadth-first search, but because `path' is encoded
+        // into the state, we don't need to check that nodes are unexplored
+        for (npath, npos) in options {
+            queue.push_back((npath, npos));
+        }
+    }
+
+    paths
+}
+
+fn main() {
+    // My personal puzzle input
+    let input = "edjrjqaa";
+
+    let paths = solve_puzzle(input);
+
+    // Part 1 gives "DUDRDLRRRD" for me
+    println!("Part 1 solution: {}", paths.first().unwrap());
+
+    // Part 2 gives 502 for me
+    println!("Part 2 solution: {}", paths.last().unwrap().len());
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn part1_example1() {
+        let passwd = "ihgpwlah";
+        assert_eq!(solve_puzzle(passwd).first().unwrap(), "DDRRRD");
+    }
+
+    #[test]
+    fn part2_example1() {
+        let passwd = "ihgpwlah";
+        assert_eq!(solve_puzzle(passwd).last().unwrap().len(), 370);
+    }
+
+    #[test]
+    fn part1_example2() {
+        let passwd = "kglvqrro";
+        assert_eq!(solve_puzzle(passwd).first().unwrap(), "DDUDRLRRUDRD");
+    }
+
+    #[test]
+    fn part2_example2() {
+        let passwd = "kglvqrro";
+        assert_eq!(solve_puzzle(passwd).last().unwrap().len(), 492);
+    }
+
+    #[test]
+    fn part1_example3() {
+        let passwd = "ulqzkmiv";
+        assert_eq!(
+            solve_puzzle(passwd).first().unwrap(),
+            "DRURDRUDDLLDLUURRDULRLDUUDDDRR"
+        );
+    }
+
+    #[test]
+    fn part2_example3() {
+        let passwd = "ulqzkmiv";
+        assert_eq!(solve_puzzle(passwd).last().unwrap().len(), 830);
+    }
+}