2025 Day 4 - Mapping on paper

Oh dear, it's only a 12 day advent calendar and work has already got to me makng me hiddeously late on this one. I've been trying to avoid spoilers on reddit, but from glances at the memes going around, I think the difficulty level is going to ramp up!

Anyway, I'm skipping part 2 of day 3 until I can think properly, and instead moving onto day 4, which is an old favourite problem of mine relating to grids and cartesian coordinates and neighbours.

In this case, we are going to load a grid into memory of locations of rolls of paper, and then we want to look through the grid working out which have <4 neighbours.

In this case, our grid doesn't seem to need much, it's really just a grid of "present or not present", so we can approach this one of two ways. If we think we'll need the grid proper for part two, then we can use my Grid structure, which is a Vector of Vectors of Chars which I can index into reasonably efficiently. But because we don't care about the actual characters, we could more efficiently store this as a set of coordinates. If a coordinate is in the set then there's a roll there, and if it's not, there isn't. A check neighbours would just generate the 8 coordinates around a coordinate and then we can count the number of hits in the set (which is a simple union of both sets and count the results).

I suspect we'll want to come back in part 2 as we'll either need to modify whcih rolls are present as we remove rolls or path find our way from left to right or something with fewest moves, but for now the Set idea sounds good.

First of all, lets turn the input text into a grid. This is so we can pass around our grid. Remember that we're only storing coordinates that have a roll of paper to make life simpler.

fn parse_grid(input: &str) -> HashSet<Coordinate> {
    input
        .lines()
        .enumerate()
        .flat_map(|(y, line)| {
            line.chars().enumerate().flat_map(move |(x, c)| match c {
                '@' => Some(Coordinate::new(x as i32, y as i32)),
                _ => None,
            })
        })
        .collect::<HashSet<_, _>>()
}

In this case, we use enumerate, which turns ['.', '@', '.'] into [(0,'.'), (1,'@'), (2,'.')], and then we're only producing a Coordinate struct for where we found @ symboles. Because we have a match, we need to signal that we're returning either Something or Nothing, which is a great case for an Option. You can easily think of this like a list that either has 1 item or none, so [(0,'.'), (1,'@'), (2,'.')] would turn into [[], [Coordinate(1,0)], []].

We're also using flat_map here which takes a sequence of sequences and flattens them into just a simple sequence. Tehy're handy for Options because None is treated as an empty sequence, so they just end up being skipped, resulting in the above turning into [Coordinate(1,0)]. We use flat_map at the y level as well, giving us just a stream of Coordinate objects, which we turn into a set.

Next, let's approach the generate neighbours. We don't care about the edges of the grid, as they can't contain rolls of paper, so we can assume that anything outside of the bounds simply won't be added to the grid. So our generate neighbours is just going to go through [-1, 0, 1] in boith directions and ignore the option in the center.

fn neighbours(coord: &Coordinate) -> HashSet<Coordinate> {
    let mut res = HashSet::new();
    for y in coord.y - 1..coord.y + 2 {
        for x in coord.x - 1..coord.x + 2 {
            if !(x == coord.x && y == coord.y) {
                res.insert(Coordinate::new(x, y));
            }
        }
    }
    res
}

Now we can combine them with a simple function to count the number of neighbours for a given cell from the grid

fn count_neighbours(grid: &HashSet<Coordinate>, location: &Coordinate) -> usize {
    neighbours(location).intersection(grid).count()
}

This is very simple, take all 8 neighbours of each location, and then get the setwise intersection of the grid, and then count how many are in it. A setwise intersection is just the mathmatical overlap of any items that are the same in both sets, so this just gives us neighbours that are rolls in the grid.

Part 1 is therefore just to count how many of the warehouse have more than 4 neighbours

pub fn calculate_part1(input: &str) -> usize {
    let grid = parse_grid(input);
    grid.iter()
        .filter(|coord| count_neighbours(&grid, coord) < 4)
        .count()
}

Very simple, lets see what part 2 does to this approach.

Day 4 Part 2 - Try try try and try again

Ok, this looks like it might be easier than I thought. I wondered if we were going to move rolls around, but actually all we are doing is instead of just counting how many rolls we have removed, we are creating generations where we find all the rolls that have less than 4 neighbours, and removing them. We're now keeping a running count, and if no rolls are removed, we can stop counting.

This is very similar to the last part1, in fact we may not need any helper functions at all for this.

Our part 2 is going to start the same as part 1, we're going to parse the grid. We're then going to do the filter count neighbours and store the result. Then while the length of that result isn't 0, we're going to add the length to our running total, and we're going to update the grid to be the set difference, i.e. the grid with all the neighbours removed. And because we're doing this in a loop, once the number of valid neighbours gets to 0, we stop and return our total.

We can test this with single iteration versions, any small grid with fewer than 4 rolls will remove them all in iteration 1 and return the number of cells. A block of 9 rolls should remove all the corners in iteration 1, remove all the edges in iteration 2 and finally remove the last center in iteration 3.

pub fn calculate_part2(input: &str) -> usize {
    let mut grid = parse_grid(input);
    let mut valid_neighbours: HashSet<&Coordinate> = grid
        .iter()
        .filter(|coord| count_neighbours(&grid, coord) < 4)
        .collect();
    let mut total = 0;
    while valid_neighbours.len() > 0 {
        total += valid_neighbours.len();
        grid = grid
            .iter()
            .filter(|coordinate| !valid_neighbours.contains(coordinate))
            .copied()
            .collect();
        valid_neighbours = grid
            .iter()
            .filter(|coord| count_neighbours(&grid, coord) < 4)
            .collect();
    }
    total
}

So I said we could do this all in a function, but the get valid neighbours is a bit ugly in it's repetition. We can tidy that up a bit by extracting the while condition out to a local boolean.

pub fn calculate_part2(input: &str) -> usize {
    let mut grid = parse_grid(input);
    let mut has_valid_neighbours = true;
    let mut total = 0;
    let mut valid_neighbours = HashSet::new();
    while has_valid_neighbours {
        valid_neighbours = grid
            .iter()
            .filter(|coord| count_neighbours(&grid, coord) < 4)
            .collect();
        has_valid_neighbours = valid_neighbours.len() > 0;
        total += valid_neighbours.len();
        grid = grid
            .iter()
            .filter(|coordinate| !valid_neighbours.contains(coordinate))
            .copied()
            .collect();
    }
    total
}

That's a tiny bit nicer, so lets try it...

Tiny bit slow, I think all the copying data around is horribly inefficient. There's almost certainly a way to do this where we build up a dead list or similar that would be more efficient. But runs in 1.5 seconds, so while slow it's good enough for now.