3 files changed, 84 insertions, 0 deletions

diff --git a/2021/day12/Cargo.toml b/2021/day12/Cargo.toml
new file mode 100644
index 0000000..d1c136c
--- /dev/null
+++ b/2021/day12/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "day12"
+version = "0.1.0"
+authors = ["Federico Igne <git@federicoigne.com>"]
+edition = "2018"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/2021/day12/resources/input.txt b/2021/day12/resources/input.txt
new file mode 100644
index 0000000..5a75dd8
--- /dev/null
+++ b/2021/day12/resources/input.txt
@@ -0,0 +1,21 @@
+mx-IQ
+mx-HO
+xq-start
+start-HO
+IE-qc
+HO-end
+oz-xq
+HO-ni
+ni-oz
+ni-MU
+sa-IE
+IE-ni
+end-sa
+oz-sa
+MU-start
+MU-sa
+oz-IE
+HO-xq
+MU-xq
+IE-end
+MU-mx
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
+    }
+}