2023.8[1]

1 files changed, 30 insertions, 42 deletions

diff --git a/2023/rs/code/eight/src/main.rs b/2023/rs/code/eight/src/main.rs
index 9e58f07..5ca6420 100644
--- a/2023/rs/code/eight/src/main.rs
+++ b/2023/rs/code/eight/src/main.rs
@@ -1,11 +1,10 @@
 use std::collections::BTreeMap;
+use std::iter::Iterator;
 
 static INPUT: &str = include_str!("input.txt");
 
 fn gcd(mut a: u128, mut b: u128) -> u128 {
-    while b > 0 {
-        (a, b) = (b, a % b)
-    }
+    while b > 0 { (a, b) = (b, a % b) }
     a
 }
 
@@ -13,6 +12,17 @@ fn lcm(a: u128, b: u128) -> u128 {
   a * b / gcd(a, b)
 }
 
+fn steps<'a, I: Iterator<Item = bool> + Clone>(mut last: &'a str, instructions: &I, triples: &BTreeMap<&'a str, (&'a str, &'a str)>, goal: &str) -> u128 {
+  for (n, instr) in instructions.clone().cycle().enumerate() {
+    if last.ends_with(goal) {
+      return n as u128;
+    }
+    let pair = triples[last];
+    last = if instr { pair.1 } else { pair.0 };
+  }
+  unreachable!()
+}
+
 fn main() {
   let (valueified_instr, valueified_triples) = {
     let mut iter = INPUT.lines();
@@ -22,45 +32,23 @@ fn main() {
     (instr, triples)
   };
 
-  let mut last = "AAA";
-  for (n, instr) in valueified_instr.clone().cycle().enumerate() {
-    if last == "ZZZ" {
-      println!("Steps to reach `ZZZ`: {n}");
-      break;
-    }
-    let pair = valueified_triples[last];
-    last = if instr { pair.1 } else { pair.0 };
-  }
+  let part1 = steps("AAA", &valueified_instr, &valueified_triples, "ZZZ");
+  println!("Steps to reach `ZZZ`: {part1}");
 
-/*
-  let mut lasts = valueified_triples.keys().filter(|s| s.as_bytes()[2] == b'A').cloned().map(|a| (a, 0u128)).collect::<Vec<_>>();
-  for last in &mut lasts {
-    for (n, instr) in valueified_instr.clone().cycle().enumerate() {
-      let pair = valueified_triples[last.0];
-      last.0 = if instr { pair.1 } else { pair.0 };
-      if last.0.as_bytes()[2] == b'Z' {
-        last.1 = n as u128;
-        break;
-      }
-    }
-  }
-  dbg!(&lasts);
-  // yes, i could optimize the maths here, but i do not feel like it.
-  let total = lasts.into_iter().fold(1, |a, (_, n)| lcm(n, a));
-  println!("Steps for all to reach `Z`: {total}");
+  let mut part2 = valueified_triples
+    .keys()
+    .filter(|s| s.as_bytes()[2] == b'A')
+    .cloned()
+    .map(|k| steps(k, &valueified_instr, &valueified_triples, "Z"))
+    .fold(1, lcm);
 
-  OK there's totally a way to do this cleverly like above but I can't think of it. This method overshoots, apparently.
-  It assumes the period here is the time it takes to reach Z. What I really need to do is like, find the LCM of the real periods but offset such that the final LCM is n below and blah blah ugh im gonna write the brute forcer and shit and hope it's done.
-  */
-  let mut lasts = valueified_triples.keys().filter(|s| s.as_bytes()[2] == b'A').cloned().collect::<Vec<_>>();
-  for (n, instr) in valueified_instr.clone().cycle().enumerate() {
-    for last in &mut lasts {
-      let pair = valueified_triples[*last];
-      *last = if instr { pair.1 } else { pair.0 };
-    }
-    if lasts.iter().all(|a| a.as_bytes()[2] == b'Z') {
-      println!("Steps for all to reach `Z`: {n}");
-      break;
-    }
-  }
+  println!("Steps to reach unanimous 'Z': {part2}");
+
+  // dude what the fuck was this.
+  // i genuinely don't get why this was right.
+  // i also don't get why my earlier, near-identical impl, was wrong.
+  // i've seen other solutions that use the phase of the actual loop through the map and i feel like that should come in here
+  // this shouldn't be right, and if it is, i don't know why my earlier, logically identical, implementation was broken.
+  // ...
+  // fucking hell
 }