When a puzzle starts out as “see, it’s a grid, and something can be in a cell or it can be empty, and cells can change depending on what’s around them” — I think John Conway’s “Game of Life”. There’s one of these, every year.
The rules were… shorter than expected. There was only one rule, namely that any cell that had fewer than four neighbors would die. Part 1 was to just iterate once; part 2 was to iterate until it reached a steady state, and the values in both were the total number of cells cleared.
The picture up top has, overlaid on it, a portion of the final state after part 2 completed. I thought it might form a recognizable shape or something, but it was just blobs. Was worth doing.
The thing about Conway’s Game of Life, even this alternate rules one, is that you’re not really interested in empty cells, and the less time you can spend with them, the better. After all, there’s an infinity of empty cells, and only a few set cells.
I guess it’s like the Monty Haul thought experiment. Given three doors, behind each of which is a prize. Two of the prizes are joke prizes, and one is really nice. You choose a door; the host opens one of the doors you didn’t choose to reveal a joke prize, then offers to let you change your guess. Do you? It’s hard to figure out.
But let’s say there are 1000 doors. You pick a door, and the host opens 998 doors with joke prizes behind them leaving just your door, and one other door. Do you change to that door? Sure. It’s always better to change your pick.
Game of Life is like that. It takes place on an infinite grid. If there’s as many empty spaces as filled spaces in the grid, do you model the whole grid? What if it’s just set in the middle of an infinity of empty cells stretching all directions? You ignore the empty ones.
When I encounter this sort of puzzle, that’s just what I do. I save the positions of the filled cells and never consider the empty ones. These filled cell position are stored in the paper_table table in the code above.
I had an interesting discussion with another AoC participant this morning on Mastodon about this puzzle. Mina thought people should avoid using tables/dictionaries/maps or what have you and just use arrays, as the random access nature of arrays made them superior to the more indirect addressing for maps. I pointed out that my language for this AoC, Lua, doesn’t have arrays; not real ones, anyway.
It made me think about my solution. I solved it just before I had to go to work, and was happy with my solution. I kept thinking about the discussion while at work. I can’t use arrays, that was a non-starter for Lua, but you can see in the code above that for each active cell, I look at all the neighbors to count the number of nearby active cells. This means looking at empty cells a lot. Perhaps I could just make a neighbors table and run through one pass to set up neighbor counts, then another pass to remove cells that don’t make the cut.
This was slower, and so I went with my original solution. It still isn’t fast enough to keep my kitty animating cleanly. I could add more yields, but I don’t care that much.
Four puzzles down, eight to go.
Leave a Reply