Algorithm for reversing the GoL rules

For general discussion about Conway's Game of Life.
Post Reply
IncJSG
Posts: 3
Joined: February 18th, 2022, 2:38 am

Algorithm for reversing the GoL rules

Post by IncJSG » February 18th, 2022, 3:02 am

Hello there,

I'm a bit new on this forum but, as it seems full of competent people on the GoL subject, it may be a good place for my topic.
I know that discussions are more related to interesting evolving patterns but, in my case, I'm more about working on an algorithm to run the game in reverse. I know this is a NP hard problem and that's not always possible to find a predecessor. But for not too big world grids, it is often definitively possible.

I googled a lot on this subject and the best reference I could find is this one:
https://nbickford.wordpress.com/2012/04 ... nd-profit/
It's lacking a lot of details, and it mentions methods like Wood, Duparc and Quadwood that also seem to lack strong reference in the literature. Anyway, reading between the lines is possible to understand the main idea of its methodology and I could start from there.

Now I would like to go beyond this. So my question is, does someone here knows / heard about any practical algorithm to run the GoL backward ?

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

Re: Algorithm for reversing the GoL rules

Post by hotdogPi » February 18th, 2022, 7:08 am

GoL can't be reversed. There are too many options that converge to the same patterns.
User:HotdogPi/My discoveries

Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉞㉟㊱㊳㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,68,70,73,74S,75,76S,80,84,88,90,96
100,02S,06,08,10,12,14G,16,17G,20,26G,28,38,47,48,54,56,72,74,80,92,96S
217,486,576

S: SKOP
G: gun

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

Re: Algorithm for reversing the GoL rules

Post by dvgrn » February 18th, 2022, 7:32 am

hotdogPi wrote:
February 18th, 2022, 7:08 am
GoL can't be reversed. There are too many options that converge to the same patterns.
That's maybe a good general summary, but there are a lot of exceptions that should be mentioned.

In early 2018, Tom Rokicki put together an experimental patch for Golly that allowed it to call a SAT solver (minisat) to run Life backwards for small patterns. It just picked one out of the (often) thousands of possibilities, but it often ran pretty fast, at least up to 30x30 or so. I don't think that experiment was ever put out on GitHub or anywhere public, but I have a copy in an email somewhere if anyone wants to look at it.

Along similar lines, you can set up your average small pattern in JavaLifeSearch or WinLifeSearch, or in LLS (the CA-rule/SAT-solver combination that most people around here use the most), and usually you'll get an answer back near-instantly (for small enough values of "small", anyway).

So it's not that it can't be done, it's just that it's unreliable, and when you iterate back through many generations, you get bigger and bigger patterns that are more and more likely to be Gardens of Eden ... without, most of the time, ever seeing anything but bigger and bigger patches of space dust.

I've been wishing for many years now for a reliable metric that can pick predecessors that are somehow more likely to be glider-constructible -- in my fevered imagination, you would step backward, picking the most glider-constructible option among the available choices at each step, and after a while you'd have a glider synthesis recipe for whatever it was.

People do attempt things along these lines every few years, but coming up with a workable metric is a very very difficult problem. Without a God's algorithm for glider syntheses, you usually can't tell a late-stage glider collision from random space dust.

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Algorithm for reversing the GoL rules

Post by HartmutHolzwart » February 18th, 2022, 8:19 am

In view of the recent development: For a pattern to have many predecessors makes it more likely that one of them is glider constructible. So one heuristic would be to try to stabilize the center into a still life with many predecessors and try to grow that core with every generation, while keeping some minimum number of predecessor limit for sub patches of a certain size. The outcome would be a constructible still life surrounded by some sparks.

Not much different from what‘s already used, but with the additional minimal limit for number of predecessors.

IncJSG
Posts: 3
Joined: February 18th, 2022, 2:38 am

Re: Algorithm for reversing the GoL rules

Post by IncJSG » February 18th, 2022, 9:35 am

dvgrn wrote:
February 18th, 2022, 7:32 am
hotdogPi wrote:
February 18th, 2022, 7:08 am
GoL can't be reversed. There are too many options that converge to the same patterns.
That's maybe a good general summary, but there are a lot of exceptions that should be mentioned.

In early 2018, Tom Rokicki put together an experimental patch for Golly that allowed it to call a SAT solver (minisat) to run Life backwards for small patterns. It just picked one out of the (often) thousands of possibilities, but it often ran pretty fast, at least up to 30x30 or so. I don't think that experiment was ever put out on GitHub or anywhere public, but I have a copy in an email somewhere if anyone wants to look at it.

Along similar lines, you can set up your average small pattern in JavaLifeSearch or WinLifeSearch, or in LLS (the CA-rule/SAT-solver combination that most people around here use the most), and usually you'll get an answer back near-instantly (for small enough values of "small", anyway).

