Day 11 - Flashes of inspiration

This is a problem around having a grid of octopuses that build up energy and flash. That's a fairly simple simulation, the tricky part is that when an octopus flashes it's light, it adds energy to all of its neighbours.

We're going to have to process the octopuses carefully to avoid infinite loops, and to make sure that we've caught all of them.

Luckily, this is problem is almost exactly the same as the problem from a few days ago, and a flood fill algorithm should manage most of it. What we need to be careful of in this case is that an octopus affects its neighbours, so a given octopus can be visited multiple times by the flood fill (which doesn't happen for our previous flood fill), but that it can only flash the once.

The way that I'm going to deal with this is the same flood fill algorithm that we used before, visit all the octopuses (octopi?) that have reached a flash threshold, and for each octopus, we'll add energy to the neighbours. If any have reached flash threshold, we'll add them to teh list. But critically, we won't reset those counters yet, we'll let them keep building up. This means that we should only visit each octopus to make it flash itself if it reached exactly 9, so when we get from 9 to 10, we add the energy but don't add it to the visit list.

So the algorithm will look like:

Start with a tovisit list that is all the octopuses that have 9 energy
Start with an empty  visited list
While theres an octopus in the tovisit list
  Make the octopus flash by adding it to visited list
  Go to each of the neighbours of the octopus adding 1 to their energy level
  If their energy level is now exactly 9, add them to the tovisit list
  Remove the octopus from the tovisit list
Now go through all octopuses that have a value 9 or greater, and set them to 0
return the list of octopuses that flashed

Lets give it a try

## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()

import collections
import IPython.display
Coord = collections.namedtuple("Coord", ["x", "y"])

class Grid:
    def __init__(self, width, height, cells):
        self.width = width
        self.height = height
        self.cells = cells

    def get_neighbours(self, coord):
        return [Coord(coord.x+d.x, coord.y+d.y) for d in [Coord(-1,-1), Coord(0, -1), Coord(1, -1), Coord(-1, 0), Coord(1, 0), Coord(-1, 1), Coord(0, 1), Coord(1, 1)] if Coord(coord.x+d.x, coord.y+d.y) in self.cells]

    def execute_step(self):
        tovisit = []
        visited = []
        for coord in self.cells:
            self.cells[coord] += 1
            if self.cells[coord] > 9:
                tovisit.append(coord)
        while tovisit:
            coord = tovisit.pop()
            visited.append(coord)
            for neighbour in self.get_neighbours(coord):
                self.cells[neighbour] += 1
                if self.cells[neighbour] == 10:
                    tovisit.append(neighbour)
        for coord in visited:
            self.cells[coord] = 0

        return visited
            
    def display(self, flashes=[]):
        for y in range(self.height):
            s = ""
            for x in range(self.width):
                if Coord(x,y) in flashes:
                    s += f" **{self.cells[Coord(x,y)]}** "
                else:
                    s += f" {self.cells[Coord(x,y)]} "
            IPython.display.display(IPython.display.Markdown(s))
        IPython.display.display("")   



def parse_input(lines):
    cells = {}
    width = len(lines[0])
    height = len(lines)
    for y, line in enumerate(lines):
        for x, octopus in enumerate(line):
            cells[Coord(x,y)] = int(octopus)
    return Grid(width, height, cells)

octopuses = parse_input("""11111
19991
19191
19991
11111""".split("\n"))

octopuses.display()
assert 1 == octopuses.cells[Coord(0,0)]
assert 9 == octopuses.cells[Coord(1,1)]
assert 1 == octopuses.cells[Coord(2,2)]
assert 1 == octopuses.cells[Coord(4,4)]

assert [Coord(1,0), Coord(0,1), Coord(1,1)] == octopuses.get_neighbours(Coord(0,0))


flashes = octopuses.execute_step()
octopuses.display(flashes)
assert 3 == octopuses.cells[Coord(0,0)]
assert 0 == octopuses.cells[Coord(1,1)]
assert 0 == octopuses.cells[Coord(2,2)]
assert 4 == octopuses.cells[Coord(1,0)]
assert 5 == octopuses.cells[Coord(2,0)]
assert 9 == len(flashes)

flashes = octopuses.execute_step()
octopuses.display(flashes)
assert 4 == octopuses.cells[Coord(0,0)]
assert 1 == octopuses.cells[Coord(1,1)]
assert 1 == octopuses.cells[Coord(2,2)]
assert 5 == octopuses.cells[Coord(1,0)]
assert 6 == octopuses.cells[Coord(2,0)]
assert 0 == len(flashes)

1 1 1 1 1

1 9 9 9 1

1 9 1 9 1

1 9 9 9 1

1 1 1 1 1

''

3 4 5 4 3

4 0 0 0 4

5 0 0 0 5

4 0 0 0 4

3 4 5 4 3

''

4 5 6 5 4

5 1 1 1 5

6 1 1 1 6

5 1 1 1 5

4 5 6 5 4

''

Cool, that works on the simple input, lets try it on the test input

octopuses = parse_input("""5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526""".split("\n"))

count = 0
for x in range(10):
    flashes = octopuses.execute_step()
    count += len(flashes)
assert 204 == count
for x in range(90):
    flashes = octopuses.execute_step()
    count += len(flashes)
assert 1656 == count

That worked, and somewhat to my surprise, I didn't get the numbers wrong in those range arguments. I was expecting at least 1 off by one error!

Onto production input

octopuses = parse_input([line.strip() for line in open("day11.txt").readlines()])
count = 0
for x in range(100):
    flashes = octopuses.execute_step()
    count += len(flashes)
print(count)

1785

Ok, onto part 2.

I think the easiest way to do this, via brute force, is to keep looping the execute step until we get a flashes that returns us the length of the input, 100.

octopuses = parse_input("""5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526""".split("\n"))

steps = 0
while True:
    steps += 1
    flashes = octopuses.execute_step()
    if len(flashes) == 100:
        break
assert 195 == steps

Ok, lets try that on prod data

octopuses = parse_input([line.strip() for line in open("day11.txt").readlines()])
steps = 0
while True:
    steps += 1
    flashes = octopuses.execute_step()
    if len(flashes) == 100:
        break
print(steps)

354