Last modified: 2023-12-06 @ 7aa92a7

# Advent of Code 2023: Day 03

*This post is part of a series: Advent of Code 2023*

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, `Symbol`

s and `Number`

s. 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 `Position`

s, and some `Number`

s 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 :)