Rulesrc: Finding rules for a spaceship

For scripts to aid with computation or simulation in cellular automata.
User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » July 31st, 2019, 9:03 pm

It would be interesting to have an option to specify a search space directly. For example, if you want to find a spaceship matching a certain pattern for a number of generations, but want to specify certain additional transitions to increase the likelihood of finding a spaceship, you could draw an extra spark whose evolution uses those transitions. But that might unintentionally narrow down other transitions you want to vary. If the transition occurs relatively early in the spark's evolution, progrulesrc is unlikely to find the rulespace with the requisite change without affecting desired transitions.

For example suppose you wanted to search the following pattern, matching 10 generations, which woks in 2^52 rules from B2eik3in4a/S2-i3nqr to B2eik3inq4aenqwz5-iry6-i7c8/S2-i3aknqr4-ij5678, but wanted to also specify S4az to increase your odds of finding a higher-period ship.

Code: Select all

x = 4, y = 3, rule = B2eik3in4a/S2-i3nqr4az
3o$3bo$b2o!
You could add this spark to your starting pattern:

Code: Select all

x = 3, y = 5, rule = B2eik3in4a/S2-i3nqr4az
2o$2o$bo$b2o$b2o!
but doing so would also exclude S4r, which occurs in the very first generation. At this stage, progrulesrc could remove S4a and/or add B2c and produce a rulespace that is much more explosive than this one:

Code: Select all

x = 4, y = 3, rule = B2-an3in4a/S2-i3nqr4rz
3o$3bo$b2o!
Compare:

Code: Select all

x = 4, y = 3, rule = B2eik3in4a/S2-i3nqr4arz
3o$3bo$b2o!
(Nb: I first encountered this limitation with searchRule-matchPatt2.py in a rulespace with spaceships based on a particular replicator.)

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Rulesrc: Finding rules for a spaceship

Post by wildmyron » August 2nd, 2019, 3:44 am

LaundryPizza03 wrote:It would be interesting to have an option to specify a search space directly.
Thank you for the description of what you would like to be able to do. This comes under the TODO item "Decouple the rulespace matching from the target pattern". There are two ways I can see this being implemented:
  • Manually over-ride the entire rulespace matching process - This could be done with two parameters for the min and max rule desired. They could be specified something like this:

    Code: Select all

    minrule = "B2eik3in4a/S2-i3nqr4az"
    maxrule = "B2eik3inq4aenqwz5-iry6-i7c8/S2-i3aknqr4-ij5678"
    If both these parameters are specified then the current rulespace checking is skipped and these parameters are used instead.
  • Specify additional constraints on the rulespace with manually specified lists of rule elements. Something like

    Code: Select all

    B_need_extra = []
    S_need_extra = ["4a", "4z"]
    B_OK_extra = []
    S_OK_extra = []
    B_forbid_extra = []
    S_forbid_extra = []
I don't think either of these is a big change and both could be made flexible enough that they would be entirely optional. Do you have a preference for either of these options? I'll try to implement one of these over the coming weekend.

Edit: In the meantime, if you want to try out the search you mentioned with an ad-hoc change to the code, you can do so by defining two of those parameters at the top of the script:

Code: Select all

# Rule space adjustments
B_need_extra = []
S_need_extra = ["4a", "4z"]
and changing this part of the code:

Code: Select all

    # Determine the rulespace to search
    B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
 
to:

Code: Select all

    # Determine the rulespace to search
    B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
    B_need.extend(B_need_extra)
    S_need.extend(S_need_extra)
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.

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » August 2nd, 2019, 10:57 pm

wildmyron wrote:
LaundryPizza03 wrote:It would be interesting to have an option to specify a search space directly.
Thank you for the description of what you would like to be able to do. This comes under the TODO item "Decouple the rulespace matching from the target pattern". There are two ways I can see this being implemented:
  • Manually over-ride the entire rulespace matching process - This could be done with two parameters for the min and max rule desired. They could be specified something like this:

    Code: Select all

    minrule = "B2eik3in4a/S2-i3nqr4az"
    maxrule = "B2eik3inq4aenqwz5-iry6-i7c8/S2-i3aknqr4-ij5678"
    If both these parameters are specified then the current rulespace checking is skipped and these parameters are used instead.
  • Specify additional constraints on the rulespace with manually specified lists of rule elements. Something like

    Code: Select all

    B_need_extra = []
    S_need_extra = ["4a", "4z"]
    B_OK_extra = []
    S_OK_extra = []
    B_forbid_extra = []
    S_forbid_extra = []
