ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Question about Golly's cell list

Has something gone haywire? Let us know about it!

Question about Golly's cell list

Postby Scorbie » December 27th, 2015, 10:22 pm

I began to wonder why the format of Golly's cell list is like the one now.
The current cell list format is uncomfortable to use because:
  • It's unintuitive.
  • One has to convert cell lists to list of coordinates (i.e. [(x, y)...()]) to do just about anything. (Except the functions supported by Golly.)
  • The padding zero in the multistate cell list can lead to bugs instead of generating error messages.
If I were to design the python interface of Golly, I would use:
  • Set of coordinates {(x0, y0), (x1, y1), ...} for representing 2-state cells
  • Dict of coordinates and states {(x0, y0): s0, (x0, y0): s1, ...} for representing multistate cells.
(But not that I am changing anything as there seems to be too many scripts already. Or isn't it?
Maybe this can be introduced when Golly starts using Python 3. EDIT: and Perl 5.14+.
EDIT2: I'm willing to rewrite glife if Golly uses this cell format.)

Why is golly's celllist like this? Is it because plife used this format?

EDIT: Offtopic... but does Golly use Perl 5.14 now?
Golly's popup window shows that it tried to but cannot find something like libperl5.14.so.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby dvgrn » December 28th, 2015, 5:48 pm

Scorbie wrote:I began to wonder why the format of Golly's cell list is like the one now.
The current cell list format is uncomfortable to use because:
  • It's unintuitive.
  • One has to convert cell lists to list of coordinates (i.e. [(x, y)...()]) to do just about anything. (Except the functions supported by Golly.)
  • The padding zero in the multistate cell list can lead to bugs instead of generating error messages.
Why is golly's celllist like this? Is it because plife used this format?

That's probably the closest thing to a reason that I can come up with.

Things were much simpler before Golly 2.0, when multi-state universes first became possible. When cell lists lengths were always even, and (I'm guessing a little bit here) the underlying C++ code could handle simple lists much more cleanly than lists of lists or lists of tuples, and simple lists took a lot less memory... there didn't seem to be any good argument for making things unnecessarily complicated.

By the time Golly 2.0 appeared, flat lists seemed normal, and lots of scripts had already been written that assumed that patterns would be passed around that way. Once backward compatibility with older scripts was accepted as a goal, it would have been hard to jump to a nested or dict structure.

And there was that nice feature that odd-length cell lists never happened unless they were multistate. It seemed like a small price to pay, to "simply" append a 0 to a list whenever necessary to signal that it was multistate.

That seemed better than passing around a cell list plus an optional extra list of cell states, half the length of the cell list, that could be presumed to be all 1's if it wasn't there... or I suppose another option would be converting all cell lists to 3-tuples and eating up lots of extra memory, unnecessarily if the universe has only two states.

In hindsight the even/odd list length signal was a very hackerish solution, elegant in one way and kludgey in another -- maybe the kind of thing that only a programmer would think of. On the other hand, it certainly is more efficient in terms of memory use. It might turn out to be a significantly faster way for Python and Golly to talk to each other, than the nested-lists or dictionary alternatives. It's hard to tell for sure without rewriting the whole package -- Golly plus many dozens of scripts -- and doing a lot of profiling. That seems like a lot of work to do, especially if it turns out that the new version is much less efficient (but maybe slightly easier to use.)

Really it's pretty easy to translate back and forth between nested lists and flat lists. Recently I've been using

coords = zip(flatcells[0::2],flatcells[1::2])

to get from a flat two-state cell list to a nested list. For multistate lists, it's

coords = zip(flatcells[0::3],flatcells[1::3])

coords = zip(flatcells[0::3],flatcells[1::3],flatcells[2::3])


(depending on whether you want to keep the state as part of the tuple.)

And to translate back to a flat list, it's

flatcells = []
map(flatcells.extend, coords)


And then you have to add the 0 back on the end, but only if you know it's a multi-state list with an even number of coordinates:

if len(flatcells)%2==0: flatcells+=[0]

--------------------------------

-- Yup, that's looking pretty messy.

So it's certainly not a bad idea to write a competitor for glife that hides all this nonsense from script-writers. Not a replacement for glife, though -- there are too many scripts out there that depend on the silly way glife works now. No point in breaking all the existing stuff that's limping along perfectly well.

Still, there'd be nothing wrong with a new "slife" module -- "s" for "simple", "sensible", "Scorbie", or some such. If it turned out to be widely used, something like that could be moved into the standard Golly package right next to glife.
User avatar
dvgrn
Moderator
 
Posts: 5825
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Question about Golly's cell list

Postby A for awesome » December 28th, 2015, 6:14 pm

Might it be doable to add an extra optional boolean parameter to the glife functions that handle cell lists that specifies what format the lists should be output in (flat or nested/dict)? This seems like it should retain compatibility with older scripts while optionally providing the more intuitive option of working with nested cell lists (assuming the default setting would be flat lists). Also, new functions (or even executables) could be created to translate between flat and nested lists.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1876
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: Question about Golly's cell list

Postby Scorbie » December 28th, 2015, 10:31 pm

dvgrn wrote:Things were much simpler before Golly 2.0, when multi-state universes first became possible.
Ahh. Now I get it... Yeah, things must have been simpler before multistate universes.
dvgrn wrote:When cell lists lengths were always even, and (I'm guessing a little bit here) the underlying C++ code could handle simple lists much more cleanly than lists of lists or lists of tuples, and simple lists took a lot less memory... there didn't seem to be any good argument for making things unnecessarily complicated.
I'm not sure about the cleanness of code... but if it was implemented "because of" memory, it's clearly a big mistake as we need to parse the cell lists again to something usable. (Memory usage: cell list + usable form instead of usable form) Also, one might want to spare thinking about performance or memory usage in Python scripting :wink:
dvgrn wrote:That seemed better than passing around a cell list plus an optional extra list of cell states, half the length of the cell list, that could be presumed to be all 1's if it wasn't there... or I suppose another option would be converting all cell lists to 3-tuples and eating up lots of extra memory, unnecessarily if the universe has only two states.
Two-state cell list and multistate cell-lists are incompatible anyway, so I guess my suggestion of data structures (using sets and dicts) would solve the technical problems. About memory usage due to the extra tuples... I'll never know how much that would be. For a large pattern with a gazillion cells and not doing much besides simple things, maybe cell lists are the way to go. For small patterns, the difference might be negligible. Note all the "might"s. I don't know how python manages its objects in memory. But a sure thing is that on cases where you convert the cell list to a more comfortable data structure, it is more memory-efficient to use the more comfortable data structure in the first place. Do we encounter those cases often? I'll never know. That must be different from user to user.
dvgrn wrote:It's hard to tell for sure without rewriting the whole package -- Golly plus many dozens of scripts -- and doing a lot of profiling. That seems like a lot of work to do, especially if it turns out that the new version is much less efficient (but maybe slightly easier to use.)
Yes, I think changing the Golly source to convert the cell lists would be to much to ask. (Especially cause it's what I cannot do.) But in general, (slightly off-topic) I think using Python focuses on easy and quick scripting rather than fast code.
dvgrn wrote:So it's certainly not a bad idea to write a competitor for glife that hides all this nonsense from script-writers. Not a replacement for glife, though -- there are too many scripts out there that depend on the silly way glife works now. No point in breaking all the existing stuff that's limping along perfectly well.
Yes, I think this is the right conclusion. Gotta start writing slife.
(A small thing is, that I always forget to use the glife module. Partly because there's not enough documentation?)
A for awesome wrote:Might it be doable to add an extra optional boolean parameter to the glife functions that handle cell lists that specifies what format the lists should be output in (flat or nested/dict)?
Well, that's what I thought initially, but tweaking a standard module in Golly might not be too desirable, I guess.

Edit: I might have been a little carried on, but I didn't mean to condemn the Golly gang or development or glife etc. (And honestly after writing all that zip(celllist[::2], celllist[1::2]) I'm getting used to it :roll:) Nonetheless I'll try to peek at existing codebases and see i) whether zip(celllist[::2], celllist[1::2] ) is really done often or not, and ii) if it is used often, try to implement a library with the actions that use them in mind.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby Scorbie » December 29th, 2015, 7:45 am

Scorbie wrote:One has to convert cell lists to list of coordinates (i.e. [(x, y)...()]) to do just about anything. (Except the functions supported by Golly.)
It was rather one has to convert cell lists to list of coordinates to do just about everything I want to do :roll: (I'm trying to add target matching to ptbsearch as a golly script. + and other things.) After reading several scripts in this forum, I found out that quite a lot of the things are doable in glife. (And that glife is a pretty big module.) The most significant thing that is not listed on glife is: checking if two pattens are equal. And things derived from that, such as searching subpatterns etc.

1. Equality testing
Equality in glife.pattern is kinda dangerous because it is not implemented and fallbacks to list equality (without any warnings) and can lead to errors. (I have almost falled in for this one when writing my script.)
Hopefully, a simple def __eq__(self, other) implementation would solve that.
Speaking of safety and enhancements, I would like these to be added to glife. (Or I could add it myself.)
  • Converting messages to strings automatically without complaining in g.show, g.note, g.exit etc.
  • Raising error messages when one tries to do a multicell list associated thingy to a 2-state cell list. (Once encountered this but forgot what the specific problem was.)
2. Subpattern searching
Although searching for subpatterns is used a lot by scripts, people don't seem to feel uncomfiness often as most of the pattern searching is done by custom rules. This is really fast but only works for "specific" targets. (99% of the time gliders) On the other hand, one could generalize to searching arbitrary patterns (just like str.find(substring)) but that's really slow with the {(cell, cell)} form. So we would have to make a new datatype anyway, or any suggestions for a fast subpattern searching algorithm? I'm not talking about big, big arrays, even a 2-digit x 2-digit bounding box pattern is slow.

In (my) summary, the data structure looks a little uneasy to me, but many things are implemented in glife than I thought, so the things to be improved is Either: some enhancements in the glife module would be okay...(Equality testing + some assertions) Or: hopeless with any data structure right now.(Subpattern searching.)
Okay, so just minor enhancements would suffice. Making another module seems to be a bit of an overkill.

Oh! There was one more instance of using zip(celllist[::2], celllist[1::2]). Not using glife. I think a thorough documentation of glife would be very helpful for Golly Python scripters. (Like me.)
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby dvgrn » December 30th, 2015, 9:55 am

Scorbie wrote:1. Equality testing
Equality in glife.pattern is kinda dangerous because it is not implemented and fallbacks to list equality (without any warnings) and can lead to errors. Hopefully, a simple def __eq__(self, other) implementation would solve that.

A variant that I've coded a few times now is equality irrespective of orientation -- can Pattern A be rotated and/or reflected to match Pattern B exactly? That's a little more complicated. You need some concept of normalization: sort (according to any convenient ordering rule) to find the smallest representation of Patterns A and B, and then just see if the normalized patterns are the same. For oscillating patterns, presumably all phases would be included in the sorting process.

Scorbie wrote:Speaking of safety and enhancements, I would like these to be added to glife. (Or I could add it myself.)
  • Converting messages to strings automatically without complaining in g.show, g.note, g.exit etc.
  • Raising error messages when one tries to do a multicell list associated thingy to a 2-state cell list. (Once encountered this but forgot what the specific problem was.)

I like the idea of any-object-safe versions of g.show, g.note, g.warn, g.exit. Might even start importing glife again to use those -- I've had to edit in a str() inside my diagnostic note()s more times than I can count.

For the second item -- what glife functions are associated only with multicell lists? Single-state lists were all that existed when glife was added to Golly 1.0, but as far as I remember, everything in glife should work for either type of list. The getminbox() function is the only one that needs an explicit test to see which type of list it's dealing with, but all the other functions are supposed to Just Work.

I tried a quick test script using pattern(), apply(), and display(), and they worked equally well for a LifeHistory pattern (which golly.parse() converts to multistate) and a plain Life pattern (which converts to a one-state list).

Here's something that I ran into that definitely causes a lot of strange bugs: RLE with a header line "x = ..., y = ..." gets interpreted incorrectly. The first line seems to be interpreted as multiline RLE, with lowercase letters o through y counting as state 1, and other lowercase letters ignored, but uppercase letters A through Z interpreted as states 1 through 26. Will have to sort through Golly source code to see exactly why that's happening; it would be nice if g.parse() could go through all the same parsing steps as Open from Clipboard does.
User avatar
dvgrn
Moderator
 
Posts: 5825
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Question about Golly's cell list

Postby dvgrn » December 30th, 2015, 10:04 am

Scorbie wrote:2. Subpattern searching
Although searching for subpatterns is used a lot by scripts, people don't seem to feel uncomfiness often as most of the pattern searching is done by custom rules. This is really fast but only works for "specific" targets. (99% of the time gliders) On the other hand, one could generalize to searching arbitrary patterns (just like str.find(substring)) but that's really slow with the {(cell, cell)} form. So we would have to make a new datatype anyway, or any suggestions for a fast subpattern searching algorithm? I'm not talking about big, big arrays, even a 2-digit x 2-digit bounding box pattern is slow.

That's an item that has been on my wish list for many years, actually. Imagine a database containing every pattern in the old and new glider gun collections, for example. How can I make some kind of 2D subpattern index, so that I can easily find all the patterns that use a particular p7 pipsquirter oscillator? (Maybe I'm swapping in a new smaller version of the pipsquirter, or some other similarly obsessive little project.)

Subpattern searching is maybe not quite hopeless. If storage space isn't too much of an issue, a possible new datatype might be a hashlife-inspired pattern format that stores all possible ways of chopping a large pattern up into NxN pieces. Macrocell-ish compression could be used on each of the NxN overlapping tilings.

Then if you're looking for a smaller-than-NxN subpattern, you only need to make one pass through the list of NxN tiles. If the subpattern doesn't show up in a tile, it's not in the pattern. Conversely, if it does show up, the quadtree structure will quickly tell you where the tile is used in the larger pattern.

Short of this kind of pre-indexing trickery, here is the most workable algorithm I've used so far. Don't expect anything too amazing -- it's pretty straightforward:

1) Translate the pattern to be searched into nested-list form. Let's call this list searchpattern[]. Maybe a set or some other Python collection type would be more efficient, I haven't done thorough timing tests. Simple lists of coord tuples seem to work quite well.
2) Translate the subpattern to search for into a normal-form nested list, let's call it subpat_ON[]. First ON cell in the upper left is at (0,0). You can actually remove the (0,0) cell, but that's a minor detail.
3) Make a list -- subpat_OFF[] -- of all OFF cells adjacent to the cells in the subpattern, to prevent false-positive matches. Depending on the search, you might use all OFF cells within two cells of an ON cell, or whatever. For larger patterns, using all OFF cells in the bounding box slows down the search too much, and anyway you start to miss good matches due to other nearby objects.
4) Generate and normalize the other orientations of the subpattern, if needed, and run the same search for each.

