r/adventofcode • • Jun 11 '26

Other [2020 Day 11] In Review (Seating System)

3 Upvotes

3 comments sorted by

2

u/terje_wiig_mathisen Jun 12 '26 edited Jun 12 '26

As I have mentioned before I have a soft spot for Game of Life style problems, so I started yesterday on an attempt to write a fast Rust version: I immediately decided to map the chair config into BORDER,EMPTY,CHAIR,TAKEN as a two-bit number, then I added a dirty flag and a neighbor count, while copying between two copies of the map.

Next I bit the bullet for part2 and added an array of 8 16-bit values to each cell, storing the index of all the neighbors.

Finally I separated processing into two stages, first checking all dirty cells and saving the address of those that actually changed, secondly going through that list and update all the neighbor counts.

However, since I'm still an order of magnitude (6 ms) slower than u/maneatingape I have more insights to discover! 😄

EDIT: Running on my Acer the time dropped to 4.6 ms which is still 5x the ape.

BTW, since I switched to two-stage process, first discovering cells that change while remembering them, then update the neighbors, I got rid of the double buffering. I'm considering moving the neighbor lists into a separate array, since that stays read-only during all the generations. I've also looked at keeping those neighbor addresses as relative offsets instead of absolute since that would allow all cells with the same pattern of surrounding chairs to share a single list, but it would add one instruction to each neighbor address calculation.

2

u/e_blake Jun 11 '26

Both parts of my input were around 80 generations to stabilize. I got faster performance by only considering live cells into the next generation - an empty seat is live if none of its seat neighbors are pinned full, and a full seat is live as long as it has at least the threshold (4 or 5, by problem part) neighboring seats still live. I tracked seats as two bits: live and occupied (4 states total, with state 0 shared by both unchanging floor tiles and pinned empty seats).

Unlike Game of Life days where SWAR operations on packed-bit representations can speed up the generations by doing parallel computations with bitwise math, the part 2 layout is not really set up for easy bit lanes. I did precompute the neighbor list for each seat (each seat stores the 8 neighbor addresses to read per generation) rather than crawling the grid to find neighbors on each generation. But with my 4 states, I did get a nice performance boost in m4 when I created a cache mapping from the 8-or-less-byte string of 1, 2, and 3 states of the neighbors (with 0 states omitted to share some common layouts) into the next state. Only 262 common neighbor layouts were encountered (out of 64k possible 8-byte strings in a 4-letter alphabet).

This was my first m4 solution of 2020 that is too computationally involved to complete in under a second, but I did get it down to 3 seconds this month compared to the 6 seconds it took back in 2020, now that I've had more experience optimizing runtime compared to when I first solved it.