Advent of Code 2023: Day 3

03 Dec 2023 . category: . Comments

Whew. This year has been a …definite step up from years past in difficulty. Fortunately, with a few simple tools we can make quick work of this puzzler.

Using Space Hashes will help us a ton here. It will turn the problem into a coordinate-addressed space that will make it easier to check the surroundings for each symbol.

A Word on Coordinate Systems

It’s important to consider what coordinate system we’re going to use. Most of us are familiar with a coordinate system like so from our pre-algebra days:

     +y
     ^
     |
-x <-+-> +x
     |
     V
     -y

While it might seem intuitve to have the positive Y-axis point up to the top, when we’re reading in data line by line, it’s actually much easier if we flip the system about its X-axis, like so:

     -y
     ^
     |
-x <-+-> +x
     |
     V
     +y

This is much more intuitive when we consider how we’ll read this text out of the file, line-by-line, from left to right. Additionally, in my source code, I tend to use “Compass” notation like so:

       north
         ^
         |
west <---+---> east
         |
         V
       south

In other words, “north” is the negative Y-axis, “south” is the positive Y-axis, and so on. Here’s how one might define them as vectors using image.Point.

	ptNorth := image.Pt(0, -1)
	ptSouth := image.Pt(0, 1)
	ptEast := image.Pt(1, 0)
	ptWest := image.Pt(-1, 0)
	ptNorthEast := ptNorth.Add(ptEast)
	ptNorthWest := ptNorth.Add(ptWest)
	ptSouthEast := ptSouth.Add(ptEast)
	ptSouthWest := ptSouth.Add(ptWest)

Part 1

Here’s how the top-level algorithm is going to work.

1. Build space hashes to hold the part numbers and symbols.
2. Iterate over the hash with the symbol locations, look for numbers surrounding the symbol
3. Add up all the seen numbers.

Easy, right? Well, there’s some gotchas along the way.

Gotcha 1: Parsing out Part Numbers

The part numbers space hash is going to be a little different from other ones I’ve done in the past, because each point the part number covers is going to have to store the full part number (we’ll see why in a minute). Meaning, if part number 125 starts at coordinate (2,3), I’m going to store 125 in coordinates (2, 3), (3,3), and (4,3). Oof.

Go’s regexp library is a little limited compared to what you can find in a modern Python runtime. It doesn’t support repeated subgroups or overlapping matches (both of which might have made earlier days easier.) But, for this problem, it had exactly what I needed – FindAllStringIndex(), This handy method spits out a pair of integers you can use to access the match in slice notation. Here’s an example.

matchNumber := regexp.MustCompile(`\d+`)
idxs := matchNumber("467..114..", -1) // -1 signifies unlimited matches
fmt.Println(idxs) // [[0,3],[5,8]]

With the output of this function, I’m able to know where each number in the line starts and ends, and I have enough info to extract it from the line of text, like so.

		idxs = matchNumber.FindAllStringIndex(line, -1)
		for _, loc := range idxs {
      partStr := line[loc[0]:loc[1]] // slice notation selects the part number out of the line
			partNum, _ := strconv.Atoi(partStr) // we can safely convert it because we know it's numeric
			for i := loc[0]; i < loc[1]; i++ { // store the parsed value in each point it occupies
				parts[image.Pt(i, lineNo)] = partNum
			}
		}

Neat!

Gotcha 2: Who Said Part Numbers Were Unique?

Any of the 8 neighbors of the symbol can contain a part number. It could be to the west…

.......
.45&...

…or the east…

.......
...&45.

or north or south.

 north    south
....45.  ...&...
...&...  ..45...

Above and below are tricky. In the “north” example, the smbol only sees the 4 out of 45, meaning it’d find the number 45 only once looking at its eight neighbors in the parts space hash. The “south” example, however, is a little more involved. In that example, the symbol can see the numbers 4and 5, meaning that it’s see the number 45 twice in the space hash. If I’m not careful, I’ll overcount part numbers this way!

You might be forgiven for thinking, as I did, that part numbers within a specific assembly ought to be unique. You might then decide to add all part numbers to a Set datastructure (or map[int]bool since Go has no Set type) so that way you don’t actually have to worry about this particular problem.

