I had a similar question a while back and ended up with Voip.ms.

https://discuss.tchncs.de/post/2418116

When I toured the concentration camp at Dachau some years ago, the tour guide was very clear on this point: people did elect the Nazis.

In 1932, the Nazi party became the largest party in the German parliament, with 37.3% of the vote. It is true that it was not mandatory to make Hitler chancellor, but as the head of the largest party, it would have been expected.

The Nazi party received massive support in democratic elections, where the expectation of the voters would have been that if the Nazi party gained enough seats, Hitler would become chancellor.

This is an important point to me, as it shows that it is possible for democratic elections to result in a fascist government that dismantles democracy. Ignoring this historical example prevents us from applying the lesson to new situations.

Hah. I tried doing some research about what this kind of drain is called, but I have no idea. I’ve never had a drain like this before, but I guess it must not be too rare?

In my case, the issue is that it starts to stink a lot. We had a plumber out a few years ago, and he opened that thing up and used a plunger to remove a ton of hair. He then suggested we wash it out every now and again, but I haven’t been able to do it for a while now, since I can’t get that thing open.

Not at all a silly question! I have tried, yes. Also, I’ve been able to remove it before, but the last time I put it in, I really jammed it in, I guess. There are no threads, so the turning is really just about generating force.

This looks very promising! Have you used something like this before? Most references I see online use this to remove the entire drain, not simply to turn the little thing inside. Is that accurate?

It’s not the most complex game, but Dixit has really beautiful cards, in my opinion.

I agree that the cards are great! Have you heard of the Fan Art Pack? It has variants of a bunch of the cards in a different style, which I also quite like.

As St IGNUcious said, proprietary software is the sin. Using vi the penance.

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.