apgsearch: a high-performance soup searcher

[dvgrn]

Found the seed: it's 2014-11-28T14:08:58.074000_. (Without the final period, of course.) I shall test it to see if the problem recurs.

EDIT: Can't seem to jump to the middle, so I'd have to start it from the beginning. Considering that I've already got a search running, I'll hold off on it for now.

Nothing interesting happens with apgsearch v0.5, with the "initpos =" line modified to

Code: Select all

initpos = int(g.getstring("Initial position: ", "0"))

and running 100K soups starting at 5600000, or 10K soups starting at 5641500. No middleweight spaceship occurs at soup #5642300, but there's one at 5642361:

MWSS @ 5641917, 5642087, 5642361, 5643742 ...

I'm trying the run again from zero, but it seems as if this one might remain a mystery -- caused by cosmic rays, maybe, or the Flying Spaghetti Monster. You're running unmodified apgsearch v0.5, I take it?

EDIT: Yup, ran 10 million soups overnight starting with that seed, with no apparent troubles around 5.6 million (though I suppose if apgsearch had some kind of temporary hiccup and eventually recovered, I wouldn't necessarily see anything.)

[Scorbie]

I'm not sure why, but my bootleg version of apgsearch with symmetry returns "OVERSIZE" to this pretty normal soup with this soupid (with even plus symmetry):
Scorbie_2014-12-02T00:57:48.438000_1038820

Code: Select all

x = 32, y = 32, rule = B3/S23
8obo2b2ob2ob2o2bob8o$3o3bob6ob2ob6obo3b3o$3b6obo4b2o4bob6o$ob2o2bo2bob
obo4bobobo2bo2b2obo$o2bo4bo5bo2bo5bo4bo2bo$12o2b4o2b12o$2bo4b4obo2b2o
2bob4o4bo$obob2ob3obobo4bobob3ob2obobo$o2b2o2b2obo2bo4bo2bob2o2b2o2bo$
3bo4b2ob10ob2o4bo$o2b8o2bo4bo2b8o2bo$bobo2b3o5b4o5b3o2bobo$2bo2b4o2b2o
6b2o2b4o2bo$10o2b2ob2ob2o2b10o$3obo3b2obo3b2o3bob2o3bob3o$3b3o2bo2bobo
b2obobo2bo2b3o$3b3o2bo2bobob2obobo2bo2b3o$3obo3b2obo3b2o3bob2o3bob3o$
10o2b2ob2ob2o2b10o$2bo2b4o2b2o6b2o2b4o2bo$bobo2b3o5b4o5b3o2bobo$o2b8o
2bo4bo2b8o2bo$3bo4b2ob10ob2o4bo$o2b2o2b2obo2bo4bo2bob2o2b2o2bo$obob2ob
3obobo4bobob3ob2obobo$2bo4b4obo2b2o2bob4o4bo$12o2b4o2b12o$o2bo4bo5bo2b
o5bo4bo2bo$ob2o2bo2bobobo4bobobo2bo2b2obo$3b6obo4b2o4bob6o$3o3bob6ob2o
b6obo3b3o$8obo2b2ob2ob2o2bob8o!

Any Idea why?? Is it because of the straight beehive trails?

[calcyman]

Yeah, it features a 42-by-4 pseudo-still-life, which doesn't fit in a 40-by-40 box and therefore is rejected before having a chance to be tested against the `decompositions' dictionary. Hence `OVERSIZED'.

[Scorbie]

Oh, it was a feature, not a bug! Thanks!!

[Lewis]

How difficult would it be to implement something that saves the seed number of any soup that runs for longer than a given time, e.g. 40,000 generations?

[dvgrn]

How difficult would it be to implement something that saves the seed number of any soup that runs for longer than a given time, e.g. 40,000 generations?

Not too difficult, I think. Some testing would have to be done, but I suspect that with a cutoff like 40,000 you wouldn't slow down apgsearch noticeably at all -- because only a tiny fraction of soups fail to stabilize in 6,000 ticks, and when they don't stabilize they get checked out anyway by a slow-and-careful piece of code that could easily figure out a rough time to stabilization.

Looks to me like the relevant code starts with "def stabilise3(self):"... The first part throws out everything up to 30*200 = 6000. After this there's a chunk of grouchy code that seems to check everything up to 30*4000=120000 ticks. Anything that doesn't settle by then would get reported as pathological, I think (?)

So somewhere in there you'd have to set a special flag if the oscar.py-based code takes unusually long to settle -- 40K ticks, or whatever threshold seems interesting. Could award some number of points for a big enough number, I suppose... even if this search started getting used for cryptocurrency after all, a rare-methuselah soup is presumably just as un-forgeable as a rare-object soup.

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

You would have to be careful not to award methuselah-points for anything that turned out to be a switch engine or whatever. And the hard part might be to make the methuselah-scoring code as rule-agnostic as the rest of apgsearch. The 40,000 cutoff might be fairly B3/S23-specific.

-- I wonder if apgsearch could use some kind of power-law frequency calculation to figure out an appropriate cutoff point for a given rule? E.g., only start collecting rare long-lived patterns after 100,000 ticks or so, when it reliably knows what "rare" means for the rule in question?

[flipper77]

I've put it off for way too long, here's the updated common names dictionary that also includes Andrej Okrasinski's search results, plus some from my use of his screensaver, as well as many others from my frequent use apgsearch, especially symmetrical objects(pufferfish, and the large cluster of pd-type oscillators are there just to keep track of them, so other p15 oscillators not listed I can check). The dict is now just under 9000 objects, so those running apgsearch with standard soups will identify some of the rarer objects now.

I had to split the dict into 3 sections due to the 256kb limit per file, so you'll need to get all three.
EDIT: If you see that some objects have changed scores, this is due to the rough heuristic suggested by Adam that I used, but the scores make sense to me, so there's a good chance I won't change them soon.

[flipper77]

Some modifications need to be made to the dict. Here's the list of 86 objects whos scores need to be changed:

Code: Select all

                   "xs15_g8jdzpic": ("?15?153", 20),
                   "xs15_354m96zw32": ("?15?147", 20),
                   "xs15_8kk3123z641": ("?15?146", 20),
                   "xs16_178jd453": ("?16?154", 20),
                   "xs16_32qbzca43": ("?16?004", 20),
                   "xs16_651248n96": ("?16?180", 20),
                   "xs16_o8bdzx3156": ("?16?061", 20),
                   "xs16_35s2mzx1252": ("?16?070", 20),
                   "xs17_3pq3qic": ("?17?074", 20),
                   "xs17_c88bp46z33": ("?17?170", 20),
                   "xs17_69lmzx34a6": ("?17?151", 20),
                   "xs17_ciarzxc952": ("?17?123", 20),
                   "xs17_6a88b5z653": ("?17?089", 20),
                   "xs17_39mgmaz321": ("?17?094", 20),
                   "xs17_gilmz1w6jo": ("?17?160", 20),
                   "xs17_wmkiarz252": ("?17?062", 20),
                   "xs17_3lk2sgz343": ("?17?136", 20),
                   "xs17_39c8a52z253": ("?17?076", 20),
                   "xs17_0g8o653z1qm": ("?17?060", 20),
                   "xs17_8kkjaaczx23": ("?17?164", 20),
                   "xs17_0312koz69a43": ("?17?052", 20),
                   "xs17_0g9fgka4z321": ("?17?173", 20),
                   "xs17_4a9f0ckzx311": ("?17?091", 20),
                   "xs18_3iab96z343": ("?18?027", 20),
                   "xs18_bd0u2kozw23": ("?18?004", 20),
                   "xs18_3hu0628c48c": ("?18?150", 20),
                   "xs18_35a88czca53": ("?18?114", 20),
                   "xs18_64kbaicz0321": ("?18?159", 20),
                   "xs18_0jhu0og4cz32": ("?18?115", 20),
                   "xs18_69iczx11dik8": ("?18?097", 20),
                   "xs18_0mkid96z1221": ("?18?143", 20),
                   "xs18_3lowggozw3496": ("?18?069", 20),
                   "xs19_4aa40vhar": ("?19?063", 20),
                   "xs19_3iar2qrzw1": ("?19?094", 20),
                   "xs19_cc0si96zbd": ("?19?070", 20),
                   "xs19_696o6hrzw23": ("?19?122", 20),
                   "xs19_8o0e9jzc9611": ("?19?128", 20),
                   "xs19_6icgf9gz23x11": ("?19?068", 20),
                   "xs19_025acz8kid113": ("?19?014", 20),
                   "xs19_0ca52z65115ac": ("?19?119", 20),
                   "xs19_031e88gz8kid11": ("?19?060", 20),
                   "xs20_3lm0uiz3443": ("?20?106", 20),
                   "xs20_bq2r96z3421": ("?20?047", 20),
                   "xs20_35aczw319lic": ("?20?109", 20),
                   "xs20_65lmzw14b871": ("?20?034", 20),
                   "xs20_gbaacz11dik8": ("?20?108", 20),
                   "xs20_69e0ok8z6953": ("?20?069", 20),
                   "xs20_4a9b8b96zx33": ("?20?001", 20),
                   "xs20_xj1u0oozca611": ("?20?100", 20),
                   "xs20_354kmzx123cko": ("trans-ship_on_ship and longhook", 20),
                   "xs20_069a4z8e1d952": ("?20?053", 20),
                   "xs20_651u0okczw643": ("?20?103", 20),
                   "xs20_0g04a96zold113": ("?20?081", 20),
                   "xs20_25a8a6zx6515a4": ("?20?003", 20),
                   "xs20_069aczg8o6513z01": ("?20?102", 20),
                   "xs21_69abaa4z2553": ("?21?067", 20),
                   "xs21_069acz4all96": ("?21?054", 20),
                   "xs21_cic87piczw113": ("?21?064", 20),
                   "xs21_33gv1s6z03421": ("?21?041", 20),
                   "xs21_39u066z643033": ("?21?057", 20),
                   "xs21_255mgm93z0643": ("?21?029", 20),
                   "xs21_0gt3ob96z3421": ("?21?066", 20),
                   "xs21_4a9b8b5zw6513": ("?21?074", 20),
                   "xs21_0jhkmz32w69ic": ("?21?049", 20),
                   "xs21_69m88czxdd113": ("?21?016", 20),
                   "xs21_651u08oz4aa611": ("?21?043", 20),
                   "xs21_651u08oz4a9521": ("?21?036", 20),
                   "xs22_6960uhe0e96": ("?22?041", 20),
                   "xs22_69f0rbz25521": ("?22?046", 20),
                   "xs22_0g8e1dqz6b871": ("?22?036", 20),
                   "xs22_cc0v1u0oozx123": ("?22?054", 20),
                   "xs22_354c0cczx69d113": ("?22?050", 20),
                   "xs23_3pmkkmzcia401": ("?23?003", 20),
                   "xs23_3pmggzxmkl2zw1221": ("?23?015", 20),
                   "xs24_0gs2t1eoz4aa611": ("?24?007", 20),
                   "xs24_0mlhe8gz32w358go": ("?24?003", 20),
                   "xs25_69b8bb8ozw6996": ("?25?005", 20),
                   "xs25_mlhegmmz1x3443": ("?25?006", 20),
                   "xs25_69ege2s0siczx121": ("?25?004", 20),
                   "xs26_69bqa4zx4abqic": ("?26?008", 20),
                   "xs26_o8g0s2ibpicz643w1": ("?26?003", 20),
                   "xs26_g39s0s48gz11d4ko11": ("?26?006", 20),
                   "xs27_354q4oz69d1ehp": ("?27?002", 20),
                   "xs27_0gwo4qabqicz343032": ("?27?003", 20),
                   "xs29_0gs2llmz32012egnc": ("?29?001", 20),
                   "xs30_69b88c0cczx330311d96": ("?30?001", 20)

[dvgrn]

Some modifications need to be made to the dict. Here's the list of 86 objects [whose] scores need to be changed...

Bah, humbug -- this has gotten a little too complicated. With a ZIP archive all of the common names easily fit into one file -- along with the rest of apgsearch, for that matter. Can we just roll all the changes into a semi-official apgsearch v5.1?

I looked back a few pages, and don't think I missed any other updates -- the spaceships are all in v5.0. There are a few more that might be added, I suppose: isn't a crab at least as likely as a weekender? But I doubt we'll see either one crawling out of the soup, at least until we build up a distributed search project on the scale of Folding@home or so...!

EDIT: Finally got tired of having to scroll to almost-the-bottom of a huge census report to see whether there were any high-scoring soups in the latest run. Attached is a version 0.52 that puts the highest score at the top of the report, with a link to the high-score table.

Suddenly even ten-million-soup runs are coming back with nothing but known objects... I should try comparing my list of found objects with the new common-names list, and see how many of apgsearch's discoveries on my system are really new.

[Freywa]

I see opportunity for massive optimisation: instead of having to compute the results in the objects folder all over again when a new instance of the script is run, re-use the objects folder. That way even memoisation can be skipped and every instance of running will start up rather fast.

Then again, it would be really nice if apgsearch could read the progress file and continue where it left off, instead of having to restart every time – to prevent my father from catching me doing an overnight run, of course.

[flipper77]

When it comes to symmetrical soups, it would probably be best to do something along these lines for the hashsoup() function(this version utilizes all 4 lines of symmetry, both orthogonal and diagonal):

Code: Select all

def hashsoup(instring):

    s = hashlib.sha256(instring).digest()
    
    thesoup = []

    for j in xrange(32):

        t = ord(s[j])

        for k in xrange(8):

            x = k + 8*(j % 2)
            y = int(j / 2)

            if (t & (1 << (7 - k)) and (x - y >= 0)):

                thesoup.append(x)
                thesoup.append(y)

                thesoup.append(y)
                thesoup.append(x)


                thesoup.append(-x)
                thesoup.append(y)

                thesoup.append(-y)
                thesoup.append(x)


                thesoup.append(x)
                thesoup.append(-y)

                thesoup.append(y)
                thesoup.append(-x)


                thesoup.append(-x)
                thesoup.append(-y)

                thesoup.append(-y)
                thesoup.append(-x)

    g.putcells(thesoup, 0, 0)

My last 5 000 000 soup search with this code ran ~10% faster over the original hashsoup() function apgsearch comes with, which is of some notability. Perhaps others could try it out as well to see what kind of speed boosts other get.

EDIT: Changed the function to be more uniform, and overall, more readable.

[flipper77]

Lately, I've been doing lots and lots of symmetrical soup searches, and I've been getting some decent results with my customized version of apgsearch, most modifications are there to incorporate specific symmetries that you input after rule selection.

I'll do my best to give a decent description of changes:

• Hashsoup() function now accepts symmetry strings, and appropriate code to deal with them, and now returns soup, instead of direct placement.
• Now that hashsoup() returns the soup, using g.store(hashsoup()) instead makes for more convenient temp soup files(inspired by others on these forums).
• Now the "latest_census.html" and search_(...) files include the symmetry string to keep track of which soups used what symmetries.
• Defined a new function check(string) that analyzes the symmetry string you input, and makes sure it's proper, and makes changes if needed(some symmetries don't work with others).
• (Unrelated) Added a few more objects to dict, primarily symmetrical.

Now I'll describe how symmetry strings work:

• The symmetry string consists of 5 numerical characters.
• Each char must be between 0 and 2 inclusive, except 2nd to last(0 to 3 inclusive).
• 0 represents the absence of a particular symmetry("00000" represents assymetrical soups).
• 1st number represents diagonal symmetries:
  • If 1, there's one line of diagonal symmetry.
  • If 2, there's two lines of diagonal symmetry, rest of the string is ignored.
• 2nd number represents reflection across x-axis:
  • If 1, the reflection has odd length.
  • If 2, the reflection has even length.
• 3rd number represents reflection across y-axis (same as above)
• 4th number represents rotation (180 degrees):
  • If 1, both soup dimensions are odd length.
  • If 2, one dimension is odd, the other is even.
  • If 3, both soup dimensions are even length.
• 5th number represents rotate4 (90 degrees):
  • If 1, both soup dimensions are odd length.
  • If 2, both soup dimensions are even length.

The check function is simple to describe:

• Checks if input symmetry string is valid(if not, uses "00000" as default).
• If the first char is 2, the rest is ignored.
• If there's any kind of line-symmetry, rotational symmetries are ignored.
• If there's some type of rotate4 symmetry, rotate2 symmetry is ignored
• Otherwise, return current string

Here's the unofficial version of apgsearch with symmetry options:

apgsearch-v0.53.zip

hacked version(w/ symmetry options)

(151.95 KiB) Downloaded 411 times

I've tested it several times, and it seems to work without any problems. If you understand how these symmetry strings work, it'll be very easy to do soup searches on any symmetries you want.

If there are any bugs related to symmetry-type things, be sure to let me know.

EDIT: Be sure to change soup seed, since I posted a direct copy of my personal version.

[calcyman]

Thank you!

The current commonnames dict seems to have peculiarities, such as disproportionately low scores for symmetrical objects:

"xp29_y8252y1252zy94c4x4c4z8k8y0ogydgoy08k8zy3hyfhz252y031yd13y0252zy9464x464zy88k8y18k8": ("p29 pre-pulsar-shuttle", 20),

That seems to suggest that p29 pre-pulsar shuttles are as common as bipoles (certainly not the case!).

The scores should be based upon natural frequency in asymmetric soups. No modification is required for symmetric soups, since (for example) if a mold appears in a soup with D8 symmetry, it appears 8 times (and therefore contributes 8 times the score of a single mold).

I'll experiment with Google's Datastore API when I next have some free time, so that the object list can be stored remotely (in catagolue) instead of in the apgsearch source code.

[flipper77]

That seems to suggest that p29 pre-pulsar shuttles are as common as bipoles (certainly not the case!).

The scores should be based upon natural frequency in asymmetric soups. No modification is required for symmetric soups, since (for example) if a mold appears in a soup with D8 symmetry, it appears 8 times (and therefore contributes 8 times the score of a single mold).

I'll experiment with Google's Datastore API when I next have some free time, so that the object list can be stored remotely (in catagolue) instead of in the apgsearch source code.

Yes, I agree that the scores shouldn't be that low, since there have been a few inconsistencies with some of my top-scoring soups, but I don't have a really good scoring system for new objects that pop up, since most of their frequencies in asymmetric soups would be so tremendously low that just assigning a high enough scoring value would suffice.

As for the object list, that's a fantastic idea, since I'm not in love with idea that most lines in the code are taken just by the object list, and others here would most likely agree.

[calcyman]

Hmm, I may have misunderstood your symmetry string, but it doesn't appear to support all 16 different types of symmetries.

Here's the full list:

• C1 -- e.g. eater
• C2 (even, even) -- e.g. snake
• C2 (even, odd) -- e.g. snake siamese snake
• C2 (odd, odd) -- e.g. integral
• C4 (even, even)
• C4 (odd, odd)
• D2 orthogonal (even) -- e.g. table on dock
• D2 orthogonal (odd) -- e.g. hat
• D2 diagonal -- e.g. ship
• D4 orthogonal (even, even) -- e.g. block on block on block
• D4 orthogonal (even, odd) -- e.g. beehive
• D4 orthogonal (odd, odd) -- e.g. house on house
• D4 diagonal (even, even) -- e.g. barge
• D4 diagonal (odd, odd) -- e.g. ship
• D8 (even, even) -- e.g. block
• D8 (odd, odd) -- e.g. tub

where the first symbol gives the group, the words 'orthogonal' and 'diagonal' refer to the directions of any lines of symmetry, and the words in parentheses give the parities of any dimensions constrained by the symmetry.

In particular, it looks like you don't distinguish between the two D4 diagonal types.

[flipper77]

where the first symbol gives the group, the words 'orthogonal' and 'diagonal' refer to the directions of any lines of symmetry, and the words in parentheses give the parities of any dimensions constrained by the symmetry.

In particular, it looks like you don't distinguish between the two D4 diagonal types.

Thanks for catching that, a quick fix should fix that, and if possible, I would have preferred a more streamlined way of distinguishing symmetry, would people prefer entering strings like C4e which is C4 even, and C2oo which is C2 double odd, I want to make entering symmetries fit a more uniform format.

EDIT: I'm proposing a format for inputting symmetries:

• Primary symmetry goes first (C1, C2, D4 etc.)
• An underscore comes after to separate details
• "+" stands for solely orthogonal, "x" stands for solely diagonal
• Even and odd types are handled with a single number:
  • 1 stands for odd or odd^2(depending of primary symmetry)
  • 2 stands for even or even+odd(depending of primary symmetry)
  • 4 stands for even^2

With this format, all 16 symmetries look like this:

• C1
• C2_1
• C2_2
• C2_4
• C4_1
• C4_4
• D1_+1
• D1_+2
• D1_x
• D2_+1
• D2_+2
• D2_+4
• D2_x1
• D2_x4
• D4_1
• D4_4

[calcyman]

Sure, that's an excellent notation -- nice and intuitive!

I think that it's slightly more common to use D_2n than D_n for the symmetry group of a regular n-gon (since the order of the group is 2n, rather than n). In particular, groupprops uses D8 as the main title (but says 'also called D4' in parentheses):

http://groupprops.subwiki.org/wiki/Dihedral_group:D8

Catagolue (the cloud-hosted GoL object database, written in Java) is progressing well. I'm starting to get accustomed to using the Google Datastore, and everything else (such as the user interface) is straightforward enough. Here's a current screenshot to give an idea what the user interface will resemble:

Screenshot of Catagolue

screenshot3.png (245.16 KiB) Viewed 17814 times

The comments are formatted in a bespoke flavour of markdown which (in addition to the usual features of markdown) interprets fenced RLE code blocks and (provided they are sufficiently small) displays the pattern as an SVG to the left of the RLE code (see screenshot above).

Anyway, at the moment, my intention for the logical structure of the Datastore is roughly as follows:

• The highest-level entity is Rule. Rules don't really have much data associated with them, and just serve to group the next level of entities:
• Entities of types Object, Pattern and Census are direct children of Rule entities. For example, the Objects 'LWSS' and 'pentadecathlon' will be children of the Rule 'b3s23'. Similarly, the census for C4_4-symmetric soups in B36/S23 will be a child of the rule 'b36s23'.
• Object entities have Syntheses as child entities. A Synthesis is basically a tuple (initial object, final object, cost, arrangement of gliders), and is specifically a child of the 'final object'.
• Census entities have children of types Haul and Page. A Page contains an up-to-date table of object counts of a particular type (such as all xs16_ objects); the reason for having separate pages is due to a one-megabyte limit on entity sizes in Google Datastore. A Haul is an ephemeral container of object counts from a particular run of apgsearch, and will be deleted as soon as the relevant information is transferred (sequentially and atomically) to the corresponding Pages and Objects.

(I already have entities of type Comment and CommentThread to allow users to comment on objects, patterns etc.)

On the other end, I need to experiment with Python's urllib2 to enable apgsearch to send multipart POST requests to Catagolue. (GET requests are considerably easier, so I should soon have the feature enabling one to download commonobjects from Catagolue instead of storing them in the apgsearch source code.)

Once everything is up and running, we can incorporate functionality such as querying the best synthesis of a particular object X. In particular, if we (say) have a synthesis of X based on an object Y, and there is a later reduction in the cost of Y, then a subsequent query of X will give the updated cost.

[Extrementhusiast]

Once everything is up and running, we can incorporate functionality such as querying the best synthesis of a particular object X. In particular, if we (say) have a synthesis of X based on an object Y, and there is a later reduction in the cost of Y, then a subsequent query of X will give the updated cost.

You'll have to keep all of the connections, though, in case one route becomes better than another. Of course, this would probably involve repetitive iterations of Dijkstra's algorithm on thousands of nodes.... (Said nodes would probably best be color-coded, to differentiate between the objects that have a direct synthesis from those that don't.)

[calcyman]

You'll have to keep all of the connections, though, in case one route becomes better than another.

Indeed, that's the idea.

Of course, this would probably involve repetitive iterations of Dijkstra's algorithm on thousands of nodes

To find the optimal incremental synthesis for X (based on individual 'atomic syntheses'), we only need one application of Dijkstra's algorithm, and it won't require thousands of nodes (assuming it has a reasonably cheap synthesis). The trick is to apply Dijkstra's algorithm in reverse (i.e. begin at X and attempt to backtrack until you reach the empty object).

Alternatively, in the amortized problem (wanting to find optimal incremental syntheses for all objects, rather than just a single object), we keep track of the costs of all objects in our graph. Then, whenever we reduce the cost of a particular object X, we highlight X to indicate that it has been improved. Now keep iterating the following procedure until no highlighted nodes remain:

-- Choose some highlighted node X.
-- Systematically consider each Y such that there exists a partial synthesis X --> Y. If the cost of Y can be reduced by concatenating this with the optimal synthesis of X, adjust the cost of Y accordingly and highlight Y.
-- Unhighlight X.

This algorithm should terminate really quickly, since it's rare for an object to lie on the unique 'critical path' of thousands of other objects.

[flipper77]

Here's the latest unnofficial version of apgsearch with symmetries(uses D_2n instead of D_n):

apgsearch-v0.54.zip

Hacked version w/ symmetry notation (and changes)

(152.22 KiB) Downloaded 360 times

The way the hashsoup() function works is that it's passed a symmetry string like the previous version I uploaded before, but apgsearch asks you for one of these symmetry options:

• C1
• C2_1
• C2_2
• C2_4
• C4_1
• C4_4
• D2_+1
• D2_+2
• D2_x
• D4_+1
• D4_+2
• D4_+4
• D4_x1
• D4_x4
• D8_1
• D8_4

The obvious reason for this is optimizing the speed of the hashsoup() function, for which I've made many small optimizations of my own through experimentation using same number of soups, and same root. If anyone else can optimize it further speed-wise, I'd appreciate it.

EDIT: I fixed a few bugs with the hashoup function, since C2_2 and C2_4 are incorrect, and D4_x4's NE diagonal is OFF. For those who have the one with the bugged version of hashsoup, just replace it with this:

Code: Select all

def hashsoup(instring, sym):

    s = hashlib.sha256(instring).digest()

    thesoup = []

    d  = int(sym[0])
    ox = int(sym[1])
    oy = int(sym[2])
    rx = int(sym[3])
    ry = int(sym[4])
    r4 = int(sym[5])

    for j in xrange(32):

        t = ord(s[j])

        for k in xrange(8):

            x = k + 8*(j % 2)
            y = int(j / 2)

            if t & (1 << (7 - k)):

                if not d or x >= y:

                    thesoup.append(x)
                    thesoup.append(y)

                if (d > 1) and x <= y:
                    thesoup.append(y)
                    thesoup.append(-x-(d==3))

    # Standard soup:
    if sym == "000000":
        return thesoup

    # Checks for diagonal symmetries:
    if d:
        for x in xrange(0, len(thesoup), 2):
            thesoup.append(thesoup[x+1])
            thesoup.append(thesoup[x])
        if d > 1:
            d = 2 - d
            for x in xrange(0, len(thesoup), 2):
                thesoup.append(d-thesoup[x+1])
                thesoup.append(d-thesoup[x])
            return thesoup

    # Checks for orthogonal x symmetry:
    if ox:
        for x in xrange(0, len(thesoup), 2):
            thesoup.append(thesoup[x])
            thesoup.append(1-thesoup[x+1]-ox)

    # Checks for orthogonal y symmetry:
    if oy:
        for x in xrange(0, len(thesoup), 2):
            thesoup.append(1-thesoup[x]-oy)
            thesoup.append(thesoup[x+1])

    # Checks for rotate2 symmetry:
    if rx or ry:
        rx -= 1
        for x in xrange(0, len(thesoup), 2):
            thesoup.append(thesoup[x]-15-rx)
            thesoup.append(thesoup[x+1])

        for x in xrange(0, len(thesoup), 2):
            thesoup.append(-thesoup[x]-rx)
            thesoup.append(1-thesoup[x+1]-ry)

    # Checks for rotate4 symmetry:
    if r4:
        r4 = 1 - r4
        for x in xrange(0, len(thesoup), 2):
            thesoup.append(r4-thesoup[x])
            thesoup.append(r4-thesoup[x+1])

        for x in xrange(0, len(thesoup), 2):
            thesoup.append(thesoup[x+1])
            thesoup.append(r4-thesoup[x])

    return thesoup

EDIT2: Small change to hashsoup function again.

[knightlife]

2 pi + blinker ----> 52-bit still life:

Code: Select all

x = 26, y = 47, rule = B3/S23
2bo$obo$b2o2$23bo$23bobo$23b2o8$9bobo$10b2o$10bo7bo$16b2o$17b2o22$23b
2o$23bobo$23bo2$b2o$obo$2bo!

[flipper77]

I noticed that apgsearch imports the rect() and pattern() functions, but I haven't found a single use of either function in the code, did I miss something, or is it old code that isn't used anymore.

[flipper77]

Another thing I want to talk about, is sub-folders within each rule folder, and when you use a new symmetry for that particular rule, apgsearch generates a new folder named whatever symmetry you enter. Is this a good idea, or is there a better way to deal with different symmetry settings?

[gameoflifeboy]

Apgsearch thinks the following pentadecathlon variation in B3/S238 is a pentadecathlon (it's different in some stages).

Code: Select all

x = 10, y = 3, rule = B3/S238
2bo4bo$2ob4ob2o$2bo4bo!

[wildmyron]

Apgsearch thinks the following pentadecathlon variation in B3/S238 is a pentadecathlon (it's different in some stages).

Code: Select all

x = 10, y = 3, rule = B3/S238
2bo4bo$2ob4ob2o$2bo4bo!

This is down to the life-centric nature of the common names list. The reason this happens is that the phase which gives the canonical representation in B3/S238 is the same as for B3/S23, and both patterns have the same period. The best way to resolve this is to use a rule specific object list.