Timeline for The 1-step vanishing polyplets on Conway's game of life
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2018 at 23:46 | comment | added | Sebastien Palcoux | @EpsilonNeighborhoodWatch: Very nice! Feel free to extend the classification beyond $n=12$ if you want. | |
| Jan 8, 2018 at 23:10 | comment | added | Ilmari Karonen | @SebastienPalcoux: True, connectedness is a global property. But if you're generating the pattern e.g. row by row, it should be possible to keep track of the connected components of each partial pattern and to prune any extension that either a) closes off a component so that it cannot be connected to the rest of the pattern, or b) has two separate components so far apart that connecting them would require exceeding the $n$ cell limit. I'd expect the time savings from restricting the search space to be worthwhile, even with the extra cost of tracking the connected components. | |
| Jan 8, 2018 at 23:04 | comment | added | Atsma Nayem | @SebastienPalcoux After a rewrite and some more computation time I have completed the classification of $n \leq 12$. | |
| Jan 8, 2018 at 23:02 | history | edited | Atsma Nayem | CC BY-SA 3.0 |
added 2484 characters in body
|
| Jan 8, 2018 at 22:36 | comment | added | Sebastien Palcoux | @IlmariKaronen: see this comment of David Eppstein. | |
| Jan 4, 2018 at 15:55 | comment | added | Ilmari Karonen | It should be pretty efficient, if you make sure to prune the search space as early as possible. For an even more efficient search, you could use something like David Eppstein's de Bruijn graph based spaceship search algorithm (which is actually directly applicable: just search for "spaceships" with speed 0 and period 1 in rule B3/S0145678) with extra pruning rules to reject patterns that are disconnected or too large. | |
| Jan 4, 2018 at 15:43 | comment | added | Atsma Nayem | @IlmariKaronen I don't know if that is any better. I'll have to do some testing but my first impression would be that that would be really inefficient. When I have some time I will try to think of more efficient ways to generate and cull poyplets. | |
| Jan 4, 2018 at 15:38 | comment | added | Ilmari Karonen | I guess you're doing something like generating all the $n-1$ cell polyplets, then extending each of them by one cell in every direction and removing duplicates to get the $n$ cell polyplets? That's pretty inefficient, both because you end up generating lots of duplicates, and also because you can't really do any pruning. I'd suggest a different approach; for example, you could simply start recursively filling an $n \times n$ grid from one corner with cells that are either live or dead, pruning any subpatterns that a) won't vanish, b) can't be connected or c) have more than $n$ live cells. | |
| Jan 4, 2018 at 15:18 | comment | added | Atsma Nayem | @IlmariKaronen I was looking at subspace pruning the problem however is that any polyplet can always be a member of a 1-step vanishing pattern. So there are no forbidden subpatterns. If there are other ways of pruning that you or anyone might know of I'm all ears currently I'm just pruning polyplets with a symmetry. | |
| Jan 4, 2018 at 6:19 | comment | added | Ilmari Karonen | Also note that 1-step vanishing patterns in standard GoL (rule B3/S23) are exactly the same as still life patterns in the "semi-complementary" rule B3/S0145678, so any existing software for exhaustively enumerating still lifes (or oscillators or spaceships) in Life-like cellular automata could be directly repurposed as long as they don't have the GoL rules hardcoded. | |
| Jan 4, 2018 at 6:14 | comment | added | Ilmari Karonen | I'm not familiar enough with Haskell to fully follow your code, but it looks like it's first generating the polyplets and testing them to see if they vanish. I suspect a considerably more efficient method would be to check the GoL rules during the polyplet generation (e.g. check all the neighbors of a cell whenever it is set on or off) and to prune the search space early as soon as you find a subpattern that cannot vanish. | |
| Jan 4, 2018 at 4:50 | history | edited | Atsma Nayem | CC BY-SA 3.0 |
Finished testing case 8
|
| Jan 4, 2018 at 0:14 | comment | added | Atsma Nayem |
@SebastienPalcoux Running it again it took me 286.21 secs or about 5 minutes. TIO actually does computation server side so it was Dennis' servers that took 30 seconds. If your computer is reasonably powerful it might be able to outpace both TIO's servers and myself (assuming you trust my code enough to run it).
|
|
| Jan 4, 2018 at 0:02 | comment | added | Sebastien Palcoux | How long did your laptop take for $n=6$? (mine took 30s online) | |
| Jan 4, 2018 at 0:01 | history | edited | Atsma Nayem | CC BY-SA 3.0 |
Added an alternative implementation
|
| Jan 3, 2018 at 23:58 | comment | added | Atsma Nayem | @SebastienPalcoux My computer took an hour and a half to do $n=7$, however it is a 9 year old laptop. This algorithm is probably exponential or worse, I'd expect $n=8$ to take around a day for me to compute. I've been looking into speeding things up particularly by using symmetries. If a list of the Polyplets existed it would probably speed things up. | |
| Jan 3, 2018 at 23:51 | comment | added | Sebastien Palcoux | I tried a computation online, it works up to $n=6$, but then the computation stops after 60s. How long did you need for $n=7$? How long a usual laptop should need for $n=8$? for $n=9$? According to oeis.org/A030222, the $n$-polyplets has been computed by Matthew Cook (et al.) up to $n=17$, so perhaps the list exists somewhere. | |
| Jan 3, 2018 at 21:04 | history | edited | Atsma Nayem | CC BY-SA 3.0 |
added 1 character in body
|
| Jan 3, 2018 at 19:18 | review | First posts | |||
| Jan 3, 2018 at 19:19 | |||||
| Jan 3, 2018 at 19:14 | history | answered | Atsma Nayem | CC BY-SA 3.0 |