Then the actual search:

5) For each ON cell (x,y) in searchpattern[], check to see that every cell in subpat_ON[] can be translated by (x,y) to match another cell in searchpattern[]. Just use plain Python "in" or "not in". Stop as soon as a subpat_ON[] cell doesn't match, and go on to the next ON cell in searchpattern[].
6) If all subpat_ON[] cells match, check that all the subpat_OFF[] cells, again translated by (x,y), are not in searchpattern[]. Stop as soon as an exception is found.
7) If everything matches, remove all the matching cells from searchpattern[], then go back to step 4 to try and match the next remaining ON cell.

Steps 5 and 6 are pretty fast, because usually the mismatch shows up in the first few ON cells. With this method, even searching for any orientation of dozens of different objects, my recently reworked recognizer script can run through a big pattern like the glider-to-weekender-to-glider converter, and find all of the pieces in fifteen seconds or so.

This works best if you have a complete library of matching subpatterns, because then you can always find a match for the upper left cell, and remove the other associated cells which would all otherwise be unrecognizable, and therefore very slow to process. If you're trying to recognize large circuitry components, the library has to be ordered with larger subpatterns first -- e.g., find Snark reflector before eater, otherwise the Snark reflector won't be recognizable by the time that subpattern is tried.

I've been thinking about trying a trivial modification of steps 5 and 6, to allow up to M mismatches before giving up. Too high a value of M would probably slow the search down unbearably, but at low values, welded objects and other nonstandard variants could still be recognized.

