First part was simple enough. Second part was easy logically, but after running the brute force solution with a parallel iterator from rayon and maxing out all 12 cores of this CPU, it was still taking forever. I always get tripped up by these ones that need fancy math, because although I was always good at math, I’ve never been good at looking at these problems and figuring out what kind of formula would apply. So I cheated and looked at other people’s comments for their solutions, and saw the least common multiple mentioned. This made sense to me, so I implemented it and got a result almost instantly. I hate having to look at other comments to solve these things, but I never would have came to that conclusion myself.

The code still isn’t the cleanest, and I’d love to tidy up the parsing, but it works and I’m happy.

https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day08.rs

impl Solver for Day08 {
    fn star_one(&self, input: &str) -> String {
        let (directions, map) = input.split_once("\n\n").unwrap();

        let mut route_map = HashMap::new();

        for line in map.lines() {
            let line = line.replace(" ", "").replace("(", "").replace(")", "");
            let (position, destinations) = line.split_once('=').unwrap();
            let (left, right) = destinations.split_once(',').unwrap();
            route_map.insert(position.to_string(), (left.to_string(), right.to_string()));
        }

        let mut current_position = "AAA".to_string();
        for (step, direction) in directions.chars().cycle().enumerate() {
            current_position = match direction {
                'L' => route_map[¤t_position].0.to_string(),
                'R' => route_map[¤t_position].1.to_string(),
                _ => unreachable!(),
            };

            if current_position == "ZZZ" {
                return (step + 1).to_string();
            }
        }

        unreachable!()
    }

    fn star_two(&self, input: &str) -> String {
        let (directions, map) = input.split_once("\n\n").unwrap();

        let mut route_map = HashMap::new();

        for line in map.lines() {
            let line = line.replace(" ", "").replace("(", "").replace(")", "");
            let (position, destinations) = line.split_once('=').unwrap();
            let (left, right) = destinations.split_once(',').unwrap();
            route_map.insert(position.to_string(), (left.to_string(), right.to_string()));
        }

        let positions = route_map
            .keys()
            .filter(|pos| pos.ends_with('A'))
            .collect::>();

        let steps = positions
            .iter()
            .filter(|pos| pos.ends_with('A'))
            .map(|pos| {
                let mut current_position = pos.to_string();
                for (step, direction) in directions.chars().cycle().enumerate() {
                    current_position = match direction {
                        'L' => route_map[¤t_position].0.to_string(),
                        'R' => route_map[¤t_position].1.to_string(),
                        _ => unreachable!(),
                    };

                    if current_position.ends_with('Z') {
                        return step + 1;
                    }
                }
                unreachable!()
            })
            .collect::>();

        steps
            .into_iter()
            .reduce(|acc, steps| acc.lcm(&steps))
            .unwrap()
            .to_string()
    }
}