apgsearch v1.0

[gameoflifeboy]

I think the next step for apgsearch should be to search "barely-exploding" rules like b23/s37 by running them in a torus, where every pattern is bound to stabilize eventually. For example, b23/s37 in a 16 by 16 torus usually stabilizes in about 300 gens.
There would also have to be a script for separating oscillators and spaceships, and the hope of discovering new infinite growth patterns would be lost...
Of course I'm not saying every rule should be run in a torus, just the barely-exploding ones.

[flipper77]

I'm more interested in the number of unique objects, and how often such objects are turning up, so I've written the following script:

Code: Select all

Script

...

This script is really useful, but you want to make a small change in the appropriate spot so it can scan symmetries with a "+" in it properly.

Code: Select all

# find all object prefixes
for oprefix in re.findall(r'<a href="/census/' + rule_sym.replace('+', '\+') + '/(.*?)"', census_data):

Note: Literally just used said script a few minutes ago, turns out all 11-bit still lifes have been encountered in the b3s23/C1 census, while only four 12-bit still lifes are yet to be found!

[biggiemac]

For example, what about initial densities other than 50%? It would be a little fiddly to get a guaranteed-random attenuation or thickening of the SHA-256 bit pattern to hit an arbitrary density, but percentages like 25% or 75% should be easy enough -- superimpose a rotated copy of the soup on itself, maybe?

I hacked apgsearch to support 25% and 75% as symmetries, using two hashes per soup and bitwise and/or. I'm running it overnight tonight at 25%. Hope Catagolue will accept this..

I ran a test of 100k soups and it seems to function well locally. What will be needed for this to work with the site?

Edit: It looks like I done goofed with regards to my symmetry naming.. Ending the symmetry with a percent symbol escapes any further path so I can't view my haul online. I will rename it to 25pct and 75pct. I am terribly sorry if this causes any cleanup issues.

Edit2: It saves the correct soup locally but the soups it puts on catagolue are different.. I will try to fix this.
Edit3: Hmm, it is because saving locally calls hashsoup() but posting to catagolue calles hashlib.sha256() directly. How are symmetries handled at all..?
Edit4: No, wait, I was mistaken in edit3. I don't see now why the census that pops up when I quit apgsearch has the correct soups for the links but the one that gets posted to catagolue doesn't.

[simsim314]

@calcyman

Can you provide some access (or API) to the db of the patterns?

I think of few things that I could use:

1. Make queries. Like I'm searching for something capable to function as an eater2 for a while now. It would be nice to query the SLs by some part of it. In general it would be nice to search in bellman output format.

2. It would also be nice to get regular updates - what new objects were found the last x days.

3. Major discovery alert system like new spaceships and/or new periods.

[towerator]

Ok... This time, I'm getting the hang of it, will be posting my first results in a few hours. Can you explain me how does symmetry works?

[flipper77]

Ok... This time, I'm getting the hang of it, will be posting my first results in a few hours. Can you explain me how does symmetry works?

You can go here for an explanation, it's where I explain how the symmetry notation works. For the symmetries starting with "D", those were changed, so that all numbers preceding the underscore(_) would match the order of that particular symmetry.

[praosylen]

Is there any way that the overall census of all object types for a rule/symmetry could be displayed on one page (as opposed to merely 10-cell still lives, period 6 oscillators, etc.)? It is quite irritating to not be able to figure out the overall frequency of all objects without manually going to each census subpage and combining all the totals by hand to figure out relative frequencies of objects. In addition to that, it might be helpful to have census pages for each major type of pattern (still lives, oscillators, spaceships, infinite growth patterns).

[flipper77]

Is there any way that the overall census of all object types for a rule/symmetry could be displayed on one page (as opposed to merely 10-cell still lives, period 6 oscillators, etc.)?

I believe this is the answer you're looking for, it comes from the previous apgsearch thread.

• 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.

You could create a script that could collect the numbers, and display cumulative counts for all objects for a particular census, if you really want to see the statistics that badly. Although, he did mention that he may add the ability to download the results for a census, or something similar.

[simsim314]

You could create a script that could collect the numbers, and display cumulative counts for all objects for a particular census

Why back engineer something Adam has done already? One could make a crawler on Adam's site download all the data and create updatable database from the site pages. But why?

[towerator]

I can't get hoy you send your data to the catalogue. Is it automatic?

[biggiemac]

I can't get hoy you send your data to the catalogue. Is it automatic?

Yes, it is sent automatically when you either quit with q or reach the target number of soups. The results are updated every 2 hours.

[Scorbie]

How does apgsearch deal with growing ships?

Code: Select all

 x = 9, y = 7, rule = B3/S24568
2b5o$9o$b7o$bo2bo2bo$b7o$bo5bo$bo5bo!

[flipper77]

How does apgsearch deal with growing ships?

It handles them by applying a function called linearlyse(), which is a function that handles just about any pattern that exhibits linear growth such as puffers, wickstretchers, guns, and what you just mentioned.

[Scorbie]

So that would mean that the ship would be represented as ylNN, where NN is the lcm of the periods of the front and back ends, right?