It could be handy to be able to figure out that some weird object is actually two overlapping Snarks, plus some pattern that can be XORed onto the combination to complete the weld. For example, a GUI that allows you to move Snarks around would just need an XOR weld pattern for every known workable overlap.

-- This is probably getting a little far afield from the original question, though. For the linear propagator project I applied the same algorithm to find all the interesting still lifes in random ash constellations... with "interesting" defined as "anything that isn't in the subpattern library yet".
User avatar
dvgrn
Moderator
 
Posts: 5825
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Question about Golly's cell list

Postby Scorbie » December 30th, 2015, 11:18 am

dvgrn wrote: my recently reworked recognizer script can run through a big pattern like the glider-to-weekender-to-glider converter, and find all of the pieces in fifteen seconds or so.
I knew you wrote something like that! I was working with a survive (for ptbsearch) with pattern matching and just finished it. Searched for that pattern-recognition script but failed to find it (I thought it was the Conduit-Compiler, but no...), so I wrote it on my own.
Interestingly my search method is identical to your explanation 5-7 :), and after reading your description just before I got to optimize it quite a lot. Thanks :)
dvgrn wrote:I've been thinking about trying a trivial modification of steps 5 and 6, to allow up to M mismatches before giving up. Too high a value of M would probably slow the search down unbearably, but at low values, welded objects and other nonstandard variants could still be recognized.
Actually that *can* be done with nearly 0 mismatches. If I read it correctly, the "on filters" and "off filters" need not be stable themselves. Therefore you can just search the "active region" of a functional part (Like the partial result of Bellman) instead of the whole pattern. But that's not perfect as eater2s can replace the eaters, but that seems to be rare enough.
dvgrn wrote:Subpattern searching is maybe not quite hopeless. If storage space isn't too much of an issue, a possible new datatype might be a hashlife-inspired pattern format that stores all possible ways of chopping a large pattern up into NxN pieces. Macrocell-ish compression could be used on each of the NxN overlapping tilings.
dvgrn wrote:This works best if you have a complete library of matching subpatterns, because then you can always find a match for the upper left cell, and remove the other associated cells which would all otherwise be unrecognizable, and therefore very slow to process. If you're trying to recognize large circuitry components, the library has to be ordered with larger subpatterns first -- e.g., find Snark reflector before eater, otherwise the Snark reflector won't be recognizable by the time that subpattern is tried.
Well... I wish you good luck on memory management. I never thought I would do anything big enough with Golly to care memory (and thought my system's memory was big enough, har, har,) but caching the translations in a dict almost caused my system to crash. My targets were simply: Rs, Bs, Hs, Pis, and Gliders (with all orientations), for a total of 48 objects, for all positions inside a 80x80 region. And that uses at least 700MBs. (And I'm not sure how much that actually is, as the memory kept being allocated until my system was in danger.) So think about what will happen if you add more objects. I think one could use a small (16x16) region with no problems.
dvgrn wrote: For the linear propagator project I applied the same algorithm to find all the interesting still lifes in random ash constellations... with "interesting" defined as "anything that isn't in the subpattern library yet".
What's the linear... Ah, I see. Didn't know replicator's name was linear propagator. Why did you try to find the still lifes in that project? Doesn't the linear propagator use only spartan still lifes?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby dvgrn » December 30th, 2015, 1:14 pm

