rstatoropt

[amling]

Automated, best-effort stator optimization in strips:
https://github.com/amling/rstatoropt

EDIT 2023/12/06: moved to https://codeberg.org/amling/rstatoropt

For starters I ran it on a collection suggested to me [1] and it produced quite a few reductions, even when restricted to not increase bounding box.

Some of these might be "right", e.g. a few examined by hand but more or less randomly:

Code: Select all

x = 117, y = 131, rule = B3/S23
5bo2bo2bo66b2o$5b7o66b2o$75bo$5b7o63b7o$4bo7bo60b2o7bo$2obob2o3b2obob
2o53bobo2b2o3b2obo$bobobo5bobobo54b2obobo5bobo$bobo9bobo57bo9bob2o$2ob
o9bob2o56bo9bob2o$bobo9bobo54b2obo9bo$bobobo5bobobo54bo2bobo5bobo$2obo
b2o3b2obob2o55bo2b2o3b2ob2o$4bo7bo60b2o7bo$5b7o63b6obo$75bo5bo$5b7o66b
3o$5bo2bo2bo66bo24$10bo$8b5o$7bo5bo59b2o9bo$7bo2b2obo22bo37bo5b2obobo$
3bob3obobob2o19b5o34bo5bobob2o$3b2o4bo23bo5bo33b2o4bo22bo8b2o$6b2ob2o
22bob2o2bo36b2ob2o20bobob2o4bo$b5obobo2bo19b2obobob3obo27b5obobo2bo19b
2obobo5bo$o6bo3bobo23bo4b2o26bo6bo3bobo23bo4b2o$2o2b5ob2obo22b2ob2o29b
2o2b5ob2obo22b2ob2o$12b2o20bo2bobob5o36b2o20bo2bobob5o$5b2o4b3o12bo6bo
bo3bo6bo28b2o4b3o12bo6bobo3bo6bo$5b2o4b3o5b2o4bobo5bob2ob5o2b2o28b2o4b
3o5b2o4bobo5bob2ob5o2b2o$12b2o4bo2bo3bo2bo4b2o47b2o4bo2bo3bo2bo4b2o$2o
2b5ob2obo5bobo4b2o5b3o4b2o28b2o2b5ob2obo5bobo4b2o5b3o4b2o$o6bo3bobo6bo
12b3o4b2o28bo6bo3bobo6bo12b3o4b2o$b5obobo2bo20b2o36b5obobo2bo20b2o$6b
2ob2o22bob2ob5o2b2o29b2ob2o22bob2ob5o2b2o$3b2o4bo23bobo3bo6bo26b2o4bo
23bobo3bo6bo$3bob3obobob2o19bo2bobob5o27bo5bobob2o19bo2bobob5o$7bo2b2o
bo22b2ob2o33bo5b2obobo20b2ob2o$7bo5bo23bo4b2o29b2o9bo22bo4b2o$8b5o19b
2obobob3obo58b2obobo5bo$10bo22bob2o2bo61bobob2o4bo$33bo5bo62bo8b2o$34b
5o$36bo24$8b2o4b2o61b2o4b2o$7bobo4bobo59bobo4bobo$7bo8bo59bo8bo$4b2obo
bo4bobob2o51bob2obobo4bobob2obo$5bobobo4bobobo52b2obobobo4bobobob2o$4b
o2bobob2obobo2bo56bobob2obobo$4bobo2b2o2b2o2bobo55bo2b2o2b2o2bo$2b3ob
2obo4bob2ob3o53b2obo4bob2o$bo8bo2bo8bo56bo2bo$bo2b5o6b5o2bo50b5o6b5o$
2obo16bob2o48bo16bob2o$bob2o3b2o4b2o3b2obo49b2o3b2o4b2o3b2obo$bo7b6o7b
o55b6o7bo$2b3o2b2o6b2o2b3o48b4o2b2o6b2o2b3o$4bo14bo50bo2bo14bo2$24b2o
67b2o$2b2o2bo13b3o2bo45b2o2bo13b3o2bo$2bo2b2o6bo9b2o46bo2b2o6bo9b2o$3b
5o4bobo4bo52b5o4bobo4bo$12bobo4bo61bobo4bo$13bo9b2o57bo9b2o$3b5o12b3o
2bo46b5o12b3o2bo$2bo2b2o17b2o45bo2b2o17b2o$2b2o2bo8b2o54b2o2bo8b2o2$8b
o3bo6bo3bo53bo3bo6bo3bo2bo$6b3o2bo8bo2b3o49b3o2bo8bo2b4o$5bo3b3o3b2o3b
3o3bo47bo3b3o3b2o3b3o$5bob2ob5o2b5ob2obo47bob2ob5o2b5ob2o$4b2obo6b4o6b
ob2o45b2obo6b4o6bo$5bo2b5obo2bob5o2bo50b5obo2bob5o$5bo7b2o2b2o7bo55b2o
2b2o$6b3ob2obo4bob2ob3o53b2obo4bob2o$8bobo2bo4bo2bobo55bo2bo4bo2bo$8bo
2bobo4bobo2bo51b2o3bobo4bobo3b2o$9bobob6obobo52bo2bobob6obobo2bo$8b2ob
2o2b2o2b2ob2o53b2ob2o2b2o2b2ob2o$11bo8bo59bo8bo$11bobo4bobo59bobo4bobo
$12b2o4b2o61b2o4b2o!

Some maybe less, e.g.:

Code: Select all

