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

[Fred Lunnon]

  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/
>