Scorbie wrote:
dvgrn wrote:I've been thinking about trying a trivial modification of steps 5 and 6, to allow up to M mismatches before giving up. Too high a value of M would probably slow the search down unbearably, but at low values, welded objects and other nonstandard variants could still be recognized.
Actually that *can* be done with nearly 0 mismatches. If I read it correctly, the "on filters" and "off filters" need not be stable themselves. Therefore you can just search the "active region" of a functional part (Like the partial result of Bellman) instead of the whole pattern.

Yeah, that works well if you just want to test for the presence/absence of some particular mechanism. It gets trickier if you then want to remove the whole mechanism and go on searching to see what else is in the pattern. In that case you really need some kind of library with all the known welds and variants.

Scorbie wrote:What's the linear... Ah, I see. Didn't know replicator's name was linear propagator. Why did you try to find the still lifes in that project? Doesn't the linear propagator use only spartan still lifes?

It was part of the project of generating a slow-salvo recipe for the circuitry. I had Paul Chapman's search results from several years back, that listed all ways of turning a block into another block. Instead of running my own searches for beehives, boats, etc., I truncated the block-move recipes and then ran a recognizer script to see what the intermediate targets were. The targets were guaranteed to be non-explosive and P2, so I didn't have to worry that there would be anything unrecognizable in there.

