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

apgsearch v1.0

For general discussion about Conway's Game of Life.

Re: apgsearch v1.0

Postby gameoflifeboy » March 7th, 2015, 6:31 pm

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.
User avatar
gameoflifeboy
 
Posts: 474
Joined: January 15th, 2015, 2:08 am

Re: apgsearch v1.0

Postby flipper77 » March 10th, 2015, 12:39 pm

Andrew wrote: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:
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.
# 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!
User avatar
flipper77
 
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch v1.0

Postby biggiemac » March 11th, 2015, 5:11 am

dvgrn wrote: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.
Last edited by biggiemac on March 11th, 2015, 4:37 pm, edited 3 times in total.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: apgsearch v1.0

Postby simsim314 » March 11th, 2015, 9:15 am

@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.
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: apgsearch v1.0

Postby towerator » March 11th, 2015, 12:00 pm

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?
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 328
Joined: September 2nd, 2013, 3:03 pm

Re: apgsearch v1.0

Postby flipper77 » March 11th, 2015, 12:14 pm

towerator wrote: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.
User avatar
flipper77
 
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch v1.0

Postby A for awesome » March 11th, 2015, 12:25 pm

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).
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: 1807
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: apgsearch v1.0

Postby flipper77 » March 11th, 2015, 12:45 pm

A for awesome wrote: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.
calcyman wrote:
  • 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.
User avatar
flipper77
 
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch v1.0

Postby simsim314 » March 11th, 2015, 4:28 pm

flipper77 wrote: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?
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: apgsearch v1.0

Postby towerator » March 11th, 2015, 4:58 pm

I can't get hoy you send your data to the catalogue. Is it automatic?
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 328
Joined: September 2nd, 2013, 3:03 pm

Re: apgsearch v1.0

Postby biggiemac » March 11th, 2015, 5:01 pm

towerator wrote: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.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: apgsearch v1.0

Postby Scorbie » March 11th, 2015, 8:57 pm

How does apgsearch deal with growing ships?
x = 9, y = 7, rule = B3/S24568
2b5o$9o$b7o$bo2bo2bo$b7o$bo5bo$bo5bo!
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1379
Joined: December 7th, 2013, 1:05 am

Re: apgsearch v1.0

Postby flipper77 » March 11th, 2015, 9:29 pm

Scorbie wrote: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.
User avatar
flipper77
 
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch v1.0

Postby Scorbie » March 11th, 2015, 9:33 pm

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?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1379
Joined: December 7th, 2013, 1:05 am

Re: apgsearch v1.0

Postby calcyman » March 11th, 2015, 11:30 pm

flipper77 wrote: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/yl1168_1_500_183e3c95ffa1b4f7f55dc5d97da8ddad/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.)
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 2025
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v1.0

Postby codeholic » March 12th, 2015, 6:06 pm

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
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: apgsearch v1.0

Postby biggiemac » March 12th, 2015, 7:20 pm

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:

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%.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: apgsearch v1.0

Postby wildmyron » March 13th, 2015, 11:23 am

biggiemac wrote: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:

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().
The latest version of the 5S Project contains over 47,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron
 
Posts: 1110
Joined: August 9th, 2013, 12:45 am

Re: apgsearch v1.0

Postby towerator » March 13th, 2015, 4:32 pm

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?
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 328
Joined: September 2nd, 2013, 3:03 pm

Re: apgsearch v1.0

Postby Kazyan » March 13th, 2015, 4:43 pm

towerator wrote: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.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 814
Joined: February 6th, 2014, 11:02 pm

Re: apgsearch v1.0

Postby towerator » March 13th, 2015, 5:08 pm

Kazyan wrote:
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.
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 328
Joined: September 2nd, 2013, 3:03 pm

Re: apgsearch v1.0

Postby velcrorex » March 15th, 2015, 12:12 pm

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.
-Josh Ball.
User avatar
velcrorex
 
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: apgsearch v1.0

Postby biggiemac » March 15th, 2015, 10:25 pm

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.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: apgsearch v1.0

Postby flipper77 » March 17th, 2015, 1:51 am

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):
# 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.
Last edited by flipper77 on March 19th, 2015, 2:37 am, edited 1 time in total.
User avatar
flipper77
 
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch v1.0

Postby gameoflifeboy » March 18th, 2015, 3:29 pm

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.
User avatar
gameoflifeboy
 
Posts: 474
Joined: January 15th, 2015, 2:08 am

PreviousNext

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 1 guest