Advent of Code - Day 5

Alright. Today, we are going to learn something that will be useful to us in the coming days.

Let’s see what we are dealing with.

Edit: An interesting algorithm to read up on is Bresenham’s line algorithm.

Day 5 - Part 1

We deal with vents today. The sea is a dangerous place after all. Fortunately for us, these vents line up perfectly so Santa can dodge them easily. We get a bunch of coordinates which form lines basically. The wording is pretty weird, says one end and the other. But these are just begin and end coordinates in a 2D grid.

We see the example, and it’s a 2D grid with lines drawn over. Let’s list our rules.

lines with start x, y coordinates and end x, y coordinates
only consider vertical and horizontal lines
count the number of points where lines intersect

Now, this seems like a problem for which you can use a 2D matrix. A coordinate system. But what if I tell you that you don’t need that. Why? Let’s think about this problem for a little bit. What do you need? You need a way to track some points. You need a way to see if a point already occurred or not… Aka, was an intersection point of two or more lines. What could help you track if a certain point, a certain data, was already encountered or not? What could be something that could we could use to easily and quickly access a value using another value? Have a little think. Go on, I’ll wait.

Okay, here we go. It’s a map. Or a dict. Or an associative array. That’s right, that’s all we need. A map which can track if we encountered a point before. The map key is x, y together and the value is a simple count.

In Go, we use a struct for that like this:

type point struct {
    x, y int
}

And then our map is like this: seaFloor := make(map[point]int).

Alright let’s scan our input. We use our trusty Sscanf function again, because the input follows a nice format:

	for _, l := range split {
		var (
			x1, x2 int
			y1, y2 int
		)
		fmt.Sscanf(l, "%d,%d -> %d,%d", &x1, &y1, &x2, &y2)

		lines = append(lines, line{
			begin: point{x: x1, y: y1},
			end:   point{x: x2, y: y2},
		})
	}

Now, I know that we said, that a map is enough and you don’t need a 2D map. But how do we check horizontally and vertically then? Well, what is horizontal vertical? We check the sample.

0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2

Out of these, horizontal and vertical only mean that ONE OF THE COORDINATES EQUALS. And the other either increases or decreases.

Okay, so we track if we need to add or subtract 1 to a number. Because “drawing a line” is literally just increasing the coordinate. One of them at least.

for _, l := range lines {
    addx := 0
    addy := 0
    ...

So when do we increase x and when y? If one of them is greater or smaller than the other.


for _, l := range lines {
    addx := 0
    addy := 0
    if l.begin.x > l.end.x {
        addx = -1
    }
    if l.begin.x < l.end.x {
        addx = 1
    }

We do that with y as well. But… This will result in both x and y increasing at the same time if neither of them equal. That would be… diagonal! We ignore that. We could say at the begin, something like, if neither of them equal, continue.

For now I just skip if both addx and addy are not 0. Then comes our for loop. We have to “draw a line” from a starting point to and end point. So we just start adding the addN to the respective number until they match the end coordinate.

And once we have a new coordinate we save that in our map. And if the map already contains it, we just increase that by one. In Go, that’s easy, because things in the map have a default value. For int that’s 0. Which is perfect for us.

Our for loop looks like this:

		for startX != targetX || startY != targetY {
			seaFloor[point{x: startX, y: startY}]++

			startX += addX
			startY += addY
		}

Easy. Except I had a small bug here, where I forgot to add the last item as well.

		seaFloor[point{x: startX, y: startY}]++

Now, we are ready to count overlaps. Which will just be going through the map and doing a count++ in case a value in the map is greater than 1.

	overlaps := 0
	for _, v := range seaFloor {
		if v > 1 {
			overlaps++
		}
	}
	fmt.Println("overlaps: ", overlaps)

And done! That’s all. No need for a 2D map or tracking coordinates or walking around with nested for loops.

We run this on the test and our sample input and we got the right result!

Day 5 - Part 2

We check part 2 and guess what!! The only change is that we have to also run diagonally. What luck!?

I just remove the addx and addy check and we have part 2 done.

Conclusion

And that’s it! We are done for today. We learned that we don’t always need a matrix to solve problems with coordinates. We have to keep an open mind and find the right data to represent our problem. The right data will solve 50% of the puzzle.

The repository for all my solutions for AOC 2021 can be found here.

Thank you for reading!

Gergely.

Advent of Code - Day 5#

Day 5 - Part 1#

Day 5 - Part 2#

Conclusion#

Advent of Code - Day 5

Day 5 - Part 1

Day 5 - Part 2

Conclusion