Then when a loaf or a tub or whatever was the next object to be constructed, I could just look through the "loaf" or "tub" recipes to find the cheapest one that fit the current incremental construction.

That whole process badly needs to be automated, of course, but I keep thinking of new ways to optimize recipes -- building two objects at once, looking for a recipe that leaves an extra block in the right place to start the next recipe from, etc.

It's probably time to re-do that search properly, and build as big a database as possible. The current recipe library only goes up to 9 gliders, and leaves out a huge number of useful constructions even in that range: anything that can't be extended to make a block-move recipe in 9 gliders or less, will be left out, including huge numbers of potentially useful small constellations.

Some alternate recipe libraries could also be generated with the same search code -- P1 intermediate targets only, or recipes restricted to one glider color or parity.

-- But I'm getting off-subject again. I guess the question is, does it make sense to add any of this normalizing/recognizing functionality to the glife module? As I've outlined it, the recognition algorithm seems a little too specific -- it's good for figuring out what object the upper-left corner ON cell is part of, but not so good for quickly finding out if subpattern S can be found inside pattern P.
User avatar
dvgrn
Moderator
 
Posts: 5825
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Question about Golly's cell list

Postby Scorbie » December 30th, 2015, 6:38 pm

dvgrn wrote:As I've outlined it, the recognition algorithm seems a little too specific -- it's good for figuring out what object the upper-left corner ON cell is part of, but not so good for quickly finding out if subpattern S can be found inside pattern P.
What's the difference? EDIT: You're not talking about the algorithm you described earlier with steps 1-8, are you? I actually did use that naive algorithm for target matching and I think that is as general as it can be.

