day 12

3 files changed, 126 insertions, 0 deletions

diff --git a/data/2021/12.txt b/data/2021/12.txt
new file mode 100644
index 0000000..1d5c9fe
--- /dev/null
+++ b/data/2021/12.txt
@@ -0,0 +1,24 @@
+re-js
+qx-CG
+start-js
+start-bj
+qx-ak
+js-bj
+ak-re
+CG-ak
+js-CG
+bj-re
+ak-lg
+lg-CG
+qx-re
+WP-ak
+WP-end
+re-lg
+end-ak
+WP-re
+bj-CG
+qx-start
+bj-WP
+JG-lg
+end-lg
+lg-iw
diff --git a/src/2021/12/mod.rs b/src/2021/12/mod.rs
new file mode 100644
index 0000000..e722c22
--- /dev/null
+++ b/src/2021/12/mod.rs
@@ -0,0 +1,98 @@
+fn small(s: &str) -> bool {
+    s.chars().all(|c| c.is_lowercase())
+}
+
+fn single_small(path: &[String]) -> bool {
+    path.iter().filter(|s| small(s)).count()
+        == path
+            .iter()
+            .filter(|s| small(s))
+            .collect::<std::collections::HashSet<_>>()
+            .len()
+}
+
+fn paths_from1(
+    graph: &std::collections::HashMap<
+        String,
+        std::collections::HashSet<String>,
+    >,
+    path: Vec<String>,
+) -> i64 {
+    let mut total = 0;
+    for neighbor in graph[&path[path.len() - 1]].iter() {
+        if small(neighbor) && path.contains(neighbor) {
+            continue;
+        }
+        if neighbor == "end" {
+            total += 1;
+        } else {
+            let mut path = path.clone();
+            path.push(neighbor.to_string());
+            total += paths_from1(graph, path);
+        }
+    }
+    total
+}
+
+fn paths_from2(
+    graph: &std::collections::HashMap<
+        String,
+        std::collections::HashSet<String>,
+    >,
+    path: Vec<String>,
+) -> i64 {
+    let mut total = 0;
+    for neighbor in graph[&path[path.len() - 1]].iter() {
+        if neighbor == "start" {
+            continue;
+        }
+        if small(neighbor) && path.contains(neighbor) && !single_small(&path)
+        {
+            continue;
+        }
+        if neighbor == "end" {
+            total += 1;
+        } else {
+            let mut path = path.clone();
+            path.push(neighbor.to_string());
+            total += paths_from2(graph, path);
+        }
+    }
+    total
+}
+
+pub fn part1() -> anyhow::Result<i64> {
+    let mut graph = std::collections::HashMap::new();
+    for line in data_lines!()? {
+        let line = line?;
+        let nodes: Vec<String> =
+            line.split('-').map(|s| s.to_string()).collect();
+        let edges = graph
+            .entry(nodes[0].clone())
+            .or_insert_with(std::collections::HashSet::new);
+        edges.insert(nodes[1].clone());
+        let edges = graph
+            .entry(nodes[1].clone())
+            .or_insert_with(std::collections::HashSet::new);
+        edges.insert(nodes[0].clone());
+    }
+    Ok(paths_from1(&graph, vec!["start".to_string()]))
+}
+
+pub fn part2() -> anyhow::Result<i64> {
+    let mut graph = std::collections::HashMap::new();
+    for line in data_lines!()? {
+        let line = line?;
+        let nodes: Vec<String> =
+            line.split('-').map(|s| s.to_string()).collect();
+        let edges = graph
+            .entry(nodes[0].clone())
+            .or_insert_with(std::collections::HashSet::new);
+        edges.insert(nodes[1].clone());
+        let edges = graph
+            .entry(nodes[1].clone())
+            .or_insert_with(std::collections::HashSet::new);
+        edges.insert(nodes[0].clone());
+    }
+    Ok(paths_from2(&graph, vec!["start".to_string()]))
+}
diff --git a/src/2021/mod.rs b/src/2021/mod.rs
index ccac2b0..a829642 100644
--- a/src/2021/mod.rs
+++ b/src/2021/mod.rs
@@ -20,6 +20,8 @@ mod day9;
 mod day10;
 #[path = "11/mod.rs"]
 mod day11;
+#[path = "12/mod.rs"]
+mod day12;
 // NEXT MOD
 
 pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> {
@@ -46,6 +48,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> {
         (10, 2) => day10::part2(),
         (11, 1) => day11::part1(),
         (11, 2) => day11::part2(),
+        (12, 1) => day12::part1(),
+        (12, 2) => day12::part2(),
         // NEXT PART
         _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)),
     }