Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

No Part 2

Advent of Code 2021 - Day 25

Day 25: Sea Cucumber

Useful Links

Concepts and Packages Demonstrated

matplotlibimageio

VisualisationanimationtqdmProgress bar

Problem Intro

OMG! It’s Christmas day.

It was a relief that this problem was easy to solve. I’ve got presents to open!! I say easy… Not completely trivial, and there is at least one gotcha.

Overview

We need to land our sub on the seafloor. But the seafloor is covered in sea cucumbers. Specifically, there are two herds of cucumbers:

Our input data is map of the starting locations of these migrating sea cucumbers. E.g.

v...>>.vv>
.vv>>.vv..
>>.>v>...v
>>v>>.>.v.
v>v.vv.v..
>.>>..v...
.vv..>.>v.
v.v..>>v.v
....v..v.>

The grid uses . to denote empty spaces.

The migration rules:

Part 1

What is the first step on which no sea cucumbers move?

The cucumbers will stop moving when they’re all blocked.

I’ll create a Grid class, that represents all the sea cucumber locations, and can simulate their movement with each step:

class Grid():
    """ Store locations of sea cucumbers. """
   
    def __init__(self, data: list[str]) -> None:
        """ Take input data and convert from list-of-str to list-of-list for easier manipulation. """
        self._grid = [list(row) for row in data]    # Now a nested list of list.
        self._row_len = len(self._grid[0])
        self._grid_len = len(self._grid)
        self._changed_last_cycle = True
    
    @property
    def changed_last_cycle(self):
        return self._changed_last_cycle

    def cycle(self):
        """ Performs a migration cycle for our east-moving and south-moving herds 
        Performs all east, and then performs all south. Then updates the grid. """
        self._changed_last_cycle = False
        
        # Make a copy of the grid.  Shallow copy won't work, as we have a nested list. Deepcopy is too slow.
        tmp_grid = [[self._grid[y][x] for x in range(self._row_len)] for y in range(self._grid_len)]
        
        # process east herd, row by row
        for y in range(self._grid_len):
            for x in range(self._row_len):
                next_x = (x+1)%self._row_len  # get right / wrap-around
                if self._grid[y][x] + self._grid[y][next_x] == ">.":
                    tmp_grid[y][x] = "."
                    tmp_grid[y][next_x] = ">"
                    self._changed_last_cycle = True
        
        self._grid = tmp_grid
        
        east_migrated = [[tmp_grid[y][x] for x in range(self._row_len)] for y in range(self._grid_len)]
                
        for y in range(self._grid_len):
            for x in range(self._row_len):
                next_y = (y+1)%self._grid_len  # get below / wrap-around
                if tmp_grid[y][x] + tmp_grid[next_y][x] == "v.":
                    east_migrated[y][x] = "."
                    east_migrated[next_y][x] = "v"
                    self._changed_last_cycle = True
        
        self._grid = east_migrated
        
    def __repr__(self) -> str:
        return "\n".join("".join(char for char in row) for row in self._grid)

This is how it works:

Now we just need to read in the data, construct a Grid class from it, then cycle our Grid until there are no more changes:

with open(INPUT_FILE, mode="rt") as f:
    data = f.read().splitlines()

grid = Grid(data)

i = 0
while grid.changed_last_cycle:
    i += 1
    grid.cycle()

logger.info("We've stopped migrating at iteration %d", i)

It works!! Hurrah!

22:57:03.946:DEBUG:__main__:    Created Grid
22:57:06.336:INFO:__main__:     We've stopped migrating at iteration 360
22:57:06.336:INFO:__main__:     Execution time: 2.3969 seconds

Part 2

There’s nothing to do. Turns out we’ve saved Christmas!!

Woop, woop!!

Visualisation

It would be great to build an animation to visualise our migrating sea cucumber herds. Here’s my strategy for building the animation:

Here’s our modified Grid class:

