Day 8, part 2

5 files changed, 120 insertions, 16 deletions

diff --git a/08/Cargo.toml b/08/Cargo.toml
index 56de1ce..86d1d7c 100644
--- a/08/Cargo.toml
+++ b/08/Cargo.toml
@@ -7,8 +7,8 @@ edition = "2021"
 name = "part-1"
 path = "src/part-1.rs"
 
-#[[bin]]
-#name = "part-2"
-#path = "src/part-2.rs"
+[[bin]]
+name = "part-2"
+path = "src/part-2.rs"
 
 [dependencies]
diff --git a/08/src/part-1.rs b/08/src/part-1.rs
index bdfb409..89d51b5 100644
--- a/08/src/part-1.rs
+++ b/08/src/part-1.rs
@@ -2,7 +2,7 @@ mod stuff;
 
 use std::collections::{HashMap};
 
-use crate::stuff::{ascii_to_u64, is_all_ascii_ws, read_helper, Direction, Node};
+use crate::stuff::{ascii_to_u64, is_all_ascii_ws, read_helper, walk, Direction, Node};
 
 pub const START: Node = [b'A', b'A', b'A'];
 pub const FINISH: Node = [b'Z', b'Z', b'Z'];
@@ -41,16 +41,7 @@ fn main() {
         nodes.insert(node, (node_l, node_r));
     }
 
-    let mut node: Node = START;
-    for (i, instruction) in instructions.into_iter().cycle().enumerate() {
-        if node == FINISH {
-            println!("{}", i);
-            break;
-        }
-        let (left, right) = nodes.get(& node).expect("Non-existent node");
-        match instruction {
-            Direction::L => { node = *left; },
-            Direction::R => { node = *right; }
-        }
-    }
+    let res = walk(START, |node| node == FINISH, & nodes, & instructions);
+    println!("{}", res);
+
 }
diff --git a/08/src/part-2.rs b/08/src/part-2.rs
new file mode 100644
index 0000000..90d4356
--- /dev/null
+++ b/08/src/part-2.rs
@@ -0,0 +1,47 @@
+mod stuff;
+
+use std::collections::{HashMap};
+
+use crate::stuff::{is_all_ascii_ws, lcm, read_helper, walk, Direction, Node};
+
+fn main() {
+    let mut stdin = std::io::stdin().lock();
+
+    let mut buf: Vec<u8> = Vec::new();
+
+    let num_bytes = read_helper(&mut stdin, &mut buf, b'\n').expect("IO error");
+    if num_bytes == 0 { panic!("Malformed input"); }    
+    let instructions: Vec<Direction> = (& buf).into_iter()
+        .map(|& c| Direction::try_from(c).expect("Malformed input"))
+        .collect();
+
+    let num_bytes = read_helper(&mut stdin, &mut buf, b'\n').expect("IO error");
+    assert!(is_all_ascii_ws(& buf));
+
+    let mut nodes: HashMap<Node, (Node, Node)> = HashMap::new();
+    let mut starts: Vec<Node> = Vec::new();
+    loop {
+        let num_bytes = read_helper(&mut stdin, &mut buf, b'=').expect("IO error");
+        if num_bytes == 0 { break; }
+        let node: Node = core::array::from_fn(|i| buf[i]);
+        
+        let num_bytes = read_helper(&mut stdin, &mut buf, b',').expect("IO error");
+        if num_bytes == 0 { panic!("Malformed input"); }
+        let node_l: Node = core::array::from_fn(|i| buf[2+i]);
+
+        let num_bytes = read_helper(&mut stdin, &mut buf, b'\n').expect("IO error");
+        if num_bytes == 0 { panic!("Malformed input"); }
+        let node_r: Node = core::array::from_fn(|i| buf[1+i]);        
+
+        if node[2] == b'A' { starts.push(node); }
+        nodes.insert(node, (node_l, node_r));
+    }
+
+    let mut res: u64 = 1;
+    for start in (& starts).into_iter() {
+        let n: u64 = walk(*start, |node| node[2] == b'Z', & nodes, & instructions).try_into().unwrap();
+        res = lcm(res, n);
+    }
+
+    println!("{}", res);
+}
diff --git a/08/src/stuff.rs b/08/src/stuff.rs
index 835c65e..7e88605 100644
--- a/08/src/stuff.rs
+++ b/08/src/stuff.rs
@@ -1,3 +1,4 @@
+use std::collections::{HashMap};
 use std::io::{BufRead};
 
 pub fn ascii_to_u64(s: & [u8]) -> u64 {
@@ -40,9 +41,64 @@ impl TryFrom<u8> for Direction {
 
 pub type Node = [u8; 3];
 
+pub fn gcd(mut m: u64, mut n: u64) -> u64 {
+    if m < n {
+        std::mem::swap(&mut m, &mut n);
+    }
+    
+    while n > 0 {
+        let r: u64 = m % n;
+        m = n;
+        n = r;
+    }
+    m
+}
+
+pub fn lcm(m: u64, n: u64) -> u64 {
+    m*(n/gcd(m, n))
+}
+
+pub fn walk<'a, I, F>(start: Node, is_finish: F, map: & HashMap<Node, (Node, Node)>, instructions: I) -> usize
+where I: IntoIterator<Item = &'a Direction>,
+<I as IntoIterator>::IntoIter: Clone,
+F: Fn(Node) -> bool {
+    let mut node: Node = start;
+    for (i, instruction) in instructions.into_iter().cycle().enumerate() {
+        if is_finish(node) {
+            return i;
+        }
+        let (left, right) = map.get(& node).expect("Non-existent node");
+        match instruction {
+            Direction::L => { node = *left; },
+            Direction::R => { node = *right; }
+        }
+    }
+    unreachable!("Non-terminating map")
+}
+
 
 #[cfg(test)]
 mod tests {
     use super::*;
 
+    #[test]
+    fn test_gcd() {
+        assert_eq!(gcd(1238124652, 22146), 2);
+    }
+
+    #[test]
+    fn test_gcd_2() {
+        assert_eq!(gcd(5025124, 1040), 52);
+    }
+
+    #[test]
+    fn test_gcd_3() {
+        assert_eq!(gcd(1040, 5025124), 52);
+    }
+
+    #[test]
+    fn test_lcm() {
+        assert_eq!(lcm(1040, 5025124), 100502480);
+    }
+
 }
diff --git a/08/test-3.txt b/08/test-3.txt
new file mode 100644
index 0000000..5b3fa58
--- /dev/null
+++ b/08/test-3.txt
@@ -0,0 +1,10 @@
+LR
+
+11A = (11B, XXX)
+11B = (XXX, 11Z)
+11Z = (11B, XXX)
+22A = (22B, XXX)
+22B = (22C, 22C)
+22C = (22Z, 22Z)
+22Z = (22B, 22B)
+XXX = (XXX, XXX)