Day 25 - Moving fish

I've skipped a number of days, so I figured that I should take a punt at one of the more interesting ones.

In Day 25, we are modelling a number of fish, which can move either horizontally or vertically. They take turns, so we need to iterate through each of the fish one at a time, type by type, and move it to the new location.

We need to implement the algorithm correctly, we need to make each fish scan the space in front of them before we move them.

If we implement this this way, we are going to have to iterate over each list of animals twice. We can do this in a slightly more efficient way by building up a list of animals to move in the first pass, then only iterate through the animals that want to move.

We're going to build two main data structures therefore. We're going to have a pair of lookup tables, one that stores for each coordinate whether there is an animal in it. It's just a simple dictionary of coordinate->boolean. Secndly, we are going to have a pair of lists of east facing creates and a list of south facing creatures. Each creature in this list is a list of coordinates. When we look to move a creature, we look at the dictionary to see if the target location is filled. When we actually move, we're going to remoeve the old coordinates from the list, and add the new coordinates to teh list, as well as update the dictionary.

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

class Cucumbers:
    def __init__(self, lines):
        self.blocking = {}
        self.eastfacing = []
        self.southfacing = []
        self.height = len(lines)
        self.width = len(lines[0])
        for y,line in enumerate(lines):
            for x,char in enumerate(line):
                match char:
                    case ">":
                        self.blocking[(x,y)] = True
                        self.eastfacing.append((x,y))
                    case "v":
                        self.blocking[(x,y)] = True
                        self.southfacing.append((x,y))
        
test1 = Cucumbers("""...>>>>>...""".split("\n"))
assert test1.height == 1
assert test1.width == 11
assert test1.eastfacing == [(3,0),(4,0),(5,0),(6,0),(7,0)]
assert test1.southfacing == []
assert test1.blocking == {(3,0):True,(4,0):True,(5,0):True,(6,0):True,(7,0):True}

test2 = Cucumbers("""..........
.>v....v..
.......>..
..........""".split("\n"))
assert test2.height == 4
assert test2.width == 10
assert test2.eastfacing == [(1,1),(7,2)]
assert test2.southfacing == [(2,1),(7,1)]
assert test2.blocking == {(1,1):True,(2,1):True,(7,2):True,(7,1):True}

Ok, we can create a world with the data structures, so now we need to actually define a step command.

class Cucumbers:
    def __init__(self, lines):
        self.blocking = {}
        self.eastfacing = []
        self.southfacing = []
        self.height = len(lines)
        self.width = len(lines[0])
        for y,line in enumerate(lines):
            for x,char in enumerate(line):
                match char:
                    case ">":
                        self.blocking[(x,y)] = True
                        self.eastfacing.append((x,y))
                    case "v":
                        self.blocking[(x,y)] = True
                        self.southfacing.append((x,y))

    def step(self):
        hasmoved = False
        self.tomove = []
        for cumber in self.eastfacing:
            newx = (cumber[0]+1)%self.width
            newy = cumber[1]
            if not self.blocking.get((newx,newy), False):
                self.tomove.append(cumber)
        for cumber in self.tomove:
            hasmoved = True
            newx = (cumber[0]+1)%self.width
            newy = cumber[1]
            self.eastfacing.remove(cumber)
            self.eastfacing.append((newx,newy))
            self.blocking[cumber] = False
            self.blocking[(newx,newy)] = True
        self.tomove = []
        for cumber in self.southfacing:
            newx = cumber[0]
            newy = (cumber[1]+1)%self.height
            if not self.blocking.get((newx,newy), False):
                self.tomove.append(cumber)
        for cumber in self.tomove:
            hasmoved = True
            newx = cumber[0]
            newy = (cumber[1]+1)%self.height
            self.southfacing.remove(cumber)
            self.southfacing.append((newx,newy))
            self.blocking[cumber] = False
            self.blocking[(newx,newy)] = True
        return hasmoved

    def __str__(self):
        ss = []
        for y in range(self.height):
            s = ""
            for x in range(self.width):
                if (x,y) in self.eastfacing:
                    s += ">"
                elif (x,y) in self.southfacing:
                    s += "v"
                else:
                    s+= "."
            ss.append(s)
        return "\n".join(ss)


