MY EYES

Rust

I figured that Part 2 would want something to do with unique paths, so I tried to generate all paths in Part 1, which took too long. So I then decided to go with dynamic programming. In Part 1, I stored a cache of whether a given state can lead to the solution. In Part 2, I updated it to store how many options are possible from a given state.

https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day19.rs?ref_type=heads

use std::collections::HashMap;

use crate::solver::DaySolver;

fn parse_input(input: String) -> (Vec<String>, Vec<String>) {
    let towels = input.lines().take(1).collect::<String>().split(", ").map(|s| s.to_string()).collect();

    let designs = input.lines().skip(2).map(|s| s.to_string()).collect();

    (towels, designs)
}

fn how_many_ways(cache: &mut HashMap<String, usize>, towels: &[String], current: String, target: &str) -> usize {
    if let Some(ways) = cache.get(&current) {
        *ways
    } else if current == target {
        cache.insert(current.clone(), 1);
        1
    } else if !target.starts_with(&current) {
        cache.insert(current.clone(), 0);
        0
    } else {
        let ways = towels.iter()
            .map(|t| format!("{}{}", current, t))
            .map(|next| how_many_ways(cache, towels, next, target))
            .sum();
        cache.insert(current, ways);
        ways
    }
}

pub struct Day19Solver;

impl DaySolver for Day19Solver {
    fn part1(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .filter(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), d) > 0)
            .count()
            .to_string()
    }

    fn part2(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .map(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), &d))
            .sum::<usize>()
            .to_string()
    }
}

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

    #[test]
    fn test_part1() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("6", solver.part1(input.to_string()));
    }

    #[test]
    fn test_part2() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("16", solver.part2(input.to_string()));
    }
}

Rust

I essentially used flood fill to collect each region. Part 1 was then relatively easy: for each point, check how many neighbors are outside of the region.

Part 2 took me forever, and I ended up looking for hints online, where I discovered that an easy way to count the number of sides is to instead count the number of corners. Doing this for "normal" corners (e.g. in a square) was relatively easy, but "reverse corners" took me a long time. Corners like here what we see in the NE corner of the first C in the third row here:

....
..C.
..CC
...C

I'm more or less happy with my solution, but my brain is now totally fried.

https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day12.rs?ref_type=heads

use std::collections::HashSet;

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

fn perimeter_score(c: Coordinate, grid: &MyGrid) -> usize {
    let plant_type = grid[c];

    Direction::orthogonal_iter()
        .map(|d| grid.neighbor_in_direction(c, d))
        .map(|c_opt| match c_opt {
            None => 1,
            Some(c) => if grid[c] == plant_type {
                0
            } else {
                1
            }
        })
        .sum()
}

type MyGrid = Grid<char>;

struct Region {
    #[allow(dead_code)]
    plant_type: char,
    coordinates: HashSet<Coordinate>,
}

impl Region {
    fn new(plant_type: char, coordinates: HashSet<Coordinate>) -> Region {
        Region { plant_type, coordinates }
    }

    fn iter(&self) -> impl Iterator<Item = &Coordinate> {
        self.coordinates.iter()
    }

    fn part1_score(&self, grid: &MyGrid) -> usize {
        self.coordinates.len() * self.coordinates.iter().map(|c| perimeter_score(*c, grid)).sum::<usize>()
    }

    fn part2_score(&self, grid: &MyGrid) -> usize {
        let area = self.coordinates.len();
        let sides = self.number_of_corners(grid);

        area * sides
    }

