[seqfan] Re: Finding the longest period Life-patterns on nxn toroidal board?

[Rob Pratt]

You can model the problem as finding a longest cycle in a directed graph with 2^(n^2) nodes and the same number of links. Each node corresponds to a 0-1 nxn matrix and has a link to its successor after applying the Life rules.  Because each node has outdegee 1, the cycles are just the strongly connected components.  For n = 1 to 5, I get maximum cycle lengths 1, 1, 1, 8, and 20, respectively.

> On Jun 1, 2019, at 12:31 PM, Fred Lunnon <fred.lunnon at gmail.com> wrote:
> 
>  In my experience armchair "worry" constitutes an unproductive
> approach to program development.  I prefer to  ---
> 
> (1) Implement a simple, modular algorithm which in principle solves
> a substantial sub-problem;
> 
> (2) If that proves too slow/large/special, identify the limiting factor
> and develop that further;
> 
> (3) Retain the obsolete version, comparing outputs in order to
> assist in validating the improved version;
> 
> (4) Iterate, until
>    something more interesting to do turns up,
>    competing team has been beaten hollow,
>    management terminates project,
>    programmer committed to sanatorium,
>    partner threatens divorce,
> etc, etc.
> 
>  In this case for instance, canonicalisation might if required be
> improved in various ways; but until your complete prototype has
> lurched to its feet, you have no way to establish whether (as I
> suspect) life simulation actually dominates amortised execution time.
> 
> WFL
> 
> 
> 
>> On 6/1/19, hv at crypt.org <hv at crypt.org> wrote:
>> I'm worried that the canonicalization will itself be too slow to make
>> sense to do on all 2^(MN) combinations: if possible, I'd like to find
>> an approach that could potentially get up to around 16 x 16.
>> 
>> I need to do some experiments to see how much it gains, but I think it
>> should be possible to do something like:
>> - enumerate the distinguishable arrangements for a single 1 x N row;
>> - order and index them;
>> - create a lookup for the 2^N combinations to associate each with the
>> index of its canonical form;
>> - for each canonical row, select it as the first row; for each of the
>> remaining rows, select only those of the 2^N combinations that map to
>> a canonical index less than that of the first row (or the same index,
>> as long as none of the preceding rows have had a lesser index).
>> 
>> That doesn't prune out every non-canonical arrangement, but I think
>> it should be a good start, and should be much faster than a full
>> canonicalization of every possible arrangement.
>> 
>> Hugo
>> 
>> Allan Wechsler <acwacw at gmail.com> wrote:
>> :Explicit enumeration is harder, indeed. I have not been able to do much
>> :better than the following:
>> :
>> :Each underlying configuration can be represented as an MxN rectangle of
>> :bits in a number of ways. Each way can be read as a string of MN bits, and
>> :then interpreted as a binary integer. Select as canonical the
>> :representation with the smallest such reading.
>> :
>> :Now iterate over the 2^MN representations, produce the underlying
>> :configuration, and star "reading" it in all the possible ways, comparing
>> :the resulting values with the original. If you find any representation
>> :whose value is less than the original, discard the original and go on to
>> :the next representation. But if the original value turns out to be the
>> :smallest possible, then it is canonical and should be listed.
>> :
>> :This astronomical double loop can be optimized in many ways, but I don't
>> :think the basic idea can be improved.
>> :
>> :On Sat, Jun 1, 2019 at 5:18 AM <hv at crypt.org> wrote:
>> :
>> :> Thanks, A222187 will also of course be treating the 2 x 2 cases 11 / 00
>> :> and 10 / 10 as distinct, hence a(2) = 7.
>> :>
>> :> The linked A222188 is what I was really after though, to try and consider
>> :> if I can come up with any remotely efficient algorithm to enumerate
>> :> the distinct cases.
>> :>
>> :> Hugo
>> :>
>> :> Allan Wechsler <acwacw at gmail.com> wrote:
>> :> :This is a job for the Frobenius-Burnside-Cauchy-Polya counting formula.
>> I
>> :> :am sure this sequence is in OEIS.
>> :> :
>> :> :[pauses for 15 minutes to work it out]
>> :> :
>> :> :OK, after working out F(4) = 34 by hand, I found A222187, "Number of
>> :> :toroidal n X 2 binary arrays ...", which counts the number of cases we
>> :> have
>> :> :to try to find the longest-lived Life pattern on such an array. It
>> doesn't
>> :> :tell us how to enumerate them, though.
>> :> :
>> :> :
>> :> :
>> :> :On Fri, May 31, 2019 at 8:21 PM <hv at crypt.org> wrote:
>> :> :
>> :> :> Antti Karttunen <antti.karttunen at gmail.com> wrote:
>> :> :> :Find the (representatives of) patterns that produce a maximal
>> possible
>> :> :> :cyclic sequence of patterns on nxn toroidal board, with Conway's
>> :> :> :"Life" cellular automaton rules.
>> :> :>
>> :> :> I've started thinking about this, and am unsure if I've confused
>> myself.
>> :> :>
>> :> :> On a 1 x n board the number of distinguishable starting positions
>> seems
>> :> :> to be A000029 (which makes sense). Richer results for Conway's Life
>> :> :> start with a 7-cycle at n=7 (1101000, a 3-place glider), and 6- and
>> :> :> 8-cycles at n=8.
>> :> :>
>> :> :> On a 2 x n board, the analagous sequence appears to start
>> 1,3,6,13,33,74
>> :> :> which is not in the OEIS.
>> :> :>
>> :> :> Have I miscalculated? If it needs to be added, what's a useful way to
>> :> :> describe the 2D analogue of a bracelet?
>> :> :>
>> :> :> For reference, below are the 13 distinguishable results I find for n=3
>> :> :> on a 2xn grid.
>> :> :>
>> :> :> Hugo
>> :> :>
>> :> :> ... (1)
>> :> :> ...
>> :> :>
>> :> :> x.. (6 analogues, including itself)
>> :> :> ...
>> :> :>
>> :> :> xx. (6)
>> :> :> ...
>> :> :>
>> :> :> x.. (3)
>> :> :> x..
>> :> :>
>> :> :> x.. (6)
>> :> :> .x.
>> :> :>
>> :> :> xxx (2)
>> :> :> ...
>> :> :>
>> :> :> xx. (12)
>> :> :> x..
>> :> :>
>> :> :> xx. (6)
>> :> :> ..x
>> :> :>
>> :> :> xxx (6)
>> :> :> x..
>> :> :>
>> :> :> xx. (3)
>> :> :> xx.
>> :> :>
>> :> :> xx. (6)
>> :> :> x.x
>> :> :>
>> :> :> xxx (6)
>> :> :> xx.
>> :> :>
>> :> :> xxx (1)
>> :> :> xxx
>> :> :>
>> :> :> total: 64 = 2^6 analagues accounted for.
>> :> :>
>> :> :> END
>> :> :>
>> :> :> --
>> :> :> Seqfan Mailing list - http://list.seqfan.eu/
>> :> :>
>> :> :
>> :> :--
>> :> :Seqfan Mailing list - http://list.seqfan.eu/
>> :>
>> :> --
>> :> Seqfan Mailing list - http://list.seqfan.eu/
>> :>
>> :
>> :--
>> :Seqfan Mailing list - http://list.seqfan.eu/
>> 
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>> 
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/