aoc 2023 day 08

main.rs

use std::{collections::HashMap, io::BufRead};

fn main() {
    let (instr, adjacent) = parse(std::io::stdin().lock());

    let phase1 = solve(&instr, &adjacent);

    let phase2 = solve_many(&instr, &adjacent);

    assert_eq!(phase1, 14429);
    assert_ne!(phase2, 22411, "low");
    assert_eq!(phase2, 10921547990923);
}

/// Ascii
type Label = [u8; 3];

fn solve(instructions: &[bool], adjacent: &HashMap<Label, (Label, Label)>) -> usize {
    let mut now_at = b"AAA";

    let mut instructions = instructions.iter().copied().cycle();
    let mut steps = 0;

    while now_at != b"ZZZ" {
        let (left, right) = adjacent.get(now_at).unwrap();
        now_at = if instructions.next().unwrap() {
            right
        } else {
            left
        };

        steps += 1;
    }

    steps
}

fn solve_many(instructions: &[bool], adjacent: &HashMap<Label, (Label, Label)>) -> usize {
    let mut places: Vec<&Label> = adjacent.keys().filter(|x| x[2] == b'A').collect::<Vec<_>>();

    let mut instructions = instructions.iter().copied().cycle();
    let mut steps = 0;

    let mut cycles = Vec::new();

    while !places.is_empty() {
        steps += 1;
        let instr = instructions.next().unwrap();

        places.retain_mut(|now_at| {
            let (l, r) = adjacent.get(*now_at).unwrap();
            *now_at = if instr { r } else { l };
            let retain = now_at[2] != b'Z';

            if !retain {
                cycles.push(steps);
            }
            retain
        });
    }

    let max_factor_counts = cycles
        .iter()
        .copied()
        .map(|n| {
            let mut factors = HashMap::new();
            let mut x = n;

            while x % 2 == 0 {
                x /= 2;
                *factors.entry(2).or_default() += 1;
            }

            let mut d = 3;

            while d * d <= x {
                while x % d == 0 {
                    x /= d;
                    *factors.entry(d).or_default() += 1;
                }

                // skip the evens
                d += 2;
            }

            if x > 1 {
                *factors.entry(x).or_default() += 1;
            }

            (n, factors)
        })
        .fold(
            HashMap::<usize, usize>::new(),
            |mut max_factor_counts, (_n, factor_counts)| {
                for (factor, count) in factor_counts {
                    max_factor_counts
                        .entry(factor)
                        .and_modify(|old_max| *old_max = (*old_max).max(count))
                        .or_insert(1);
                }

                max_factor_counts
            },
        );

    let lcm = max_factor_counts
        .into_iter()
        .fold(1, |acc, (factor, count)| {
            acc * factor.pow(u32::try_from(count).unwrap())
        });

    lcm
}

fn parse(mut input: impl BufRead) -> (Vec<bool>, HashMap<Label, (Label, Label)>) {
    let mut s = String::new();
    let read = input.read_line(&mut s).unwrap();
    assert_ne!(read, 0);

    let instructions = s
        .trim()
        .chars()
        .map(|x| {
            assert!(x == 'L' || x == 'R');
            x == 'R'
        })
        .collect::<Vec<_>>();

    s.clear();
    let read = input.read_line(&mut s).unwrap();
    assert_ne!(read, 0);

    let mut adjacent = HashMap::new();

    loop {
        s.clear();
        let read = input.read_line(&mut s).unwrap();
        if read == 0 {
            break;
        }
        let line = s.trim();

        let (source, dests) = line.split_once(" = (").unwrap();

        let (left, right) = dests.split_once(", ").unwrap();

        let right = right.strip_suffix(')').unwrap();

        let source = Label::try_from(source.as_bytes()).unwrap();
        let left = Label::try_from(left.as_bytes()).unwrap();
        let right = Label::try_from(right.as_bytes()).unwrap();

        let old = adjacent.insert(source, (left, right));
        assert_eq!(old, None);
    }

    (instructions, adjacent)
}

#[cfg(test)]
fn parse_str(s: &str) -> (Vec<bool>, HashMap<Label, (Label, Label)>) {
    parse(std::io::Cursor::new(s))
}

#[test]
fn example_phase2() {
    let input = "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)";

    let (instr, adjacent) = parse_str(input);

    let steps = solve_many(&instr, &adjacent);
    assert_eq!(steps, 6);
}