So it's not that it can't be done, it's just that it's unreliable, and when you iterate back through many generations, you get bigger and bigger patterns that are more and more likely to be Gardens of Eden ... without, most of the time, ever seeing anything but bigger and bigger patches of space dust.

I've been wishing for many years now for a reliable metric that can pick predecessors that are somehow more likely to be glider-constructible -- in my fevered imagination, you would step backward, picking the most glider-constructible option among the available choices at each step, and after a while you'd have a glider synthesis recipe for whatever it was.

People do attempt things along these lines every few years, but coming up with a workable metric is a very very difficult problem. Without a God's algorithm for glider syntheses, you usually can't tell a late-stage glider collision from random space dust.
Thanks, this is interesting.

The argument "this is not reversible" is indeed often used although the point is not to reverse a pattern "mathematically", but instead to just reverse it if it is possible. And in the case you get multiple solutions, you are free to chose one and to repeat the process.

For the metric I could at least provide one with the results I get on 8x8 periodic grids, as I can resolve them almost instantaneously. I never compiled statistics on random grids but most of the time, at least one inverse exists. I will do that asap and come back with some numbers.

I'm pretty confident I could reverse 12x12 grids with some modifications of my software, but what I'm seeking now are new tips to jump on 16x16 grids.

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

Re: Algorithm for reversing the GoL rules

Post by dvgrn » February 18th, 2022, 10:40 am

IncJSG wrote:
February 18th, 2022, 9:35 am
I'm pretty confident I could reverse 12x12 grids with some modifications of my software, but what I'm seeking now are new tips to jump on 16x16 grids.
Would any LLS experts out there care to throw together a quick walkthrough of how to do the setup to find predecessors of 16x16 grids? I suspect LLS would be one of the more useful benchmarks for comparison purposes here.

(I'd like to become an LLS expert this year, and I'm definitely not one now, so that would really help me out if nobody else.)

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Algorithm for reversing the GoL rules

Post by Macbi » February 18th, 2022, 12:50 pm

dvgrn wrote:
February 18th, 2022, 10:40 am
IncJSG wrote:
February 18th, 2022, 9:35 am
I'm pretty confident I could reverse 12x12 grids with some modifications of my software, but what I'm seeking now are new tips to jump on 16x16 grids.
Would any LLS experts out there care to throw together a quick walkthrough of how to do the setup to find predecessors of 16x16 grids? I suspect LLS would be one of the more useful benchmarks for comparison purposes here.

(I'd like to become an LLS expert this year, and I'm definitely not one now, so that would really help me out if nobody else.)
1) Go to the source and click the download button and then unzip it once it downloads. There's no particular location where you have to put it. I've linked to the 'develop' branch of the project which is technically not the official version. It's much better than version 0 but I haven't been prioritising releases.
2) Download a SAT solver. The best one is kissat. Download and unzip it, then open a terminal window in its build directory and run './configure && make test'. This should compile kissat and create a file called 'kissat' in the build directory. (For me one of the tests fails but this file still appears.) It's this file which is the solver.
3) Drag kissat from that directory to the solvers directory of LLS.
4) Create a 'search pattern' to describe what you want to find. In this case it should look something like this:

Code: Select all

*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
,,,,,,,,,,,,,,,,,,,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0
0,0,1,1,1,0,0,0,1,1,1,1,0,1,1,0,1,0,0,0
0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,1,0,0
0,0,0,0,0,1,1,1,0,1,1,0,1,1,1,1,1,0,0,0
0,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,1,1,0,0
0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0
0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,0,1,0,0
0,0,1,0,0,0,1,0,1,1,1,0,1,1,0,1,0,0,0,0
0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,0
0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0
0,0,1,1,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,0
0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,0,0
0,0,0,1,1,1,1,0,1,0,0,0,1,1,1,0,1,1,0,0
0,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,0,1,0,0
0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,1,1,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
The pattern describes cells separated by commas. The line of commas in the middle separates the two generations of the search pattern. The first generation is full of *s, which represent an unknown cell. The second generation is full of 0s and 1s, which represent dead and alive cells respectively. I've included a margin of two dead cells around the 16 by 16 soup, so that the predecessor might be slightly larger than the soup. One easy way to make this search pattern would be to create the soup in Golly and then select it (with the margin) and run this csv_from_selection.py script:

Code: Select all

import golly as g

x, y, width, height = g.getselrect()
grid = [["0"]*width for _ in range(height)]
cells = g.getcells([x, y, width, height])
for i in range(0,len(cells),2):
    grid[cells[i + 1] - y][cells[i] - x] = "1"
    