[calcyman]

It handles them by applying a function called linearlyse(), which is a function that handles just about any pattern that exhibits linear growth such as puffers, wickstretchers, guns, and what you just mentioned.

Indeed -- here's a growing spaceship which appeared in Josh Ball's recent explorations:

http://catagolue.appspot.com/object/yl1 ... d/b3s24568

(Okay, it's the same one you posted. But my point still stands.)

So that would mean that the ship would be represented as ylNN, where NN is the lcm of the periods of the front and back ends, right?

Or some divisor thereof, yes. (In particular, if the growing spaceship is glide-reflective, then it will only register half of the traditional definition of period.)

[codeholic]

One item for the wish list: a button on a certain object's page that would notify the authenticated user by email (or either way) when it shows up in any soup, e. g. http://catagolue.appspot.com/object?apg ... rule=b3s23

[biggiemac]

Woot, 7 billion C1 soups in catagolue!

So I have enabled two new symmetries and Adam provided the support for them in his back-end Java code: they are 25pct and 75pct, the terminology being the expected density of ON cells. To enable them, change the string of accepted symmetries to include the strings "25pct" and "75pct"; a search for "8x32" (with the quotes) will take you to the line, and modify hashsoup() as follows, everything not in this block unchanged:

Code: Select all

def hashsoup(instring, sym):

    s = hashlib.sha256(instring).digest()
    s2 = hashlib.sha256("hackme" + instring).digest()

    thesoup = []

    if sym in ['D2_x', 'D8_1', 'D8_4']:
        d = 1
    elif sym in ['D4_x1', 'D4_x4']:
        d = 2
    else:
        d = 0

    for j in xrange(32):

        t = ord(s[j])
        if (sym == '25pct'): # Bitwise AND to mask out roughly half the ON bits
            t = t & ord(s2[j])
        elif (sym == '75pct'): # Bitwise OR to turn on roughly half the OFF bits
            t = t | ord(s2[j])

        for k in xrange(8):

Thanks to the great properties of sha256 it doesn't have any systematic shortcomings, and it now enables targeting lower- or higher- density soups rather than an expected density of 50%.

[wildmyron]

So I have enabled two new symmetries and Adam provided the support for them in his back-end Java code: they are 25pct and 75pct, the terminology being the expected density of ON cells. To enable them, change the string of accepted symmetries to include the strings "25pct" and "75pct"; a search for "8x32" (with the quotes) will take you to the line, and modify hashsoup() as follows, everything not in this block unchanged:

Code: Select all

def hashsoup(instring, sym):

    s = hashlib.sha256(instring).digest()
    s2 = hashlib.sha256("hackme" + instring).digest()

    thesoup = []

    if sym in ['D2_x', 'D8_1', 'D8_4']:
        d = 1
    elif sym in ['D4_x1', 'D4_x4']:
        d = 2
    else:
        d = 0

    for j in xrange(32):

        t = ord(s[j])
        if (sym == '25pct'): # Bitwise AND to mask out roughly half the ON bits
            t = t & ord(s2[j])
        elif (sym == '75pct'): # Bitwise OR to turn on roughly half the OFF bits
            t = t | ord(s2[j])

        for k in xrange(8):

Thanks to the great properties of sha256 it doesn't have any systematic shortcomings, and it now enables targeting lower- or higher- density soups rather than an expected density of 50%.

Is this going to be the official hashsou() for these symmetry options? I ask because if the "hackme" string doesn't make it into the official version then it won't be possible to determine the soups from the soup id (with the official version of hashsoup().

Also, the second call to sha256 is only necessary when using the new symmetry options, so it's probably worth hiding behind an if().

[towerator]

I have a rather beefy computer, but for some reasons individual searches don't go much further than 250 soups/s. Meanwhile, I can easily run 4 of them (possibly more) without experimenting any lag. Do you know the origin of this problem?

[Kazyan]

I have a rather beefy computer, but for some reasons individual searches don't go much further than 250 soups/s. Meanwhile, I can easily run 4 of them (possibly more) without experimenting any lag. Do you know the origin of this problem?

apgsearch does not currently support running a single search on multiple CPU cores. What you're doing by running more searches is applying different copies of apgsearch to different cores, and it sounds like you're running a quad-core computer or better, so you can run 4 searches.

[towerator]

apgsearch does not currently support running a single search on multiple CPU cores. What you're doing by running more searches is applying different copies of apgsearch to different cores, and it sounds like you're running a quad-core computer or better, so you can run 4 searches.

Then it's about time to use my 5th core.

[velcrorex]

On the page for a rule where you select the symmetry, could that page have information on how many soups have been searched for each symmetry? For example on this page it might be nice to know which symmetries have been neglected without clicking every link and comparing soup counts.

[biggiemac]

Would it be possible to have oscillators sub-categorized by rotor? The xp2 pages are a bit overwhelming in their current state (particularly for D8) and if xpN linked to a list of rotors it would be easier to see the variation. From there it could hold links to the stators that have been found for each rotor.

[flipper77]

I've made another change to Andrew's script that finds new unique objects, this time I've added a sorting function to it so that both the .txt file and html file are sorted according to type(still life, oscillator, spaceship, oversized etc.), then by prefix number, then by lexicographical order(EDIT: I've changed the script in accordance to an amazing change to catagolue that speeds the script up drastically):

Code: Select all

# Scan pages at http://catagolue.appspot.com to determine the number of
# unique objects found for a specified rule and symmetry.

# NB. Doesn't detect new zz_LINEAR objects.

import golly as g
import urllib2
import re

census_prefix = 'http://catagolue.appspot.com/textcensus/'
object_prefix = 'http://catagolue.appspot.com/object?apgcode='

def obj_sort(obj):
    alpha = 'abcdefghijklmnopqrstuvwxyz'
    numeric = '0123546789'
    sort_order = ['ov', 'xs', 'xp', 'xq',\
                  'yl', 'zz', 'PATHOLOGICAL']

    cat, ch, details = obj.partition('_')
    main = sort_order.index(cat.rstrip(numeric))
    prenum = cat.lstrip(alpha)
    try:
        int(prenum)
        middle = prenum.zfill(4) + ch
    except:
        middle = ''

    return (alpha[main] + middle + details)

# prompt for rule and symmetry
inifile = g.getdir('data') + 'scan-catagolue.ini'
rule_sym = 'b3s23/C1'
try:
    f = open(inifile, 'r')
    rule_sym = f.readline()
    f.close()
except:
    # should only happen 1st time (inifile doesn't exist)
    pass

rule_sym = g.getstring('Enter the desired rule and symmetry\n' +
                       '(eg. b3s23/C1):', rule_sym, 'Enter rule/symmetry')
if len(rule_sym) == 0:
    g.exit()

# remember specified rule/symmetry for next time
try:
    f = open(inifile, 'w')
    f.write(rule_sym)
    f.close()
except:
    g.warn('Unable to save rule and symmetry in file:\n' + inifile)

objfile = g.getdir('data') + 'catagolue-' + rule_sym.replace('/','-') + '.txt'
old_objects = []

# loads previous objects
try:
    f = open(objfile, 'r')
    contents = f.readlines()
    f.close()
    g.show('Reading previous file...')
    for line in contents:
        old_objects.append(line.partition('\n')[0])
except:
    # should only happen 1st time
    pass

url = urllib2.urlopen(census_prefix + rule_sym)
census_data = url.read()

htmlfile = g.getdir('temp') + 'obj.html'
f = open(htmlfile, 'w')
f.write('<html>\n<title>' + rule_sym + '</title>\n<body>\n')
f.write('<p>Object prefixes and counts...<br>\n')

obj_names = []
new_objects = []
ocount = 0

page = census_prefix + rule_sym
url = urllib2.urlopen(page)
obj_data = url.readlines()
ocount = len(obj_data) - 1
types = {}

# scans text census page
g.show('Scanning census data...')
for line in obj_data:
    obj_name, num = map(lambda arg: arg.strip('"'), line.split(','))
    
    # ignore first line
    if obj_name == 'apgcode':
        continue
    type = obj_name.split('_')[0]
    if types.has_key(type):
        types[type] += 1
    else:
        types[type] = 1
    obj_names.append(obj_name)
    if obj_name not in old_objects:
        new_objects.append(obj_name)

for type in sorted(types.keys(), key=obj_sort):
    f.write(type + ' : ')
    f.write(str(types[type]) + '<br>\n')

# save all object names in a text file
ofile = open(objfile, 'w')
g.show("Writing objects to file...")
for obj in sorted(obj_names, key=obj_sort):
    ofile.write(obj + '\n')
ofile.close()

g.show("Linking new objects...")
f.write('</p><p>Total number of objects: ' + str(ocount))

if len(new_objects) > 0:
    f.write('</p><p>New objects have been found since last scan:<br>')
    rule = rule_sym.partition('/')[0]
    for obj in sorted(new_objects, key=obj_sort):
        # show link to object in Catagolue
        f.write('<a href="' + object_prefix + obj + '&rule=' + rule + '">' + obj + '</a><br>\n')
elif len(old_objects) > 0:
    f.write('</p><p>(No new objects found since last scan.)')

f.write('</p><p>All object names are saved in <a href="edit:' + objfile + '">' + objfile + '</a>')
f.write('</p></body>\n</html>\n')
f.close()

g.show('Done')

g.open(htmlfile)

This way, at least the html window displays objects in an order that's much easier to read(and the .txt file for whatever reason). It would be good if not only the census page was sorted this way, but also the hauls, specifically for objects which share number of occurrences because I also get mislead when the last few objects are specific rare 9-bit SLs, since I expect the largest SLs, rarest oscillators, or rarest spaceships to appear at the end.

[gameoflifeboy]

Now that Calcyman has added a feature to display long lists of objects on multiple pages, perhaps we can have a list of all objects of a particular rule and symmetry in order of frequency finally?
Also, instead of displaying the most popular rule/symmetry combinations, maybe we can have a list of the most popular rules, which when clicked on lead to a list of symmetries.