I don't think either of these is a big change and both could be made flexible enough that they would be entirely optional. Do you have a preference for either of these options? I'll try to implement one of these over the coming weekend.

Edit: In the meantime, if you want to try out the search you mentioned with an ad-hoc change to the code, you can do so by defining two of those parameters at the top of the script:

Code: Select all

# Rule space adjustments
B_need_extra = []
S_need_extra = ["4a", "4z"]
and changing this part of the code:

Code: Select all

    # Determine the rulespace to search
    B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
 
to:

Code: Select all

    # Determine the rulespace to search
    B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
    B_need.extend(B_need_extra)
    S_need.extend(S_need_extra)
The entry could use a single query, in the same form used by LLS or the naïve one produced by get-all-iso-rules.py, to make it easier to check consistency. In the former case, it would be pB2eik-acn3in-acejkry4a-cijkrty5-iry6-i7-c8/S2acekn-i3nqr-ceijy4az-ij5678. Macbi has a script for doing the conversion.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » August 3rd, 2019, 4:10 am

This isn't exactly the right place for this, but it may be significant with regards to searchRule.matchPatt2.py. When attempting to find the rules containing a moon, B2aceikn is shortened to the nonsensical "Baceikn" instead of "B2". This happens for many rulespaces containing B2a.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Rulesrc: Finding rules for a spaceship

Post by wildmyron » August 3rd, 2019, 11:43 am