    fn number_of_corners(&self, grid: &MyGrid) -> usize {
        self.coordinates.iter().cloned()
            .map(|coordinate| {
                // How many corners do we have from here?
                // println!("Checking {}", border_coordinate);

                let corner_count = Direction::diagonal_iter()
                    .filter(|corner_direction| {
                        // Either:
                        // 1) Both neighbor directions are not 100% in the region
                        // 2) Both neighbors are in the region, but the corner itself isn't

                        let corner_in_region = match grid.neighbor_in_direction(coordinate, *corner_direction) {
                            None => false,
                            Some(c) => self.coordinates.contains(&c),
                        };

                        let both_neighbors_not_in_region = corner_direction.neighbor_directions().iter()
                            .all(|direction| match grid.neighbor_in_direction(coordinate, *direction) {
                                None => true,
                                Some(c) => !self.coordinates.contains(&c),
                            });

                        let both_neighbors_in_region = corner_direction.neighbor_directions().iter()
                            .all(|direction| match grid.neighbor_in_direction(coordinate, *direction) {
                                None => false,
                                Some(c) => self.coordinates.contains(&c),
                            });

                        both_neighbors_not_in_region || (both_neighbors_in_region && !corner_in_region)
                    })
                    .count();
                // println!("Corner count = {}", corner_count);
                corner_count
            })
            .sum()
    }
}

fn parse_input(input: String) -> MyGrid {
    input.lines()
        .map(|line| line.chars().collect())
        .collect::<Vec<Vec<char>>>()
        .into()
}

fn find_region_at(grid: &MyGrid, start: Coordinate) -> Region {
    let plant_type = grid[start];
    let mut coordinates = HashSet::new();
    let mut frontier = vec![start];

    while let Some(coordinate) = frontier.pop() {
        if grid[coordinate] == plant_type  && !coordinates.contains(&coordinate) {
            coordinates.insert(coordinate);
            frontier.extend(grid.orthogonal_neighbors_iter(coordinate));
        }
    }

    Region::new(plant_type, coordinates)
}

fn find_regions(grid: &MyGrid) -> Vec<Region> {
    let mut visited_coordinates: HashSet<Coordinate> = HashSet::new();
    let mut regions = vec![];

    for coordinate in grid.coordinates_iter() {
        if !visited_coordinates.contains(&coordinate) {
            let region = find_region_at(grid, coordinate);
            visited_coordinates.extend(region.iter().cloned());
            regions.push(region);
        }
    }

    regions
}

pub struct Day12Solver;

impl DaySolver for Day12Solver {
    fn part1(&self, input: String) -> usize {
        let grid = parse_input(input);
        let regions = find_regions(&grid);

        regions.into_iter()
            .map(|region| region.part1_score(&grid))
            .sum()
    }

    fn part2(&self, input: String) -> usize {
        let grid = parse_input(input);
        let regions = find_regions(&grid);

        regions.into_iter()
            .map(|region| region.part2_score(&grid))
            .sum()
    }
}

Rust

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

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

fn add_distance(coordinate: Coordinate, distance: (i64, i64)) -> Option<Coordinate> {
    coordinate.try_add(distance)
}

fn sub_distance(coordinate: Coordinate, distance: (i64, i64)) -> Option<Coordinate> {
    coordinate.try_sub(distance)
}

fn part2_possible_antinodes<F>(
    grid: &Grid<Option<char>>,
    coordinate: Coordinate,
    distance: (i64, i64),
    op: F,
    mut accumulator: Vec<Coordinate>
) -> Vec<Coordinate>
where F: Fn(Coordinate, (i64, i64)) -> Option<Coordinate> {
    match op(coordinate, distance).filter(|c| grid.get(*c).is_some()) {
        None => accumulator,
        Some(next_coord) => {
            accumulator.push(next_coord);
            part2_possible_antinodes(grid, next_coord, distance, op, accumulator)
        }
    }
}

trait Pairable<T> {
    fn pairs(&self) -> Vec<(&T, &T)>;
}

impl<T> Pairable<T> for HashSet<T> {
    fn pairs(&self) -> Vec<(&T, &T)> {
        let v: Vec<&T> = self.iter().collect();

        let mut p = vec![];

        for i in 0..v.len() {
            let thing1 = v[i];

            for thing2 in &v[i+1..] {
                p.push((thing1, *thing2));
            }
        }

        p
    }
}

