For scripts to aid with computation or simulation in cellular automata.
biggiemac
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: Script request thread

Well, we would have to find a meaningful way to enumerate such patterns.

So the idea with "spatially connected" is that, while building up a pattern cell by cell, every new cell has to be at most 2 away from the current pattern, to have an effect on its cells in the very next generation? Meaning something like two R-pentominos 15 cells apart that interact eventually but not immediately wouldn't be part of the enumeration?

I like the idea, but you should note that surprisingly many interesting patterns don't fall under the category of "spatially connected" in any phase. Look at the two smallest glider guns, for example.
Physics: sophistication from simplicity.

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: Script request thread

biggiemac wrote:Well, we would have to find a meaningful way to enumerate such patterns.

So the idea with "spatially connected" is that, while building up a pattern cell by cell, every new cell has to be at most 2 away from the current pattern, to have an effect on its cells in the very next generation? Meaning something like two R-pentominos 15 cells apart that interact eventually but not immediately wouldn't be part of the enumeration?

I like the idea, but you should note that surprisingly many interesting patterns don't fall under the category of "spatially connected" in any phase. Look at the two smallest glider guns, for example.
I think that as long as the objects interact at some point, they should be counted. However, this might cause problems with 8+ cell patterns because of this:

Code: Select all

x = 30, y = 30, rule = B3/S23
o$b2o$2o27$27b3o!  Maybe something could check if the objects are just reoccurrances of a previous pattern, but I don't know. \100\97\110\105 biggiemac Posts: 504 Joined: September 17th, 2014, 12:21 am Location: California, USA Re: Script request thread drc wrote: I think that as long as the objects interact at some point, they should be counted. That makes the enumeration you are hoping for impractical if not impossible. 3-glider collisions haven't even been searched exhaustively due to the combinatorial explosion of G + methuselah possibilities - for example, the 4-glider synthesis thread opens with a new 3-glider collision to bi-pond, not discovered until 2014. drc wrote: Maybe something could check if the objects are just reoccurrances of a previous pattern, but I don't know. I can't imagine doing that efficiently in a program designed to be as fast as apgsearch. Assuming the combinatorial explosion of configurations, such a check would need to store the set of "previous patterns" in memory, which would blow up. It wouldn't make it very far before grinding to a halt or running out of resources. Maybe someone can find a balance between the not-very-interesting 2-cell neighborhood enumeration and the impractical anything-that-interacts enumeration to give a useful program. I'm not seeing it at the moment though. Physics: sophistication from simplicity. Gamedziner Posts: 795 Joined: May 30th, 2016, 8:47 pm Location: Milky Way Galaxy: Planet Earth Re: Script request thread Request: Script that randomly gives starting locations and directions to glider guns (although spaced apart so they don't destroy each other immediately). This could be useful to discovering new glider-constructible ships with guns already being made available from the beginning. Code: Select all x = 81, y = 96, rule = LifeHistory 58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!


gmc_nxtman
Posts: 1149
Joined: May 26th, 2015, 7:20 pm

Re: Script request thread

I would like to request a python script in golly that functions as follows:

•Select a pattern
•Click the script, and paste in an rle
•The script searches if that subpattern is in the current selection

This would be useful for glider-synthesis collections, etc.

dvgrn
Moderator
Posts: 7196
Joined: May 17th, 2009, 11:00 pm
Contact:

Re: Script request thread

gmc_nxtman wrote:I would like to request a python script in golly that functions as follows:

•Select a pattern
•Click the script, and paste in an rle
•The script searches if that subpattern is in the current selection
There are several existing scripts along those general lines. I posted a find-object.py a couple of years ago, which you could use as you describe, if you paste the search object into the universe and then select it before running the script.

As the notes say, though, this is really good at finding false positives in big blocks of ON cells. Luckily big blocks of ON cells are rather rare. If you want to do better you can add a test for the OFF cells within one diagonal cell of any ON cell.

If I remember correctly, I implemented the nearby-OFF-cells trick in the recognizer script that I've been using off and on to reduce chris_c's G-to-W-to-G megapattern. A little inspired borrowing of code from that project should produce exactly what is wanted.

Anyone up for the challenge? I have a couple of dozen items on my Life to-do list before this, just at the moment... Better yet, write something more efficient from the ground up, instead. My Python code is likely to be near-unreadable to anyone who is used to good modern object-oriented style, and so it's probably not really worth salvaging.

Scorbie
Posts: 1466
Joined: December 7th, 2013, 1:05 am

Re: Script request thread

I wrote something along these lines too. It lets you specify the ON cells and OFF cells of the target pattern (inside the script, but I think you could change that trivially.)
viewtopic.php?f=9&t=1536&p=26327#p26327

Very unfortunately, I think my code isn't too pretty either. At least I documented it a bit and the project is smaller and less ambitious than dvgrn's, so I guess you would have less code to read.

EDIT: Actually, you would only have to see the function matchtarget(), and how the patterns are defined. (And maybe how I made the program a little faster by grouping the pattern into blobs.)

EDIT: Sorry to dvgrn for not replying that for so long... I have ran your code but haven't looked through it enough. But I think rewriting the script to lua would make the scripts faster, I think... (One think that may make lua version slower: I am not sure if there is a way to convert the lua cells to coordinates, fast.)
Best wishes to you, Scorbie

muzik
Posts: 3910
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Script request thread

I want to see a script that can generate mashup rules such as Rainbow.

Preferably so I can generate rules like this easily, without needing to do any of the manual work.
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Script request thread

Can we have a script that translate kcode notation into golly ruletable?

EDIT: bprentice used a java script to accomplish the equivalent.

v3k4_mph.rule
input:systematic name:v3k4_002210002201212
output:ruletable

Code: Select all

@RULE v3k4_002210002201212
@COLORS

0 0 0 0
1 0 155 155
2 200 200 0
3 200 0 200

@TABLE
n_states:3
neighborhood:vonNeumann
symmetries:permute

var a={1}
var b={2}

var d={0}

var j={0,1,2,1}

j,d,d,d,d,d
j,d,d,d,a,d
j,d,d,a,a,b
j,d,a,a,a,b
j,a,a,a,a,a

j,b,d,d,d,d
j,b,a,d,d,d
j,b,a,a,d,d
j,b,a,a,a,b

j,b,b,d,d,b
j,b,b,a,d,d
j,b,b,a,a,a

j,b,b,b,d,b
j,b,b,b,a,a

j,b,b,b,b,b

##old stuff overwritten

j,0,0,0,0,0
j,0,0,0,1,0
j,0,0,1,1,1
j,0,1,1,1,2
j,1,1,1,1,2

j,2,0,0,0,2
j,2,1,0,0,0
j,2,1,1,0,2
j,2,1,1,1,1

j,2,2,0,0,0
j,2,2,1,0,0
j,2,2,1,1,2

j,2,2,2,0,2
j,2,2,2,1,0

j,2,2,2,2,2


Last edited by shouldsee on September 29th, 2016, 7:06 am, edited 1 time in total.

Rhombic
Posts: 1067
Joined: June 1st, 2013, 5:41 pm

Re: Script request thread

Script that calculates a number of gliders to be fired at a selected pattern to yield a non-zero number of spaceships, no static ash (so 0 still lifes, 0 oscillators... only spaceships)

If possible, it would be great if the script allowed non-CGoL rules with gliders to be explored too (just like glider-destruction.py)
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Script request thread

biggiemac wrote:This'll probably work. I tested it for spaceships, still lives and oscillators. Just select a rectangle in golly containing only the pattern you care about (plus any amount of empty space) and the apgcode of the object will go to your clipboard. As a side effect, the script makes a new layer.

You can certainly get nonsense out of it, by selecting an active object or multiple disjoint objects. But if you use it well it'll do the right thing.
There appears to be a bug somewhere. The following object from jslife (o0124.lif, 1st row, 2nd object) gets assigned a wrong (and nonsensical) code:

Code: Select all

x = 69, y = 75, rule = B3/S23
11$38b2ob2o$37bobobo$36bo4bo$36bob2o2b2o$34bobob2o4bo$33bobobo2b2ob2o$33bobobo2b2o$34bobob2o3b2o$36bobo2b2obo$36bo2bo2bo$34b2o3bob2o$33bo2b
3o2bob2obo$34b2o7bob2o$35bob2obobo$35bobo3bo$34b2obo$36bob4o$36bo3b2o
3b2o$37bo7bo$21bo16bo4bobo$20bobo20b2o10b2o$21bo33bobo$52b2obobo$19b5o
28bobobo$18bo4bo30bo$17bo2bo32b2o$14bo2bob2o31b3o$13bobobo5bo28b3o$14b o2bo4bobo27b3o$17b2o2bo2bo28b2o$22b2o8b3o19bo$30b2o2bo17bobobo$30bo2b 2o17b2obobo$30b3o22bobo$55b2o2$34bo$33bo$34bo$44b2o$39b4o2bo$38bo4b2o$
45b3o$37b2o3bobo2bo$36bo4bo3b2o$35b2o$35b2o$32b2ob2ob2o$32bo2bo5b2o$33bobobo4bo$34bo5bo$35b2obobo$36bobobobo$35bo2b2obobo$35b2o4bobo$41b2o !  apgcode produced by the script (linebreaks added for readability): Code: Select all xq1_y9g8970rp2s0gzy9d5ob3kc3s343zy764269j81aq2t52zy74s0g0662i9611y8gz697 o4cy311yfo9a98gzxvveybgwgoy3o48g32gv04a4zcis346ya78054gia0hex11zy8ggy71z y6ckla29111a8gzybo8044g7v0kczyao4o78e0mq1zyb11  If you speak, your speech must be better than your silence would have been. — Arabian proverb Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_ Proud member of the Pattern Raiders! dvgrn Moderator Posts: 7196 Joined: May 17th, 2009, 11:00 pm Location: Madison, WI Contact: Re: Script request thread Apple Bottom wrote:There appears to be a bug somewhere. The following object from jslife (o0124.lif, 1st row, 2nd object) gets assigned a wrong (and nonsensical) code: Code: Select all x = 69, y = 75, rule = B3/S23... Does it have to do with the size limitation on apgcodes? I've tried bending that rule, and the results have never been very good... well, of course you can extend the height with no problem, but I seem to recall that weird things are likely to happen above width 40. Apple Bottom Posts: 1034 Joined: July 27th, 2015, 2:06 pm Contact: Re: Script request thread dvgrn wrote: Apple Bottom wrote:There appears to be a bug somewhere. The following object from jslife (o0124.lif, 1st row, 2nd object) gets assigned a wrong (and nonsensical) code: Code: Select all x = 69, y = 75, rule = B3/S23... Does it have to do with the size limitation on apgcodes? I've tried bending that rule, and the results have never been very good... well, of course you can extend the height with no problem, but I seem to recall that weird things are likely to happen above width 40. I'm not sure it's that. The script regularly breaks on larger objects, but when it does it always throws an error message instead, like this: Code: Select all Traceback (most recent call last): File "<string>", line 1, in <module> File "apgcode.py", line 113, in <module> canonise() File "apgcode.py", line 43, in canonise representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0], rect[1]+rect[3]-1, 1, 0, 0, -1)) File "apgcode.py", line 89, in canonise_orientation representation += chars[zeroes - 4] IndexError: string index out of range  Without having looked at the code, I think this is due to a long runs of zeros (40+). (See this thread.) There doesn't seem to be a hard limit on the size of the bounding box, so long no such run occurs in any phase/orientation of the object; all larger objects I've used the script on so far have either failed to encode (as above), or yielded a code that looked sensible and that had the correct object type and period at the very least. If you speak, your speech must be better than your silence would have been. — Arabian proverb Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_ Proud member of the Pattern Raiders! A for awesome Posts: 2105 Joined: September 13th, 2014, 5:36 pm Location: Pembina University, Home of the Gliders Contact: Re: Script request thread Apple Bottom wrote:There appears to be a bug somewhere. The following object from jslife (o0124.lif, 1st row, 2nd object) gets assigned a wrong (and nonsensical) code: Code: Select all rle apgcode produced by the script (linebreaks added for readability): Code: Select all xq1_y9g8970rp2s0gzy9d5ob3kc3s343zy764269j81aq2t52zy74s0g0662i9611y8gz697 o4cy311yfo9a98gzxvveybgwgoy3o48g32gv04a4zcis346ya78054gia0hex11zy8ggy71z y6ckla29111a8gzybo8044g7v0kczyao4o78e0mq1zyb11  It's not nonsensical; Catagolue, at least, parses it correctly when xq1 is changed to xp0: praosylen#5847 (Discord) 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}$$ Apple Bottom Posts: 1034 Joined: July 27th, 2015, 2:06 pm Contact: Re: Script request thread A for awesome wrote:It's not nonsensical; Catagolue, at least, parses it correctly when xq1 is changed to xp0: True. I meant nonsensical as that it's not an xq1 (and there's no such thing in Conway Life to begin with). The above isn't the only pattern in jslife triggering this, BTW. The first object in o0030-gun.lif also does, for instance: Code: Select all x = 45, y = 35, rule = B3/S23 4$28bo$27b4o$10b2o14b2obobo$2bo7bo2bo11b3obo2bo2b2o$bo3b2o7bo11b2obobo
3b2o$bo5bo6bo12b4o$2b5o7bo7bo5bo$10bo2bo9bo$10b2o9b3o15$38b2o$38bobo$40bo$40b2o!

