Algorithm for reversing the GoL rules
Algorithm for reversing the GoL rules
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 ?
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 ?
Re: Algorithm for reversing the GoL rules
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
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
Re: Algorithm for reversing the GoL rules
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.
-
- Posts: 841
- Joined: June 27th, 2009, 10:58 am
- Location: Germany
Re: Algorithm for reversing the GoL rules
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.
Not much different from what‘s already used, but with the additional minimal limit for number of predecessors.
Re: Algorithm for reversing the GoL rules
Thanks, this is interesting.dvgrn wrote: ↑February 18th, 2022, 7:32 amThat'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.
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.
Re: Algorithm for reversing the GoL rules
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.)
Re: Algorithm for reversing the GoL rules
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.dvgrn wrote: ↑February 18th, 2022, 10:40 amWould 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.)
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
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")
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
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!
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.
Re: Algorithm for reversing the GoL rules
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.
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.
Re: Algorithm for reversing the GoL rules
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
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’
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
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 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!
Code: Select all
Getting search pattern...
Done
Preprocessing...
Unsatisfiability proved in preprocessing
Done
Time taken: 0 seconds
Unsatisfiable
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.