Part numbers repeat throughout your input, however. Using the Set approach will cause you to undercount part numbers and end up with a value too low. Annoyingly, the sample input doesn’t have any duplicate numbers in it, so you’d totally miss this if you were testing with that input. That means we’re going to have to figure out how to count part numbers properly – a given symbol might very well see the same number twice in its surroundings, even! Boo.

Let’s sketch out more of these cases.

..345..   .231...   ...45..   544.65..
...&...   ...&...   ...&...   ...&....

The symbol can see at most 2 unique numbers provided there’s no number directly north of it. Further, if there is a number directly north of the symbol, it is the only number the symbol can see north of itself. Here’s what it looks like in pseudocode

if number is directly north {
	lookup part number directly north
	if it exists, add it to the part numbers list
} else {
	for corners: northwest, northeast {
		look up number at corner
		if it exists, add it to the part numbers list
	}
}

The same logic follows for the south. Here’s what my code looked like. Note the helper function addIfPresent that only adds the number to the result slice if there’s a part number at that location. Also, for the sake of readability, I took out the definitions of the compass points.

func findPartNums(p image.Point, parts map[image.Point]int) []int {

	var result []int

	addIfPresent := func(results []int, o image.Point) []int {
		num, ok := parts[o]
		if !ok {
			return results
		}
		return append(results, num)
	}

	// look east and west first -- these are always seen once by the symbol
	result = addIfPresent(result, p.Add(ptEast))
	result = addIfPresent(result, p.Add(ptWest))

	num, directlyAbove := parts[p.Add(ptNorth)]
	if !directlyAbove {
		result = addIfPresent(result, p.Add(ptNorthEast))
		result = addIfPresent(result, p.Add(ptNorthWest))
	} else {
		result = append(result, num)
	}

	// same logic holds for south
	num, directlyBelow := parts[p.Add(ptSouth)]
	if !directlyBelow {
		result = addIfPresent(result, p.Add(ptSouthEast))
		result = addIfPresent(result, p.Add(ptSouthWest))
	} else {
		result = append(result, num)
	}

	return result
}

Part 2

Phew. Once we get through Part 1, Part 2 seems like it’d be way easier. The algorithm isn’t all that different from the first part, right?

1. Build space hashes to hold the part numbers and symbols.
2. Iterate over all the “gear” symbols. For each gear symbol, calculate the ratio
3. Return the sum of all ratios.

But, there’s one more Gotcha waiting for us.

Gotcha 3: Are You Sure You Know What a Gear Is?

You might think a gear is an asterisk symbol (*). But if your read the Advent of Code prompt carefully, you’ll find the following definition.

A gear is any * symbol that is adjacent to exactly two part numbers.

It turns out, there’s a ton of * symbols that don’t have exactly 2 part numbers. Whoops.

Here’s what the final solution looked like, using findPartNums() from Part 1. Note the use of continue – it keeps the happy path left-aligned and simplifies the code following it in the loop.

func part2(r io.Reader) int {
	symbols, parts := parseSpaces(r)

	acc := 0

	for p, symbol := range symbols {
		if symbol != '*' {
			continue
		}

		nums := findPartNums(p, parts)
		if len(nums) != 2 {
			continue
		}

		ratio := nums[0] * nums[1]
		acc += ratio
	}

	return acc
}

Takeaways

With Advent of Code, each puzzle can teach you lessons that will make other puzzles easier to work with.

• The sample input is useful (to a point). It’s not a bad idea to test your code with the sample input before moving on, but it doesn’t always include all valid cases.
• Data modeling is a great way to make the problem a lot easier. I probably could have worked with the string representation directly, but modeling the input as a set of points using a space hash made it much easier to reason thru my solution.
• Skectch things out! In order to solve the north/south problem, I literally used graph paper. Reach for pencil and paper without shame as you think through corner cases!
• Read the prompt. Then read it again. It was tempting to slam myself back into the code when I got hit with setbacks, but my breakthroughs came from reading the definitions of “part number” and “gear” very carefully.

My solution is available here on GitHub.

Vishal Kotcherlakota is a reformed sysadmin, who writes code and will talk incessantly about DevOps to anyone who will listen. All views expressed here are his and not those of his employers.