Advent Of Code - Day 11

Today was an easier one again. It’s been a while since I last did some recursion anyway. At least, that’s how I solved this. I’m pretty sure my solution isn’t the most efficient one, but at least it’s working and it’s not horrible.

Day 11 - Part 1

We have some number tracking to do again. This time, instead of fishes, we find ourself an bioluminescent octopus! This time, the rules are neatly outlined to us in a straight forward list. It sort of is like a Conway’s Game of Life scenario in which the current point affects its neighbours.

Remember last time we did directions? Well guess what’s coming to come in handy again. Our directions, but with diagonal directions.

var (
	directions = []point{
		{x: 0, y: -1},
		{x: -1, y: -1},
		{x: -1, y: 0},
		{x: 1, y: 1},
		{x: 0, y: 1},
		{x: -1, y: 1},
		{x: 1, y: 0},
		{x: 1, y: -1},
	}
)

What the plan here? I’ve drawn it our on paper. It’s pretty easy actually. We have to track if an octopus already flashed or not. For that, we’ll use a struct which will hold something like flashed bool value. We’ll have to think about how to reset that after a step is done though.

Next step is, go through the list and if they didn’t flash in that round ( aka !flashed ) then we increase its energy. If the energy is above 9 ( aka. == 10 ), we flash. What is flash? It’s a recursive function. When dealing with recursive functions you have to determine two things.

What is my exit criteria?
What is my base case? ( aka. the recurring logic )

What is our exit? When there are no more neighbours. What is our base case? Find all neighbours for a given point which did not flash yet and increase their energy. If they are energy reaches 10, flash. That’s where our recurring call will happen. If a neighbour reaches energy level 10 we’ll call flash with that neighbour’s coordinate.

Alright, that isn’t so bad. Did we forget something? Yes… The reset. Unfortunately, this also means that those which did flash, we’ll have to manually go and reset after everything has been done. If we reset them mid logic, then they might flash again, or might get their energy levels increased. Which is not what we want. Ah well.. I’ll figure something out later maybe.

Okay, let’s see some code. Our initial thing is to loop through the steps and increase the energy level.

	for i := 0; i < steps; i++ {
		for y := 0; y < len(grid); y++ {
			for x := 0; x < len(grid[y]); x++ {
				if !grid[y][x].flashed {
					grid[y][x].energy++
					if grid[y][x].energy == 10 {
						flash(point{x: x, y: y}, i, grid)
					}
				}
			}
		}
		// reset flashed
        // unfortunate extra loop...
		for y := 0; y < len(grid); y++ {
			for x := 0; x < len(grid[y]); x++ {
				if grid[y][x].flashed {
					grid[y][x].flashed = false
				}
			}
		}
	}

Now, flash…

func flash(currentPoint point, currentStep int, grid [10][10]*octopus) {
	// flash the current octopus
	flashCount++
	grid[currentPoint.y][currentPoint.x].energy = 0
	grid[currentPoint.y][currentPoint.x].flashed = true
	// select neighbors and increase their energy
	for _, d := range directions {
		np := point{x: currentPoint.x + d.x, y: currentPoint.y + d.y}
		if np.x >= 0 && np.x < len(grid[currentPoint.y]) && np.y >= 0 && np.y < len(grid) {
			if !grid[np.y][np.x].flashed {
				grid[np.y][np.x].energy++
				if grid[np.y][np.x].energy == 10 {
					flash(np, currentStep, grid)
				}
			}
		}
	}
}

So, what’s going on in here? Once an octopus flashes, we set its energy to 0 and we set flashed to true. This is important, because otherwise it would flash again in the same step. Which is not allowed. Then, we check its neighbors and increase their energy. And if that reaches 10, we flash… And that’s it! We do some counting to get how many times we flashed and done!

Day 10 - Part 2

Part 2 is just let it run and see when every one of these is 0. Pretty simple, I didn’t have to change much, just remove the counter for the for loop and add in a check in our reset loop which was already there anyways.

		allZeros := true
		for y := 0; y < len(grid); y++ {
			for x := 0; x < len(grid[y]); x++ {
				if grid[y][x].flashed {
					grid[y][x].flashed = false
				}
				if grid[y][x].energy != 0 {
					allZeros = false
				}
			}
		}
		if allZeros {
			// +1 because steps begin from 0.
			fmt.Println("sync achieved at: ", i+1)
			display(grid)
			break
		}

And with that, part 2 is done!

Conclusion

Today we had a little fun with recursion. Which is nice, because I didn’t had to write recursion in a while.

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

Thank you for reading!

Gergely.

Advent Of Code - Day 11#

Day 11 - Part 1#

Day 10 - Part 2#

Conclusion#

Advent Of Code - Day 11

Day 11 - Part 1

Day 10 - Part 2

Conclusion