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

use std::collections::BTreeMap;

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

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