If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

gmc_nxtman
Posts: 1149
Joined: May 26th, 2015, 7:20 pm

Re: Script request thread

Apple Bottom wrote:
A for awesome wrote:It's not nonsensical; Catagolue, at least, parses it correctly when xq1 is changed to xp0:
True. I meant nonsensical as that it's not an xq1 (and there's no such thing in Conway Life to begin with).

The above isn't the only pattern in jslife triggering this, BTW. The first object in o0030-gun.lif also does, for instance:

Code: Select all

x = 45, y = 35, rule = B3/S23
4$28bo$27b4o$10b2o14b2obobo$2bo7bo2bo11b3obo2bo2b2o$bo3b2o7bo11b2obobo 3b2o$bo5bo6bo12b4o$2b5o7bo7bo5bo$10bo2bo9bo$10b2o9b3o15$38b2o$38bobo$
40bo$40b2o!  That might be because it's not an oscillator, but a predecessor to an oscillator. simeks Posts: 369 Joined: March 11th, 2015, 12:03 pm Location: Sweden Re: Script request thread gmc_nxtman wrote:That might be because it's not an oscillator, but a predecessor to an oscillator. This could to be the problem with the first pattern too. There's one cell on at the start that is off in generation 124: Code: Select all x = 45, y = 56, rule = LifeHistory 25.2A.2A$24.A.A.A$23.A4.A$23.A.2A2.2A$21.A.A.2A4.A$20.A.A.A2.2A.2A$20.A.A.A2.2A$21.A.A.2A3.2A$23.A.A2.2A.A$23.A2.A2.A$21.2A3.A.2A$20.A2.
3A2.A.2A.A$21.2A7.A.2A$22.A.2A.A.A$22.A.A3.A$21.2A.A$23.A.4A$23.A3.2A
3.2A$24.A7.A$8.A16.A4.A.A$7.A.A20.2A10.2A$8.A33.A.A$39.2A.A.A$6.5A28.
A.A.A$5.A4.A30.A$4.A2.A32.2A$.A2.A.2A31.3A$A.A.A5.A28.3A$.A2.A4.A.A 27.3A$4.2A2.A2.A28.2A$9.2A8.3A19.A$17.2A2.A17.A.A.A$17.A2.2A17.2A.A.A$17.3A22.A.A$42.2A2$21.A$20.A$21.A$31.2A$26.4A2.A$25.A4.2A$32.3A$24. 2A3.A.A2.A$23.A4.D3.2A$22.2A$22.2A$19.2A.2A.2A$19.A2.A5.2A$20.A.A.A4. A$21.A5.A$22.2A.A.A$23.A.A.A.A$22.A2.2A.A.A$22.2A4.A.A\$28.2A!


Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Script request thread

