I bought Ghost of Tsushima in one of the recent sales, and I've been enjoying it a great deal, so I'll likely be joining you there.

Rust

I was stuck for a while, even after getting a few hints, until I read the problem more closely and realized: there is only one non-cheating path, and every free space is on it. This means that the target of any shortcut is guaranteed to be on the shortest path to the end.

This made things relatively simple. I used Dijkstra to calculate the distance from the start to each space. I then looked at every pair of points: if they are a valid distance away from each other, check how much time I would save jumping from one to the next. If that amount of time is in the range we want, then this is a valid cheat.

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

// Critical point to note: EVERY free space is on the shortest path.

use itertools::Itertools;

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

type MyGrid = Grid<MazeElement>;

enum MazeElement {
    Wall,
    Free,
    Start,
    End,
}

impl MazeElement {
    fn is_free(&self) -> bool {
        !matches!(self, MazeElement::Wall)
    }
}

fn parse_input(input: String) -> (MyGrid, Coordinate) {
    let grid: MyGrid = input.lines()
        .map(|line| line.chars().map(|c| match c {
            '#' => MazeElement::Wall,
            '.' => MazeElement::Free,
            'S' => MazeElement::Start,
            'E' => MazeElement::End,
            _ => panic!("Invalid maze element: {}", c)
        })
             .collect())
        .collect::<Vec<Vec<MazeElement>>>()
        .into();

    let start_pos = grid.iter().find(|(_, me)| matches!(me, MazeElement::Start)).unwrap().0;

    (grid, start_pos)
}

fn solve<R>(grid: &MyGrid, start_pos: Coordinate, min_save_time: usize, in_range: R) -> usize
where R: Fn(Coordinate, Coordinate) -> bool {
    let (cost_to, _) = dijkstra(
        start_pos,
        |&c| grid.orthogonal_neighbors_iter(c)
            .filter(|&n| grid[n].is_free())
            .map(|n| (n, 1))
            .collect()
    );

    cost_to.keys()
        .cartesian_product(cost_to.keys())
        .map(|(&c1, &c2)| (c1, c2))
        // We don't compare with ourself
        .filter(|&(c1, c2)| c1 != c2)
        // The two points need to be within range
        .filter(|&(c1, c2)| in_range(c1, c2))
        // We need to save at least `min_save_time`
        .filter(|(c1, c2)| {
            // Because we are working with `usize`, the subtraction
            // could underflow. So we need to use `checked_sub`
            // instead, and check that a) no underflow happened, and
            // b) that the time saved is at least the minimum.
            cost_to.get(c2).copied()
                .and_then(|n| n.checked_sub(*cost_to.get(c1).unwrap()))
                .and_then(|n| n.checked_sub(c1.distance_to(c2)))
                .map(|n| n >= min_save_time)
                .unwrap_or(false)
        })
        .count()
}

pub struct Day20Solver;

impl DaySolver for Day20Solver {
    fn part1(&self, input: String) -> String {
        let (grid, start_pos) = parse_input(input);
        solve(
            &grid,
            start_pos,
            100,
            |c1, c2| c1.distance_to(&c2) == 2,
        ).to_string()
    }

    fn part2(&self, input: String) -> String {
        let (grid, start_pos) = parse_input(input);
        solve(
            &grid,
            start_pos,
            100,
            |c1, c2| c1.distance_to(&c2) <= 20,
        ).to_string()
    }
}

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

    #[test]
    fn test_part1() {
        let input = include_str!("../../inputs/test/20");
        let (grid, start_pos) = parse_input(input.to_string());
        let actual = solve(&grid, start_pos, 1, |c1, c2| c1.distance_to(&c2) == 2);
        assert_eq!(44, actual);
    }

    #[test]
    fn test_part2() {
        let input = include_str!("../../inputs/test/20");
        let (grid, start_pos) = parse_input(input.to_string());
        let actual = solve(&grid, start_pos, 50, |c1, c2| c1.distance_to(&c2) <= 20);
        assert_eq!(285, actual);
    }
}

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.