path: root/2023/rs/code/eight/src/main.rs

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) }
    a
}

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();
    let instr = iter.next().unwrap().bytes().map(|c| c == b'R');
    iter.next().unwrap();
    let triples = iter.map(|s| (&s[0..3], (&s[7..10], &s[12..15]))).collect::<BTreeMap<_, _>>();
    (instr, triples)
  };

  let part1 = steps("AAA", &valueified_instr, &valueified_triples, "ZZZ");
  println!("Steps to reach `ZZZ`: {part1}");

  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);

  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
}