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:
calculate desired targed position
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)
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.
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.
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…
I then fire up GIMP and select the Filters → Animation → Optimize (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.
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.