x = 35, y = 7, rule = B3/S23
2b2ob2o$bobob2o27bo$o2bo30bo$2o3b2o27bo$3bo2bo$2obobo$2ob2o!

This is the unfortunate result of the optimizer only considering the rotor per se to be the identity of the oscillator and so deciding that entire complex oscillator just wants to be a blinker. It's technically correct per its intended programming although maybe not what a human would decide...

Attached is a tarball of the 119 reductions from running it with arguments 0 (don't increase bounding box) and 10 (width of optimization strips) on the 893 individual oscillators some light analysis had dumped out of that collection. The "manifest" has a list of oscillator IDs (assigned by original analyzer/splitter) and then the "before" and "after" files are dumped into folders sorted by period.

I'm guessing at a minimum P2 and P3 aren't going to be very interesting since many of them seem to be somewhat more artistic and/or have a different notion of oscillator identity than the optimizer. As for the rest, who can say?

[1] https://github.com/dvgrn/b3s23osc

[LaundryPizza03]

Is this script specific to Conway's Life, or does it also work for OCA? Your fore and back test case, in particular, should be minimal in the non-totalistic rule B1e3/S23. It should be easy to verify manually.

Code: Select all

x = 7, y = 7, rule = B1e3/S23
2ob2o$2obobo$6bo$3ob3o$o$bobob2o$2b2ob2o!

[amling]

Is this script specific to Conway's Life, or does it also work for OCA? Your fore and back test case, in particular, should be minimal in the non-totalistic rule B1e3/S23. It should be easy to verify manually.

Code: Select all

x = 7, y = 7, rule = B1e3/S23
2ob2o$2obobo$6bo$3ob3o$o$bobob2o$2b2ob2o!

Uh, not strictly specific to B3/S23, although the code as written is. Rule is encoded in "f_live":

Code: Select all

fn f_live(live: usize, nh: usize) -> bool {
    let magic_ct = 2 * nh + 1 - live;
    6 <= magic_ct && magic_ct <= 8
}

The optimizations are however specific to what the wiki informs me would be called "outer totalistic", namely that the immediate future of a cell is determined by its own liveness and the count of live neighbors.

[Sokwe]

This is the unfortunate result of the optimizer only considering the rotor per se to be the identity of the oscillator and so deciding that entire complex oscillator just wants to be a blinker. It's technically correct per its intended programming although maybe not what a human would decide...

One way you might be able to get around this is by allowing the user to set some stator cells as fixed, so that they can't be changed by the optimizer. So, for example, you could fix the center of the blinker rotor to be off.

[amling]

One way you might be able to get around this is by allowing the user to set some stator cells as fixed, so that they can't be changed by the optimizer. So, for example, you could fix the center of the blinker rotor to be off.

Any cell it considers "rotor" it will leave alone. Right now the rotor analysis happens to pick rotor strictly but I had considered modifying it to understand input "r" for "cell is off but please consider it rotor anyway" and "R" for "cell is on but please consider it rotor anyway". Either way not relevant for batch optimization of existing pattern collection.

EDIT: Done, but you can't win them all, now it optimizes

Code: Select all

**.**..
**.*.*.
......*
***r***
*......
.*.*.**
..**.**

to

Code: Select all

...**
....*
.*.*.
*....
**...

[hkoenig]

There are a number of possible casings for that rotor. Which one of these were you expecting?

Code: Select all

x=103, y=9, rule = B3/S23
3o9b2o10b2o3b2o5b2o10b2ob2o7b2ob2obo5b2ob2obo5b2ob2o2b2o3b2ob2obo$12bobo9b
o4bo6bobo3b2o4b2obobo6b2obob2o5b2obob2o5b2obo2bobo4bobob2o$25b3obo8bo2bob
o7bo2bo8bo11bo11bo8bo2bo$14bobo10bob2o7b2o8b2o3b2o5b2o3b2o5b2o3b2o8b2obo5b
2o3b2o$15b2o10bobo2bo8bo6bo2bo8bo2bo2bo5bo2bo2bo12bo7bo2bo$31b2o5b2obo7bob
ob2o6bobobo7bobobo9b5o4b2obobo$25bobo10b2ob3o6b2ob2o5b2ob2o9b2ob2o8bo8bob
2ob2o$25b2o17bo44bo$43b2o43b2o!

[amling]

There are a number of possible casings for that rotor. Which one of these were you expecting?

Code: Select all

x=103, y=9, rule = B3/S23
3o9b2o10b2o3b2o5b2o10b2ob2o7b2ob2obo5b2ob2obo5b2ob2o2b2o3b2ob2obo$12bobo9b
o4bo6bobo3b2o4b2obobo6b2obob2o5b2obob2o5b2obo2bobo4bobob2o$25b3obo8bo2bob
o7bo2bo8bo11bo11bo8bo2bo$14bobo10bob2o7b2o8b2o3b2o5b2o3b2o5b2o3b2o8b2obo5b
2o3b2o$15b2o10bobo2bo8bo6bo2bo8bo2bo2bo5bo2bo2bo12bo7bo2bo$31b2o5b2obo7bob
ob2o6bobobo7bobobo9b5o4b2obobo$25bobo10b2ob3o6b2ob2o5b2ob2o9b2ob2o8bo8bob
2ob2o$25b2o17bo44bo$43b2o43b2o!

I wasn't "expecting" anything, the program works as designed. It's less evidence against "the program does what I intended" and more evidence against "any optimizations per this definition of oscillators from that collection will be interesting because that collection 'is thought to be optimal'".

[Sokwe]

How feasible do you think your method would be for finding the intersection of all minimal stators for a particular oscillator. Here I mean that a cell is in the intersection of two patterns if it has the same state in both patterns. For example, consider the p5 you used as an example in your first post:

Code: Select all

x = 87, y = 17, rule = B3/S23
5bo2bo2bo66b2o$5b7o66b2o$75bo$5b7o63b7o$4bo7bo60b2o7bo$2obob2o3b2obob
2o53bobo2b2o3b2obo$bobobo5bobobo54b2obobo5bobo$bobo9bobo57bo9bob2o$2ob
o9bob2o56bo9bob2o$bobo9bobo54b2obo9bo$bobobo5bobobo54bo2bobo5bobo$2obo
b2o3b2obob2o55bo2b2o3b2ob2o$4bo7bo60b2o7bo$5b7o63b6obo$75bo5bo$5b7o66b
3o$5bo2bo2bo66bo!

I used JLS to find the intersection (or "combination", as JLS calls it) of all 68-cell variants fitting in a 17×17 bounding box, which looks like this:

Code: Select all

.....???????.....
......?????......
.....?.....?.....
....??*****??....
...?*...r...*?...
?.??.R*rrr*R.??.?
??.*.*rr.rr*.*.??
??.*.rr...rr.*.??
??.*rr.....rr*.??
??.*.rr...rr.*.??
??.*.*rr.rr*.*.??
?.??.R*rrr*R.??.?
...?*...r...*?...
....??*****??....
.....?.....?.....
......?????......
.....???????.....

where '?' is a stator cell not in the intersection. JLS is too slow to do this in most cases, so I was wondering if your method might yield a faster solution.

[Scorbie]

For those who are lazy and just want to paste whatever the script outputs, postprocess the results with sed.

Code: Select all

cargo run --release m n < input-file 2>&1 | sed 's/r/./g'

Or using here documents,

Code: Select all

cargo run --release m n << EOF 2>&1 | sed 's/r/./g'
(Paste your dot star pattern here)
EOF

Sometimes I'm even lazy to do `sed 's/r/./g'` so I do `sed 's r . g'` instead.

[hotdogPi]

7: 44P7 is a sparker and needs clearance; other three reduced.
8: Two reduced, one not reduced because RLE size, one deleted due to similarity with others.
9: Billiard table reduced; honey farm hassler previously had major p3 rotor reduction.
10: Wick reduced, sparker deleted because it's too large and obsoleted by 55P10 anyway, blinker hassler previously had a huge rotor reduction.
11: One partially changed (eater 2 is kept in standard form; they're identical in population), one deleted for being similar, and one not changed because RLE size.
12: All four changed.
13: Changed. 53P13 needs an update on the wiki page.
15: Bi-block hassler changed; the other is that way to preserve symmetry.
17: Changed.
18: One changed; also a two-row reduction. The other is that way to preserve symmetry.
20: One changed; the other two have had major reductions that aren't live yet.
21: Traffic light hassler changed despite lower clearance because the p7 keeps the original form. Also a 4-row reduction. The other one would have a larger RLE size if chnaged.
25: Loaf hassler changed. Wing and block hassler half changed; the higher-clearance p5 sparker should be shown at least somewhere in the collection.
27: Changed.
30: Both reduced. Both are also bounding box reductions. Wondering why one side has a snake and the other an aircraft carrier, though.
35: Changed. It's also a 2-row reduction.
45: Want to preserve symmetry.
50: One has been reduced but isn't live yet (it's actually in jslife), and the other has been deleted for being a simple phase change on an already existing p25.
55: There's a recently discovered more compact form that's not live yet.
56: Changed.
57: Changed. Reduced by 6 rows; the wiki article on 258P3 needs an update.
74: This has already been changed; it's just not live yet.
90: Changed. While it's actually one byte more, it still feels better in the reduced form.
110: Reduced. (It's still one of the largest, but I know this program only reduces stators, not rotors.)
188: One changed, the other not due to RLE size difference.
225: Want to preserve symmetry.
230: There's a smaller form that isn't live yet but uses smaller p5s the same way one of the p50s does.
246: I optimize RLE size over population.
532: I optimize RLE size over population.

I also checked p5, p6, and the larger p4s, despite no summary above.

[amling]

How feasible do you think your method would be for finding the intersection of all minimal stators for a particular oscillator. Here I mean that a cell is in the intersection of two patterns if it has the same state in both patterns.

The tricky bit is probably defining "all" and "minimal" in "all minimal stators". Right now rstatoropt breaks ties in a single strip of optimization by preferring existing contents and then by strip contents themselves making each strip optimization deterministic (we still do strips in random order so overall still random). This could be changed to pick among ties randomly and thereby randomly walk between a bunch of matched population variants. Something something decide how long you want to run for something something.

What is the goal/use for the intersection of minimal stators?

[Sokwe]

The tricky bit is probably defining "all" and "minimal" in "all minimal stators".

By "minimal", I meant having minimum population. By "all", I meant all within a given bounding box.

What is the goal/use for the intersection of minimal stators?

When minimizing an oscillator, I like to consider all possibilities, so I can make a final decision on a "canonical" form based on aesthetics. For example, the p5 in your first post can be minimized with 90-degree rotational symmetry:

Code: Select all

x = 17, y = 17, rule = B3/S23
8bo$8b3o$5bo5bo$5b6obo$3b2o7bo$2bo2b2o3b2ob2o$bobobo5bobo$bobo9bo$2obo
9bob2o$3bo9bobo$3bobo5bobobo$2b2ob2o3b2o2bo$4bo7b2o$4bob6o$5bo5bo$6b3o
$8bo!

This feature is ultimately unimportant, so you shouldn't feel the need to implement it.

[DroneBetter]

I have gotten much use out of this, for both reducing my own rudimentary oscillator search results (to find that their rotors are already parts of known oscillators) and perusing old forgotten billiard table oscillators on the wiki to see whether there is a reduction no-one thought to note (which worked for New five (29 -> 28) and 123P27.1 (123 -> 120)), thank you very much for it.

Could you allow inputted patterns to have four additional cell types labelled, representing each combination of 'stator that is [off/on] that I would like to be [off/on] in the output,' so modifications of slices containing them would constrain themselves to searching only the stator configurations that contain them in the desired state (or return it unmodified if impossible, in case another slice can solve it)? Then one would be able to increase oscillators' clearances with it as well as reduce population, or minimise the noninteracting portion of an eater/drifter-style still life.

[amling]

Could you allow inputted patterns to have four additional cell types labelled, representing each combination of 'stator that is [off/on] that I would like to be [off/on] in the output,' so modifications of slices containing them would constrain themselves to searching only the stator configurations that contain them in the desired state (or return it unmodified if impossible, in case another slice can solve it)? Then one would be able to increase oscillators' clearances with it as well as reduce population, or minimise the noninteracting portion of an eater/drifter-style still life.

"r" is already off/off and "R" is on/on (the internals think of it as a rotor cell that is always off/on then, but the effect is the same).

As for forcing a stator cell to be on or off instead of what it was in input, it does not sit well with the rest of the algorithm, at least in my recollection of it. It might work to do as you suggest: search each strip constrained as requested, but now a strip search can fail at worst instead of finding the existing solution at worst in which case you'd just refuse to replace. I'll go digging when I'm at a real computer to see if I can swing it.

rstatoropt is really designed to be a piecemeal optimizer, not a solver, and I think this type of problem might be better served by a program more oriented that way.

[amling]

Could you allow inputted patterns to have four additional cell types labelled, representing each combination of 'stator that is [off/on] that I would like to be [off/on] in the output,' so modifications of slices containing them would constrain themselves to searching only the stator configurations that contain them in the desired state (or return it unmodified if impossible, in case another slice can solve it)? Then one would be able to increase oscillators' clearances with it as well as reduce population, or minimise the noninteracting portion of an eater/drifter-style still life.

I'll go digging when I'm at a real computer to see if I can swing it.

I have a criminally rough sketch of this pushed up to codeberg as 20240210-forces-01. "f" marks a cell which is off but which any alteration must turn on and "F" marks a cell which is on but any alteration must turn off. It's a huge mess for a variety of reasons and I'm not really sure how to clean it up.

The biggest problem is that it thrashes constantly. Normally it refuses alterations that do not strictly reduce population which thus prevents useless fiddling of equal-size solutions. But now we have to accept even strip solutions that make population worse (as they might fix such forced cells). Probably we want to do something like accept a change if there were forced cells it fixes or it reduced population. I guess I have to think on it, but I'm not too excited about this change in general.

In the meantime it generally works (at least in my testing), although it does not always succeed in completing the forced changes and it outputs a lot of useless thrashing on the way.

[DroneBetter]

Another proposal, if you wouldn't mind: cells could be labelled c and C in the input, to be treated as constantly off and on irrespective of neighbours' states, such that all changes to slices containing them are forced to replace them with configurations of ordinary stators.

This would allow rstatoropt to weld different objects together.

[amling]

Another proposal, if you wouldn't mind: cells could be labelled c and C in the input, to be treated as constantly off and on irrespective of neighbours' states, such that all changes to slices containing them are forced to replace them with configurations of ordinary stators.

This would allow rstatoropt to weld different objects together.

I am not sure I follow, perhaps an example and how you imagine it going when run would help?

Generally I would try to solve welding problems with an actual search program. I assume anything searching for still-life-only completions is going to be insanely fast.

[DroneBetter]

I am not sure I follow, perhaps an example and how you imagine it going when run would help?

50P9 has a small rotor and a large stator; in the case of wanting to weld multiple, one would be able to input a significantly smaller pattern (with constant cells placed in the neighburhood of all non-exposed rotor), allowing them to be placed closer

Code: Select all

instead of this,   only this
........rr........ ........rr........
.......rrrr....... .......rrrr.......
....rrRRrrRRrr.... ....rrRRrrRRrr....
....rRrrRRrrRr.... ....rRrrRRrrRr....
...*.R.RRRR.R.*... ...CcRcRRRRcRcC...
.***.*.R..R.*.***. ....cCcRccRcCc....
*...**.****.**...* ......cCCCCc......
.**...*....*...**. ........cc........
...**..*..*..**... ..................
...*.**....**.*... ..................

it would be maybe less efficient than JLS but more convenient, allowing it to find (minimal) stator completions as well as optimisations

it wouldn't be too difficult to implement, right?

[amling]

I am not sure I follow, perhaps an example and how you imagine it going when run would help?

50P9 has a small rotor and a large stator; in the case of wanting to weld multiple, one would be able to input a significantly smaller pattern (with constant cells placed in the neighburhood of all non-exposed rotor), allowing them to be placed closer

Code: Select all

instead of this,   only this
........rr........ ........rr........
.......rrrr....... .......rrrr.......
....rrRRrrRRrr.... ....rrRRrrRRrr....
....rRrrRRrrRr.... ....rRrrRRrrRr....
...*.R.RRRR.R.*... ...CcRcRRRRcRcC...
.***.*.R..R.*.***. ....cCcRccRcCc....
*...**.****.**...* ......cCCCCc......
.**...*....*...**. ........cc........
...**..*..*..**... ..................
...*.**....**.*... ..................

it would be maybe less efficient than JLS but more convenient, allowing it to find (minimal) stator completions as well as optimisations

it wouldn't be too difficult to implement, right?

Unfortunately my understanding has only reached "user wants to input incomplete stator" not "completely specified algorithm" and until I have the latter I cannot make a computer do anything. In particular I am still stuck on how we would optimize from step to step. Even if we invent some sort of notion of intermediate state with errors (representing something like the c's) what would then constitute a legal step for a single strip's search? Would it have to fix all the errors? Just produce a strip with fewer errors? It's not even clear there is a path to a completed pattern that reduces the number of errors all the way (what if the stator has to get wider before it gets thinner and solves?). Not to mention what on earth to do with errors in the boundaries of the strip. Normally the boundaries (which are two cells wide) are all left fixed so compatibility between the possibly-changed strip and the rest of the pattern is guaranteed.

"Incomplete stator" seems to me like the sort of thing that goes into search programs, not optimization programs and this sort of thing still sounds like exactly what I would use a real search program for. As a extremely quick and dirty example, trying to demonstrate welding two of this sparker nearish each other, this input file (3.in):

Code: Select all

| ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ |
| ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ |
| ............................ | ............................ | ............................ | ................**.......... | ............................ | ............................ | ............................ | ............................ | ............................ |
| ............................ | ............................ | ...............****......... | ............................ | ............................ | ............................ | ................**.......... | ...............*..*......... | ............................ |
| ..............**..**........ | ..............******........ | .............********....... | ............**......**...... | ................**.......... | ...............****......... | ...............****......... | ...............*..*......... | ..............**..**........ |
| ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. |

and constraint (3.cstr):

Code: Select all

| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999..9999999999 | 9999999999999999..9999999999 | 9999999999999999..9999999999 | 9999999999999999**9999999999 | 9999999999999999..9999999999 | 9999999999999999..9999999999 | 9999999999999999..9999999999 | 9999999999999999..9999999999 | 9999999999999999..9999999999 |
| 999999999999999....999999999 | 999999999999999....999999999 | 999999999999999****999999999 | 999999999999999....999999999 | 999999999999999....999999999 | 999999999999999....999999999 | 999999999999999.**.999999999 | 999999999999999*..*999999999 | 999999999999999....999999999 |
| 999999999999..**..**..999999 | 999999999999..******..999999 | 999999999999.********.999999 | 999999999999**......**999999 | 999999999999....**....999999 | 999999999999...****...999999 | 999999999999...****...999999 | 999999999999...*..*...999999 | 999999999999..**..**..999999 |
| 999999999999.*..**..*.999999 | 999999999999**......**999999 | 999999999999**......**999999 | 999999999999...****...999999 | 999999999999.**.**.**.999999 | 999999999999..*....*..999999 | 999999999999..*....*..999999 | 999999999999..*....*..999999 | 999999999999..**..**..999999 |
| 9999999999999*9****9*9999999 | 9999999999999*9*..*9*9999999 | 9999999999999*9....9*9999999 | 9999999999999*9....9*9999999 | 9999999999999.9*..*9.9999999 | 9999999999999*9*..*9*9999999 | 9999999999999*9*..*9*9999999 | 9999999999999*9*..*9*9999999 | 9999999999999*9*..*9*9999999 |
| 999999999999999*99*999999999 | 999999999999999.99.999999999 | 999999999999999*99*999999999 | 999999999999999*99*999999999 | 999999999999999*99*999999999 | 999999999999999*99*999999999 | 999999999999999*99*999999999 | 999999999999999*99*999999999 | 999999999999999*99*999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999..9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999*.9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 |
| 9999.**999999999999999999999 | 9999.**999999999999999999999 | 9999***999999999999999999999 | 9999*.*999999999999999999999 | 9999.*.999999999999999999999 | 9999..*999999999999999999999 | 9999..*999999999999999999999 | 9999..*999999999999999999999 | 9999..*999999999999999999999 |
| 9999*.9999999999999999999999 | 9999*.9999999999999999999999 | 9999*.9999999999999999999999 | 9999..9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999**9999999999999999999999 |
| 999.*.**99999999999999999999 | 999.*.*.99999999999999999999 | 999**..*99999999999999999999 | 999..*.*99999999999999999999 | 999...**99999999999999999999 | 999.*.**99999999999999999999 | 999.*.**99999999999999999999 | 999**.**99999999999999999999 | 999.****99999999999999999999 |
| 99...**999999999999999999999 | 99..*..999999999999999999999 | 99.**..999999999999999999999 | 99*..*.999999999999999999999 | 99..**.999999999999999999999 | 99..*..999999999999999999999 | 99.**..999999999999999999999 | 99.....999999999999999999999 | 99.....999999999999999999999 |
| 99...**999999999999999999999 | 99..*..999999999999999999999 | 99.**..999999999999999999999 | 99*..*.999999999999999999999 | 99..**.999999999999999999999 | 99..*..999999999999999999999 | 99.**..999999999999999999999 | 99.....999999999999999999999 | 99.....999999999999999999999 |
| 999.*.**99999999999999999999 | 999.*.*.99999999999999999999 | 999**..*99999999999999999999 | 999..*.*99999999999999999999 | 999...**99999999999999999999 | 999.*.**99999999999999999999 | 999.*.**99999999999999999999 | 999**.**99999999999999999999 | 999.****99999999999999999999 |
| 9999*.9999999999999999999999 | 9999*.9999999999999999999999 | 9999*.9999999999999999999999 | 9999..9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999**9999999999999999999999 |
| 9999.**999999999999999999999 | 9999.**999999999999999999999 | 9999***999999999999999999999 | 9999*.*999999999999999999999 | 9999.*.999999999999999999999 | 9999..*999999999999999999999 | 9999..*999999999999999999999 | 9999..*999999999999999999999 | 9999..*999999999999999999999 |
| 9999..9999999999999999999999 | 9999.*9999999999999999999999 | 9999.*9999999999999999999999 | 9999*.9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 | 9999..9999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |
| 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 | 9999999999999999999999999999 |

can be run like:

Code: Select all

rlife llsss p9 3.in --constraint grid:3.cstr:pd:9 00 00 00

and produce partials like this:

Code: Select all

x = 280, y = 19, rule = LifeHistory
F.28B.F.28B.F.15B4A9B.F.28B.F.28B.F.28B.F.16B2A10B.F.15BA2BA9B.F.28B.
F$F.14B2A2B2A8B.F.14B6A8B.F.13B8A7B.F.12B2A6B2A6B.F.16B2A10B.F.15B4A
9B.F.15B4A9B.F.15BA2BA9B.F.14B2A2B2A8B.F$F.13BA2B2A2BA7B.F.12B2A6B2A
6B.F.12B2A6B2A6B.F.15B4A9B.F.13B2AB2AB2A7B.F.14BA4BA8B.F.14BA4BA8B.F.
14BA4BA8B.F.14B2A2B2A8B.F$F.11BABAB4ABABA2BA2B.F.11BABABA2BABABA2BA2B
.F.11BABA6BABA2BA2B.F.11BABA6BABA2BA2B.F.11BA3BA2BA3BA2BA2B.F.11BABAB
A2BABABA2BA2B.F.11BABABA2BABABA2BA2B.F.11BABABA2BABABA2BA2B.F.11BABAB
A2BABABA2BA2B.F$F.9B3ABABA2BABAB4A2B.F.9B3ABA6BAB4A2B.F.9B3ABABA2BABA
B4A2B.F.9B3ABABA2BABAB4A2B.F.9B3ABABA2BABAB4A2B.F.9B3ABABA2BABAB4A2B.
F.9B3ABABA2BABAB4A2B.F.9B3ABABA2BABAB4A2B.F.9B3ABABA2BABAB4A2B.F$F.8B
A3B2AB4AB2A6B.F.8BA3B2AB4AB2A6B.F.8BA3B2AB4AB2A6B.F.8BA3B2AB4AB2A6B.F
.8BA3B2AB4AB2A6B.F.8BA3B2AB4AB2A6B.F.8BA3B2AB4AB2A6B.F.8BA3B2AB4AB2A
6B.F.8BA3B2AB4AB2A6B.F$F.7BA2BA3BA4BA3BA4B.F.7BA2BA3BA4BA3BA4B.F.7BA
2BA3BA4BA3BA4B.F.7BA2BA3BA4BA3BA4B.F.7BA2BA3BA4BA3BA4B.F.7BA2BA3BA4BA
3BA4B.F.7BA2BA3BA4BA3BA4B.F.7BA2BA3BA4BA3BA4B.F.7BA2BA3BA4BA3BA4B.F$F
.7BAB2AB2A2B2A2BAB2A4B.F.7BAB2AB2A2B2A2BAB2A4B.F.7BAB2AB2A2B2A2BAB2A
4B.F.7BAB2AB2A2B2A2BAB2A4B.F.7BAB2AB2A2B2A2BAB2A4B.F.7BAB2AB2A2B2A2BA
B2A4B.F.7BAB2AB2A2B2A2BAB2A4B.F.7BAB2AB2A2B2A2BAB2A4B.F.7BAB2AB2A2B2A
2BAB2A4B.F$F.6B2A3BA5BAB2ABA5B.F.6B2A3BA5BAB2ABA5B.F.6B2A3BA5BAB2ABA
5B.F.6B2A3BA5BAB2ABA5B.F.6B2A3BA5BAB2ABA5B.F.6B2A3BA5BAB2ABA5B.F.6B2A
3BA5BAB2ABA5B.F.6B2A3BA5BAB2ABA5B.F.6B2A3BA5BAB2ABA5B.F$F.8BABA2B4A2B
A3BA4B.F.5BA2BABA2B4A2BA3BA4B.F.5BA2BABA2B4A2BA3BA4B.F.4BA3BABA2B4A2B
A3BA4B.F.8BABA2B4A2BA3BA4B.F.8BABA2B4A2BA3BA4B.F.8BABA2B4A2BA3BA4B.F.
8BABA2B4A2BA3BA4B.F.8BABA2B4A2BA3BA4B.F$F.5B4ABAB2A3B2A2B2A2BA2B.F.5B
4ABAB2A3B2A2B2A2BA2B.F.4B5ABAB2A3B2A2B2A2BA2B.F.4BAB3ABAB2A3B2A2B2A2B
A2B.F.5BAB2ABAB2A3B2A2B2A2BA2B.F.6B3ABAB2A3B2A2B2A2BA2B.F.6B3ABAB2A3B
2A2B2A2BA2B.F.6B3ABAB2A3B2A2B2A2BA2B.F.6B3ABAB2A3B2A2B2A2BA2B.F$F.4BA
4BABA4BA5BAB2A2B.F.4BA4BABA4BA5BAB2A2B.F.4BA4BABA4BA5BAB2A2B.F.9BABA
4BA5BAB2A2B.F.5BA3BABA4BA5BAB2A2B.F.5BA3BABA4BA5BAB2A2B.F.5BA3BABA4BA
5BAB2A2B.F.5BA3BABA4BA5BAB2A2B.F.4B2A3BABA4BA5BAB2A2B.F$F.4BAB3A2BA5B
ABA2BA5B.F.4BABABA2BA5BABA2BA5B.F.3B2A2B2A2BA5BABA2BA5B.F.5BAB2A2BA5B
ABA2BA5B.F.6B3A2BA5BABA2BA5B.F.4BAB3A2BA5BABA2BA5B.F.4BAB3A2BA5BABA2B
A5B.F.3B2AB3A2BA5BABA2BA5B.F.4B5A2BA5BABA2BA5B.F$F.5B2ABABA7B2A3B3A2B
.F.4BA3BABA7B2A3B3A2B.F.3B2A3BABA7B2A3B3A2B.F.2BA2BA2BABA7B2A3B3A2B.F
.4B2A2BABA7B2A3B3A2B.F.4BA3BABA7B2A3B3A2B.F.3B2A3BABA7B2A3B3A2B.F.8BA
BA7B2A3B3A2B.F.8BABA7B2A3B3A2B.F$F.5B2ABA2B3A11BA2B.F.4BA3BA2B3A11BA
2B.F.3B2A3BA2B3A11BA2B.F.2BA2BA2BA2B3A11BA2B.F.4B2A2BA2B3A11BA2B.F.4B
A3BA2B3A11BA2B.F.3B2A3BA2B3A11BA2B.F.8BA2B3A11BA2B.F.8BA2B3A11BA2B.F$
F.4BAB3A5BA13B.F.4BABABA5BA13B.F.3B2A2B2A5BA13B.F.5BAB2A5BA13B.F.6B3A
5BA13B.F.4BAB3A5BA13B.F.4BAB3A5BA13B.F.3B2AB3A5BA13B.F.4B5A5BA13B.F$F
.4BA4B3A2BA13B.F.4BA4B3A2BA13B.F.4BA4B3A2BA13B.F.9B3A2BA13B.F.5BA3B3A
2BA13B.F.5BA3B3A2BA13B.F.5BA3B3A2BA13B.F.5BA3B3A2BA13B.F.4B2A3B3A2BA
13B.F$F.5B4A3BABAB2A10B.F.5B4A3BABAB2A10B.F.4B5A3BABAB2A10B.F.4BAB3A
3BABAB2A10B.F.5BAB2A3BABAB2A10B.F.6B3A3BABAB2A10B.F.6B3A3BABAB2A10B.F
.6B3A3BABAB2A10B.F.6B3A3BABAB2A10B.F$F.8BA2BA2BA2BA10B.F.5BA2BA2BA2BA
2BA10B.F.5BA2BA2BA2BA2BA10B.F.4BA3BA2BA2BA2BA10B.F.8BA2BA2BA2BA10B.F.
8BA2BA2BA2BA10B.F.8BA2BA2BA2BA10B.F.8BA2BA2BA2BA10B.F.8BA2BA2BA2BA10B
.F!

It did not complete before filling 8 GB (the limit I set) and dying but it's likely solvable and as a demo it will suffice. Proper search programs also have the benefit of allowing encoding exact clearance (by replacing 9s with dots in the constraint), more sophisticated and explicit control of search branches, sizes and directions, etc.

EDIT: As a further demo, taking a random longer partial and seeding a nearly identical search with a longer input file (`3b.in`):

Code: Select all

| ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ |
| ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ | ............................ |
| ............................ | ............................ | ............................ | ................**.......... | ............................ | ............................ | ............................ | ............................ | ............................ |
| ............................ | ............................ | ...............****......... | ............................ | ............................ | ............................ | ................**.......... | ...............*..*......... | ............................ |
| ..............**..**........ | ..............******........ | .............********....... | ............**......**...... | ................**.......... | ...............****......... | ...............****......... | ...............*..*......... | ..............**..**........ |
| .............*..**..*....... | ............**......**...... | ............**......**...... | ...............****......... | .............**.**.**....... | ..............*....*........ | ..............*....*........ | ..............*....*........ | ..............**..**........ |
| ...........*.*.****.*.*..*.. | ...........*.*.*..*.*.*..*.. | ...........*.*......*.*..*.. | ...........*.*......*.*..*.. | ...........*...*..*...*..*.. | ...........*.*.*..*.*.*..*.. | ...........*.*.*..*.*.*..*.. | ...........*.*.*..*.*.*..*.. | ...........*.*.*..*.*.*..*.. |
| .........***.*.*..*.*.****.. | .........***.*......*.****.. | .........***.*.*..*.*.****.. | .........***.*.*..*.*.****.. | .........***.*.*..*.*.****.. | .........***.*.*..*.*.****.. | .........***.*.*..*.*.****.. | .........***.*.*..*.*.****.. | .........***.*.*..*.*.****.. |
| ........*...**.****.**...... | ........*...**.****.**...... | ........*...**.****.**...... | ........*...**.****.**...... | ........*...**.****.**...... | ........*...**.****.**...... | ........*...**.****.**...... | ........*...**.****.**...... | ........*...**.****.**...... |
| .......*..*...*....*...*.... | .......*..*...*....*...*.... | .......*..*...*....*...*.... | .......*..*...*....*...*.... | .......*..*...*....*...*.... | .......*..*...*....*...*.... | .......*..*...*....*...*.... | .......*..*...*....*...*.... | .......*..*...*....*...*.... |
| .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... | .......*.**.**..**..*.**.... |
| ......**...*.....*.**.*..... | ......**...*.....*.**.*..... | ......**...*.....*.**.*..... | ......**...*.....*.**.*..... | ......**...*.....*.**.*..... | ......**...*.....*.**.*..... | ......**...*.....*.**.*..... | ......**...*.....*.**.*..... | ......**...*.....*.**.*..... |
| ........*.*..****..*...*.... | .....*..*.*..****..*...*.... | .....*..*.*..****..*...*.... | ....*...*.*..****..*...*.... | ........*.*..****..*...*.... | ........*.*..****..*...*.... | ........*.*..****..*...*.... | ........*.*..****..*...*.... | ........*.*..****..*...*.... |
| .....****.*.**...**..**..*.. | .....****.*.**...**..**..*.. | ....*****.*.**...**..**..*.. | ....*.***.*.**...**..**..*.. | .....*.**.*.**...**..**..*.. | ......***.*.**...**..**..*.. | ......***.*.**...**..**..*.. | ......***.*.**...**..**..*.. | ......***.*.**...**..**..*.. |
| ....*....*.*....*.....*.**.. | ....*....*.*....*.....*.**.. | ....*....*.*....*.....*.**.. | .........*.*....*.....*.**.. | .....*...*.*....*.....*.**.. | .....*...*.*....*.....*.**.. | .....*...*.*....*.....*.**.. | .....*...*.*....*.....*.**.. | ....**...*.*....*.....*.**.. |
| ....*.***..*.....*.*..*..... | ....*.*.*..*.....*.*..*..... | ...**..**..*.....*.*..*..... | .....*.**..*.....*.*..*..... | ......***..*.....*.*..*..... | ....*.***..*.....*.*..*..... | ....*.***..*.....*.*..*..... | ...**.***..*.....*.*..*..... | ....*****..*.....*.*..*..... |
| .....**.*.*.......**...***.. | ....*...*.*.......**...***.. | ...**...*.*.......**...***.. | ..*..*..*.*.......**...***.. | ....**..*.*.......**...***.. | ....*...*.*.......**...***.. | ...**...*.*.......**...***.. | ........*.*.......**...***.. | ........*.*.......**...***.. |
| .....**.*..***...........*.. | ....*...*..***...........*.. | ...**...*..***...........*.. | ..*..*..*..***...........*.. | ....**..*..***...........*.. | ....*...*..***...........*.. | ...**...*..***...........*.. | ........*..***...........*.. | ........*..***...........*.. |
| ....*.***.....*............. | ....*.*.*.....*............. | ...**..**.....*............. | .....*.**.....*............. | ......***.....*............. | ....*.***.....*............. | ....*.***.....*............. | ...**.***.....*............. | ....*****.....*............. |
| ....*....***..*............. | ....*....***..*............. | ....*....***..*............. | .........***..*............. | .....*...***..*............. | .....*...***..*............. | .....*...***..*............. | .....*...***..*............. | ....**...***..*............. |
| .....****...*.*.**.......... | .....****...*.*.**.......... | ....*****...*.*.**.......... | ....*.***...*.*.**.......... | .....*.**...*.*.**.......... | ......***...*.*.**.......... | ......***...*.*.**.......... | ......***...*.*.**.......... | ......***...*.*.**.......... |
| ........*..*..*..*.......... | .....*..*..*..*..*.......... | .....*..*..*..*..*.......... | ....*...*..*..*..*.......... | ........*..*..*..*.......... | ........*..*..*..*.......... | ........*..*..*..*.......... | ........*..*..*..*.......... | ........*..*..*..*.......... |
| ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. | ..????????????????????????.. |

This solves immediately:

Code: Select all

x = 22, y = 22, rule = B3/S23
10b2o2b2o$9bo2b2o2bo$7bobob4obobo2bo$5b3obobo2bobob4o$4bo3b2ob4ob2o$3b
o2bo3bo4bo3bo$3bob2ob2o2b2o2bob2o$2b2o3bo5bob2obo$4bobo2b4o2bo3bo$b4ob
ob2o3b2o2b2o2bo$o4bobo4bo5bob2o$ob3o2bo5bobo2bo$b2obobo7b2o3b3o$b2obo
2b3o11bo$ob3o5bo$o4b3o2bo$b4o3bobob2o$4bo2bo2bo2bo$2b2o3bob2o2bob2o$3b
obobo2bob2obo$2bo2b2o2bo2bo2bobob2o$2b2o6b2o2b2ob2obo!

and then rstatoropt is able to reduce it pretty quickly to e.g.:

Code: Select all

x = 22, y = 22, rule = B3/S23
10b2o2b2o$9bo2b2o2bo$7bobob4obobo$5b3obobo2bobob3o$4bo3b2ob4ob2o3bo$3b
ob2o3bo4bo3b2o$3bobo4bobo2bob2o$2b2o2bo4b2o3bobo$4bobo$b4o2b2o$o4b2o2b
o$ob3o3bo$b2obob2o$b2obobo$ob3o2bo$o4bobo$b4obo$4bo$2b2o2bo$3bob2o$3bo
$2b2o!