Enumerating Three-Glider Collisions

For scripts to aid with computation or simulation in cellular automata.
User avatar
Hdjensofjfnen
Posts: 1721
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Enumerating Three-Glider Collisions

Post by Hdjensofjfnen » July 22nd, 2018, 7:52 pm

What about this?

Code: Select all

x = 24, y = 13, rule = B3/S23
7bo14bo$8bo14bo$6b3o12b3o3$4b2o13b2o$5b2o13b2o$4bo14bo2$2o$b2o12b2o$o
15b2o$15bo!

Code: Select all

x = 5, y = 9, rule = B3-jqr/S01c2-in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

carsoncheng
Posts: 147
Joined: June 11th, 2022, 11:24 pm

Re: Enumerating Three-Glider Collisions

Post by carsoncheng » July 23rd, 2022, 8:52 pm

There has been some discussion yesterday on the wiki talk page of "3-glider collisions" (https://conwaylife.com/wiki/Talk:3-glider_collision), and I would like to ask some of those questions about the 3-glider database on the forums.

1.
GUYTU6J wrote:
July 23rd, 2022, 12:21 pm
After recognizing subtleties in interactions, an enumeration was done by 2718281828 in late 2017; the resulting database contains 464745 entries and has been used widely since then. However, many entries are practically duplicated results up to rotation, reflection and evolution, so the total number should not be cited as a precise count. No attempt to reproduce the result, verify exhaustiveness, purge duplicates or adaption to new organization has been made for the data.
Is this statement true?

2. Regarding the completeness of the database:
GUYTU6J wrote:
July 23rd, 2022, 10:04 am
I cannot see a substantiated proof that the enumeration of "interesting" results is complete. (Dvgrn used "fairly", which is not guarantee.)
Is this statement true?
Last edited by carsoncheng on July 23rd, 2022, 8:56 pm, edited 1 time in total.

hotdogPi
Posts: 1063
Joined: August 12th, 2020, 8:22 pm

Re: Enumerating Three-Glider Collisions

Post by hotdogPi » July 23rd, 2022, 8:55 pm

I remember a number that's around 190,000, which I believe is the list with the duplicates removed.
User:HotdogPi/My discoveries

Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉟,㊱,㊳S,㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,70,72,74S,75,76S,80,84,90,96,100,102S,108,110,112,114G,116,117G,120,126G,128,138,147,154,156,180,196S,217,486,576

S: SKOP
G: gun

carsoncheng
Posts: 147
Joined: June 11th, 2022, 11:24 pm

Re: Enumerating Three-Glider Collisions

Post by carsoncheng » July 23rd, 2022, 8:58 pm

hotdogPi wrote:
July 23rd, 2022, 8:55 pm
I remember a number that's around 190,000, which I believe is the list with the duplicates removed.
Could you access the script which is used to remove duplicates? If so, the result can be reproduced and added to LifeWiki.

User avatar
dvgrn
Moderator
Posts: 9103
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » July 25th, 2022, 2:40 pm

It's also not at all guaranteed that 2718281828's enumeration has at least one entry for every glider collision that should be considered unique. Didn't someone find a 3G collision in the last year or two, with output that didn't show up in a synthesise-patt.py or synth-const-4G.py search?

There are certainly examples like this one that aren't represented in the current 3G databases. The example there seems like it's definitely a "non-trivial" example, because the initial two-glider explosion interacts at T=439 with the secondary explosion in the northeast an output glider plus the third glider.

If you keep moving the third glider northward two steps at a time, I think pretty soon you'll get to where you always get the same population, just with the two blobs of ash at different distances from each other. Maybe all of those collisions, with Blob1+[Blob2 at some distance away], should count as a single 3G collision. But until that point is reached, it seems like each 3G crash might possibly be a source of novelty.

User avatar
EvinZL
Posts: 624
Joined: November 8th, 2018, 4:15 pm
Location: A tungsten pool travelling towards the sun
Contact:

Re: Enumerating Three-Glider Collisions

Post by EvinZL » August 11th, 2022, 2:12 pm

dvgrn and I were briefly talking about on Discord how we should build a 3g collision search that uses octohashes to determine matches.

To do so, you would:
  1. Download https://github.com/dvgrn/octohash
  2. Replace 12x12-1G-octohash/collisions-for-fingerprints-12x12-455380.txt by https://github.com/dvgrn/glider-collisi ... es.txt.bz2 (after unzipping)
  3. Fix the paths in 12x12-1G-octohash/fingerprint-Python3.py
  4. Run 12x12-1G-octohash/fingerprint-Python3.py in Golly
  5. Find out why it isn't working
  6. Define fingerprintfile in 12x12-1G-octohash/split-octohash-file.py
  7. Replace 45538 by 46475
  8. Run 12x12-1G-octohash/split-octohash-file.py
  9. Fix paths in 12x12-1G-octohash/find-octohash-Python3.py
  10. Use octohash
Unfortunatedly, I couldn't do step 5.

NOTE to dvgrn: I did use the correct file
Last edited by EvinZL on August 11th, 2022, 2:33 pm, edited 1 time in total.

User avatar
dvgrn
Moderator
Posts: 9103
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » August 11th, 2022, 2:26 pm

EvinZL wrote:
August 11th, 2022, 2:12 pm
dvgrn and I were briefly talking about on Discord how we should build a 3g collision search that uses octohashes to determine matches.
...
Unfortunatedly, I couldn't do step 5.
This looks like a very good start. But in step 2 you linked to colseqs.txt.bz2, whereas I think you'd need to be using rles.txt.bz2 -- right?

Might that have anything to do with the step-5 stumbling block? I haven't tried to look any farther at what kind of specific formatting the fingerprint-Python3.py script might be expecting -- maybe there's some adjustment needed there.

The general idea is that it's going to be necessary to re-generate the colseqs.txt file and make it a lot bigger, using 10-character octohashes (9 characters with a space delimiter, encoding the first 7 bytes of SHA256 hash) -- instead of the single-byte population-based hashes that are in there at the moment.

Side note: it might be a good idea to use the hash-generating code from the octo3obj project, instead of from the octohash project. I already don't remember the details, but I'm pretty sure there was some annoying reason why the generating code wasn't exactly the same...!

Side side note: there are still very much faster ways of calculating these kinds of hashes, via lifelib for example, without losing the nice feature of the search script remaining Golly Python only with no dependency on lifelib. But it's more complicated and the required code is not already lying around waiting to be used... and the plan EvinZL has posted should work fine, just needing an overnight run instead of just an hour or two.

EDIT 8/15/2022: Sounds like the "octo3g" hash-recording process is complete, so now the results are being uploaded somewhere. (?)

User avatar
EvinZL
Posts: 624
Joined: November 8th, 2018, 4:15 pm
Location: A tungsten pool travelling towards the sun
Contact:

Re: Enumerating Three-Glider Collisions

Post by EvinZL » August 15th, 2022, 3:47 pm

It is, indeed, complete. The files can be found at https://drive.google.com/drive/folders/ ... sp=sharing. Warning: there are 20 octohash files instead of 10.

User avatar
dvgrn
Moderator
Posts: 9103
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » August 16th, 2022, 4:04 pm

EvinZL wrote:
August 15th, 2022, 3:47 pm
It is, indeed, complete. The files can be found at https://drive.google.com/drive/folders/ ... sp=sharing. Warning: there are 20 octohash files instead of 10.
It took me a while to figure out that the old octohash hash-generating code was used to generate the hash files, instead of the new octo3obj function. It was probably a bad idea for me to ever allow there to be two different versions of that function, but I remember having some kind of reasonable reason at the time.

Anyway, here's a script that works for me to look through EvinZL's new 3g-collision hash files. This means, for example, that I can find out that there are 54 "vanish collisions" in the 3g database that have a final obo$obo! spark, but only three collisions that end with a final o2bo$o2bo!

Code: Select all

# find-octo3g.py
# Dave Greene, 15 August 2022 (Golly Python3)
######## Download hash files from https://drive.google.com/drive/folders/1l6TQEgNpXpFd6ATU7Tgrf7k-76MJcVi3
######## Then update line 10 below with your chosen location for the downloaded files

import golly as g
import hashlib


basepath = "C:/path/to/3g/hashes/"  ###### UPDATE THIS TO MATCH YOUR DOWNLOAD LOCATION

searchfiles = "octohashes3g_0.txt,octohashes3g_1.txt,octohashes3g_2.txt,octohashes3g_3.txt,octohashes3g_4.txt," + \
              "octohashes3g_5.txt,octohashes3g_6.txt,octohashes3g_7.txt,octohashes3g_8.txt,octohashes3g_9.txt," + \
              "octohashes3g_10.txt,octohashes3g_11.txt,octohashes3g_12.txt,octohashes3g_13.txt,octohashes3g_14.txt," + \
              "octohashes3g_15.txt,octohashes3g_16.txt,octohashes3g_17.txt,octohashes3g_18.txt,octohashes3g_19.txt"
searchlist = searchfiles.split(",")

NUMLINES = 464746

chardict = {}
for i in range(37, 127):
  chardict[i-37] = chr(i)

chardict[92-37] = "!"  # backslash
chardict[39-37] = "#"  # apostrophe
chardict[44-37] = "$"  # comma

def get9char(inputstr):
  h = hashlib.sha1()
  h.update(inputstr.encode())
  i = 0  # convert first seven bytes of SHA1 digest to an integer
  for char in h.digest()[:7]:
    i = i*256 + char
  s = ""
  while len(s)<9:
    d = i//90
    r = i - d*90
    s = chardict[r] + s
    i = (i - r) // 90   
  return s

def getoctohash(clist):
  ptr = 0
  g.new("Octotest"+str(count))
  for orientation in [[1,0,0,1],[0,-1,1,0],[-1,0,0,-1],[0,1,-1,0],[-1,0,0,1],[1,0,0,-1],[0,1,1,0],[0,-1,-1,0]]:
    g.putcells(clist,ptr*2048,0,*orientation)
    ptr += 1
  for j in range(8):
    g.select([2048*j-1024,-1024,2048,2048])
    g.shrink()
    r = g.getselrect()
    if r == []: r = [0,0,1,1]
    pat = g.getcells(r)
    deltax, deltay = 0, 0
    if pat != []:
      deltax, deltay = -pat[0], -pat[1]
    if j==0:
      minstr = str(g.transform(pat, deltax, deltay))
    else:
      strpat = str(g.transform(pat, deltax, deltay))
      if  strpat < minstr:
        minstr = strpat
  return " " + get9char(minstr)

g.setalgo("HashLife")
g.setrule("B3/S23")

try:
  g.fitsel()
except:
  pass
r = g.getselrect()
if r==[]:
  r = g.getrect()
  if r==[0]:
    g.exit("No pattern found to search for.")
  g.select(r)

count = NUMLINES
outptr = 0
pat = g.getcells(r)

g.addlayer()  # do tests in a new layer, then put results there
hash = getoctohash(pat)
g.new("Output")
g.putcells(pat,-pat[0]-128,-pat[1])
g.fit()
g.update()

for fingerprintfile in searchlist:
  with open(basepath+fingerprintfile, "r") as f:
    for line in f:
      count -= 1
      if hash in line:
        matchingpat = line[:line.index(" ")]
        g.putcells(g.parse(matchingpat),outptr*64,0)
        outptr+=1
        g.fit()
        g.update()
      if count % 1000 == 0:
        g.show("Searching.  Lines remaining: " + str(count/1000) + "K lines.")
plural = "" if outptr==1 else "s"
g.show("Found " + str(outptr) + " line" + plural + " matching " + hash + " in " + str(NUMLINES) + " lines of the octo3obj database.")
The old synthesise-patt.py either gives no results at all, or lots of false positives, in any case like this where a recognizable population sequence can't be generated for the target pattern -- so this is a huge improvement on what we had before.

EDIT: Created a octo3g git repo for the above code. The current download location for the roughly one gigabyte of hash files is given in the script comments. Many of the individual files are over GitHub's "warning level" of 50MB, so I'm not too inclined to attempt to check in such oversized files into the repo at the moment. Maybe if they were split into a total of 37 or so files of less than 30MB each, it might be worth it? -- along with adding octohash files for the 4G collisions used by synth-const-4G-Python3.py.

That last item should be pretty easy, so I'll probably take care of that in the next week or so if nobody else gets to it first.

We still definitely need versions of these octo* search scripts, that mark where the output pattern is in each search result, and rotate/reflect each search result so they're all in the same orientation and lined up, and maybe (optionally?) show the full LifeHistory reaction envelope as well. That's really not a particularly painful programming effort, though it will be slow for cases where thousands of results are being displayed, so we might need an option to turn off that reorienting/post-processing functionality.

Post Reply