apgsearch: a high-performance soup searcher

[calcyman]

It's morally a pentadecathlon.

Similarly, these two spaceships should really be considered to be the same, even though they differ very slightly in a single phase:

http://fano.ics.uci.edu/ca/rules/b368s23/g4.html (b368s23 bomber)
http://fano.ics.uci.edu/ca/rules/b36s23/g4.html (b36s23 bomber)

[flipper77]

For soups where the same object appears multiple times, especially in symmetric soups, the same soup number appears in the sample occurrences, so you while you may get 10 sample soups, they may not be necessarily unique, and this can get particularly annoying, especially with D8_1 or D8_4 symmetry, since some objects only get 2 unique soups. I've implemented in my personal version of apgsearch (for testing and otherwise) a way of actually recording 10 unique soups per object, where the number of occurrences of that object in a certain sample soup is in parentheses next to the soup number(obviously with 1 occurrence, just the soup number is displayed).

Another small thing I added is that sample soup numbers are sorted in ascending order, which is only performed when progress is saved, and displaying the census.

Before I post it, I'm thinking about separate folders within each rule that separates the censuses with different symmetries, and creates a new symmetry folder when it's the first time you use that rule and symmetry, but I want to see if other people would like something different.

[Scorbie]

Before I post it, I'm thinking about separate folders within each rule that separates the censuses with different symmetries...

By census, do you mean the report text file or the rle pattern of found objects? I think it is the former, but just checking.

I am not a long-time apgsearcher but here is my humble opinion.
I think it's an nice idea to organize censuses, but for me, maybe just a symmetry string shown in the title would be just enough. But above all things, being friendly with calcyman's database would be my first priority.

[flipper77]

By census, do you mean the report text file or the rle pattern of found objects? I think it is the former, but just checking.

Actually, I mean the objects found by apgsearch, because some objects in symmetrical soups aren't going to appear in others, but I like how the text files are handled.

I am not a long-time apgsearcher but here is my humble opinion.
I think it's an nice idea to organize censuses, but for me, maybe just a symmetry string shown in the title would be just enough. But above all things, being friendly with calcyman's database would be my first priority.

I'm thinking of placing the symmetry as the folder name (C1, C4_4, D2_x etc.), and as for the database, it would benefit me a lot if he gave an opinion on these ideas, so that this works out without too many major problems. Obviously, I wouldn't want to hinder his progress in any way.

[Scorbie]

Actually, I mean the objects found by apgsearch, because some objects in symmetrical soups aren't going to appear in others, but I like how the text files are handled.

Above all things, being friendly with calcyman's database would be my first priority.

Were there situations where you needed the census organized? I think it's a tidy idea to organize the census, but I'm just curious whether the idea came from necessity.

At first I thought that finding whether a certain object exists would be harder since one would have to search all subdirectories. But searching at the root directory would also list matches in subdirectories, so no problem.

Considering the amount of replies of your suggestion, I think most of us in the forum are really fine with any kind of organization.

[flipper77]

Were there situations where you needed the census organized? I think it's a tidy idea to organize the census, but I'm just curious whether the idea came from necessity.

The sorting of the soup numbers was only to make it a bit more orderly, and isn't technically needed, but it bothered me to see soup numbers for common objects scrambled, so I just added it in.

But the 10 unique soups implementation is definitely noteworthy to me, since I believe that 10 sample soups should mean 10 unique sample soups, and contain no duplicates whatsoever. It would be beneficial to do little things like this to the census to make it more organized and clean. Overall, making the census more legible so it's easier to read when your results come in, and you know how many of a certain object a sample soup produces, which may be helpful to some people.

[calcyman]

I also (independently) implemented the feature to only record unique soup numbers for each object.