# Show that they move and are blocks
test1 = Cucumbers("""...>>>>>...""".split("\n"))
assert str(test1) == """...>>>>>..."""
assert True == test1.step()
assert str(test1) == """...>>>>.>.."""
assert True == test1.step()
assert str(test1) == """...>>>.>.>."""


# Handle south and east in seperate stages with blocking
test2 = Cucumbers("""..........
.>v....v..
.......>..
..........""".split("\n"))
assert str(test2) == """..........
.>v....v..
.......>..
.........."""
assert True == test2.step()
assert str(test2) == """..........
.>........
..v....v>.
.........."""

# Show that they can wrap
test3 = Cucumbers("""...>...
.......
......>
v.....>
......>
.......
..vvv..""".split("\n"))
assert True == test3.step()
assert """..vv>..
.......
>......
v.....>
>......
.......
....v..""" == str(test3)

# We can detect a stable configuration
test4 = Cucumbers("""..>>v>vv..
..v.>>vv..
..>>v>>vv.
..>>>>>vv.
v......>vv
v>v....>>v
vvv.....>>
>vv......>
.>v.vv.v..""".split("\n"))
assert False == test4.step()

Ok, we can step over each stage, lets check that we can count interations until it becomes stable

class Cucumbers:
    def __init__(self, lines):
        self.blocking = {}
        self.eastfacing = []
        self.southfacing = []
        self.height = len(lines)
        self.width = len(lines[0])
        for y,line in enumerate(lines):
            for x,char in enumerate(line):
                match char:
                    case ">":
                        self.blocking[(x,y)] = True
                        self.eastfacing.append((x,y))
                    case "v":
                        self.blocking[(x,y)] = True
                        self.southfacing.append((x,y))

    def step(self):
        hasmoved = False
        self.tomove = []
        for cumber in self.eastfacing:
            newx = (cumber[0]+1)%self.width
            newy = cumber[1]
            if not self.blocking.get((newx,newy), False):
                self.tomove.append(cumber)
        for cumber in self.tomove:
            hasmoved = True
            newx = (cumber[0]+1)%self.width
            newy = cumber[1]
            self.eastfacing.remove(cumber)
            self.eastfacing.append((newx,newy))
            self.blocking[cumber] = False
            self.blocking[(newx,newy)] = True
        self.tomove = []
        for cumber in self.southfacing:
            newx = cumber[0]
            newy = (cumber[1]+1)%self.height
            if not self.blocking.get((newx,newy), False):
                self.tomove.append(cumber)
        for cumber in self.tomove:
            hasmoved = True
            newx = cumber[0]
            newy = (cumber[1]+1)%self.height
            self.southfacing.remove(cumber)
            self.southfacing.append((newx,newy))
            self.blocking[cumber] = False
            self.blocking[(newx,newy)] = True
        return hasmoved

    def iterate(self):
        iterations = 0
        while self.step():
            iterations += 1
        return iterations+1

    def __str__(self):
        ss = []
        for y in range(self.height):
            s = ""
            for x in range(self.width):
                if (x,y) in self.eastfacing:
                    s += ">"
                elif (x,y) in self.southfacing:
                    s += "v"
                else:
                    s+= "."
            ss.append(s)
        return "\n".join(ss)

test1 = Cucumbers("""v...>>.vv>
.vv>>.vv..
>>.>v>...v
>>v>>.>.v.
v>v.vv.v..
>.>>..v...
.vv..>.>v.
v.v..>>v.v
....v..v.>""".split("\n"))
assert 58 == test1.iterate()

