1 files changed, 54 insertions, 0 deletions

diff --git a/2021/day12/src/main.rs b/2021/day12/src/main.rs
new file mode 100644
index 0000000..504a97a
--- /dev/null
+++ b/2021/day12/src/main.rs
@@ -0,0 +1,54 @@
+use std::fs;
+use std::path::Path;
+use std::collections::HashMap;
+
+/* AOC21 Day 12: https://adventofcode.com/2021/day/12 */
+fn main() {
+    let input = Path::new("resources").join("input.txt");
+    let content = fs::read_to_string(input).expect("Unable to read input file");
+    let mut adj = HashMap::<&str,Vec<&str>>::new();
+    content.lines()
+           .map(|l| l.split_once('-').expect("Malformed input"))
+           .for_each(|(from,to)| {
+                adj.entry(from).or_default().push(to);
+                adj.entry(to).or_default().push(from);
+            });
+    println!("Ex1: the result is {}", genpath(&mut vec!["start"], &adj));
+    println!("Ex2: the result is {}", genpath_rep(&mut vec!["start"], &adj));
+}
+
+fn genpath<'a>(path: &mut Vec<&'a str>, adj: &HashMap<&str,Vec<&'a str>>) -> u32 {
+    let last = path.last().unwrap();
+    if *last == "end" { 1 } else {
+        let mut paths = 0;
+        if let Some(vec) = adj.get(last) {
+            let next: Vec<&str> = vec.iter().filter(|n| n.chars().all(|c| c.is_uppercase()) || !path.contains(&n)).cloned().collect();
+            for n in next {
+                path.push(n);
+                paths += genpath(path, adj);
+                path.pop();
+            }
+        }
+        paths
+    }
+}
+
+fn genpath_rep<'a>(path: &mut Vec<&'a str>, adj: &HashMap<&str,Vec<&'a str>>) -> u32 {
+    let last = path.last().unwrap();
+    if *last == "end" { 1 } else {
+        let mut paths = 0;
+        if let Some(vec) = adj.get(last) {
+            for n in vec.iter().filter(|&n| *n != "start") {
+                if n.chars().all(|c| c.is_lowercase()) && path.contains(n) {
+                    path.push(n);
+                    paths += genpath(path, adj);
+                } else {
+                    path.push(n);
+                    paths += genpath_rep(path, adj);
+                }
+                path.pop();
+            }
+        }
+        paths
+    }
+}