Script request thread
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.
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.
Re: Script request thread
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: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.
Code: Select all
x = 30, y = 30, rule = B3/S23
o$b2o$2o27$27b3o!
Re: Script request thread
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: I think that as long as the objects interact at some point, they should be counted.
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.drc wrote: Maybe something could check if the objects are just reoccurrances of a previous pattern, but I don't know.
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.
-
- 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: 1150
- 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.
•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.
Re: Script request thread
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.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
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.
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.)
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.)
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.
Preferably so I can generate rules like this easily, without needing to do any of the manual work.
Help wanted: How can we accurately notate any 1D replicator?
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
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.
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)
If possible, it would be great if the script allowed non-CGoL rules with gliders to be explored too (just like glider-destruction.py)
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Script request thread
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: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.
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
!
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Script request thread
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 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...
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Script request thread
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:dvgrn wrote: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 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...
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
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
- praosylen
- Posts: 2443
- Joined: September 13th, 2014, 5:36 pm
- Location: Pembina University, Home of the Gliders
- Contact:
Re: Script request thread
It's not nonsensical; Catagolue, at least, parses it correctly when xq1 is changed to xp0: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:
apgcode produced by the script (linebreaks added for readability):Code: Select all
rle
Code: Select all
xq1_y9g8970rp2s0gzy9d5ob3kc3s343zy764269j81aq2t52zy74s0g0662i9611y8gz697 o4cy311yfo9a98gzxvveybgwgoy3o48g32gv04a4zcis346ya78054gia0hex11zy8ggy71z y6ckla29111a8gzybo8044g7v0kczyao4o78e0mq1zyb11
former username: A for Awesome
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Script request thread
True. I meant nonsensical as that it's not an xq1 (and there's no such thing in Conway Life to begin with).A for awesome wrote:It's not nonsensical; Catagolue, at least, parses it correctly when xq1 is changed to xp0:
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
- gmc_nxtman
- Posts: 1150
- Joined: May 26th, 2015, 7:20 pm
Re: Script request thread
That might be because it's not an oscillator, but a predecessor to an oscillator.Apple Bottom wrote:True. I meant nonsensical as that it's not an xq1 (and there's no such thing in Conway Life to begin with).A for awesome wrote:It's not nonsensical; Catagolue, at least, parses it correctly when xq1 is changed to xp0:
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!
Re: Script request thread
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:gmc_nxtman wrote:That might be because it's not an oscillator, but a predecessor to an oscillator.
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
Ooh, good point. How sneaky of Jason to include predecessors rather than the actual oscillators!gmc_nxtman wrote:That might be because it's not an oscillator, but a predecessor to an oscillator.
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Script request thread
Did anyone get around to do this?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)
Re: Script request thread
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".Rhombic wrote:Did anyone get around to do this?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)
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
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.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.
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()
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
- BlinkerSpawn
- Posts: 1992
- 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?
Re: Script request thread
There's a very nice description on the wiki. Is there any particular detail that's unclear?BlinkerSpawn wrote:Can somebody please explain to me how apgcodes (currently) work?
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.
Semi-active here - recovering from a severe case of LWTDS.
Semi-active here - recovering from a severe case of LWTDS.
Re: Script request thread
@Apple Bottom, is what you said at the top of that thread still true, thatApple 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.
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.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).
[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...!
- praosylen
- Posts: 2443
- Joined: September 13th, 2014, 5:36 pm
- Location: Pembina University, Home of the Gliders
- Contact:
Re: Script request thread
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.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...!
former username: A for Awesome
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...