fn parse_input(input: String) -> (Grid<Option<char>>, HashMap<char, HashSet<Coordinate>>) {
    let g: Grid<Option<char>> =
        input.lines()
        .map(|line| line.chars()
             .map(|c| if c == '.' {
                 None
             } else {
                 Some(c)
             }).collect::<Vec<Option<char>>>()
        )
        .collect::<Vec<Vec<Option<char>>>>()
        .into();

    let mut freq_to_coords: HashMap<char, HashSet<Coordinate>> = HashMap::new();

    for (coord, freq_opt) in g.iter() {
        match freq_opt {
            None => (),
            Some(freq) => {
                freq_to_coords.entry(*freq)
                    .and_modify(|coords| {
                        coords.insert(coord);
                    })
                    .or_insert(HashSet::from([coord]));
            }
        }
    }

    (g, freq_to_coords)
}

pub struct Day08Solver;

impl DaySolver for Day08Solver {
    fn part1(&self, input: String) -> usize {
        let (g, freq_to_coords) = parse_input(input);

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

        for (_, coords) in freq_to_coords {
            // println!("Freq = {}", freq);
            for (c1, c2) in coords.pairs() {
                let distance = c1.xy_distance_to(c2);
                let possible_antinodes: Vec<Coordinate> = [c1.try_sub(distance), c2.try_add(distance)].into_iter()
                    .flat_map(|co| co.filter(|c| g.get(*c).is_some()))
                    .collect();

                // println!("Pair = ({},{}), antinodes = {:?}", c1, c2, possible_antinodes);

                for antinode in possible_antinodes {
                    antinodes.insert(antinode);
                }
            }
        }

        antinodes.len()
    }

    fn part2(&self, input: String) -> usize {
        let (g, freq_to_coords) = parse_input(input);

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

        for (freq, coords) in freq_to_coords {
            println!("Freq = {}", freq);
            for (c1, c2) in coords.pairs() {
                let distance = c1.xy_distance_to(c2);

                let possible_antinodes: Vec<Coordinate> = [
                    part2_possible_antinodes(&g, *c1, distance, add_distance, vec![*c1]),
                    part2_possible_antinodes(&g, *c1, distance, sub_distance, vec![*c1]),
                    part2_possible_antinodes(&g, *c2, distance, add_distance, vec![*c2]),
                    part2_possible_antinodes(&g, *c2, distance, sub_distance, vec![*c2]),
                ].into_iter().flatten().collect();

                println!("Pair = ({},{}), antinodes = {:?}", c1, c2, possible_antinodes);

                for antinode in possible_antinodes {
                    antinodes.insert(antinode);
                }
            }
        }

        antinodes.len()
    }
}

https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day08.rs?ref_type=heads

I also did it in Rust, though mine is quite a bit more verbose than yours :). https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day08.rs?ref_type=heads

Have you considered using a HashSet<(usize, usize)> to store the visited locations instead of a 2d vector?

Alas, no. We just have a Slack channel, and I think that work generally just slows down a bit in December, so people have a bit of time to work on AoC.

I run our AoC channel at work, and also reactivated it this week after a year of inactivity :).

I would love to learn a new language, but I'll probably just do it in Rust again, because I so rarely get to program in Rust :).

In the name of all that is good and holy, do not go down that staircase

With projects like these, I'm always torn between thinking that it's cool it's possible, and horror that someone somewhere will try to use this in production code.

I know I probably shouldn't engage, but I really just wanted to spark a conversation. I find the trope interesting. I agree that my Good Place example isn't that good, but still, no need to be so accusing.

I completely forgot to mention His Dark Materials! Hell doesn't appear, but Heaven is portrayed as actively bad.

I would +1 this. I'm completely bald, and almost never leave the house without a hat, even in summer. It's also important protection against sunburn :).

For something comfortable in the summer, I personally often go for brimmed hiking hats. A few that I like:

• Fjällräven Abisko Summer Hat
• Shelta Sun Hawk