Rust

Part 1 was quite straightforward: just keep track of a frontier of every beam, and keep following it, adding splitter locations to a set. Easy.

I had to give some thought to Part 2 and ended up doing dynamic programming: for every position, keep track of how many timelines go through it, solving recursively where necesary.

use std::collections::{HashMap, HashSet, VecDeque};

use crate::{grid::{Coordinate, Direction, Grid}, solver::DaySolver};

pub struct Day07Solver;

impl DaySolver for Day07Solver {
    fn part1(&self, input: String) -> String {
        let grid = Grid::from_grid_string(
            &input,
            |c| match c {
                'S' => Location::Start,
                '^' => Location::Splitter,
                '.' => Location::Empty,
                _ => panic!("Invalid location type"),
            }
        );

        let mut reached_splitters: HashSet<Coordinate> = HashSet::new();

        let mut beam_coordinates: VecDeque<Coordinate> = grid.iter()
            .filter_map(|(c, l)| match l {
                Location::Start => Some(c),
                _ => None,
            })
            .collect();

        while let Some(next) = beam_coordinates.pop_front() {
            if let Some(next_coord) = grid.neighbor_in_direction(next, Direction::Down) {
                match grid[next_coord] {
                    Location::Start => { panic!("Encountered a second start!"); },
                    Location::Splitter => {
                        if !reached_splitters.contains(&next_coord) {
                            reached_splitters.insert(next_coord);
                            [
                                grid.neighbor_in_direction(next_coord, Direction::Left),
                                grid.neighbor_in_direction(next_coord, Direction::Right),
                            ]
                                .into_iter()
                                .flatten()
                                .for_each(|c| beam_coordinates.push_back(c));
                        }
                    },
                    Location::Empty => { beam_coordinates.push_back(next_coord); }
                }
            }
        }

        reached_splitters
            .len()
            .to_string()
    }

    fn part2(&self, input: String) -> String {
        let grid = Grid::from_grid_string(
            &input,
            |c| match c {
                'S' => Location::Start,
                '^' => Location::Splitter,
                '.' => Location::Empty,
                _ => panic!("Invalid location type"),
            }
        );

        let start_coord = grid.iter().find(|(_, l)| **l == Location::Start).unwrap().0;

        let mut num_timelines: HashMap<Coordinate, usize> = HashMap::new();
        count_timelines(&mut num_timelines, &grid, 1, start_coord);

        num_timelines[&start_coord].to_string()
    }
}

fn count_timelines(
    num_timelines: &mut HashMap<Coordinate, usize>,
    grid: &Grid<Location>,
    timelines_so_far: usize,
    coordinate: Coordinate,
) {
    if num_timelines.contains_key(&coordinate) {
        return
    }

    match grid[coordinate] {
        Location::Splitter => {
            let neighbors: Vec<Coordinate> = [
                grid.neighbor_in_direction(coordinate, Direction::Left),
                grid.neighbor_in_direction(coordinate, Direction::Right),
            ]
                .into_iter()
                .flatten()
                .collect();

            neighbors.iter()
                .for_each(|next| {
                    count_timelines(num_timelines, grid, timelines_so_far, *next);
                });

            let timelines_from_here = neighbors.iter().map(|c| num_timelines[c]).sum();
            num_timelines.insert(coordinate, timelines_from_here);
        },
        _ => {
            let timelines_from_here = if let Some(next) = grid.neighbor_in_direction(coordinate, Direction::Down) {
                count_timelines(num_timelines, grid, timelines_so_far, next);
                num_timelines[&next]
            } else {
                timelines_so_far
            };

            num_timelines.insert(coordinate, timelines_from_here);
        },
    };
}

#[derive(PartialEq, Eq, Copy, Clone)]
enum Location {
    Start,
    Splitter,
    Empty,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part1() {
        let input = include_str!("../../inputs/test/07");

        let solver = Day07Solver {};
        assert_eq!("21", solver.part1(input.to_string()));
    }


    #[test]
    fn part2() {
        let input = include_str!("../../inputs/test/07");

        let solver = Day07Solver {};
        assert_eq!("40", solver.part2(input.to_string()));
    }
}