I wouldn't bother too much about organising files within directories, since I'm already about halfway through implementing the infrastructure for these results to be stored online (similar to Nathaniel's search).

Although, that said, the database is structured in a hierarchical manner. At the moment results will be stored in 'tabulations' (essentially plaintext blobs of maximum size 1MB, due to technical restrictions). For instance, all of the 18-bit still lifes appearing in asymmetrical B3/S23 searches would be stored in a tabulation with the following key:

Code: Select all

[ Rule:b3s23, Symmetry:C1, Tabulation:xs18 ]

where keys are explained here: https://cloud.google.com/appengine/docs ... e/entities

The main reason for bundling objects in tabulations (for censusing purposes, at least -- there will be separate entities for objects to contain additional data such as glider syntheses and sample soups, for example) is to minimise the number of READ/WRITE operations necessary when consulting and updating censuses, which in turn minimises the cost of running the server*.

* I'm trying to stay within the 50000-operation-per-day free quota, although it's plausible that this may be exceeded depending on the amount of traffic it receives (both online and from apgsearch).

The next version (1.0) of apgsearch is likely to be unbounded (automatically starting a new census every few million soups and uploading the results to the server).

[Gustavo6046]

together with a bunch of .rule files used by the script.

Holi xit! Coding .rule is harder than coding raw binary!

[towerator]

I have a question: once you get your script running, how can you find what are the resulting interesting patterns? Yes, I have tried "s", but it only shows what it found, not how...
Also, how to create mirrored patterns?

[flipper77]

I have a question: once you get your script running, how can you find what are the resulting interesting patterns? Yes, I have tried "s", but it only shows what it found, not how...
Also, how to create mirrored patterns?

To find how apgsearch found a particular object, you must click one of the soup numbers to the right of its canonical representation to obtain the soup it came from. As for retrieving objects from soups before the latest census, here's an updated hashsoup script that not only accepts a symmetry as an input, but it creates an .ini file because I found that can be really useful if you want to keep the root the same.

Code: Select all

# hashsoup.py  Convert soup string to soup
# Extracted from apgsearch.py v0.4, By Adam P. Goucher
# 
# Modified by Arie Paap
# Sept. 2014
#
# More modifications by Richard Schank
# Feb. 2015

import golly as g
import hashlib

# Takes approximately 350 microseconds to construct a 16-by-16 soup based
# on a SHA-256 cryptographic hash in the obvious way.
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:
        rx = 1 - rx
        for x in xrange(0, len(thesoup), 2):
            thesoup.append(thesoup[x]+rx-15)
            thesoup.append(thesoup[x+1])

        for x in xrange(0, len(thesoup), 2):
            thesoup.append(rx-thesoup[x])
            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

# Checks if symmetry is a valid one.
def check(string):
    symmetries = {"C1": [],
                  "C2": ["1", "2", "4"],
                  "C4": ["1", "4"],
                  "D2": ["+1", "+2", "x"],
                  "D4": ["+1", "+2", "+4", "x1", "x4"],
                  "D8": ["1", "4"]}

    if len(string.split("_")) != 2:
        if string == "C1":
            return "C1"
        g.exit("Please enter a valid symmetry.")

    pr, z = string.split("_")
    if symmetries.has_key(pr):
        for part in symmetries[pr]:
            if part == z:
                return string

    g.exit("Please enter a valid symmetry.")

# Converts human-readable symmetry to
# machine-readable symmetry
def convert(sym):
    if sym == "C1":
        return "000000"
    pr, z = sym.split("_")

    if pr == "C2":
        if z == "1":
            return "000110"
        if z == "4":
            return "000220"
        else:
            return "000210"

    if pr == "C4":
        if z == "1":
            return "000001"
        else:
            return "000002"

    if pr == "D2":
        if z[0] == "+":
            return "00%s000" % (z[1:])
        else:
            return "100000"

    if pr == "D4":
        if z[0] == "+":
            ox = int(int(z[1:])/4)+1
            oy = 2-(int(z[1:])%2)
            return "0%d%d000" % (ox, oy)
        if z[0] == "x":
            if z[1:] == "1":
                return "200000"
            else:
                return "300000"

    if pr == "D8":
        if z == "1":
            return "111000"
        else:
            return "122000"

# Input the soup string:
HashsoupINIFileName = g.getdir("data") + "hashsoup.ini"
try:
    f = open(HashsoupINIFileName, "r")
    line = f.readline().split()
    previousroot = line[0]
    previousnum = line[1]
    previoussymm = line[2]
    f.close()
except:
    previousroot = ""
    previousnum = ""
    previoussymm = ""

seed = g.getstring("Enter the desired soup seed:", previousroot, "Soup root string")
if not seed:
    g.exit("Please enter a seed.")
soupnum = g.getstring("Enter soup number:", previousnum, "Soup number string")
if not soupnum:
    g.exit("Please enter a soup number.")
symm = check(g.getstring("Enter symmetry:", previoussymm, "Symmetry"))

g.new("")

r = open(HashsoupINIFileName, "w")
r.write(seed + " " + soupnum + " " + symm)
r.close()

g.setname(seed + soupnum)
g.putcells(hashsoup(seed + soupnum, convert(symm)), 0, 0)

When you mention "mirrored patterns", you obviously mean soups with a certain symmetry, there's a hacked version of apgsearch where I modified some of the code to account for symmetry options with proper notation. Just download the .zip file, and don't change the hashsoup function, I uploaded a version with the fix already in place, just find this line:

Code: Select all

rootstring = g.getstring("What seed to use for this search (make this unique)?", datetime.datetime.now().isoformat()+"_Flipper77")

And replace Flipper77 with whatever you want.

Note: If you didn't already know, the census results pop up when the search is over, using 's' is when you want to generate the census without waiting for it to end.

[Gustavo6046]

Cool but I need PYTHON!

[gameoflifeboy]

In Day and Night, this spaceship supposedly appeared twice:

Code: Select all

x = 9, y = 5, rule = B3678/S34678
2bo$b5o2bo$5ob3o$b5o2bo$2bo!

but the two sample soups given both die:

Code: Select all

x = 16, y = 16, rule = B3678/S34678
2ob4obo2bo2bo$3obo3b5ob2o$o2b2ob5o$2ob2ob2o2bobob2o$2obo4b2ob3obo$2ob
3o6b2obo$ob3obobo2b2ob2o$ob4o2b3o2bo$bo2b4o3b5o$o6b4o4bo$3ob5ob3obo$o
2b2ob2o2b3obo$obobo8b2o$2o4b2o2b2o2b2o$o6b2o$bobob2o3bo4bo!

Code: Select all

x = 16, y = 16, rule = B3678/S34678
3b2o3b2o2bo2bo$b2o2bo2b3ob3o$2b2obo9bo$3ob2obobo2bob2o$o2bo2b3o$bob3o
2b3obo2bo$2b2o2b3o2bobobo$3o4b3o2bob2o$2b2o3bobo2bo2bo$ob3o2bo4b3o$ob
3o6b3obo$2obob6ob2o$ob3obobo2bob3o$o4b5o2bo$2obob6ob4o$b7obo4bo!

If anyone is curious, the seed is 2015-02-04T09:25:28.749000_ and the soup numbers are 1318306 and 1895073.

EDIT: The bug probably appears elsewhere, as soup number 90525 was listed to produce a rocket, but it dies too.

[triller]

Cool but I need PYTHON!

Simply go to:

www.python.org

and you can download a version compatible with your platform (for free).
Install (or extract, I forget) to your hard drive, and when prompted by Golly (when you try to run a script) provide the path to your installed version. Golly will remember the path.

triller

[dvgrn]

EDIT: The bug probably appears elsewhere, as soup number 90525 was listed to produce a rocket, but it dies too.

This is going to be an interesting bug. The other two soups listed as producing rockets actually do produce rockets:

Code: Select all

xq40_0sfvuvfszw1ovo1z0sgpvpgszwcvvvczook…fp2zw37f73  
30107 90525 98304

[wildmyron]

EDIT: The bug probably appears elsewhere, as soup number 90525 was listed to produce a rocket, but it dies too.

This is going to be an interesting bug. The other two soups listed as producing rockets actually do produce rockets:

Code: Select all

xq40_0sfvuvfszw1ovo1z0sgpvpgszwcvvvczook…fp2zw37f73  
30107 90525 98304

Seems to be related to the code which determines the required spacing between ashes for the census, or the code which detects which soup an object came from. The missing ships are produced from the the following soups:

Code: Select all

#C soupid 2015-02-04T09:25:28.749000_90526
x = 16, y = 16, rule = B3678/S34678
3b5obobo2bo$2o2b5ob5o$b2o3b2ob4o2bo$2o5b3o5bo$2bob2obo2b6o$obobo4b2o2b
3o$o3b3o2b2ob3o$3b3obo2b3obo$2obo4b3obo$2ob2o4b6o$8ob2obo2bo$2o3bobobo
2bo$bobob3o3b2o$4o3b2ob3o2bo$ob9obob2o$o3b2o2bob2o2bo!

Code: Select all

#C soupid 2015-02-04T09:25:28.749000_1318307
x = 16, y = 16, rule = B3678/S34678
2b5o2b5o$o5bo2b2ob2o$o4b3o7bo$bob2obo2b3o2b2o$bob3obo6b2o$2b2o4bob2obo
$o2b3ob2ob2obo$4o5b7o$2o2bob2o2bo2b3o$b2ob2ob3ob2o$3o8bo$b2ob2obo4b3o$
b2ob2o2b2obob3o$2b3o3b3o4bo$bo7bo3b3o$2b4ob2o3b2obo!

Code: Select all

#C soupid 2015-02-04T09:25:28.749000_1895063
x = 16, y = 16, rule = B3678/S34678
b4o2b3o2bobo$4o4bobobob2o$3bo2b2o3bobo$bo2b5o3bob2o$ob3o2b3ob2o2bo$2bo
2b5obobo$ob2o2bob5o2bo$2o4bobo3bobo$b2ob5obo2bobo$2ob4o6bo$4ob2o3bobob
2o$4bo2b3ob5o$bo6b2obo2b2o$bo6bob3obo$obo4b3ob2o$3obobo4bob2o!

[Gustavo6046]

Thank you! I finally have Python 2.7 but when I put the python27.dll path Golly simply close itself!

[triller]

Thank you! I finally have Python 2.7 but when I put the python27.dll path Golly simply close itself!

I recently had to reload Golly and had a similar problem.
I actually went back and downloaded an earlier release of Python and it works fine now.
You might check the release notes for Golly to see what is supported.
Not really my area.
triller

[dvgrn]

I actually went back and downloaded an earlier release of Python and it works fine now.
You might check the release notes for Golly to see what is supported.

Python 2.7 works fine on my system, with Golly 2.6. The other thing to check is 32-bit vs. 64-bit, which can certainly cause headaches. Did you download a 32-bit or a 64-bit version of Golly? You can run either one on a 64-bit computer, but you'll have to install a matching 32-bit or 64-bit version of Python. Otherwise they won't work together at all.

[Gustavo6046]

I actually went back and downloaded an earlier release of Python and it works fine now.
You might check the release notes for Golly to see what is supported.

Python 2.7 works fine on my system, with Golly 2.6. The other thing to check is 32-bit vs. 64-bit, which can certainly cause headaches. Did you download a 32-bit or a 64-bit version of Golly? You can run either one on a 64-bit computer, but you'll have to install a matching 32-bit or 64-bit version of Python. Otherwise they won't work together at all.

Sorry but I just downloaded Golly, I can't download Golly for an certain system (32bit, x86 or 64bit) because it doesn't shows the choose!

[dvgrn]

Sorry but I just downloaded Golly, I can't download Golly for an certain system (32bit, x86 or 64bit) because it doesn't shows the choose!

It's worth slowing down and looking at things a little more carefully. The default button for downloading Golly says "32-bit for Windows", so now we know which version of Golly you have. Right under the Download button there's a Browse All Files button, which lets you choose other versions.

But don't go randomly trying other versions yet! Did you install the 32-bit version of Python, or the 64-bit version? What's the name of the Python installation file?

[Gustavo6046]

Downloaded now Golly x64 and it just can't find Python even though I've specified the EXACT path!

[dvgrn]

But don't go randomly trying other versions yet! Did you install the 32-bit version of Python, or the 64-bit version? What's the name of the Python installation file?

Downloaded now Golly x64 and it just can't find Python even though I've specified the EXACT path!

I'm sorry you're having trouble. I asked two questions above, as clearly as I could. I can't diagnose the problem any further until you answer those questions.

Now that you've randomly tried running 64-bit Golly:

1) What was the exact name of the Python installer executable that you downloaded?
2) What is the complete exact path that you specified for Python, including the filename?

But none of this is really relevant to this "apgsearch" thread, which other people might want to use for its intended purpose. If you don't mind, please post any further details on a "Bugs & Errors" thread -- let's say this one.

[Gustavo6046]

But don't go randomly trying other versions yet! Did you install the 32-bit version of Python, or the 64-bit version? What's the name of the Python installation file?

Downloaded now Golly x64 and it just can't find Python even though I've specified the EXACT path!

I'm sorry you're having trouble. I asked two questions above, as clearly as I could. I can't diagnose the problem any further until you answer those questions.

Now that you've randomly tried running 64-bit Golly:

1) What was the exact name of the Python installer executable that you downloaded?
2) What is the complete exact path that you specified for Python, including the filename?

But none of this is really relevant to this "apgsearch" thread, which other people might want to use for its intended purpose. If you don't mind, please post any further details on a "Bugs & Errors" thread -- let's say this one.

1) The name (not an executable) was PythonPortable.zip and
2) the path specified is C:\Python2\App\Python27.dll