Day 23: Unstable Diffusion

Another one that I thought was fun! The input proved helpful, and was not so different from the example today as it was yesterday. Then again, it would be hard to diverge as greatly from the example to the input as yesterday did…

My solution relies on one array to store the current map, one array to store the number of elves that propose to move to a particular location, and a probably-unnecessary vector used to store each elf’s location and proposed motion. Array size was determine by… uh, guessing and getting lucky, though I did have to increase the stack size to make it work on Linux. To determine the direction an elf considers, I exploited Ada’s excellent enumerated types: type Check_Direction is ( North, South, West, East ); and then Check_Direction'Val(Current_Round + Checks_Made - 1 rem 4) tells me which direction I’m checking.

Is there a way to determine how many variants an enumerated type has?

I have an idea for a visualization, and if I find time I’ll do it later.

Added later: Now that I review the discussion on Reddit, I notice that a lot of people missed something that I almost missed myself: If no other Elves are in one of those eight positions, the Elf does not do anything during this round. Yeah, watch out for that.

I used a Hash-Map with the coordinates as Key (easily hashable), and a pointer to a record representing the current and target location of the elf at that position.

moving the elves is a three step process:

  1. calculate desired targed position
  2. insert elf into a temporary Hash-Map at the target position, if not already occupied, else set target position to current position (both, the current and the already inserted elf)
  3. replace the Hash-Map with a new one where all elves are inserted at their target position (set a flag if it differs from the previous position, for part 2 - which I already implemented at the beginning)

part 2 was easy, I could use the result of part 1 and simply continue until no moves were made.

my Enum-Wrapping function for determining the next starting value is relatively simple:

   function Next (Dir : Direction) return Direction is
     (if Dir = Direction'Last then Direction'First else Direction'Succ (Dir));

You could get the My_Enum'Pos of the My_Enum'Last value, but be careful if you use a subtype of a different enum type. Also, the first value of an enum is at position 0.

1 Like

Blockquote You could get the My_Enum'Pos of the My_Enum'Last value, but be careful if you use a subtype of a different enum type. Also, the first value of an enum is at position 0.

That came in handy yesterday with the scoring for right, down, left, up being 0, 1, 2 and 3. I just used the 'Pos attribute to convert it to a number.

Due to the high Elf density on the playfield (even when they are about to stop moving), I went “Pacman style”: using the character matrix as only data storage.
Runs in 0.15 seconds with GNAT (.gpr file: AoC_Build_Mode_Type = “Fast”).

This one seemed like others in the past where it was on an unbounded grid, and I have always just put coordinates into some kind of map. In this case, I used a Formal_Ordered_Set of coordinates, and then a Formal_Ordered_Map keyed by coordinates to track how many times a coordinate was proposed. I was anticipating the second part going way out, it was surprising for it to be relatively contained.

A funny and unplanned consequence of doing all in the matrix: the algorithm’s steps can be visualized “as is”:

===== Round 1 =====
--- after cleanup
--- after half round 1
--- after half round 2

Not sure I follow what you’re saying; can you explain?

I have an animation of all 930 rounds of my part 2! but it’s about 3.6MB large, and I don’t feel comfortable uploading that here, so I’ll provide a link, but be careful if you have issues with rapidly flashing lights, as a lot of pixels flash on and off pretty quickly.

The really interesting thing is that there is a bias toward the southeast! The elves never spread farther than 12 or 15 to the north and west, but spread 40 to 45 to the south and east. I don’t know if that depends on one’s input, but I suspect it’s because an elf’s preferred first choices are north and west, so those are more likely to clash, counterintuitively discouraging motion in that direction…

1 Like

So you write out each round as a separate PPM file, right? What did you use to combine them into an animated GIF?

Correct! I use ImageMagick to convert them to an animated GIF. Today, for example:

convert -delay 4 "*.ppm" -sample 840x840 full_thing.gif

I then fire up GIMP and select the FiltersAnimationOptimize (for GIF) to try and get it to a manageable size. That last step worked really well at shrinking yesterday’s puzzle… not so much with today’s.

1 Like

My program hasn’t a list tracking the Elves position.
On each round, it scans the character map; when it finds an Elf (#) and that Elf finds a possible destination cell (.), it puts an ‘1’ there. If there was already an ‘1’, it will be a ‘2’, and so on.
On the second half round, same scan but only the moves to ‘1’ will happen.

1 Like