Advent of Code 2023: Day 03

Code for solutions available on GitHub.

Gear Ratios

In this episode of Christmas coding, we’re tasked with finding some numbers in a grid. The lore is that the numbers are part identifiers or something like that. I don’t know, go read the lore yourself ;). I’m just chronicling the solving process.

The example grid is given as follows:

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

Each number that is adjacent to a symbol that isn’t ., even diagonally, is a valid part number. The task is to find all part numbers and sum them up.

When I see a grid, the first thing I think about is coordinates, so I started with defining a simple Position type:

struct Position {
    row: u32,
    col: u32,
}

Of course, we have two entities in this grid, Symbols and Numbers. Let’s make types for them too:

struct Symbol {
    symbol: char,
    position: Position,
}

struct Number {
    number: u32,
    position: Position,
    length: u32,
}

The Number struct has an additional length field, as the space it takes up in the grid is defined by its starting point and length. Now, I didn’t know this when solving part 1, but I had a hunch that what particular character a symbol is was going to matter for part 2, so I added that too. I was correct.

A Number is valid if it is adjacent to a Symbol, even diagonally. Or in other words, if there is a Symbol inside of a rectangle that surrounds the Number, but is one unit larger in all dimensions. Hey, that’s a pretty neat idea. Let’s make a Rectangle struct that can check if it contains a point.

struct Rectangle {
    top_left: Position,
    bottom_right: Position,
}

impl Rectangle {
    fn contains(&self, position: &Position) -> bool {
        self.top_left.row <= position.row
            && self.bottom_right.row >= position.row
            && self.top_left.col <= position.col
            && self.bottom_right.col >= position.col

    }
}

And now a helper method that can construct the proper bounding Rectangle for a Number:

impl Number {
    fn rect(&self) -> Rectangle {
        Rectangle {
            top_left: Position {
                row: self.position.row.saturating_sub(1),
                col: self.position.col.saturating_sub(1),
            },
            bottom_right: Position {
                row: self.position.row + self.length + 1,
                col: self.position.col + self.length + 1,
            },
        }
    }
}

We have to use saturating_sub because we can’t have negative numbers in Positions, and some Numbers start at row or column 0. So in these cases the Rectangle is slightly smaller than normal, but that’s fine.

Now let’s put all this together in a Grid struct:

struct Grid {
    symbols: Vec<Symbol>,
    numbers: Vec<Number>,
}

And time for parsing. Once again, this is not particularly interesting, just a bunch of nom parsers and combinators, with the only complications begin the bookkeeping of the row and column being parsed, and getting the length of a parsed number using u32::ilog10. Parsing code is here, starting in parse_grid.

Now for the solution. It’s pretty simple, by using the Number::rect and Rectangle::contains methods defined above to filter the numbers by whether their rectangle contains any symbol in the grid:

let grid = parse_grid(input);
grid.numbers
    .into_iter()
    .filter(|number| {
        let rect = number.rect();
        grid.symbols
            .iter()
            .any(|symbol| rect.contains(symbol.position))
    })
    .map(|number| number.number)
    .sum()
}

Part 2

I was right about the specific character of the symbols being important for this part. This time, the task is to find all * symbols (gears) that are adjacent to exactly 2 numbers, and sum up the product of all those pairs. Luckily, since I saved the character in each symbol, the grid’s symbols can be filtered on this:

let grid = parse_grid(input);
grid.symbols
    .into_iter()
    .filter(|symbol| symbol.symbol == '*')
    .map(|gear| {
        // Get all numbers adjacent to the gear
        // Check that there are exactly 2
        // Return the product of the numbers
    })
    .sum()
}

The easy way to go about this is to simply create an iterator over all numbers in the grid whose rectangle contains the current gear.

let grid = parse_grid(input);
grid.symbols
    .into_iter()
    .filter(|symbol| symbol.symbol == '*')
    .map(|gear| {
        let mut numbers = grid
            .numbers
            .iter()
            .filter(|number| {
                number.rect().contains(gear.position)
            });
        
        let first = numbers.next();
        let second = numbers.next();
        let third = numbers.next();

        if let (Some(first), Some(second), None) = (first, second, third) {
            first.number * second.number
        } else {
            0
        }
    })
    .sum()
}

And this works fine. It gives the right answer, only outputting non-zero for each gear with exactly two numbers adjacent to it, and was my initial solution.

I did spot an inefficiency though. It’s unnecessary to iterate over all numbers in the grid, as the only numbers that have a rectangle that contains the gear are the ones whose row is 1 less than, equal to, or 1 greater than the gear’s row.

The fix is simple:

let grid = parse_grid(input);
grid.symbols
    .into_iter()
    .filter(|symbol| symbol.symbol == '*')
    .map(|gear| {
        let mut numbers = grid
            .numbers
            .iter()
+           .skip_while(|number| {
+               number.position.row < gear.position.row.saturating_sub(1)
+           })
+           .take_while(|number| {
+               number.position.row < gear.position.row + 2
+           })
            .filter(|number| {
                number.rect().contains(gear.position)
            });
        
        let first = numbers.next();
        let second = numbers.next();
        let third = numbers.next();

        if let (Some(first), Some(second), None) = (first, second, third) {
            first.number * second.number
        } else {
            0
        }
    })
    .sum()
}

This brought the benchmark time down from about 500 microseconds to about 250. Twice as fast. That’s pretty nice :)