Thanks for the feedback. I think the partial rule format is a good idea - it's reasonably easy to express when writing it out manually. But i'll need to write a bit of extra code to interpret the format and update the rulespace determination code in sss.py to be able to easily determine rulespaces in that format. This will [robably take a bit longer as I don't have a lot of time to work on it at the moment.
LaundryPizza03 wrote:This isn't exactly the right place for this, but it may be significant with regards to searchRule.matchPatt2.py. When attempting to find the rules containing a moon, B2aceikn is shortened to the nonsensical "Baceikn" instead of "B2". This happens for many rulespaces containing B2a.
That's annoying, but seems to be cosmetic as far as searchRule-matchPatt2.py is concerned. It's not immediately obvious why that's happening, I'll look into it.
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.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Rulesrc: Finding rules for a spaceship

Post by wildmyron » October 8th, 2019, 8:10 pm

From the 5S thread.
gooddogtyson wrote:
October 8th, 2019, 7:23 pm
Every time I try to run searchRule-matchPatt2.py, it says "NameError: name 'ii' is not defined"

The Wiki page is no help, so I'm hoping someone here knows how to fix this. Thanks!
Hmm, that's odd. Where did you get your copy of the script from? There may have been a version posted with a bug.

To help with debugging, can you answer these questions:

What is the line number of the error?

What starting pattern did you use for the search?

Did you change any settings in the script? And if not do you have a copy of the *.sss.txt files? (Should get a useful error message if not, but just in case)
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.

gooddogtyson
Posts: 33
Joined: September 11th, 2019, 7:17 pm

Re: Rulesrc: Finding rules for a spaceship

Post by gooddogtyson » October 8th, 2019, 8:29 pm

wildmyron wrote:
October 8th, 2019, 8:10 pm
From the 5S thread.
gooddogtyson wrote:
October 8th, 2019, 7:23 pm
Every time I try to run searchRule-matchPatt2.py, it says "NameError: name 'ii' is not defined"

The Wiki page is no help, so I'm hoping someone here knows how to fix this. Thanks!
Hmm, that's odd. Where did you get your copy of the script from? There may have been a version posted with a bug.

To help with debugging, can you answer these questions:

What is the line number of the error?

What starting pattern did you use for the search?

Did you change any settings in the script? And if not do you have a copy of the *.sss.txt files? (Should get a useful error message if not, but just in case)
I tried both from the google drive and the github, neither seem to work

The line number is 300

I started with a simple "T" shape just to test the script

I gathered all of the txt files and I have not changed anything within the script. Thanks for replying

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Rulesrc: Finding rules for a spaceship

Post by wildmyron » October 9th, 2019, 1:19 am

gooddogtyson wrote:
October 8th, 2019, 8:29 pm
I tried both from the google drive and the github, neither seem to work
OK, that's good - you've got the latest version then. I presume you also have a copy of sss.py from the same place, otherwise there'd be a different error.
The line number is 300
Right. That error is just masking another error which must have occurred before the main loop started - which is where ii will be defined. My try .. except .. finally code is a bit dodgy, but I thought the "except Exception, e: raise" should have surfaced the error. can you change that block (at line 290) to the following:

Code: Select all

except Exception, e:
    g.note(str(e))
    raise
Run the script again and copy the content of the Note window here. That should be a much more useful error.

Edit: Or alternatively, temporarily comment out the last line and then the original exception will be raised after the finally block completes.
[/edit]
I started with a simple "T" shape just to test the script
The rule is important too. If this was a T-pentomino in CGoL then specifying more than 3 generations to match is not going to find any spaceships (because the pattern goes symmetric).

I gave a bit of detail about the options in an earlier post https://conwaylife.com/forums/viewtopic ... 608#p79608
Please note that with the default settings it's unlikely that a random pattern in a well known rule is going to give any results from the script. This is because it is unlikely to find new results for 5S in well explored parts of the search space. To contribute to 5S you should be a bit more selective about the starting pattern and number of generations to match - in particular you probably want to use starting patterns which have quite high periods.
However the script is useful for other things too if you change the options. For example, some very high period reflectorless rotating oscillators were found using the script with "bOsc = true" and using a high loopability RRO as a starting pattern. You can see these results on the last page of the RRO thread. And it can also be used for its original purpose - to find periodic patterns with a phase matching the start pattern - if you set stabCycles = 0 and use a small number for the generations to match.
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.

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » November 19th, 2019, 4:12 am

Something weird happens when I match the following ship, a 10c/490o moving down, for 12 generations. Most rules around here seem to explode, while this one does not.

Code: Select all

x = 4, y = 3, rule = B2ek3-cky4aci/S1c23ery
2b2o$obo$b2o!
The rulespace has 30 degrees of freedom (equating to about a billion rules) and the original ship is endemic, yet rulesrc is likely to find the original ship in the first several thousand rules. This likely involves a peculiarity of the pseudorandom number generator used.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Rulesrc: Finding rules for a spaceship

Post by wildmyron » November 19th, 2019, 10:40 pm

LaundryPizza03 wrote:
November 19th, 2019, 4:12 am
Something weird happens when I match the following ship, a 10c/490o moving down, for 12 generations. Most rules around here seem to explode, while this one does not.

Code: Select all

x = 4, y = 3, rule = B2ek3-cky4aci/S1c23ery
2b2o$obo$b2o!
The rulespace has 30 degrees of freedom (equating to about a billion rules) and the original ship is endemic, yet rulesrc is likely to find the original ship in the first several thousand rules. This likely involves a peculiarity of the pseudorandom number generator used.
Yes, that is a bit odd and unexpected. I think it's partly related to the PRNG and also related to the starting rule having only one transition more than the min-rule of the search.

Note that the PRNG is not really a random number generator. It is intended to cycle through all values in it's range once within a full period. You could say that it enumerates the search space in a pseudo-random order. It uses a linear congruential generator (LCG) in order to do this, with parameters chosen to ensure the period matches the range. The choice of parameters isn't made to maximise the quality of randomness because that's not really important here.
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.

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » February 28th, 2020, 9:49 am

I encountered a fatal error in searchRule-matchPatt2.py when running o$bo$bo! for 1 generation. This is an instance where get-all-iso-rules.py malfunctions, but the crash reportedly involves the very last line. It's the same bug that causes the script to throw an error if the search is terminated without finding any spaceships.

Code: Select all

finally:
    g.new('Search result')
    g.putcells(origPatt)
    if lastRule:
        g.setrule(lastRule)
        g.show('%d ships found after testing %d candidate rules.' % (Nfound, ii+1))
    else:
        g.setrule(origRule)
        g.show('No results found after testing %d candidate rules.' % ii+1)

NameError: name 'ii' is not defined

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
yujh
Posts: 3066
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: Rulesrc: Finding rules for a spaceship

Post by yujh » April 12th, 2020, 7:46 am

Is there one for spaceships only?
Rule modifier

B34kz5e7c8/S23-a4ityz5k
b2n3-q5y6cn7s23-k4c8
B3-kq6cn8/S2-i3-a4ciyz8
B3-kq4z5e7c8/S2-ci3-a4ciq5ek6eik7

Bored of Conway's Game of Life? Try Pedestrian Life -- not pedestrian at all!

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Rulesrc: Finding rules for a spaceship

Post by Hunting » April 12th, 2020, 10:39 pm

yujh wrote:
April 12th, 2020, 7:46 am
Is there one for spaceships only?
I don't get it. matchPatt2 is spaceship only if bOsc = False.

User avatar
yujh
Posts: 3066
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: Rulesrc: Finding rules for a spaceship

Post by yujh » April 12th, 2020, 10:43 pm

Hunting wrote:
April 12th, 2020, 10:39 pm
yujh wrote:
April 12th, 2020, 7:46 am
Is there one for spaceships only?
I don't get it. matchPatt2 is spaceship only if bOsc = False.
I mean a rule search for only ships.
Warning: I know nothing about python.
The starting script of this thread searches for both osc and ship.
Rule modifier

B34kz5e7c8/S23-a4ityz5k
b2n3-q5y6cn7s23-k4c8
B3-kq6cn8/S2-i3-a4ciyz8
B3-kq4z5e7c8/S2-ci3-a4ciq5ek6eik7

Bored of Conway's Game of Life? Try Pedestrian Life -- not pedestrian at all!

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Rulesrc: Finding rules for a spaceship

Post by Hunting » April 12th, 2020, 10:47 pm

yujh wrote:
April 12th, 2020, 10:43 pm
Hunting wrote:
April 12th, 2020, 10:39 pm
yujh wrote:
April 12th, 2020, 7:46 am
Is there one for spaceships only?
I don't get it. matchPatt2 is spaceship only if bOsc = False.
I mean a rule search for only ships.
Warning: I know nothing about python.
The starting script of this thread searches for both osc and ship.
matchPatt2 does the work...

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » May 10th, 2020, 2:49 am

I've noticed that rulesrc doesn't work for a single dot in the rule B0/S. (It does, however, work for most other B0 patterns.) This is also one of those cases where get_all_iso_rules.py glitches, by the way.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » November 10th, 2020, 1:50 pm

get_all_iso_rules.py doesn't seem to work in Python 3.9. It appears that string.py no longer has a function titled "replace".

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

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

Re: Rulesrc: Finding rules for a spaceship

Post by dvgrn » November 10th, 2020, 2:02 pm

LaundryPizza03 wrote:
November 10th, 2020, 1:50 pm
get_all_iso_rules.py doesn't seem to work in Python 3.9. It appears that string.py no longer has a function titled "replace".
See the Script request thread for Python 3.x updates -- replace() has to be changed to str.replace().

There are going to be quite a few of these Python 2.x -> 3.x script adjustments. Each update will probably be very minor, but there are a lot of places where Python 2.x scripts are posted, and ideally 3.x versions should be posted right alongside them.

Whenever anyone mentions a script, please if possible give a specific link or reference to where the script can be found.

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Rulesrc: Finding rules for a spaceship

Post by Hunting » November 11th, 2020, 8:06 am

dvgrn wrote:
November 10th, 2020, 2:02 pm
LaundryPizza03 wrote:
November 10th, 2020, 1:50 pm
get_all_iso_rules.py doesn't seem to work in Python 3.9. It appears that string.py no longer has a function titled "replace".
See the Script request thread for Python 3.x updates -- replace() has to be changed to str.replace().

There are going to be quite a few of these Python 2.x -> 3.x script adjustments. Each update will probably be very minor, but there are a lot of places where Python 2.x scripts are posted, and ideally 3.x versions should be posted right alongside them.

Whenever anyone mentions a script, please if possible give a specific link or reference to where the script can be found.
Perhaps, Python 3 totally sucks and is not worth using at all. If you are a 3.x enthusiast, I have nothing to say.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Rulesrc: Finding rules for a spaceship

Post by wildmyron » December 9th, 2020, 2:08 am

I have pushed an update to the sssss GitHub repo which adds Py3 compatibility to sss.py and searchRule-matchPatt2.py

If anyone wants to use any of the other searchRule-*.py scripts in this thread with Golly v4 then let me know which ones and I'll try to get them updated too.
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.

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » March 15th, 2021, 2:19 pm

I updated the main rulesrc script for Python 3.9, which is the default for Golly 4.0.1.

Code: Select all

# Rulesrc.py
#
# Arie Paap, Aug 2017
# Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.
# Updated by: LaundryPizza03, March 2021.
# Grafted by Rhombic, Aug 2017.

import golly as g
import itertools
import random

# Search parameters

# Stop if pattern is a ship with this minimum period
minShipP = 1
# Stop if pattern is an oscillator with this minimum period
minP = 2
# Maximum period to test the pattern for
maxGen = 1000
# Maximum population in any phase
maxPop = 300
# Allow search for oscillators
bOsc = True


import golly as g
from glife import validint

Hensel = [
    ['0'],
    ['1c', '1e'],
    ['2a', '2c', '2e', '2i', '2k', '2n'],
    ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
    ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
    ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
    ['6a', '6c', '6e', '6i', '6k', '6n'],
    ['7c', '7e'],
    ['8']
]

# Python versions < 2.4 don't have "sorted" built-in
try:
    sorted
except NameError:
    def sorted(inlist):
        outlist = list(inlist)
        outlist.sort()
        return outlist

# --------------------------------------------------------------------

def chunks(l, n):
    for i in range(0, len(l), n):
        yield l[i:i+n]

# --------------------------------------------------------------------

def rulestringopt(a):
    result = ''
    context = ''
    lastnum = ''
    lastcontext = ''
    for i in a:
        if i in 'BS':
            context = i
            result += i
        elif i in '012345678':
            if (i == lastnum) and (lastcontext == context):
                pass
            else:
                lastcontext = context
                lastnum = i
                result += i
        else:
            result += i
    result = str.replace(result, '4aceijknqrtwyz', '4')
    result = str.replace(result, '3aceijknqry', '3')
    result = str.replace(result, '5aceijknqry', '5')
    result = str.replace(result, '2aceikn', '2')
    result = str.replace(result, '6aceikn', '6')
    result = str.replace(result, '1ce', '1')
    result = str.replace(result, '7ce', '7')
    return result

clist = []
rule = g.getrule().split(':')[0]

fuzzer = rule + '9'
oldrule = rule
rule = ''
context = ''
deletefrom = []
for i in fuzzer:
    if i == '-':
        deletefrom = [x[1] for x in Hensel[int(context)]]
    elif i in '0123456789/S':
        if deletefrom:
            rule += ''.join(deletefrom)
            deletefrom = []
        context = i
    if len(deletefrom) == 0:
        rule += i
    elif i in deletefrom:
        deletefrom.remove(i)
rule = rule.strip('9')

if not (rule[0] == 'B' and '/S' in rule):
    g.exit('Please set Golly to a Life-like rule.')

if g.empty():
    g.exit('The pattern is empty.')

s = g.getstring('How many generations to remain unchanged:', '', 'Rules calculator')
if not validint(s):
    g.exit('Bad number: %s' % s)

numsteps = int(s)
if numsteps < 1:
    g.exit('Period must be at least 1.')

g.select(g.getrect())
g.copy()
s = int(s)

for i in range(0,s):
    g.run(1)
    clist.append(list(chunks(g.getcells(g.getrect()), 2)))
    mcc = min(clist[i])
    clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

g.show('Processing...')

ruleArr = rule.split('/')
ruleArr[0] = ruleArr[0].lstrip('B')
ruleArr[1] = ruleArr[1].lstrip('S')

b_need = []
b_OK = []
s_need = []
s_OK = []

context = ''
fuzzed = ruleArr[0] + '9'
for i in fuzzed:
    if i in '0123456789':
        if len(context) == 1:
            b_need += Hensel[int(context)]
            b_OK += Hensel[int(context)]
        context = i
    elif context != '':
        b_need.append(context[0] + i)
        b_OK.append(context[0] + i)
        context += context[0]
context = ''
fuzzed = ruleArr[1] + '9'
for i in fuzzed:
    if i in '0123456789':
        if len(context) == 1:
            s_need += Hensel[int(context)]
            s_OK += Hensel[int(context)]
        context = i
    elif context != '':
        s_need.append(context[0] + i)
        s_OK.append(context[0] + i)
        context += context[0]

for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
    if not i in b_OK:
        b_OK.append(i)
        execfor = 1
        # B0 and nontotalistic rulestrings are mutually exclusive
        try:
            g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
        except:
            b_OK.remove(i)
            execfor = 0
        for j in range(0, s * execfor):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    b_OK.remove(i)
                    break
            except:
                b_OK.remove(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        b_OK.sort()

    if not i in s_OK:
        s_OK.append(i)
        execfor = 1
        # B0 and nontotalistic rulestrings are mutually exclusive
        try:
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
        except:
            s_OK.remove(i)
            execfor = 0
        for j in range(0, s * execfor):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    s_OK.remove(i)
                    break
            except:
                s_OK.remove(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        s_OK.sort()

    if i in b_need:
        b_need.remove(i)
        g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
        for j in range(0, s):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    b_need.append(i)
                    break
            except:
                b_need.append(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        b_need.sort()

    if i in s_need:
        s_need.remove(i)
        g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
        for j in range(0, s):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    s_need.append(i)
                    break
            except:
                s_need.append(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        s_need.sort()

g.setrule(oldrule)
ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need)) + \
    ' - B' + ''.join(sorted(b_OK)) + '/S' + ''.join(sorted(s_OK))
g.show(rulestringopt(ruleres))

ruleB="B"+''.join(sorted(b_need))
ruleS="S"+''.join(sorted(s_need))
isotropiclistB = sorted(b_OK)
isotropiclistS = sorted(s_OK)

# Remove B0 and B1 conditions
for wrongvalues in ["0","1c","1e"]:
    if wrongvalues in isotropiclistB:
        isotropiclistB.remove(wrongvalues)

# Generate a random isotropic rule which is likely to allow spaceships to exist
def randIsoRule():
    # Birth conditions
    prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
    rulestr = ruleB
    for elem in isotropiclistB:
        if random.random()<prob: rulestr+=elem
    # Ensure rule has a chance of supporting ships
    if len(rulestr) == 1:
        # Add a random rule element
        rulestr+=random.choice(isotropiclistB)
    if not rulestr[1] in '23':
        # Add two random 2x or 3x rule elements
        rulestr+=random.choice(isotropiclistB[:16])
        rulestr+=random.choice(isotropiclistB[:16])
    
    # Survival conditions (force S0 for dot survival)
    prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
    rulestr+='/'+ruleS
    for elem in isotropiclistS:
        if random.random()<prob: rulestr+=elem
    return(rulestr)
    
# ----------------------------------------------------------

# Return the minimum and maximum of the absolute value of a list of numbers
def minmaxofabs(v):
    v = list(map(abs, v))
    return min(v), max(v)

# Test a pattern in the given rule to determine if it reappears
def testRule(rulestr):
    r = g.getrect()
    if r:
        g.select(r)
        g.clear(0)
    g.putcells(testPatt)
    g.setrule(rulestr)
    for ii in range(maxGen):
        g.run(1)
        pop = int(g.getpop())
        if (pop < minPop or pop > maxPop):
            break
        elif (pop == testPop):
            # Test for periodicity
            r = g.getrect()
            if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                period = ii+1
                if (r[0] == 0 and r[1] == 0 ):
                    # Oscillator (reject if low period or bOsc is False)
                    if bOsc and period >= minP:
                        return (period, )
                elif ( period >= minShipP ):
                    # Spaceship (reject if low period)
                    return (r[0], r[1], period) 
                break # Pattern is a low period oscillator or spaceship
    return ()
    
# Set up the search with the current pattern
testRect = g.getrect()
testPop = int(g.getpop())
testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])

if bOsc: minPop = 2 # Patterns with 0, or 1 cells can not be oscillators
else: minPop = 3 # Patterns with 0, 1, or 2 cells can not be ships

g.new('spRulesrc')

for ii in itertools.count(0,1):
    if bOsc==False:
        while 1:
            j=randIsoRule()
            if "2a" in j: break
            if "2c" in j: break
            if "3i" in j: break
    else:
        j=randIsoRule()
    result = testRule(j)
    if result:
        # Interesting pattern found
        break
    if (ii % 1000 == 0):
        g.select([])
        g.show('%d candidate rules tested for interesting patterns' % (ii))
        g.update()
        g.new("")
        
g.new('Search result')
if result:
    g.putcells(testPatt)
    if (len(result) == 1):
        # Pattern is an oscillator
        description = 'Found oscillator with period = %d' % result
    elif (len(result) == 3):
        dx, dy, period = result
        dy, dx = minmaxofabs( (dx, dy) )
        if dy == 0:
            description = 'Found orthogonal spaceship with speed = %dc/%d' % (dx, period)
        elif dy == dx:
            description = 'Found diagonal spaceship with speed = %dc/%d' % (dx, period)
        else:
            description = 'Found knightship with speed = (%d, %d)c/%d' % (dx, dy, period)
    else:
        g.exit('Unrecognised pattern')
    g.show(description)
else:
    g.show('No results found')
    

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » April 3rd, 2022, 1:31 am

rulesrc sometimes returns nonsense results in B0 rules, e.g. the following pattern is erroneously billed as c/5d:

Code: Select all

x = 4, y = 2, rule = B02-n3cjnqr4-inqw5cikn6a7c/S013a4iqrw6k
bo$o2bo!
oscar.lua, by comparison, correctly fails to find periodicity.

EDIT: 10c/44o misidentified as 10c/43o; also correctly identified by oscar:

Code: Select all

x = 3, y = 2, rule = B013-iky4aeiknrw5i6c78/S012ckn3jr4ajkqwyz5cky
2bo$obo!

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
wwei47
Posts: 1651
Joined: February 18th, 2021, 11:18 am

Re: Rulesrc: Finding rules for a spaceship

Post by wwei47 » April 3rd, 2022, 3:03 pm

LaundryPizza03 wrote:
April 3rd, 2022, 1:31 am
rulesrc sometimes returns nonsense results in B0 rules, e.g. the following pattern is erroneously billed as c/5d:

Code: Select all

x = 4, y = 2, rule = B02-n3cjnqr4-inqw5cikn6a7c/S013a4iqrw6k
bo$o2bo!
I think I know what is going on. If you run that pattern starting at generation 1, then it reappears at generation 6 with a (1,1) displacement. rulesrc then says "It moved! Spaceship found!!!".
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » April 3rd, 2022, 3:07 pm

wwei47 wrote:
April 3rd, 2022, 3:03 pm
LaundryPizza03 wrote:
April 3rd, 2022, 1:31 am
rulesrc sometimes returns nonsense results in B0 rules, e.g. the following pattern is erroneously billed as c/5d:

Code: Select all

x = 4, y = 2, rule = B02-n3cjnqr4-inqw5cikn6a7c/S013a4iqrw6k
bo$o2bo!
I think I know what is going on. If you run that pattern starting at generation 1, then it reappears at generation 6 with a (1,1) displacement. rulesrc then says "It moved! Spaceship found!!!".
Then what explains why this object, which is a predecessor to a 3c/10o spaceship, turned up a false positive for c/3o?

Code: Select all

x = 3, y = 3, rule = B012en3ek4ciknqtz5cny8/S02-kn4aeint5ij6k
2bo$o$2bo!

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
wwei47
Posts: 1651
Joined: February 18th, 2021, 11:18 am

Re: Rulesrc: Finding rules for a spaceship

Post by wwei47 » April 3rd, 2022, 3:15 pm

LaundryPizza03 wrote:
April 3rd, 2022, 3:07 pm
Then what explains why this object, which is a predecessor to a 3c/10o spaceship, turned up a false positive for c/3o?

Code: Select all

x = 3, y = 3, rule = B012en3ek4ciknqtz5cny8/S02-kn4aeint5ij6k
2bo$o$2bo!
What cycle detection algorithm is rulesrc using?
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

Post Reply