Advent of Code 2021 – Day 25

Posted on by

The days between Christmas and the new year are always quiet. The weather has been miserable and I’m not feeling particularly inspired to carry on with a brick breaker game I started a couple of months ago, so I thought I’d have a go at the final Advent of Code puzzle for 2021.

The idea is to move two herds of sea cucumbers across a grid, and determine when they can no longer move. The rightwards moving herd “>” moves first. A sea cucumber can only move if there’s an empty space next to it (the grid wraps). The downwards moving herd “V” always moves second. If there are no legal moves the puzzle is completed.

A game on an 8×8 grid part way through – there are 9 changes in position between generation 4 and 5.

Here’s my code, written in Sharp S-BASIC on the MZ-700. There are a couple of refinements that aren’t called for in the puzzle as set. First, the grid can be specified as any size on line 180 (this code version shows 10×10) and the starting position is randomly generated (subroutine at line 290).

Lines 10 – 220

I’ve added two identical modulo functions to deal with the grid wrapping conditions – one for X and the other for Y. (lines 200-220). This means that rectangular and square grids work properly. The modulo function is only necessary as S-BASIC doesn’t have a native mod operator,

Lines 230-380

There’s a subroutine to print out the grid after each generation (lines 390-480) …

Lines 390 – 580

… but the bulk of the code is in the subroutine between lines 490 and 770. I apologise for lines 580 and 710 in particular as it’s spectacularly ugly to increment ‘for’ loop variables like that,

Lines 590 – 770

It occurs to me that there’s a much more efficient movement algortihm that I could implement. It would involve just a single array to represent the sea cucumber state and only consider the spaces on the grid. If the weather stays as poor as it is at the moment I shall have another play. It also occurs to me that some starting grids will never complete. I wonder if there’s a neat way of working out which ones?

The github repositiory with an .mzf emulator file for this program is here.

This puzzle iteration finished after 29 generations and 2m, 19s on a Sharp MZ-700.

Update 29/12/2021

There’s now a version 7 in my repository which implements the single array / only consider spaces method. On a 10×10 grid it saves around a second per generation.

Update 31/12/2021

I’ve created a version that will run on the RC2014. Happy New Year!