gmc_nxtman wrote:That might be because it's not an oscillator, but a predecessor to an oscillator.
Ooh, good point. How sneaky of Jason to include predecessors rather than the actual oscillators!

Still would be nice to get a message saying the pattern isn't properly encodable (or, alternatively, the apgcode for the oscillator it evolves into), but that's less urgent. It sure is a relief to hear the script's not strictly buggy either.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Rhombic
Posts: 1067
Joined: June 1st, 2013, 5:41 pm

Re: Script request thread

Rhombic wrote:Script that calculates a number of gliders to be fired at a selected pattern to yield a non-zero number of spaceships, no static ash (so 0 still lifes, 0 oscillators... only spaceships)

If possible, it would be great if the script allowed non-CGoL rules with gliders to be explored too (just like glider-destruction.py)
Did anyone get around to do this?
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

dvgrn
Moderator
Posts: 7196
Joined: May 17th, 2009, 11:00 pm
Contact:

Re: Script request thread

Rhombic wrote:
Rhombic wrote:Script that calculates a number of gliders to be fired at a selected pattern to yield a non-zero number of spaceships, no static ash (so 0 still lifes, 0 oscillators... only spaceships)

If possible, it would be great if the script allowed non-CGoL rules with gliders to be explored too (just like glider-destruction.py)
Did anyone get around to do this?
In a technical sense, this one is pretty easy. In fact, it has already been written several times -- there's a slow-salvo destruction search script in the supporting code for Andrew Wade's Gemini spaceship, for example. All you'd have to do is save out one block or something at the end, and convert it to an *WSS seed -- or a loafer or Cordership seed, if you prefer. It's certainly not optimal, but it's a perfectly good "number of gliders".

