aoc-2021-rust

commit 50a6f2473953019b6d15216da013e59fe10ec8a3
parent c9479238ea02674b65fde86c1723427ee65834c9
Author: Louis Burda <quent.burda@gmail.com>
Date:   Mon, 12 Sep 2022 15:13:37 +0200

Add day 11 and 12 solutions

Diffstat:
M
src/11/src/main.rs
 | 
2
++
M
src/12/input.test
 | 
17
+++++++----------
M
src/12/src/main.rs
 | 
53
++++++++++++++++++++++++++++++++++++++++++++++-------

3 files changed, 55 insertions(+), 17 deletions(-)
diff --git a/src/11/src/main.rs b/src/11/src/main.rs
@@ -73,6 +73,7 @@ fn part1(aoc: &mut aoc::Info) {
     }
 
     println!("{}", flashes);
+    aoc.solution = Some("1681");
 }
 
 fn part2(aoc: &mut aoc::Info) {
@@ -91,6 +92,7 @@ fn part2(aoc: &mut aoc::Info) {
     }
 
     aoc.answer = Some(format!("{}", step));
+    aoc.solution = Some("276");
 }
 
 fn main() {
diff --git a/src/12/input.test b/src/12/input.test
@@ -1,10 +1,7 @@
-dc-end
-HN-start
-start-kj
-dc-start
-dc-HN
-LN-dc
-HN-end
-kj-sa
-kj-HN
-kj-dc
+start-A
+start-b
+A-c
+A-b
+b-d
+A-end
+b-end
diff --git a/src/12/src/main.rs b/src/12/src/main.rs
@@ -3,13 +3,14 @@ use std::collections::HashMap;
 /* assume no two big caves are next to each other
  * => otherwise infinite paths possible */
 
-#[derive(PartialEq)]
+#[derive(PartialEq,Clone)]
 struct Node {
     name: String,
     small: bool,
     adj: Vec<String>
 }
 
+#[derive(Clone)]
 struct NodeState<'a> {
     node: &'a Node,
     index: usize
@@ -77,6 +78,37 @@ fn part1(aoc: &mut aoc::Info) {
     println!("{}", paths);
 }
 
+fn self_paths<'a>(nodes: &'a HashMap<String,Node>,
+            path: &'a Vec<NodeState<'a>>, cur: &'a Node) -> usize {
+    let prevlen = path.len();
+
+    let mut path: Vec<NodeState<'a>> = path.to_vec();
+    path.push(NodeState { node: cur, index: 0 });
+
+    let mut paths: usize = 0;
+    while path.len() > prevlen {
+        let current = path.last_mut().unwrap();
+        if current.index < current.node.adj.len() {
+            let adj: &Node = nodes.get(&current.node.adj[current.index])
+                .unwrap();
+            current.index += 1;
+            if adj == cur {
+                paths += 1;
+            } else if adj.name != "start" && adj.name != "end" {
+                let count = path.iter().filter(|x| x.node == adj).count();
+                if count <= 1 || !adj.small {
+                    path.push(NodeState { node: adj, index: 0 });
+                }
+            }
+        } else {
+            /* backtrack */
+            path.pop();
+        }
+    }
+
+    return paths;
+}
+
 fn part2(aoc: &mut aoc::Info) {
     let nodes = parse_input(&aoc.input);
 
@@ -88,17 +120,23 @@ fn part2(aoc: &mut aoc::Info) {
     while path.len() > 0 {
         let current = path.last_mut().unwrap();
         if current.index < current.node.adj.len() {
-            let adj: &Node = nodes.get(&current.node.adj[current.index]).unwrap();
+            let adj: &Node = nodes.get(&current.node.adj[current.index])
+                .unwrap();
             current.index += 1;
             if adj.name == "end" {
-                for p in &path {
+                let mut prod: usize = 1;
+                for (i, p) in path.iter().enumerate() {
                     aoc::debug!(aoc, "{} -> ", p.node.name);
+                    if i == 0 { continue; }
+                    prod += 1 + self_paths(&nodes, &path, p.node);
                 }
+                paths += prod;
                 aoc::debug!(aoc, "end\n");
-                paths += 1;
-            } else if adj.name != "start"
-                    && path.iter().filter(|x| x.node == adj).count() <= 1 || !adj.small {
-                path.push(NodeState { node: adj, index: 0 } );
+            } else if adj.name != "start" {
+                let count = path.iter().filter(|x| x.node == adj).count();
+                if count < 1 || !adj.small {
+                    path.push(NodeState { node: adj, index: 0 } );
+                }
             }
         } else {
             /* backtrack */
@@ -112,3 +150,4 @@ fn part2(aoc: &mut aoc::Info) {
 fn main() {
     aoc::run(part1, part2);
 }
+