Gear Ratios

Advent of Code 2023 Day 3

Part 1

A fun twist on a classic theme

• Grid? check!
• Adjacent cells? check!

The twist? The adjacent cells contain portions of a larger number! So, it's not enough to just check the eight adjacent cells of each symbol.

This is gonna be fun!

A couple approaches

1. Find every number; Check if any of its digits are adjacent to a symbol; Count it towards the sum if so.
2. Find every symbol; Check which digits it is adjacent to; Compare the digits with a larger list of number locations; Count the corresponding numbers toward the sum
3. Probably something else that I'll either think of part-way or won't think of and wish I had

Mini-challenge: do any numbers repeat?

I prefer to use approach #1 above.

That would be real easy if I can make a 1:1 mapping of number to location.

That won't be as easy if any giving number appears more than once in the grid.

Regardless, I predict it will be helpful to know all the numbers and know the row and cells that each number occupies.

Thankfully, matching only the numbers is easy with use of this regular expression:

/\d+/g

Using that, I can generate a list of all the numbers.

Then, I can generate a unique list of numbers.

Lastly, I can compare the length/size of each list.

If they are equal, then no numbers repeat!

Else, they are not equal, and at least one number repeats.

Here's how I do that in JavaScript:

const nums = [...input.matchAll(/\d+/g)].map(el => +el[0])
const uniques = new Set([...nums])
console.log(nums.length, uniques.size)

For the example input, the numbers are equal.

For my puzzle input, the second number is nearly half.

Bummer.

Shifting gears: matching all the symbols

The grid is filled with digits, dots and other non-alphanumeric characters.

I need a regular expression that matches the 'other's.

After some research and trial and error, it seems like this will do the trick:

/[^0-9.]/g

That reads as: Any character that is not the digits 0 thru 9 or a period

Great! Now, what could I do with that? Well, use approach #2 from way above, maybe?

Pivot: saving all symbols' coordinates

• I don't care what the symbol is
• I do care where the symbol is
• That is, its location vertically and horizontally within the grid

To determine that, I need to do the following work:

• Split the input into each line of the grid
• Keeping the line as a string
• Search each line for symbol matches
• Accumulate an array of locations
• Where each item is an array
• Containing the row and column of the symbol

In JavaScript, my algorithm looks like this:

const grid = input.split('\n')
const symbolCoords = grid.reduce((coords, line, index) => {
  let matches = [...line.matchAll(/[^0-9.]/g)]
  matches.forEach(match => {
    coords.push([index, match.index])
  })
  return coords
}, [])

Now I have a list of coordinates that of which I can soon check all eight adjacent cells.

Not yet though, since doing that would just tell me "there's an 8 in this cell" or "there's a 1 in this cell".

That's great and all, but I need to know the larger number that any single digit is a part of.

Sidenote: two important details about the puzzle input

1. There are no symbols in the first or last lines
2. No single number is adjacent to more than one symbol

Why are those details important?

1. I don't have to account for 'out-of-bounds' cells when looking at cells adjacent to symbols
2. I don't have to worry about miscounting a number twice when moving from symbol to symbol

Back to my digit-finder, but this time with more oomph!

Looking at the example input:

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

I can match the top-left number, 467.

I know that in its string it spans the indices 0-2.

I'd like to save that as:

In row 0 - the first row:
  Cell 0 corresponds to 467
  Cell 1 corresponds to 467
  Cell 2 corresponds to 467

Why?

• So that when I look at adjacent cells to the * in row 2 and find the 7 northwest of it
• I'll know I'm looking at row 0 cell 2, which contains a digit in the number 467
• And I can add 467 to a Set of digits

Why a Set of digits?

Well, let's continue with the same symbol:

• It will see the 3 that corresponds to the 35
• It will also see the 5 that corresponds to the 35

I don't want to double-count 35.

And when I attempt to add it to a Set the second time, there will remain only one 35 in the Set.