The spec is a little bit vague in other areas, too, and it's not really clear why you'd want something like this. Do gliders count as spaceships? If so, the task is even simpler: run the Gemini destruction script, then add one more glider. Or if the glider has to hit something, then adjust the script so that a single output glider is tolerated, somewhere during the destruction process.

Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Script request thread

biggiemac wrote:This'll probably work. I tested it for spaceships, still lives and oscillators. Just select a rectangle in golly containing only the pattern you care about (plus any amount of empty space) and the apgcode of the object will go to your clipboard. As a side effect, the script makes a new layer.
BTW, there was some discussion a while back about extending apgcodes to handle large sparse patterns -- more precisely about defining what THE canonical apgcode should be in edge cases not currently handled well by Calcyman's apg* family of tools and Catagolue.

The consensus was to a greedy algorithm for each representation, and then apply impose the usual ordering to choose the canonical encoding.

I've therefore gone ahead and adjusted the above script to handle this. This is literally a 5-minute job, so it may not actually be correct, but as far as I can tell so far it seems to work. Save this as apgcode-greedy.py or so, and watch it not choke on patterns such as this twin-bees shuttle variant (which showed up in C2_2 and was classified as an ov_p46).

Code: Select all

import golly as g

# Golly selection to apgcode (in clipboard)
# stolen shamelessly from apgsearch.  Thanks Adam!