Ok, lets get the puzzle input in and try that

prod = Cucumbers([line.strip() for line in open("day25.txt").readlines()])
print(prod.iterate())
print(prod)

492 vv.>>vvvvvvvvvv.vv..v.vv........................................................................>>>>>>>>>>>>>>>>>>>>>>>>vv>>>vvv........>vv vv.>v>vvvvvvvvv.vv.vv.vv.v..............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>>>vvv.....>>>>v vv.>vv>vvvvvvvvvvv.vv.vv.v.v.................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>>>vvvv.....>>> >vv>vvvvvvvvvvvvvv.vv.vv.v.v......................................................................>>>>>>>>>>>>>>>>>>>>>>>>>vv>>>vvvv.....>> >>vv>vvvvvvvvvvvvv.vv.vvvv.vv..........................................................................>>>>>>>>>>>>>>>>>>>>>vv>>>vvvv.....> >>>vv>v>vvvvvvvvvv.vvvvvvv.vv..................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>>>>vvv....> .>>vvv>v>vvvvvvvvvvvvvvvvv.vv.................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>>>>vvv.... .>>vvvvvv>vvvvvvvvvvvvvvvv.vvv...........................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>>>>vvv... ..>>vvvvvv>vvvvvvvvvvvvvvv.vvv..........................................................................>>>>>>>>>>>>>>>>>>>>>>>>vv>>>>vvv.. ..>>>vvvvvvvvvvvvvvvvvvvvv.vvv........................................................................>>>>>>>>>>>>>>>>>>>>>>>>v>vvv..>>vvv. ...>>>vvvvvvvvvvvvvvvvvvvv.vvvvv................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>>>>vvv>>>>vvv v...>>>vvvvvvvvvvvvvvvvvvvvvvvvvv..................................................................>>>>>>>>>>>>>>>>>>>>>>>>vvv.>>>vvv>>>>vv vv...>>>vvv>vvvvvvvvvvvvvvvvvvvvv....................................................................>>>>>>>>>>>>>>>>>>>>>>vvv..>>>vvv>>>>v vv....>>>vvv>vvvvvvvvvvvvvvvvvvvv........................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv....>vvv>>>> >vv....>>>vvv>vvvvvvvvvvvvvvvvvvv.....................................................................>>>>>>>>>>>>>>>>>>>>>>>>v.v.>>>vvv>>> >>v.....>>>vvv>vvvvvvvvvvvvvvvvvv..................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvv...>vvvv. v.>vv....>>>vvv>vvvvvvvvvvvvvvvvvv.......................................................................>>>>>>>>>>>>>>>>>>>>>>>>vv...vvvvv vv.vv......>>vvv>vvvvvvvvvvvvvvvvv........................................................................>>>>>>>>>>>>>>>>>>>>>>>>vvv.>vvvv vv.vv>vv....>>vvv>vvvvvvvvvvvvvvvv.v..................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvv>vvv vv.>>>v>v....>vvvv>vvvvvvvvvvvvvvv.v...........................................................................>>>>>>>>>>>>>>>>>>>>>vvvv>vv vvv...>>>v...>vvvvvvvvvvvvvvvvvvvv.v......................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvv>v vvvv..>>>>v..v>vvvv>vvvvvvvvvvvvvv.vv..v...............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvv vvvvv....>vvv>v>vvvvvvvvvvvvvvvvvvvvv..vv..........................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvv >vvvvv...>>vv.>v>vvvvvvvvvvvvvvvvvvvvv.vv............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>vvvvv.v.>>vvv>v>vvvvvvvvvvvvvvvvvvvv.vv.v..v....................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>vvvvvv.vv>vvv>v>vvvvvvvvvvvvvvvvvvv.vv.v..v.......................................................................>>>>>>>>>>>>>>>>>>>>>> >>>>vvvvvvvvvvvvvvv>>vvvvvvvvvvvvvvvvv.vv.v..v...............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>vvv>>v>v>vvvvv.>>vvvvvvvvvvvvvvvv.vvvv..v...............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>vvv.vvvvvvvvvvv.>vvvvvvvvvvvvvvvvvvvv..v..v...........................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>vv.vv>v>vvvvvvv.vvvvvvvvvvvvvvvvvvvv..v..v.............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvvv..v..v....v.............................................................>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvv..vv.v..vvv....................................................................>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvv.vv.v..vvv....v.............................................................>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvv.vv.v.vvvv....v...............................................................>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>vv>v>vvv>vvvvvvvvvvvvvvvvvvvvvvvvv.vvvv....v.........................................................>>>>>>>>>>>>>>>>>>>>>>> >>v.>>>>>>>>>>>>vv>v>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...v.............................................................>>>>>>>>>>>>>>>>>>> >>>v..>>>>>>>>>>>vv>v>v>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...v.......................................................................>>>>>>>>> >>>>v...>>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvv..vv........................................................................>>>>>>>> >>>>>v..>>>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvv..vv.................................................................>>>>>>>>>>>>>>> >>>>>>v....>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvv..vv...................................................................>>>>>>>>>>>>> >>>>>>>v.....>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvv..vvv..................................................................>>>>>>>>>>>>> >>>>>>>>v.>>>>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv................................................................>>>>>>>>>>>>>>> >>>>>>>>>>v..>>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvv.v...................................................................>>>>>>>>>> >>>>>>>>>>>v..>>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvv.v........v........................................................>>>>>>>>>>>> >>>>>>>>>>>>v...>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvv.vv.......v........................................................>>>>>>>>>>>> >v>>>>>>>>>>>v..>>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvv.vv.......v........................................................>>>>>>>>>>>> >>v>>>>>>>>>>>v.....>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvv.vv.......v............................................................>>>>>>>> >>>v>>>>>>>>>>>v...>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvv.v.....v.v.................................................................> >>>>>>>>>>>>>>>>v>>>>>>>>>>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvv.....v.v.v..v..........................................................>>> >>>>>>>>>>>>>>>>>v.........>>>vv>v>>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvv....v.v.v..v........................................................>>>>> >>>>>>>>>>>>>>>>>>v......>>>>>>vv>v>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..vv.v.v..v.....................................................>>>>>>>> >>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vv>v>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvv.v.v..v..........................................................>>> >>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vvvv..>vvvvvvvvvvvvvvvvvvvvvvvvvvv.vvv.v.v..v............................................................. ........>>>>>>>>>>>>>v>>>>>>>>>>>>vvvv..>vvvvvvvvvvvvvvvvvvvvvvvvvv.vvv.v.v..v.....v...v................................................... >>>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vvvv..>vvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvv..v.....v...v.................................................>> .....>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vvvv..>vvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvv..v.....v...v......v............................................ ..>>>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvv..v.....v...v......v............................................ ...>>>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvv..v.v...v...v......v............................................ ......>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..v.v...v...v......vv........................................... ......>>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..v.v...v.v.v.vv...vv........................................... .........>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.v.v.vvvvvvv.vv...vvv.......................................... ......>>>>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvvv.vv...vvvvv........................................ ..........>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vv...vvvvv........................................ .....>>>>>>>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vv...vvvvv........................................ .........>>>>>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vv...vvvvv........................................ ................>>>>>>>>>>>>>>>>>vv>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvv........................................ ..............>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvvv....v.................................. ..................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvvvv...v.................................. ...................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvvvvv..v.................................. ............>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvvvvv..v.................................. ........................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvv>vvvvvvvvvvvvvvvvvvvvvv.vvvvvvvvv..v.................................. ...................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvvvvv..v.................................. .....................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvvvvvvvv..v..v............................... .....................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..v..v............................... .............................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..vv.v............................... ............................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..vv.v............................... ..............................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..vvvv............................... ...........................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv..vvvv............................... ................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv............................... ................................>>>>>>v...>>>>>>>>>>>>>>>>>>>>>vv>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv............................... .............................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv............................... ....................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv............................... ......................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv............................... ......................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>v>vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv............................... .................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>v>vvvvvvvvvv>vvvvvvvvvvvvvvvvvvvvv..v...v........................ ......................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vv>v>vvvvvvvvv.>vvvvvvvvvvvvvvvvvvvvv.v.v.v........................ .................................vvvvv.....>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vvvvvvvvvvvvvv.>vvvvvvvvvvvvvvvvvvvvvv.vvv........................ .................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>v>v>vvvvvvvvvv.>vvvvvvvvvvvvvvvvvvvvv.vvv....v................... ................................................>>>>>>>>>>>>>>>>>>>>>>>>vv>v>vvvvvvvvvvvv.vvvvvvvvvvvvvvvvvvvvv.vvv....v................... ..........................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>v>>vvv>vvvvvvvvvvvvvvvvvvvvvvvvvvvv.vvv.v..v................... .........................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>v>>>>>vvvvvvv>vvvvvvvvvvvvvvvvvvvv.vvv.vv.v................... ............................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vv>v>>>>>vvvvvv.vvvvvvvvvvvvvvvvvvvvvvvv.vv.v................... ..................................................>>>>>>>>>>>>>>>>>>>>>>>>>>vv>v>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvvvvvvvvv.v.....v............. .......................................................>>>>>>>>>>>>>>>>>>>>>>vv>v>>>>>vvvvv>>v>vvvvvvvvvvvvvvvvvvvvvvv.v.....v............. ......................................................>>>>>>>>>>>>>>>>>>>>>>>>vv>>>v>>>vvvvv>>v>>vvv>vvvvvvvvvvvvvvvvv.v.....v............. ...............................................................>>>>>>>>>>>>>>>>vv>>>v>>>vvvvv>>v>>vvv>vvvvvvvvvvvvvvvv.v.....v............. ..........................................................>>>>>>>>>>>>>>>>>>>>>>v>>v>v>>>vvvv.>>>>vvvv>vvvvvvvvvvvvvvvvvv....v............. .........................................................>>>>>>>>>>>>>>>>>>>>>>>>>>vv>v>>>vvv.>>>>vvvvv>vvvvvvvvvvvvvvvvvvv..v............. ...........................................................>>>>>>>>>>>>>>>>>>>>>>>>>vv>v>>>vv.>>>>vvvvvv>vvvvvvvvvvvvvvvvvv.vv...v......... ...............................................................>>>>>>>>>>>>>>>>>>>>>>vv>v>>>v.>>>>>vvvvvv>vvvvvvvvvvvvvvvvv.vv...v......... ..................................................................>>>>>>>>>>>>>>>>>>>>vv>v>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvv...v......... .................................................................>>>>>>>>>>>>>>>>>>>>>>vv>v>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvv..v......... ...................................................................>>>>>>>>>>>>>>>>>>>>>vv>v.>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvvvv......... ......................................................................>>>>>>>>>>>>>>>>>>>vv>v..>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvvv......... ......................................................................>>>>>>>>>>>>>>>>>>>>v.>>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvv......... ....................................................................>>>>>>>>>>>>>>>>>>>>>>>v.>>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvv..v..... ...............................................................>>>>>>>>>>>>>>>>>>>>>vvvv...>v.>>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvv..v..... .............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>v.>>>>v.>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvv..v..... .v...................................................................>>>>>>>>>>>>>>>>>>>>v.>>>>v.>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvv..v..... .v................................................................>>>>>>>>>>>>>>>>>>>>>>>>v.>>>>v..>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvv.vv.... .v................................................................>>>>>>>>>>>>>>>>>>>>>>>>>v.>>>>>v>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvv.... .v.........................................................................>>>>>>>>>>>>>>>>>v>>>>>>v.>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvvv.. .v................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvvvv.. .v...........................................................................>>>>>>>>>>>>>>>>>>>>>>v.........>>>>vvvvvv>vvvvvvvvvvvvvvvvv.. vv..v..................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>vvv..>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvvv.. vv..v.........................................................................>>>>>>>>>>>>>>>>>>>>>>v.>>>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvvv.. vv..v......v...............................................................>>>>>>>>>>>>>>>>>>>>>>>>>>v.>>>>>>>>>>>>>vvvvvv>vvvvvvvvvvvvvv.. vv..v......v................................................................>>>>>>>>>>>>>>>>>>>>>>>>vvv.......>>>>>>>vvvvvv>vvvvvvvvvvvvv.. vv..vv.....v....................................................................>>>>>>>>>>>>>>>>>>>>>>v.>>>>>>>>>>>>>>vvvvvv>vvvvvvvvvvvv.. vv..vv..v..v...................................................................>>>>>>>>>>>>>>>>>>>>>>>vv........>>>>>>>vvvvvv>vvvvvvvvvvv.. vv..vv..v..v.................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>v.v>>>>>>>>>>>>>>vvvvvv>vvvvvvvvvvv. vv..vvv.v..v...........................................................................>>>>>>>>>>>>>>>>v.vv..>>>>>>>>>>>>vvvvvv>vvvvvvvvvvv vvv.vvv.v..v.....................................................................>>>>>>>>>>>>>>>>>>>>>>v.vvvvv>>>>>>>>>>>>vvvvvv>vvvvvvvvvv vvv.vvv.v..v.................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvv>>v>>>>>>>>>>>>vvvvvv>vvvvvvvvv vvvvvvv.v..v..................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvvv...>>>>>>>>>vvvvvv>vvvvvvvv vvvvvvv.vv.v..........................................................................>>>>>>>>>>>>>>>>>>>>vvvvvvv.>>>>>>>>>>>vvvvvv>vvvvvvv vvvvvvvvvv.vv...v...................................................................>>>>>>>>>>>>>>>>>>>>>>>vv>>vvv>>>>>>>>>>>>vvvvvv>vvvvvv vvvvvvvvvvvvv...v.........................................................................>>>>>>>>>>>>>>>>>>vvvvvvv..>>>>>>>>>>vvvvvv>vvvvv vvvvvvvvvvvvv...v................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvvv....>>>>>>>>vvvvvv>vvvv vvvvvvvvvvvvv.v.v..................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvv.........>>vvvvvv>vvv vvvvvvvvvvvvv.v.v......................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvv..v.>>>>>>>vvvvvv>vv vvvvvvvvvvvvv.v.v.....................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvv.>v>>>>>>>>vvvvvv>v vvvvvvvvvvvvv.v.v...................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>>vvvvvv>vvv.>v.....>>>vvvvvv> >vvvvvvvvvvvvvv.v.............................................................................>>>>>>>>>>>>>>>>>>>>>vvv>vv..>v...>>>>>vvvvvv v>>vvvvvvvvvvvv.v.............................................................................>>>>>>>>>>>>>>>>>>>>>>>vv>vv..vv..>>>>>>vvvvv vv>>vvvvvvvvvvv.v...v.v.....................................................................>>>>>>>>>>>>>>>>>>>>>>>>>>vv>vvv>vv>>>>>>>>vvvv vv>>vvvvvvvvvvv.v...v.vv........................................................................>>>>>>>>>>>>>>>>>>>>>>>vv>vvvvvv......>>vvv

And that's it, the end of AoC 2021. I'm going to try to tackle some of the challanges I missed over the next month or so in slow time, but that was fun.

I note that this one took nearly a minute to find a stable place. We could probably speed up the step function by using some slightly better structures, list appending is quite slow for example. But it works, and that's plently sufficient for now.