For scripts to aid with computation or simulation in cellular automata.

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.

biggiemac

Posts: 503
Joined: September 17th, 2014, 12:21 am
Location: California, USA

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:
x = 30, y = 30, rule = B3/S23o$b2o$2o27$27b3o! Maybe something could check if the objects are just reoccurrances of a previous pattern, but I don't know. This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.) Current rule interest: B2ce3-ir4a5y/S2-c3-y drc Posts: 1664 Joined: December 3rd, 2015, 4:11 pm Location: creating useless things in OCA ### 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. biggiemac Posts: 503 Joined: September 17th, 2014, 12:21 am Location: California, USA ### 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. Gamedziner Posts: 531 Joined: May 30th, 2016, 8:47 pm Location: Milky Way Galaxy: Planet Earth ### 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. gmc_nxtman Posts: 1128 Joined: May 26th, 2015, 7:20 pm ### 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. dvgrn Moderator Posts: 4845 Joined: May 17th, 2009, 11:00 pm Location: Madison, WI ### 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.) http://www.conwaylife.com/forums/viewto ... 327#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 Scorbie Posts: 1358 Joined: December 7th, 2013, 1:05 am ### 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. waiting for apgsearch to support one-dimensional rules muzik Posts: 2781 Joined: January 28th, 2016, 2:47 pm Location: Scotland ### 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 @RULE v3k4_002210002201212@COLORS0 0 0 01 0 155 1552 200 200 03 200 0 200@TABLEn_states:3neighborhood:vonNeumannsymmetries:permutevar a={1}var b={2}var d={0}var j={0,1,2,1}j,d,d,d,d,dj,d,d,d,a,dj,d,d,a,a,bj,d,a,a,a,b j,a,a,a,a,aj,b,d,d,d,dj,b,a,d,d,dj,b,a,a,d,dj,b,a,a,a,bj,b,b,d,d,bj,b,b,a,d,dj,b,b,a,a,aj,b,b,b,d,bj,b,b,b,a,aj,b,b,b,b,b##old stuff overwrittenj,0,0,0,0,0j,0,0,0,1,0j,0,0,1,1,1j,0,1,1,1,2 j,1,1,1,1,2j,2,0,0,0,2j,2,1,0,0,0j,2,1,1,0,2j,2,1,1,1,1j,2,2,0,0,0j,2,2,1,0,0j,2,2,1,1,2j,2,2,2,0,2j,2,2,2,1,0j,2,2,2,2,2 Last edited by shouldsee on September 29th, 2016, 7:06 am, edited 1 time in total. shouldsee Posts: 406 Joined: April 8th, 2016, 8:29 am ### 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 what is “sesame oil”? Rhombic Posts: 992 Joined: June 1st, 2013, 5:41 pm ### 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: x = 69, y = 75, rule = B3/S2311$38b2ob2o$37bobobo$36bo4bo$36bob2o2b2o$34bobob2o4bo$33bobobo2b2ob2o$33bobobo2b2o$34bobob2o3b2o$36bobo2b2obo$36bo2bo2bo$34b2o3bob2o$33bo2b3o2bob2obo$34b2o7bob2o$35bob2obobo$35bobo3bo$34b2obo$36bob4o$36bo3b2o3b2o$37bo7bo$21bo16bo4bobo$20bobo20b2o10b2o$21bo33bobo$52b2obobo$19b5o28bobobo$18bo4bo30bo$17bo2bo32b2o$14bo2bob2o31b3o$13bobobo5bo28b3o$14bo2bo4bobo27b3o$17b2o2bo2bo28b2o$22b2o8b3o19bo$30b2o2bo17bobobo$30bo2b2o17b2obobo$30b3o22bobo$55b2o2$34bo$33bo$34bo$44b2o$39b4o2bo$38bo4b2o$45b3o$37b2o3bobo2bo$36bo4bo3b2o$35b2o$35b2o$32b2ob2ob2o$32bo2bo5b2o$33bobobo4bo$34bo5bo$35b2obobo$36bobobobo$35bo2b2obobo$35b2o4bobo$41b2o!

xq1_y9g8970rp2s0gzy9d5ob3kc3s343zy764269j81aq2t52zy74s0g0662i9611y8gz697o4cy311yfo9a98gzxvveybgwgoy3o48g32gv04a4zcis346ya78054gia0hex11zy8ggy71zy6ckla29111a8gzybo8044g7v0kczyao4o78e0mq1zyb11
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!

Apple Bottom

Posts: 969
Joined: July 27th, 2015, 2:06 pm

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:

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.

dvgrn
Moderator

Posts: 4845
Joined: May 17th, 2009, 11:00 pm

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:

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:

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!

Apple Bottom

Posts: 969
Joined: July 27th, 2015, 2:06 pm

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:

rle

xq1_y9g8970rp2s0gzy9d5ob3kc3s343zy764269j81aq2t52zy74s0g0662i9611y8gz697o4cy311yfo9a98gzxvveybgwgoy3o48g32gv04a4zcis346ya78054gia0hex11zy8ggy71zy6ckla29111a8gzybo8044g7v0kczyao4o78e0mq1zyb11

It's not nonsensical; Catagolue, at least, parses it correctly when xq1 is changed to xp0:
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

A for awesome

Posts: 1648
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

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:

x = 45, y = 35, rule = B3/S234$28bo$27b4o$10b2o14b2obobo$2bo7bo2bo11b3obo2bo2b2o$bo3b2o7bo11b2obobo3b2o$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! Apple Bottom Posts: 969 Joined: July 27th, 2015, 2:06 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: x = 45, y = 35, rule = B3/S234$28bo$27b4o$10b2o14b2obobo$2bo7bo2bo11b3obo2bo2b2o$bo3b2o7bo11b2obobo3b2o$bo5bo6bo12b4o$2b5o7bo7bo5bo$10bo2bo9bo$10b2o9b3o15$38b2o$38bobo$40bo$40b2o!

That might be because it's not an oscillator, but a predecessor to an oscillator.

gmc_nxtman

Posts: 1128
Joined: May 26th, 2015, 7:20 pm

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:

x = 45, y = 56, rule = LifeHistory25.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.2A3.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.A27.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!
simeks

Posts: 344
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

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!

Apple Bottom

Posts: 969
Joined: July 27th, 2015, 2:06 pm

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
what is “sesame oil”?

Rhombic

Posts: 992
Joined: June 1st, 2013, 5:41 pm

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.

dvgrn
Moderator

Posts: 4845
Joined: May 17th, 2009, 11:00 pm

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

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 -1def 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 bg.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!

Apple Bottom

Posts: 969
Joined: July 27th, 2015, 2:06 pm

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

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

There's a very nice description on the wiki. Is there any particular detail that's unclear?
wildmyron

Posts: 845
Joined: August 9th, 2013, 12:45 am

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

dvgrn
Moderator

Posts: 4845
Joined: May 17th, 2009, 11:00 pm

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

A for awesome

Posts: 1648
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

PreviousNext