def bijoscar(maxsteps):

initpop = int(g.getpop())
initrect = g.getrect()
if (len(initrect) == 0):
return 0
inithash = g.hash(initrect)

for i in xrange(maxsteps):

g.run(1)

if (int(g.getpop()) == initpop):

prect = g.getrect()
phash = g.hash(prect)

if (phash == inithash):

period = i + 1

if (prect == initrect):
return period
else:
return -period
return -1

def canonise():

p = bijoscar(1000000)

representation = "#"
for i in range(abs(p)):
rect = g.getrect()
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0], rect[1], 1, 0, 0, 1))
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0]+rect[2]-1, rect[1], -1, 0, 0, 1))
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0], rect[1]+rect[3]-1, 1, 0, 0, -1))
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0]+rect[2]-1, rect[1]+rect[3]-1, -1, 0, 0, -1))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0], rect[1], 0, 1, 1, 0))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0]+rect[2]-1, rect[1], 0, -1, 1, 0))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0], rect[1]+rect[3]-1, 0, 1, -1, 0))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0]+rect[2]-1, rect[1]+rect[3]-1, 0, -1, -1, 0))
g.run(1)

if (p<0):
prefix = "q"+str(abs(p))
elif (p==1):
prefix = "s"+str(g.getpop())
else:
prefix = "p"+str(p)

g.getstring("The apgcode for your selection is:", "x"+prefix+"_"+representation)

# A subroutine used by canonise:
def canonise_orientation(length, breadth, ox, oy, a, b, c, d):

representation = ""

chars = "0123456789abcdefghijklmnopqrstuvwxyz"

for v in xrange(int((breadth-1)/5)+1):
zeroes = 0
if (v != 0):
representation += "z"
for u in xrange(length):
baudot = 0
for w in xrange(5):
x = ox + a*u + b*(5*v + w)
y = oy + c*u + d*(5*v + w)
baudot = (baudot >> 1) + 16*g.getcell(x, y)
if (baudot == 0):
zeroes += 1
else:
while zeroes > 0:
if (zeroes == 1):
representation += "0"
elif (zeroes == 2):
representation += "w"
elif (zeroes == 3):
representation += "x"
elif (zeroes > 39):
representation += "yz"
else:
representation += "y"
representation += chars[zeroes - 4]
zeroes -= 39
zeroes = 0
representation += chars[baudot]
return representation

# Compares strings first by length, then by lexicographical ordering.
# A hash character is worse than anything else.
def compare_representations(a, b):

