The First Insight
Sometimes when I'm stuck on a problem it's helpful to imagine it has already been solved. The focus changes to speculating on the solution rather than dwelling on the problem. I've seen this before, in myself as well as others, where simply knowing that a problem is solvable makes it much easier to solve.
The stumbling block for me was that I kept thinking of the problem as one of extending the cell triple by one more cell. I was stuck in a rut and couldn't get out. But if a solution did somehow exist...what would it look like? That freed up my mind to consider alternatives that I hadn't been open to before.
Why not arrange it as a square instead? The nice thing about this arrangement is each cell has exactly five outside neighbors. Aha! Now were on to something. In the original triple arrangement the cells on the edge have seven outside neighbors and the cell in the center has six. A square arrangement deals with fewer neighbors!
The symmetry of the new arrangement felt right. Imagine updating the cell. What happens when just one cell in the square changes? You have to update neighbor counts for the adjacent cells of which there are only three. What happened in the old format? If the cell is on the edge you have to update five neighbors (the center cell has two.)
This is getting better all the time! You could update all four cells at the same cost as the old method could update only three. The new format would mean touching far fewer cells! Cool!
This sounds great but how many bits do we need? Remember, we can still use the old trick of counting only the neighbors outside the cell cluster so the neighbor counts are still three bits.
E | ABCD | abcd | WWW | XXX | YYY | ZZZ E : edge ABCD : life/death status for the current generation abcd : life/death status for the next generation WWW : neighbor count for cell A XXX : neighbor count for cell B YYY : neighbor count for cell C ZZZ : neighbor count for cell D
That comes to 21 bits. We have to shave five bits off this to make it work.
It would be really great if I could make room for one more bit. I would like to have a bit to indicate the cell is 'visible'. Grids in the new life simulator will often be larger than the screen and it would be good to know that in advance and optimize away the case where it has to test the cell to see if it might be visible.
It seems a little crazy to be thinking about adding an extra bit when this format is already five bits too large but I'm feeling somewhat optimistic. I have the sense that I'm on the right track and the problems are now solvable. This breakthrough in my thinking is simply the result of changing my perspective on the problem.
Now....how do we get rid of five or six bits?