So, after walking around the *, I'll have a Set containing 467 and 35, exactly like I should.

Whew!

Now, how am I gonna build a data structure that resembles the row and nested cells above?

Maybe an array of objects:

[
  { 0: 467, 1: 467, 2: 467}, // First row
  ...,                       // Second row
]

Hmmm. Could work. Let's try!

Building the algorithm

input.split('\n').reduce((coords, line, index) => {
  let matches = [...line.matchAll(/\d+/g)]
  matches.forEach(match => {
    let number = +match[0]
    for (let i = match.index; i < match.index + match[0].length; i++) {
      coords[index][i] = number
    }
  })
  return coords
}, new Array(grid.length).fill(null).map(el => new Object()))

Seeing the expected result...after a bit of debugging:

• Filling an array with separate empty objects feels overly complicated
• I forgot that matchAll is an array of matches
• I forgot to account for the starting index of each number in my for loop's condition for stopping

[
  { '0': 467, '1': 467, '2': 467, '5': 114, '6': 114, '7': 114 },
  {},
  { '2': 35, '3': 35, '6': 633, '7': 633, '8': 633 },
  {},
  { '0': 617, '1': 617, '2': 617 },
  { '7': 58, '8': 58 },
  { '2': 592, '3': 592, '4': 592 },
  { '6': 755, '7': 755, '8': 755 },
  {},
  { '1': 664, '2': 664, '3': 664, '5': 598, '6': 598, '7': 598 }
]

Checkpoint: assessing what I have

• The coordinates of each symbol
• The coordinates of each digit
• The corresponding larger number each digit is part of

Lastly, the usual 'check all adjacent digits' algorithm

The relative coordinates of all eight cells around a central cell are:

[
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [0, -1],
  [0, 1],
  [1, -1],
  [1, 0],
  [1, 1]
]

From the symbol at [1,3] in the example input, the coordinates map to:

[
  [0, 2],
  [0, 3],
  [0, 4],
  [1, 2],
  [1, 4],
  [2, 2],
  [2, 3],
  [2, 4]
]

The first item is the row, the second is the column.

If my still-to-be-written algorithm works correctly, it will find some numbers at three of those spots:

[
  7,
  -,
  -,
  -,
  -,
  3,
  5,
  -
]

But, really, that's not important. Instead, I want to search my new dictionary of number coordinates:

[
  467,
  -,
  -,
  -,
  -,
  35,
  35,
  -
]

Adding each number to a Set:

{ 467, 35 }

And adding the sum of those numbers to an accumulating sum.

Let's write this final algorithm for Part 1 (I hope!)

Building the adjacent cell checking algorithm

symbols.reduce((grandTotal, [row, col]) => {
  let partNums = adjacents.reduce((numbers, [y, x]) => {
    if (!isNaN(+grid[row + y][col + x])) {
      numbers.add(nums[row + y][col + x])
    }
    return numbers
  }, new Set())
  return grandTotal += [...partNums].reduce((a,c) => a + c)
}, 0)

Checking, submitting and hopefully celebrating??!

My algorithm generates the correct answer with the example input.

Will it work, and will it generate the correct answer for my puzzle input?

...

YES!!! Woohoo!!!

Sheesh, that seemed like a lot of work for a Day 3 puzzle.

I'm anxious to see what Part 2 will demand of me.

Part 2

A huge sigh of relief

I think I just need to make three edits to my code:

1. Only store the locations of * symbols
2. Check if my Set size is two before performing math
3. Add the product, not the sum

My updated return statement in the algorithm from the end of Part 1:

  return grandTotal += partNums.size == 2 ? [...partNums].reduce((a,c) => a * c) : 0

Checking, submitting and celebrating

Example input: correct!
My puzzle input: correct!

Whew! My hard work in Part 1 sure paid off in Part 2.

That was quite the puzzle!

I loved the twist on the recurring adjacent cell theme.

Hopefully more challenges this year will be equally challenging but accessible.

Next, a break. Then, Day 4!