@dvgrn While we're off topic here's something that "might" be faster depending on the specific purpose of pattern searching.
Break either the whole pattern or subpatterns into connected "blobs". The live cells and their neighbors all belong to the same blob. Here's a code snippet that groups live cells into blobs:
# Parse the pattern into adjacent "blobs"
blobs = []
for x, y in oncells:
    newblob = {(nx, ny) for nx in (x-1, x, x+1)
                for ny in (y-1, y, y+1)}
    for blob in blobs[:]:
        if blob & newblob:
            blobs.remove(blob)
            newblob |= blob
    blobs
.append(newblob)

Which runs quite fast compared to the naive pattern searching. Now we only need to compare whether the blobs match the target pattern's blobs.

Hmm. I'd have to say that searching in general is quite slow, and optimization makes the search too specific.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby Scorbie » December 31st, 2015, 6:41 am

dvgrn wrote:
Scorbie wrote:1. Equality testing
Equality in glife.pattern is kinda dangerous because it is not implemented and fallbacks to list equality (without any warnings) and can lead to errors. Hopefully, a simple def __eq__(self, other) implementation would solve that.

A variant that I've coded a few times now is equality irrespective of orientation -- can Pattern A be rotated and/or reflected to match Pattern B exactly? That's a little more complicated. You need some concept of normalization: sort (according to any convenient ordering rule) to find the smallest representation of Patterns A and B, and then just see if the normalized patterns are the same. For oscillating patterns, presumably all phases would be included in the sorting process.
Actually I'm not talking about that. Consider these two cell lists:

cells1 
= [1, 1, 2, 3]
cells2 = [2, 3, 1, 1]

These two both represent two cells (1, 1) and (2, 3) but they are not considered equal. This has tripped me enough times for me to suggest an __eq__ method.
To justify tweaking glife, here's a small bug in glife:
import glife
mypat1 
= glife.pattern([0, 0], 10, 10) # Transformation not working
mypat1.put()
mypat2 = glife.pattern('o!', 10, 10)
mypat2.put()
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby dvgrn » December 31st, 2015, 9:08 am

Scorbie wrote:cells1 = [1, 1, 2, 3]
cells2 = [2, 3, 1, 1][/code]
These two both represent two cells (1, 1) and (2, 3) but they are not considered equal. This has tripped me enough times for me to suggest an __eq__ method.

Makes sense. The simplest and quickest way I've found to sort cell lists into canonical order is to run them through g.evolve(0). That also removes any overlapping cells, which you can get by combining cell lists. After that the list can be safely compared with another canonical-order cell list.

Does it make sense to enforce canonical order in all glife pattern objects at all times? Would have to add evolve() calls to transform() and join() and list initialization and so on. String initialization, too, I think, because there's that optional transformation parameter.

Now, it's not necessarily part of the spec for g.evolve(0) that it must always canonicalize an input cell list -- but in practice that's certainly what it does, and it seems unlikely that that will change in the foreseeable future.
User avatar
dvgrn
Moderator
 
Posts: 5825
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Question about Golly's cell list

Postby Scorbie » January 18th, 2016, 7:35 pm

dvgrn wrote:
Scorbie wrote:cells1 = [1, 1, 2, 3]
cells2 = [2, 3, 1, 1][/code]
These two both represent two cells (1, 1) and (2, 3) but they are not considered equal. This has tripped me enough times for me to suggest an __eq__ method.

Makes sense. The simplest and quickest way I've found to sort cell lists into canonical order is to run them through g.evolve(0). That also removes any overlapping cells, which you can get by combining cell lists. After that the list can be safely compared with another canonical-order cell list.

Does it make sense to enforce canonical order in all glife pattern objects at all times? Would have to add evolve() calls to transform() and join() and list initialization and so on. String initialization, too, I think, because there's that optional transformation parameter.
Apologies for the late reply. I didn't see your question here. Actually, you don't have to to the ordering for every cell list manipulation, you just have to override the glife.pattern's __eq__ method to something along these lines:
def __eq__(self, other):
    return g.evolve(self, 0) == g.evolve(other, 0)  # Both hand sides are lists, not glife.patterns! No super() needed.
 
And all equality comparisons using glife.pattern will work like a charm thanks to python's black magic.
I may have done something wrong, but hope you get the idea.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby Scorbie » January 23rd, 2016, 10:57 am

