3 ms·

Here's my solution: http://pastebin.com/f75a9ee http://pastebin.com/f75a9ee Usage: run and click on the window to get next generation I used Jython with a Swi

by jules 17y ago

Here's my solution: http://pastebin.com/f75a9ee http://pastebin.com/f75a9ee Usage: run and click on the window to get next generation I used Jython with a Swing GUI. It took me about 1.5 hours in total half of which was spent getting the GUI right :S (I never used Swing before). The algorithm itself was fairly straightforward. It was buggy and gliders didn't work and I tried fixing the state management in the cells but in the end the bug turned out to be in the update rule of the game of life. I had "cell is alive in the next generation if it has 2 or 3 live neighbors". That should be "a cell is alive if (it is ALIVE and has 2 or 3 neighbors) OR (it is dead and has 3 neighbors)". I don't know if it's correct now, I only tested a glider. Features: - the world is created on the fly - dead cells are removed from the world, so gliders run in O(1) space - GUI :)

jacquesm 17y ago
Neat ! A good test for 'correctness' is to run the F-pentomino both in some known good program and your own. It looks like this: xx xx x I's a really interesting little pattern that will expand quite a bit before stabilizing, it also fires off a bunch of gliders. edit: I've looked a bit more at your code, and it is almost correct for free-running instances of 'cell'. The problem is with the generation counter, you only have 1 bit for the generation. In a synchronous environment that would work, and because you propagate the 'update' signal from the first cell that is hit outward you will (probably) observe correct behaviour. But that is not the same as having cells completely independent. The connecting cells are all triggered from the first cell that gets hit. If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong. I figure the absolute minimum number of bits in the generation counter is 2, because then you have one 'dead' state in between the 3 possibilities that are current. A neighbour can be 'ahead', at the same generation or it can be 'behind' and what a cell does should be governed by the states of the neighbours. In your program you can never get in to the 'behind' state, but in a free-running hardware solution that is a definite possibility. I hope that's all clear :) Think of it this way, effectively you've made your cells globally clocked again. You also can't delete dead cells, two populations that were connected at some point in the past should stay connected or they will drift away from each other. If a 'cell' is run by a completely independent thread which runs at some arbitrary speed the whole thing should still work. Simulating asynchronous devices on synchronous devices is quite tricky!
- jules 17y ago
  > If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong. Say we have two cells next to each other. It would go wrong if one cell is triggered twice in a row without the other cell being triggered in the meantime. So I think I didn't understand the goal. So the goal is to have the system still behave correctly with any sequence op c.update() calls? E.g. if I choose do do cells[(0,0)].update() 10 times in a row it should still work. Here's the updated version: http://pastebin.com/f72c576d3 http://pastebin.com/f72c576d3 This fix took 5 minutes. I actually used a gen counter and self.state[self.gen%2] before, so changing that to %3 wasn't much work :) The other change was: if any(cells[n].gen < self.gen for n in neighbors if n in cells): return And I removed the code do delete empty cells. I thought about removing empty cells and obviously you can remove them in some cases. But in general it's undecidable I think because life is turing complete and you don't know if some group of cells is going to shoot a glider to another group, so to be safe you have to keep them in sync. Is this version correct now? I'm not sure...it seems to execute the examples correctly but maybe it will go wrong if you call update in just the right pattern. BTW does the code run on your computer?
  - jacquesm 17y ago
    That looks better like that. I can't get it to work though, because of the swing stuff. I tried running it under jython but that gives me a syntax error, and in regular python the I get an import error. ('No module named javax'). I can't verify if it is correct without being able to run it, but you can try that F pentomino and then use 'hashlife' or 'golly' to verify that it works properly. The F pentomino is complex enough in its output that I think that if it does that it will work on arbitrary patterns. As for deletions, since this is only a simulation it is an optimization, in an actual fabric you would not be deleting cells. The trick to deletions I think is that you can only delete a cell if the neighbours around it are not going to be disconnected by the deletion. Now you have a problem though, which needs supervision or abtration. This is because if two cells delete themselves at the same time that could cause two populations to become disconnected. That's exactly the kind of issue I tried to resolve by scheduling the instructions so carefully. So, I'm curious if it really works for more complex structures. All you'd need to do is change the default set and let it run for 1116 generations , then it should be stable. Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.

by jules 17y ago

jacquesm 17y ago

Neat ! A good test for 'correctness' is to run the F-pentomino both in some known good program and your own. It looks like this: xx xx x I's a really interesting little pattern that will expand quite a bit before stabilizing, it also fires off a bunch of gliders. edit: I've looked a bit more at your code, and it is almost correct for free-running instances of 'cell'. The problem is with the generation counter, you only have 1 bit for the generation. In a synchronous environment that would work, and because you propagate the 'update' signal from the first cell that is hit outward you will (probably) observe correct behaviour. But that is not the same as having cells completely independent. The connecting cells are all triggered from the first cell that gets hit. If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong. I figure the absolute minimum number of bits in the generation counter is 2, because then you have one 'dead' state in between the 3 possibilities that are current. A neighbour can be 'ahead', at the same generation or it can be 'behind' and what a cell does should be governed by the states of the neighbours. In your program you can never get in to the 'behind' state, but in a free-running hardware solution that is a definite possibility. I hope that's all clear :) Think of it this way, effectively you've made your cells globally clocked again. You also can't delete dead cells, two populations that were connected at some point in the past should stay connected or they will drift away from each other. If a 'cell' is run by a completely independent thread which runs at some arbitrary speed the whole thing should still work. Simulating asynchronous devices on synchronous devices is quite tricky!

jules 17y ago
> If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong. Say we have two cells next to each other. It would go wrong if one cell is triggered twice in a row without the other cell being triggered in the meantime. So I think I didn't understand the goal. So the goal is to have the system still behave correctly with any sequence op c.update() calls? E.g. if I choose do do cells[(0,0)].update() 10 times in a row it should still work. Here's the updated version: http://pastebin.com/f72c576d3 http://pastebin.com/f72c576d3 This fix took 5 minutes. I actually used a gen counter and self.state[self.gen%2] before, so changing that to %3 wasn't much work :) The other change was: if any(cells[n].gen < self.gen for n in neighbors if n in cells): return And I removed the code do delete empty cells. I thought about removing empty cells and obviously you can remove them in some cases. But in general it's undecidable I think because life is turing complete and you don't know if some group of cells is going to shoot a glider to another group, so to be safe you have to keep them in sync. Is this version correct now? I'm not sure...it seems to execute the examples correctly but maybe it will go wrong if you call update in just the right pattern. BTW does the code run on your computer?
- jacquesm 17y ago
  That looks better like that. I can't get it to work though, because of the swing stuff. I tried running it under jython but that gives me a syntax error, and in regular python the I get an import error. ('No module named javax'). I can't verify if it is correct without being able to run it, but you can try that F pentomino and then use 'hashlife' or 'golly' to verify that it works properly. The F pentomino is complex enough in its output that I think that if it does that it will work on arbitrary patterns. As for deletions, since this is only a simulation it is an optimization, in an actual fabric you would not be deleting cells. The trick to deletions I think is that you can only delete a cell if the neighbours around it are not going to be disconnected by the deletion. Now you have a problem though, which needs supervision or abtration. This is because if two cells delete themselves at the same time that could cause two populations to become disconnected. That's exactly the kind of issue I tried to resolve by scheduling the instructions so carefully. So, I'm curious if it really works for more complex structures. All you'd need to do is change the default set and let it run for 1116 generations , then it should be stable. Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.