if (a == "#"):
return b
elif (b == "#"):
return a
elif (len(a) < len(b)):
return a
elif (len(b) < len(a)):
return b
elif (a < b):
return a
else:
return b

g.duplicate()
g.clear(1)
canonise()

Side note - this also contains two other tweaks I'd made previously; it handles much higher-period patterns (such as this period-8372 flotilla in B378/S3567), and it pops up a dialog with the final apgcode instead of putting it into your clipboard.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Posts: 1974
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Script request thread

Can somebody please explain to me how apgcodes (currently) work?
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

wildmyron
Posts: 1447
Joined: August 9th, 2013, 12:45 am

Re: Script request thread

BlinkerSpawn wrote:Can somebody please explain to me how apgcodes (currently) work?
There's a very nice description on the wiki. Is there any particular detail that's unclear?
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

dvgrn
Moderator
Posts: 7196
Joined: May 17th, 2009, 11:00 pm
Contact:

Re: Script request thread

Apple Bottom wrote:BTW, there was some discussion a while back about extending apgcodes to handle large sparse patterns -- more precisely about defining what THE canonical apgcode should be in edge cases not currently handled well by Calcyman's apg* family of tools and Catagolue.

The consensus was to a greedy algorithm for each representation, and then apply impose the usual ordering to choose the canonical encoding.
@Apple Bottom, is what you said at the top of that thread still true, that
Apple Bottom wrote: ...a quick check of my files reveals that there are not currently any objects on Catagolue containing either yz or yy (though there are two containing yx, an xp412 in B358/S23 and the ship-pulling xq190 in B38/S23 (one variant, anyway).
If so, it seems as if it's not technically too late to support ridiculously large sparse patterns in a way that's completely backwards compatible -- practically speaking. If no apgcode has been officially recorded yet that contains a "yz", then we could still agree to update encoders and decoders everywhere, to allow variable-length base-36 encodings of long strings of 0s.

[Or we could almost just as well use plain old base 10 -- it's not like base 36 will save a very impressive number of bytes, really.]

Besides than the "yzzz####" format, another option would be "yzd####", where d is a base-36 number encoding the number of digits in the #### number. Or the number of digits minus one, as before, since there's no point in encoding yz1# instead of just plain #.

Linear or Logarithmic
I'm really perfectly happy to accept the linear-compression greedy encoding as the official apgcode-extended standard -- as long as nobody will be tempted to add a logarithmic-compression option later! But it seems to me that people probably _will_ be tempted, because apgcodes are going to keep getting used as unique identifiers for larger and larger patterns. At least, that seems likely to happen if everyone can agree on a single apgext format, hopefully relatively soon before multiple solutions get entrenched in different places.

On the other hand, I can see some possible difficulties with apgcode-encoding any pattern large enough to really need logarithmic gap compression. My "yzd####" suggestion would allow runs of zeroes up to somewhere over 10^56 before it would "go linear" again... but if you tried to encode a couple of boats, let's say, separated by 10^56 cells, it would take some tricky new code to efficiently generate all eight orientations and find the lexicographically least version for the canonical form.

There's currently no way to compress vertical gaps (right?), so the apgcodes for four of the orientations would include a string of 10^56 z's. Obviously those won't win on length and become the canonical form... but the encoder would have to be careful not to try to generate those codes and store them in memory, or anything like that.

TL;DR
I guess for the moment my vote is for the simple greedy algorithm, but my mind might not be entirely made up yet. If someone can suggest a backwards-compatible apgext format that also allows logarithmic compression of vertical gaps, I might find that to be pretty much irresistible.

Might even volunteer to write revised encoders and decoders for the format, but I won't promise anything yet...!

A for awesome
Posts: 2105
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Script request thread

dvgrn wrote:If someone can suggest a backwards-compatible apgext format that also allows logarithmic compression of vertical gaps, I might find that to be pretty much irresistible.

Might even volunteer to write revised encoders and decoders for the format, but I won't promise anything yet...!
I have some (admittedly relatively ugly) ideas for encoding vertical gaps. Because "yy" is also unused, a vertical gap could be represented by "zyy" followed by something similar to whatever is used for "yz". Or, "yy" could mean a long horizontal gap and "yz" could mean a vertical gap. I will admit that either option would make decoding slightly harder, though.
praosylen#5847 (Discord)

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}$$