with open("pattern.csv", "w") as output_file:
    output_file.write("\n".join(",".join(row) for row in grid) + "\n")
Then open up the pattern.csv file in Excel and add columns above the existing rows and fill them with *s in a rectangle of the same size. Leave a blank row between the two generations. When you save a file in Excel with the .csv filetype it will save it in csv (comma separated value) format, which is what we want. (The line of commas in the above example is an artefact of Excel giving every row the same width. LLS would work equally well if this line was blank.)
5) Save this file in the search_patterns directory of LLS, in this example I'll assume the name is pattern.csv.
6) Open the terminal in the logic-life-search directory and run the command

Code: Select all

python lls search_patterns/pattern.csv
7) The output should look something like

Code: Select all

Getting search pattern...
Done

Preprocessing...
Done

Number of undetermined cells: 400
Number of variables: 400
Number of clauses: 31498

Active width: 20
Active height: 20
Active duration: 1

Solving...
Done

Time taken: 0.7751362323760986 seconds

x = 22, y = 22, rule = B3/S23
bbbbbbbbbbbbbbbbbbbbbb$
bobbbbbbbbbobbbobbbbbb$
bbobbbbbobbbbobbbobbbb$
bbbboobbobbbbbooobbbbb$
bbobobbboobobbbobbobbb$
bbbbbbboobboobbbbobbbb$
bbbobbbobbbobobboobbbb$
bbbbbbobbbbobboobboobb$
bbboobbbobobobobbbbbbb$
bbbbbbboobbbbobbbbobob$
bbbbobbobboobobbooobob$
bbobobbbbobooobbboobbb$
bbbobboboobobbobbbbbob$
bbbbobbbbbboobbboooobb$
bbobbooboobbobbbobboob$
bbobbbbbboboboobbbboob$
booobooobobbbbbbobbobb$
booobbobbobobobbobobob$
bbobbbbbbbboooooboobbb$
bbobbboobbbbobbbbbbbob$
bbbbbbbbbbobbobbbbbbbb$
bbbbbbbbbbbbbbbbbbbbbb!
8) <- Sunglasses dude.
9) Copy the output RLE back into Golly to check that it works.

Note that the hard work of finding the predecessor is done by kissat in just 0.8 seconds. So this approach deals with 16 by 16 soups quite quickly. I tried with a 40 by 40 soup and it returned UNSAT (i.e. no predecessor within the size 2 margin) in less than five seconds.

IncJSG
Posts: 3
Joined: February 18th, 2022, 2:38 am

Re: Algorithm for reversing the GoL rules

Post by IncJSG » February 18th, 2022, 4:11 pm

Thanks a lot for those valuable explanations.
It definitively seems very interesting and I will give a look to this.

Is there an easy mean to go for periodic grids (by encoding some kind of special constraint on the borders) ? It would avoid to surround the grid with 0 to deal with its expansion. This is a bit more constrained but solutions are also more elegant.

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

Re: Algorithm for reversing the GoL rules

Post by dvgrn » February 18th, 2022, 6:18 pm

Macbi wrote:
February 18th, 2022, 12:50 pm
[awesome walkthrough]
Thanks! I've gone through all the steps, and they worked without any serious issues.

However, I ran into a whole bunch of gotchas along the way -- so I'll document them here in case anyone else finds them useful.

1) I used a Cygwin terminal window for both the downloading/cloning steps and the compilation of kissat.

Code: Select all

cd c:/repos
git clone https://github.com/arminbiere/kissat.git
cd kissat
./configure && make test
All of the kissat tests succeeded for me, but there was one rather weird compilation message:

Code: Select all

gcc -W -Wall -O3 -DNDEBUG -c ../src/substitute.c

../src/substitute.c: In function ‘kissat_substitute’:
../src/substitute.c:592:16: warning: array subscript 3 is above array bounds of ‘unsigned int[3]’ [-Warray-bounds]
  592 |         c->lits[old_size - 1] = INVALID_LIT;
      |         ~~~~~~~^~~~~~~~~~~~~~
In file included from ../src/internal.h:10,
                 from ../src/inlinevector.h:4,
                 from ../src/inline.h:4,
                 from ../src/substitute.c:3:
../src/clause.h:35:12: note: while referencing ‘lits’
Still got the executable, though!

2) I figured git clone https://gitlab.com/OscarCunningham/logi ... search.git would be the way to go for LLS, too, but apparently even when I'm looking at the development branch on gitlab, that clones the whole repo, which defaults to the "main" (non-development) branch, which is written in Python2 and errors when you run it with Python3 -- the opposite of the development branch, which uses Python3 and errors when you try to run it with Python2.

... Python2 ?! Isn't that a sign that it's maybe high time to make the development branch into the main branch, and save a whole bunch of noobconfusion?