class Grid():
    """ Store locations of sea cucumbers. """
   
    def __init__(self, data: list[str], animator: Animator=None) -> None:
        """ Take input data and convert from list-of-str to list-of-list for easier manipulation. """
        init_str = "Created Grid"
        if animator:
            init_str += " with Animator"
        logger.debug(init_str)
        
        self._grid = [list(row) for row in data]    # Now a nested list of list.
        self._row_len = len(self._grid[0])
        self._grid_len = len(self._grid)
        self._changed_last_cycle = True
        
        self._animator = animator
        self._plot_info = self.setup_fig()  # does no work if no Animator
        self._render_frame()
    
    @property
    def changed_last_cycle(self):
        return self._changed_last_cycle

    def cycle(self):
        """ Performs a migration cycle for our east-moving and south-moving herds 
        Performs all east, and then performs all south. Then updates the grid. """
        self._changed_last_cycle = False
        
        # Make a copy of the grid.  Shallow copy won't work, as we have a nested list. Deepcopy is too slow.
        tmp_grid = [[self._grid[y][x] for x in range(self._row_len)] for y in range(self._grid_len)]
        
        # process east herd, row by row
        for y in range(self._grid_len):
            for x in range(self._row_len):
                next_x = (x+1)%self._row_len  # get right / wrap-around
                if self._grid[y][x] + self._grid[y][next_x] == ">.":
                    tmp_grid[y][x] = "."
                    tmp_grid[y][next_x] = ">"
                    self._changed_last_cycle = True
        
        self._grid = tmp_grid
        self._render_frame()
        
        east_migrated = [[tmp_grid[y][x] for x in range(self._row_len)] for y in range(self._grid_len)]
                
        for y in range(self._grid_len):
            for x in range(self._row_len):
                next_y = (y+1)%self._grid_len  # get below / wrap-around
                if tmp_grid[y][x] + tmp_grid[next_y][x] == "v.":
                    east_migrated[y][x] = "."
                    east_migrated[next_y][x] = "v"
                    self._changed_last_cycle = True
        
        self._grid = east_migrated
        self._render_frame()
        
    def __repr__(self) -> str:
        return "\n".join("".join(char for char in row) for row in self._grid)
    
    def _render_frame(self):
        """ Only renders an animation frame if we've attached an Animator """
        if not self._animator:
            return
        
        east = set()
        south = set()
        
        for y in range(self._grid_len):
            for x in range(self._row_len):
                if self._grid[y][x] == ">":
                    east.add((x,y))
                elif self._grid[y][x] == "v":
                    south.add((x,y))
        
        east_x, east_y = zip(*east)
        south_x, south_y = zip(*south)
        
        axes, mkr_size = self._plot_info
        
        axes.clear()
        min_x, max_x = -0.5, self._row_len - 0.5
        min_y, max_y = -0.5, self._grid_len - 0.5
        axes.set_xlim(min_x, max_x)
        axes.set_ylim(max_y, min_y)
        
        axes.scatter(east_x, east_y, marker=">", s=mkr_size, color="black")
        axes.scatter(south_x, south_y, marker="v", s=mkr_size, color="white")
        
        # save the plot as a frame; store the frame in-memory, using a BytesIO buffer
        frame = BytesIO()
        plt.savefig(frame, format='png') # save to memory, rather than file
        self._animator.add_frame(frame)

    def setup_fig(self):
        if not self._animator:
            return
        
        my_dpi = 120
        fig, axes = plt.subplots(figsize=(1024/my_dpi, 768/my_dpi), dpi=my_dpi, facecolor="black") # set size in pixels
        axes.get_xaxis().set_visible(False)
        axes.get_yaxis().set_visible(False)
        axes.set_aspect('equal') # set x and y to equal aspect
        axes.set_facecolor('xkcd:orange')
        
        min_x, max_x = -0.5, self._row_len - 0.5
        min_y, max_y = -0.5, self._grid_len - 0.5
        axes.set_xlim(min_x, max_x)
        axes.set_ylim(max_y, min_y)

        # dynamically compute the marker size
        fig.canvas.draw()
        mkr_size = ((axes.get_window_extent().width / (max_x-min_x) * (45/fig.dpi)) ** 2)
        return axes, mkr_size

Then I created an Animator class, to do the job of storing our frames, and then stiching them together as an animation gif:

class Animator():
    """ Creates an animation file of specified target size. """
    
    def __init__(self, file: Path, fps: int, loop=1) -> None:
        """ Create an Animator. Suggest the file should be a .gif.
        Set frames per second (fps). 
        Set loop to 0, to loop indefinitely. Default is 1. """
        self._outputfile = file
        self._frames = []  # can be in-memory BytesIO objects, or files
        self._fps = fps
        self._loop = loop
        
        dir_path = Path(self._outputfile).parent
        if not Path.exists(dir_path):
            Path.mkdir(dir_path)
    
    def save_anim(self):
        """ Takes animation frames, and converts to a single animated file. """
        logger.debug("Saving animation...")
        with imageio.get_writer(self._outputfile, mode='I', fps=self._fps, loop=self._loop) as writer:
            for frame in tqdm(self._frames):
                image = imageio.imread(frame)
                writer.append_data(image)
                
        logger.info("Animation saved to %s", self._outputfile)
    
    def add_frame(self, frame):
        """ Add a frame to the animation.
        The frame can be in the form of a BytesIO object, or a file Path
        """
        self._frames.append(frame)

Some things to note about this class:

And here’s what these animations look like:

Sample Data

Sample Migrating Sea Cucumbers Animation

Actual Data

Migrating Sea Cucumbers Animation

And We’re Done!

Well, that was a touch AoC. Tougher than any I’ve done before.

I hope you found these walkthroughs useful. I’ve really enjoyed creating them.

If you want to get in touch, e.g. to offer any feedback, find me through my GitHub Profile.