2023 Advent of Code Day 8

main.rs

use std::collections::HashMap;

use lazy_static::lazy_static;
use regex::Regex;

const INPUT: &str = "..snip..";

fn main() {
    let mut iter = INPUT.lines();

    let ops = parse_op(iter.next().unwrap());
    let mut op_iter = ops.iter().cycle().enumerate();
    let paths = parse_paths(&mut iter);

    let mut count = 0;
    let mut p = String::from("AAA");
    while let Some((i, op)) = op_iter.next() {
        if p == "ZZZ" {
            count = i;
            break;
        }
        let path = paths.get(&p).unwrap();
        match op {
            Op::L => p = path.0.clone(),
            Op::R => p = path.1.clone(),
        }
    }
    println!("part1: {}", count);

    let mut p: Vec<String> = paths.keys().filter(|k| k.ends_with("A")).map(|k| k.clone()).collect();
    let mut op_iter = ops.iter().cycle().enumerate();

    let mut loops: HashMap<usize, usize> = HashMap::new();

    while let Some((i, op)) = op_iter.next() {
        p = p.iter().enumerate().map(|(n, s)| {
            if s.ends_with("Z") {
                loops.entry(n).or_insert(i);
            };
            let path = paths.get(s).unwrap();
            match op {
                Op::L => path.0.clone(),
                Op::R => path.1.clone(),
            }
        }).collect();

        if loops.len() == p.len() {
            break;
        }
    }
    let loops: Vec<usize> = loops.values().map(|v| *v).collect();
    println!("part2: {}", lcm_of_list(&loops));
}

enum Op {
    L,
    R,
}

fn parse_op(s: &str) -> Vec<Op> {
    s.chars().map(|c| match c {
        'L' => Op::L,
        'R' => Op::R,
        _ => panic!("invalid op"),
    }).collect()
}

fn parse_paths(lines: &mut dyn Iterator<Item = &str>) -> HashMap<String, (String, String)> {
    lazy_static! {
        static ref RE: Regex = Regex::new(r"(\w+) = \((\w+), (\w+)\)").unwrap();
    }

    let mut paths: HashMap<String, (String, String)> = HashMap::new();

    while let Some(s) = lines.next() {
        if s == "" { continue }

        if let Some(caps) = RE.captures(s) {
            paths.insert(caps[1].to_string(), (caps[2].to_string(), caps[3].to_string()));
        }
    }

    paths
}

fn gcd(a: usize, b: usize) -> usize {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: usize, b: usize) -> usize {
    a / gcd(a, b) * b
}

fn lcm_of_list(numbers: &[usize]) -> usize {
    numbers.iter().fold(1, |l, &num| lcm(l, num))
}