The invocation with just 'python' defaults to python3 on my system, so that works fine. It's okay to use

Code: Select all

python3 ./lls search_patterns/pattern.csv
to make sure -- and if putting in "python3" produces "Module not found" type errors, and putting in "python2" doesn't, then you don't have the development branch. Another clue is that the "search_patterns" folder doesn't show up.

Running the Python2 version (which was the non-development branch but I didn't realize that yet) I got another weird error after all the Python code seemed like it was going to work:

Code: Select all

  File "/cygdrive/c/repos/logic-life-search/src/LLS_SAT_solvers.py", line 86, in use_solver
    stdout=subprocess.PIPE, stdin=subprocess.PIPE, stderr=subprocess.PIPE)
  File "/usr/lib/python2.7/subprocess.py", line 394, in __init__
    errread, errwrite)
  File "/usr/lib/python2.7/subprocess.py", line 1047, in _execute_child
    raise child_exception
OSError: [Errno 2] No such file or directory
I think if you're getting that, it's just another sign that you need to figure out how to switch over to the development branch.

I got around having to switch branches in Git, by just downloading the ZIP file from the above link instead of using Git. That worked fine -- gave me the Python3 development branch, with the search_patterns folder and everything.

3) It might be worth adjusting csv_from_selection.py so that it makes the user choose a save location, so that it doesn't end up in whatever random folder Golly happens to think is the "current directory".

The current directory can be pretty mysterious, at least on Windows -- until I hard-coded a path, the script saved a pattern.csv successfully, but it took a system-wide search to find it (!) It turned up in C:\Users\{username}\AppData\Roaming\Golly, which is a horrible location because the AppData folder is hidden by default -- users mostly just have to know it's there, and navigate there by typing the path in File Explorer. It's not such a good idea to change settings so that you can see that hidden folder, because then it's possible to accidentally delete or move other system folders, which can wreck the operating system...

Third Time Was The Charm
After dodging those various bullets, everything now seems to be working.

I've seen all this kind of thing happen a lot before, so it didn't take me long to sort through it -- but I could imagine that someone who has never ventured outside of the world of Windows might have a tough time with the line-ending gotcha in particular. They probably wouldn't hit the development-branch problem unless they knew just enough about Git to be dangerous (like me).

EDIT: As I hoped, just adding another blank generation and another line of commas made LLS obligingly generate a 2-tick predecessor of my target pattern:

Code: Select all

*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
,,,,,,,,,,,,,,,,,,,
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
,,,,,,,,,,,,,,,,,,,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0
0,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,0
0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0
0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,0,0
0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Code: Select all

x = 22, y = 22, rule = B3/S23
bbbbbbbbbbbbbbbbbbbbbb$
bobobobobooboobbboobbb$
bbbboooooooobbobobbbbb$
bboboobbobbbobbbboobob$
bbobbbooobbobobobboobb$
bbbbbbbbboboooboboboob$
bboboobbbbbbbbbboobobb$
bbboobbobbbobbbbobbobb$
boobbbbboboobboobobbbb$
boobobbbobbbboobboobbb$
bboboobobbbbboboobobob$
bboobbbobboooooooboobb$
bbbobboobbbbbooboobbob$
bboobbbobbbbbbbbbbbbob$
bbboobbbbbobobobbobbbb$
bbobbobboboboobbbbbbob$
bbboboobbbbbboboobooob$
bbbbbbbobobbbbbbooobbb$
bbboobbooooboobbbbbbbb$
bbbbbobbbbobbbbbbbbobb$
bboobbbbboboobobobbobb$
bbbbbbbbbbbbbbbbbbbbbb!
4) On my first try to find a sample predecessor, I got

Code: Select all

Getting search pattern...
Done

Preprocessing...
    Unsatisfiability proved in preprocessing
Done

Time taken: 0 seconds

Unsatisfiable
... which didn't make a whole lot of sense, especially after I tried the exact pattern quoted above.

So I re-opened the input pattern in TextPad, saved it with Unix-style newline characters, and tried again. (On a PC you get \r\n, ASCII-13 + ASCII 10, as newline characters by default when you copy, paste, and save text files. If you don't save with Unix newlines -- just \n, ASCII 10 -- LLS will think you're specifying some kind of stripey pattern with every other line blank, and will get very very confused about this.)

I just did my pattern creation by copying and pasting and hand-editing, but when Python runs the csv_from_selection.py script on Windows, it will also use Windows line endings by default, with the same disastrous results.

However, Macbi has since pointed out that I was doing all of this while still accidentally working with main-branch LLS -- the newline problem has since been fixed. I tried it again on the development branch, and Windows line endings worked fine. So this is all just another symptom of using the main branch instead of the development branch.

Post Reply