Scorbie wrote:@dvgrn While we're off topic here's something that "might" be faster depending on the specific purpose of pattern searching.
Break either the whole pattern or subpatterns into connected "blobs". The live cells and their neighbors all belong to the same blob. Here's a code snippet that groups live cells into blobs:
# Parse the pattern into adjacent "blobs"
blobs = []
for x, y in oncells:
    newblob = {(nx, ny) for nx in (x-1, x, x+1)
                for ny in (y-1, y, y+1)}
    for blob in blobs[:]:
        if blob & newblob:
            blobs.remove(blob)
            newblob |= blob
    blobs
.append(newblob)

Which runs quite fast compared to the naive pattern searching. Now we only need to compare whether the blobs match the target pattern's blobs.
I implemented this in survive.py script and it's **way** faster.
dvgrn wrote:Steps 5 and 6 are pretty fast, because usually the mismatch shows up in the first few ON cells. With this method, even searching for any orientation of dozens of different objects, my recently reworked recognizer script can run through a big pattern like the glider-to-weekender-to-glider converter, and find all of the pieces in fifteen seconds or so.
Could you show me the script by any chance? I'm curious on how faster (or unhopefully, slower) it would be with your pattern matching program.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am

Re: Question about Golly's cell list

Postby dvgrn » January 23rd, 2016, 2:45 pm

Scorbie wrote:Could you show me the script by any chance? I'm curious on how faster (or unhopefully, slower) it would be with your pattern matching program.

Sure. Looks like I didn't post the whole mess anywhere in the spaceship-gun-building threads.

I've tested the attached package, and it seems to be in working order. If it only works on my system for some subtle reason, my apologies in advance. Scripts that write scripts are a little painful to keep one's mind wrapped around, and I just wrote export-library.py in the last hour or so.

As a sample to see if it's working:

  • Run populate-sample-library.py in Golly . This should report that it has populated the recognizer-library folder.
  • Run create-G-to-W-to-G.py . This should display a working glider-to-weekender-to-glider converter.
  • Run recognizer1.2.py. This should progressively recognize and erase all the pieces of the G-to-W-to-G pattern, starting at the top.
  • Explanation: The converter is looking in the library for subpatterns to match, and each time the upper-left live cell matches something, it removes every matching cell from the universe.
  • As soon as the script finds an upper-left live cell that it doesn't recognize, it will stop and complain.
  • If the script succeeds in emptying the universe, it will write a script that re-creates the pattern using the known pieces, to Golly's current Scripts directory.
  • Side note: this turns out to be a really efficient compressed format for most large circuit patterns, better than mc.gz or rle.gz, as long as the pattern isn't something like the Demonoid and mostly made out of gliders or other tiny pieces. Even the Demonoid might do quite well if the library grouped the gliders into repetitive chunks (the elbow-op recipes).
-----------------------

Sometime soon I hope to set up the lookup library to support recursive definitions. But right now I'm stuck on this interminable tenth-anniversary Life Lexicon update. It's actually going very well, but I never seem to run out of terms that need definitions.
Attachments
recognizer1.2.zip
Recognizer v1.2 script, with sample G-to-W-to-G pattern and a library that can recognize all the pieces
(15.15 KiB) Downloaded 792 times
User avatar
dvgrn
Moderator
 
Posts: 5825
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Question about Golly's cell list

Postby Scorbie » February 11th, 2016, 9:36 am

Apologies for not replying. I currently don't have time right now... What I was trying (or hoping, at least) to do was optimising the recognizer script... I'm not sure If I can get back...

I came here to suggest anothe cell list format: using complex numbers from cmath.
One can use sets and dicts of complex numbers.
I am not sure about memory efficiency but the affine transformation becomes trivial; i.e. just complex number arithmetic.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1381
Joined: December 7th, 2013, 1:05 am


Return to Bugs & Errors

Who is online

Users browsing this forum: No registered users and 1 guest