amling search program principles discussion / brain dump

[May13]

I was able to change the rulestring. This is inside main.rs:

Code: Select all

rule: GolRule::parse_sb("S23/B3"),

Examples:

Code: Select all

x = 149, y = 30, rule = B36/S36
o73bo73bo$o73bo36bo36bo$o35b3o35bo35b3o3b2o30bo$o34bobobob4o29bo34b4ob
ob2obob2o25bo$o33bob3o2bo2bob4o24bo17b2o14b3o3b3o4b2ob2o3b2o17bo$o11b
2o3b4o2b2o9b4o4b3o2bo2b3ob4o16bo10b4ob2ob2ob4o8bob2ob2o4bo3bob2ob2ob2o
15bo$o9b2ob2ob2obobob2obo8bob2ob3o4bo4b2obob2o15bo9b2obob2o5bo2bobo8bo
2b3o6bobobo4bobo14bo$o8bobo4bob2o4b3ob2o3bo2bo3b3o6bo4bob4o14bo8b4obo
3bo3b3o3b3ob2o2bo2bobobo8b2o4b2o14bo$o8b2o4b2o4bo4b2ob2ob3obo4bo2bo6bo
4b3o15bo9b3o4b2o2bob2obo3b2ob2ob2ob2o2bobo9b2o17bo$o11b2o5b5o4bobo4bob
ob3o2bobo6bo6bo13bo7bo6bo4b2ob2obobo3bo5bo3bo3b2o6b5ob2o12bo$o6b2ob5o
3bo4b2o2bo4bob2obo2b2o3b3o6b2o3b3o12bo6b3o3b2o4b3o10bobo5bo5bobo5bobo
3b2o12bo$o6b2o3bobo8bobo5b3o5bobobob4o6bobo4bo11bo5bo4bobo8bo3bobo3b3o
3bo3bobo2b2o7bob2obo12bo$o6bob2obo7b2o5bobo9bo6b2o5bo5bo14bo8bo5bo12bo
b3o7bobob2o6bobo3bo15bo$o9bobobobo11bobo12bo5bobobo4bo15bo7bobo2bo2b2o
2bo6bobobo10bob2ob2obobo5bo15bo$o8bo5b3obo6bo4b2o9b2ob2o2bo8b2o14bo15b
obobo3b2obo14b2o4bo3bo4b2o15bo$o8bob4o4bobob3obo15bo5bobo5bo16bo9bob2o
b2o5bob2ob2o16b2o9bo17bo$o11bo6bo2bo2bob2o13b3o2bobo5bobo16bo9b3o5bo2b
3o4bo14bo4bobo3b2o18bo$o8bo6b2o3bo3b3o18bo7b3o17bo9b3o4bo4b2obo18b2o6b
3o2bo16bo$o8bob2o3bob3o2b2o2bo16bo6b3o2bo17bo9bo4b2o2b2o5bobo16bo6b3ob
o17bo$o15bo3bob3ob2o17bo6bo4b2o15bo15bob3obo2b2o2bo14bo6b3obo2b2o14bo$
o14b2obobo2bo3b4o12bo11b2ob2o3bo10bo16bo4b2o5b2o11b2o12bob2o2b3o9bo$o
19bo4b2o2bobo10b3o7bo2bo4bob3o9bo18bo2b3o2bobob2o8bobo12bobo2bobobo8bo
$o20b2obo6b2ob2o4bob3o14bo2b4o8bo19bo3bo3b2o2b5o3b3o2bo16b3obo7bo$o18b
o3b2o3b2o3bob2ob7o12b4o3b2obo6bo19bob2o6b2o4b4o4bo13b2ob2o4b2o5bo$o18b
o8bo2bo3bo2b3o21bo3b3o5bo19bo7bo3bob2o2bo3b2o13bo9bobo4bo$o20bo7bobo4b
o21bo7b4o4bo27bo9bobo24bo2b2o4bo$o28bo9bo26b3o5bo29bo35bo7bo$o68bo4bo
66b2o5bo$o73bo73bo$o73bo73bo!

Code: Select all

x = 19, y = 68, rule = B2/S0256
7bobo$4b3o3b3o$3b2o7b2o$4b2o5b2o$5b2obob2o$8bo2$6b2ob2o$5b3o$6bo3bobo
2$12bo$10bo2bobo$7b3o6b2o$6b2o9b2o$7b3ob4ob2o$11bo2b3o$8bo6bo$10bo$7bo
3bo$6bobo3bo$12b2o$10b2obo$5bob2obob3o$4b2obo3bobo$3b3o4b2o$8bo3b4o$bo
3bobo7b2o$4bobob8o$7b2o2b2o$7b3obo2bo$4bo$5bobo7bo$2bo2bo2bo2b6o$3bobo
bobob3o3bo$3bobobobobob2o$3bobo3bo$3bobo3bobo4bo$3bobo3bo2bo$3bobo7bo$
3bobo5bo$3bobo4bo3b2o$3bobo3bo$3bobo5bo2bo$3bobob2o2bobo$3bobo7bo$3bob
o2bo2bobo$3bobo3bobobo$3bobobo5bo$3bobo2bo4bo$3bo2bo4bobo$2bo2b3o2b2ob
o$4b2ob4o2bo$4b2o7bo$4bobo3bo2bo$4bob3obo2bo$3bo6b2obo$4bo3b2o3bo$4b4o
5bo$3b2ob2ob2o2bo$o2bob3o5bo$2b2o6bo2bo$o2bo2bo4bobo$6b2o5bo$2bo4bo3bo
bo$6bob2obo2bo$8b3obob2o$9bo2bo3bo!

Code: Select all

x = 57, y = 14, rule = B367/S367
27b3o$26bobobo$25bob4o$5b3o17bo4bo$4bobobo15bobo2bobo3b3o10bo$3bob4o
10b5ob4o5bobobo8b3o$3bo5bo3bo4b2o6bobo2bo2b4obo6b5o$2bo2b2obobob3ob2o
2bo6bobo3bo5bo5b2ob2o$b2obo4bo2b3o2bo3b3ob2o3b4ob2obobo4bo6bo$5b2o2bob
obo2b3o3b2o5bo2bo4b5obo6bobo$bo2b2ob3ob3o2bo5b3obob2obobobo3bo2bo2b3ob
o2bo$3b2o2bo2b2o2b2o4b3o2bo4bo3bo2bobobo2bo3bobob2o$b2obo2b5o2bo3bob3o
b3obob2o2bob3ob3o5bobobobo$ob3o2bo3bo2b4o5bo2bo2bobo11b3obo2bob2ob2o!

But I can't figure out how exactly to change the symmetry of search. Versions of main.rs in branches "20220222-llsss-odd-01" and "master" are too different. I am most interested in even and odd symmetries.

[amling]

Shoot! Sorry for the delayed response. I wasn't keeping a close eye on this thread so I didn't notice this until just now. Is it possible to watch forum threads?

EDIT: It took me 10 seconds to find it after I had the idea that it might exist. "Subscribe topic" done.

I was able to change the rulestring. This is inside main.rs:

Code: Select all

rule: GolRule::parse_sb("S23/B3"),

Yeah, I was gonna run a seeds search and decided to fix that horrible bug factory once and for all. Glad it could help someone else as well.

But I can't figure out how exactly to change the symmetry of search. Versions of main.rs in branches "20220222-llsss-odd-01" and "master" are too different. I am most interested in even and odd symmetries.

Where it says:

Code: Select all

left_edge: LlsssEdgeSingleConstant {
    grid: picture.left_edge_grid,
    next: LlsssEdgeZero(),
},

You could change to (a):

Code: Select all

left_edge: LlsssEdgeSingleConstant {
    grid: picture.left_edge_grid,
    next: llsss::edge::LlsssEdgeXxx {
        table_engine: LlsssTableEngineChecks3::new_default_size(),
    },
},

Or (b):

Code: Select all

left_edge: llsss::edge::LlsssEdgeXxx {
    table_engine: LlsssTableEngineChecks3::new_default_size(),
},

Similarly `right_edge`. `Xxx` should be `Even`, `Odd`, `GSEven`, or `GSOdd`. Even variants expect the two outermost columns to be the same or the same rephased. Odd variants expect the outermost column to be the center one (so the second column is copied (and maybe rephased) out of bounds). `llsss::edge::` can be replaced with an import if you want to make it pretty (unclear how much rust other people [want to] know).

Variant (a) indicates to fill the edge from the provided input picture and once it runs off the end of the provided picture, start allowing any values that meet symmetry.

Variant (b) indicates to ignore the provided input picture and start allowing whatever symmetric values immediately. When I am using variant (b) I will often place an illegal character in those spaces to make sure I'm not somehow using them.

[amling]

Part 1d: "Finally done with LGOL".

So what does it add up to? What has LGOL done? The three biggest tricks not [yet] reproduced in the second, lsss-analogous program are probably:

(*) The recentering means LGOL can be good at finding very wiggly results, sometimes finding things with very thin windows that would take a very large non-recentering search to find. A good (only?) example of this is 232P7H3V0 which was found by loading that very thin arm of the common 3c/7 frontend in as that "start" and running a fairly "thin" search. Even the smaller of the two results it found "wiggles" a lot compared to how wide it is at any give point.

I've sketched something like recentering for LLSSS. More details on what it does once it's a little more baked, but provisionally it is able to find 232P7H3V0 in ~25 minutes and 2.5GB memory from about the same inputs as the original LGOL search that found it (just the chosen slice and a single parameter "width" defining how wide the search is). The original LGOL search took ~12 hours and spent most of it thrashing against the "48G" I had given it (which is internally measured and probably translates more to ~60G actual memory used).

This sounds good, but there are a few things that make this maybe a little lucky and its utility a little uncertain.

One question is can LLSSS just find this with a normal fixed-board search? I'm working through fixed board searches of increasing width, but even with the alignment chosen perfectly (i.e. the left side of the fixed board lining up with where it needs to be) it does not look good. I believe it will need width 16 to find this. Width 11 took ~26m and 7.2G and these things increase extremely fast every single width. So far width 12 has taken ~50m and 23G and might just be getting over the initial hump. I will push this line of searches until they reach width 16 or die trying, but I doubt it's gonna work out.

Another question is what happens after the first hit? LGOL can prune that part of the search tree and continue on a little more easily whereas LLSSS has to leave all the hit-related slices in memory and deal with their extensions forever. This of course all works, but I think it's going to make LLSSS worse at looking for further results after a first result. I will let the recentering LLSSS search that found 232P7H3V0 continue until it finds the tagalong or fills memory and dies. Based on the trend of `VmPeak` values and how far I think it needs to go I'd say it's about even money to make it or not.

One problem that that I despair of solving is cycle finding. LGOL will notice when a slice matches an earlier slice in the same partial (possibly shifted), but LLSSS, even when recentering, does not think of things that way and can't really notice it, neither to avoid wasting time researching continuations, nor even to print it out as a possible pattern of interest. This does not prevent recentering LLSSS from working, from being able to find interesting non-cyclic results, etc., but it does sort of put a damper on using it to find greyship edges. My best hope is to run searches and hope to spot the cycles myself in random partials. This is as silly as it sounds, but I have already used this very trick (spot cycles in long partials by eye) to find stuff even with non-recentering LLSSS.

And then of course there is the long, long road of further optimization, making it easier to run, adding more features in terms of how it configures its boundaries, figuring out what search projects should be [re]done with it, etc.

EDIT: Fixed-board width 12 made it in ~2h and ~23G. Width 13 filled memory and died without getting much of anywhere. So "great", fixed board LLSSS couldn't have found this, at least not easily (maybe some combination of spotting thin partials and choking down and shifting window by hand could hack it).

EDIT: After a total of ~5h and ~34G this recentering LLSSS search did reach the tagalong as well. This is less impressive (original LGOL search took about ~20h total to find the tagalong), but I think a lot of it can be attributed to LLSSS wasting a ton of time juggling useless continuations of the first result (e.g. most random partials it output were completely disconnected continuations whose analog would have long been pruned in the LGOL search). I'll let it run until it fills memory and dies.

[amling]

(about recentering)

And then of course there is the long, long road of further optimization, making it easier to run, adding more features in terms of how it configures its boundaries, figuring out what search projects should be [re]done with it, etc.

I've had a chance to run some more searches and subjectively it seems good in terms of what it can find per memory filled but maybe not as good as normal LLSSS in terms of time spent doing so.

As an example of how it differs from LGOL, and rather sharply from human intuition, here is the "thinnest" (per the "width" recentering takes to find it) 2c/5 ship:

Code: Select all

#C [[ TRACK 0 -2/5 ]]
x = 30, y = 46, rule = B3/S23
21bo$20bobo$19b2ob2o$19b2o$21bo$21b4o$21bo2b2o$22b2o2bo$23b5o$25bobo$
24b2obo$25bobo$22b2obo$25bo$24b3o2$27bo$27b3o$24bo$22b2o$22bo3bo$b3o
18bobob2o$bo2bo21b2o$2o22bo$2bo20bo2b2o$2bobo21bo$b2obobo18bo$b2obob2o
14b2o$2b3o2bo13bo2bo$3b2o2b2o12bobo$3b2o$4bobob2o9bo3bo$6bo11b2o3bo$
17b2o2bo$7bo8bo4bo$5bobo12bo$5bo2bo9b2o$8b2o$7b2o8bo$8bobo5b2obo$8b2o
5bo3bo$11b2o2bobo$12bo$7bo5bo$8b7o$7b2o4b2o!

Like all limit-like things I have done in LLSSS, the recentering "limit" is very much local/ephemeral. Once a given row's expansion has been completed all the results are tossed back into the same bag and can be recombined in the future in ways that violate the apparent limit. Seen here, a fairly small limit finds a fairly wide ship because it was able to work on both sides separately and then was able to combine at the bottom in a way where as it built each bit of the ship it could be part of a partial whose apparent "width at the very bottom" was small enough.

This is of course not a problem if you're just trying to solve whatever search input but it is weird.

[amling]

So what is recentering?

First perhaps a refresher/update on how LLSSS "fixed board" works... I'm going to assume/simplify some bits about the geometry, namely that NH_U_SIZE is 3, U is X, V is in the YT plane and proceeds "up Y", and W is "T-like" (det(XVT) and det(XVW) have same sign). If you go code diving know that everything is more complicated than you think

Originally LLSSS kept, for each X coordinate in some range, a bag of 3-column slices of the pattern. These contained all the on/off bits in every generation. At any given time it would make sure the set of projected left 2-column slices on one bag would match the projected right 2-column slices of its left neighboring column. The code calls these bags of 3-column slices "cols". Somewhere along the way I changed it to also keep "bcols" (boundary cols) which are the actual sets of 2-column slices that are shared by the neighboring cols and to store the cols as pairs of indices in these. These days the bcols are the more important concept and cols mostly just track CA compatibility between them.

LLSSS starts by cutting up your input grid into columns, making one entry in each bcol that is exactly whatever the input was and making one entry in each col that is exactly whatever the input was. It then proceeds, row by row downward, trying to extend these.

Now for recentering, instead of keeping one bcol/col per position, we just keep one giant, unified bcol and one giant, unified col. It also keeps one designated 2-column slice to be the left edge and one to be the right edge. But now expanding it is more complicated:

*) We start with the 2-column slice that is the left edge and walk left-to-right to see what other 2-column slices we can reach. This walk is unlimited in that it will loop until it has produced a closed set, but it does restrict each step to be "inert" in the final 2 Y rows. "Inert" usually means "all zeros", but for greyship searches I might make inert mean "all the agar in question".
*) We do the same sort of walk, but right-to-left to closure the right edge.
*) Now we do a fixed number (this is the "width" of the search) of steps "towards" the middle. These either take each 2-column slice in the in-progress left set and step one 2-column slice right or take each 2-column slice in the in-progress right set and step one 2-column slice left. We perform a fixed, limited number of these steps, and generally perform the step on whichever side is (currently) smaller.
*) Once these fixed steps are complete, we do one last check to see which 2-column slices from the left set can be left neighbors of some 2-column slice from the right set.
*) Then we filter/collapse the state to what you'd expect based on that meeting in the middle. In particular at the end each slice always has left/right neighbors (well, except possibly for the edges), and in fact has a compete path left to the left edge and a path right to the right edge.

As you can imagine this makes initialization the state a little more confusing and it makes finding and outputting results also way more confusing. More in later posts...

[amling]

As you can imagine this makes ... outputting results ... way more confusing. More in later posts...

Consider the "zero ends". This outputs results where the entire bottom 2 Y rows are zero. What do we do here? It's not how it works, but imagine filtering the bcol/col to columns that end in 2 Y rows of zeros and then filtering to whatever set is closed (and bailing if there is nothing left). Now what you want to output is "all paths from left edge to right edge", but what if you have cycles? There were no cycles in fixed-board LLSSS since X coordinate always increased (although with diamonds you could have a useless amount of variations output, filling disk and ending the search which is a real problem I have had searches hit).

You could just dump all 3-column slices that survived and make the operator deal with it. Slightly nicer is to merge neighboring 3-column slices when they have only each other as neighbors. This is approximately what the current implementation of zero ends for recentering does. It's a little more complicated because it's phrased in terms of state machines and so it outputs each pair of 3-column slice and state (merging unique neighboring pairs). Either way it's extremely confusing. Perhaps I'll worry more about it when I'm rolling in results, but it definitely means interpreting a successful search is rather involved (e.g. something this level waves business in the other thread where I'm triaging thousands of results would be absolutely impossible).

[amling]

As you can imagine this makes initialization the state a little more confusing [...]. More in later posts...

My current plan is again to kick the agony to the operator. Allow the operator to tag columns with a root "color" to make them considered unique even if the on/off bits are the same, dice up the provided grid, and then shove it all into bcol/col.

I'm going to restrict my example grids to one generation here, but you should imagine them as more normal inputs to LLSSS (with an extra row up top to mark root).

So to search for results "starting" from zeros you just provide a 3-wide board with all columns tagged with the same root ("Z" here):

Code: Select all

ZZZ
...
...

You get one bcol entry (all zeros and Z roots) and one col entry.

To search from a provided slice (with interesting bits "S"es) you might be tempted to ignore roots and do:

Code: Select all

ZZZZZZZZZZZ
...SSSSS...
...SSSSS...

But then you get the all-zeros, all-Zs slice as above and your search contains completely the from-zero search which is probably not what you want. I think you probably want to do something like:

Code: Select all

LLLMMMMMRRR
...SSSSS...
...SSSSS...

This is "good" because it forces results to start with L, proceed through some M, and end with R, but it's not quite right because it can still recombine the "S" columns in chimeric ways you might not expect (so long as they meet CA checks). I think the fully right way to do this is:

Code: Select all

LLL12345RRR
...SSSSS...
...SSSSS...

So now the only possible transitions are LL -> LL -> L1 -> 12 -> 23 -> 34 -> 45 -> 5R -> RR -> RR which forced a path through your exact input.

Unfortunately I'm not really seeing a good way to unify these cases which is why just kicking it to the operator is my current best plan.

[amling]

As you can imagine this makes initialization the state a little more confusing [...]. More in later posts...

My current plan is again to kick the agony to the operator.

This is all sketched and tested and doesn't seem quite that bad. E.g. here is an input I am using right now to search for c/6 ships with a single cell in the earliest nonzero W row:

Code: Select all

|         |         |         |         |         | LLL1RRR |
| ....... | ....... | ....... | ....... | ....... | ....... |
| ....... | ....... | ....... | ....... | ....... | ...*... |

Even in smallish test searches (~6m, ~1.6GB) this produces fun-looking partials:

Code: Select all

| ............... | ............... | ............... | ............... | ............... | ............... |
| ............... | ............... | ............... | ............... | ............... | .........*..... |
| .........*..... | .........*..... | .........*..... | .........*..... | ........***.... | ........*.*.... |
| ........*.*.... | ........*.*.... | ........*.*.... | .......**.**... | ........***.... | .......*..*.... |
| .......*..*.... | .......*..*.... | .......**.**... | ............... | .......*....... | ........**..... |
| ........**..... | ........*..*... | .......*****... | ......*........ | ............... | ............... |
| .........***... | ........*..*... | .......**..**.. | ......*.....*.. | ......*....*... | ..........***.. |
| ..........*.*.. | .......*....*.. | .......*...*... | .......**.**... | .......*..***.. | ......**..*.*.. |
| ......*****.*.. | ......*...*.... | ...........*... | ...........*... | .......*...*... | .......**...... |
| ......***...... | ..........*.... | .........**.... | ........***.... | ........*..*... | ............... |
| .......***..... | ......*..*..... | ........**..... | ........***.... | ............... | ........*.*.... |
| .........*..... | .......*.**.... | .....*......... | .........*..... | ........***.... | .........*..... |
| ......*...*.... | .....******.... | .....*....*.... | .....**........ | .....**........ | .....*****..... |
| .....***.*..... | .....*.**...... | ....**......... | ......*........ | ....*..*....... | ....*..*....... |
| ....*..*....... | ....*..**...... | ....**..*...... | ....***........ | .....**........ | ....*.......... |
| ....**......... | ...*..*........ | .......*....... | ............... | .....***....... | .....*..*...... |
| ....**......... | ............... | ............... | .......**...... | .......**...... | .....*..*...... |
| .....**.**..... | ........*...... | .......**...... | .......**...... | ......*.*...... | ......*.*...... |
| .....***....... | .......**...... | .......**...... | ......*........ | ......*........ | .....*......... |
| ....**......... | ............... | .......*....... | .....*.**...... | ....*...*...... | ...**.......... |
| ....**......... | ...*..*........ | ....***........ | ....****....... | ...***......... | .....*......... |
| ...*.*......... | ...*.**........ | ...*...*....... | ..**...*....... | ...**..*....... | ...*.*......... |
| ...*.*......... | ..**.**........ | ..**.**........ | ......*........ | ............... | ...**.......... |
| ...*.*......... | ............... | ..**........... | ..**........... | ...*........... | ....*.......... |
| ............... | ...*.**........ | .....**........ | ....*.......... | ....**......... | ....**.*....... |
| ...***.*....... | ...*.**........ | ..**........... | ....**.*....... | .....****...... | ...*..**....... |
| ...*.*......... | ...*.*.**...... | .....*.**...... | ...**..**...... | ...**.......... | ...*...**...... |
| ....*..**...... | .....*..*...... | ....*...*...... | ......**.*..... | ....**...*..... | .....*......... |
| ...**....*..... | .......*....... |                 |                 |                 |                 |

Code: Select all

x = 15, y = 43, rule = B3/S23
6$9bo$8bobo$7bo2bo$8b2o$9b3o$10bobo$6b5obo$6b3o$7b3o$9bo$6bo3bo$5b3obo
$4bo2bo$4b2o$4b2o$5b2ob2o$5b3o$4b2o$4b2o$3bobo$3bobo$3bobo2$3b3obo$3bo
bo$4bo2b2o$3b2o4bo!

[Sokwe]

I'm trying to use LLSSS to finish the 2c/5 wickstretcher, but I'm having trouble setting up back-to-front 2c/5 searches. I can't tell if it's the geometry of my input files, or the choice of u, v, w, and usize. Can you give an example of a 2c/5 b2f setup. Also, how would you get recentering to work in these cases. I imagine it could be helpful with these back-to-front searches.

[amling]

I'm trying to use LLSSS to finish the 2c/5 wickstretcher, but I'm having trouble setting up back-to-front 2c/5 searches. I can't tell if it's the geometry of my input files, or the choice of u, v, w, and usize. Can you give an example of a 2c/5 b2f setup. Also, how would you get recentering to work in these cases. I imagine it could be helpful with these back-to-front searches.

For 2c/5 b2f I'd use U=(1, 0, 0), V=(0, 2, 5), W = (0, 1, 2), TILE_BITS=1. For f2b/b2f searches like this input files have some leeway in phasing, an example possible input file for this geometry:

Code: Select all

| ........... | ........... | ........... |             |             |
| ........... | ........... | ........... | ........... | ........... |
| .....?..... | .....?..... | .....?..... | ........... | ........... |
|             |             |             | .....?..... | .....?..... |

For recentering you'd change `main` to call `main_llsss_recentering` instead and configure that. For a typical search (i.e. looking to solve a slice to zeros, with zeros on either side) only geometry and tile bits need to be changed. The example is run with input file and number of "middle steps" to do, something like `cargo run --release prompt.in 7`. Then input files look a little different... they can be any (small) number of W rows, so long as it's enough to meet geometry overlap minimum and few enough to fit a column in a single scalar (u64 by default I think). The first W row is used as "root label" which dictates what columns are considered to match or not outside of their cell contents. You can see a lot of philosophizing about this above when I was first planning recentering. An example input might look like:

Code: Select all

| LLL012RRR |           |           |           |           |
| ...**.... | ...**.... | ...*.*... |           |           |
| ......... | .....*... | ...*.*... | ...*..... | ...*..... |
|           |           |           | ...*..... | ...**.... |

A few important features:

(*) Exactly 1 W row of root labels, which is the first W row, just before the real pattern.
(*) At least three blanks on each side so that it knows it can extend with all zeros.
(*) Distinct root labels for left and right, so it doesn't think all zeros globally is a legal pattern.
(*) Distinct root labels for the relevant parts of the slice. This case would be fine w/o, but for slices with enough repetition it might create chimeric patterns by recombining 3-wide pieces otherwise.

If you get stuck on either let me know and I can push a branch with a full, runnable demo.

[Sokwe]

If you get stuck on either let me know and I can push a branch with a full, runnable demo.

I think I'm going to need this for the recentering search, as I couldn't get the 2c/5 b2f search to work, nor the c/6 f2b search from your earlier post.

[amling]

If you get stuck on either let me know and I can push a branch with a full, runnable demo.

I think I'm going to need this for the recentering search, as I couldn't get the 2c/5 b2f search to work, nor the c/6 f2b search from your earlier post.

I've pushed `20230414-2c5-rc-demo` on which `cargo run --release 1.in 5` or the like should work. `1.in` is the input file from above, `5` is the number of real steps to do (approximately what local width of pattern to search for).

EDIT: And I pushed `20230414-c6-rc-demo` do demonstrate c/6 f2b, similarly `cargo run --release 1.in 5` or the like should work.

[amling]

It loads the DB in like 6s and immediately finds a hit but then it takes it ~12m to decide what the best completion from the DB is.

These don't seem like performance issues to me.

The code in question was beyond shameful. If I were asking this as an interview question and a candidate wrote the code that I did I would not be keen on hiring them. With it fixed it's now ~6s to load DB, ~30s to do a little more precomputation on the first result, and then pretty much instantaneous (like <1s) per result after that.

In fact, this feature might have been able to find a simpler solution quicker. The way I solved it was to test a bunch of branch points by hand, then extend branches until I saw something that could maybe be completed with an existing ship, then spend far more than 20 minutes looking through the 2c/5 collection to try to find something that works, which only worked in 2 out of I think 5 total such attempts. LLSSS might have been able to solve it with less branching.

If you still have any of those prompts around you could try rerunning them with the new ends DB stuff.

LLSSS can also recognize spaced-dusty rows that I would never think to check for in the database. However I don't know if it can handle anything more complex. For example, that ship in the top-left branch uses a MWSS emulator-type spark to hit a pi, so I didn't look for a ship with a specific set of rows, but rather one with a specific side spark near the tail. With just the pi as the starting point, I'm not sure LLSSS could find this solution. However, there are a lot of other spark options to support that pi, so it probably would find something else (maybe something shorter).

Yeah, the ends DB is definitely strictly fixated on the concept of slices of 2 Y rows at a time. I think if you put in enough "top" pad you could make LLSSS do the s2s-to-b2f turn and find this turn, then copy some decent partial into a more proper b2f search where you can use the ends DB.

It loads the DB in like 6s and immediately finds a hit but then it takes it ~12m to decide what the best completion from the DB is.

Can it give an immediate solution, or must it spend some time to build a solution? One would generally want to see the best solution, but in the mean time it might be nice to have some solution. Would it be faster to minimize length or width or some other property rather than population? As you noted, it apparently tries to find solutions with the best clearance on one side, which is great.

At this point it's moot other than trying to avoid that one ~30s precomputation. I can (and will) change it to output the minpop solution before mucking with precomputing the stuff for the best clearance solutions.

If it's not too much trouble, can you give an example (in the scripts forum) of how to use the DB ends function?

Yeah, see next post...

[amling]

Check out and build the demo branch:

Code: Select all

$ git checkout 082aa72c344e
HEAD is now at 082aa72c344e... demo input
$ cargo build --release
   Compiling rlife v1.0.0 (/home/amling/git/rlife)
    Finished release [optimized + debuginfo] target(s) in 2m 27s
$

Build the DB in its compiled form from a bunch of RLE files.

`RLIFE_MAIN=edbv3-ingest` tells the program to do "ends DB V3 ingest" instead of a normal search. Some day I will figure out how to make multiple binaries in a rust project in a way that doesn't suck.

`2c5-b2f` picks the search geometry we're building a DB for. It outputs the U, V, and W this translates to and your search when run had better match exactly. If none of the preconfigured geometries are what you want you could go add more.

`1.edbv3` is the file we're building.

The rest of the arguments are files and/or directories of RLE files (can also be already-built edbv3 DBs if you want to merge some). Here I'm loading my "old" ends directory which is just a stripped-down copy of some stuff from jslife-moving and then also the asymmetric widths 10, 11, and 12 files from knight-results.

Code: Select all

$ env RLIFE_MAIN=edbv3-ingest ./target/release/rlife 2c5-b2f 1.edbv3 ~/git/life-notes/ends/2c5 knightt-results/2c5-w10-n.rle knightt-results/2c5-w11-n.rle knightt-results/2c5-w12-n.rle
20230423 19:28:19 [INFO] Lattice: Vec3(1, 0, 0), Vec3(0, 2, 5), Vec3(0, 1, 2)
20230423 19:30:54 [DEBUG] Input "/home/amling/git/life-notes/ends/2c5/jslife-moving-2c5-1.rle": 23248 edges, 23248 kept
20230423 19:30:54 [DEBUG] Input "knightt-results/2c5-w10-n.rle": 313 edges, 0 kept
20230423 19:30:54 [DEBUG] Input "knightt-results/2c5-w11-n.rle": 13794 edges, 11104 kept
20230423 19:30:55 [DEBUG] Input "knightt-results/2c5-w12-n.rle": 338739 edges, 323280 kept
20230423 19:30:58 [INFO] 357632 edges written to "1.edbv3"
$ du -hsc 1.edbv3
85M     1.edbv3
85M     total
$

Note this took several minutes even on my reasonably fancy laptop and produces a giant 85MB file.

This demo search is configured to take the DB path as an extra argument after input picture path. Depending on what searches you're running and what you want out of them you might hard-code the path instead. The input picture here is targetting that top-left branch where I've peeling back the branch east of it a bit (and left exclamation points on the stump). Even 0/0/0 padding is enough to hit in the DB so we'll just run that...

Code: Select all

$ ./target/release/rlife 1.in 1.edbv3 0 0 0
20230423 19:35:40 [INFO] Start: compile step LlsssMonitorSpineStats
20230423 19:35:40 [INFO] Finish: compile step LlsssMonitorSpineStats -> took 86.997µs
20230423 19:35:40 [INFO] Start: compile step LlsssMonitorColStats
20230423 19:35:40 [INFO] Finish: compile step LlsssMonitorColStats -> took 5.99µs
20230423 19:35:40 [INFO] Start: compile step LlsssMonitorUniquePartial
20230423 19:35:40 [INFO] Finish: compile step LlsssMonitorUniquePartial -> took 5.382µs
20230423 19:35:40 [INFO] Start: compile step LlsssMonitorFirstPartial
20230423 19:35:40 [INFO] Finish: compile step LlsssMonitorFirstPartial -> took 5.184µs
20230423 19:35:40 [INFO] Start: compile step LlsssMonitorRandomPartial
20230423 19:35:40 [INFO] Finish: compile step LlsssMonitorRandomPartial -> took 5.059µs
20230423 19:35:40 [INFO] Start: compile step LlsssMonitorRctl
20230423 19:35:40 [INFO] Finish: compile step LlsssMonitorRctl -> took 45.27µs
20230423 19:35:40 [INFO] Start: compile step LlsssStepExpand
20230423 19:35:40 [INFO] Start: compile tables
20230423 19:35:40 [INFO] Compiling [checks3 1/1] table of 12 + 1 = 13 bits
20230423 19:35:40 [INFO] Finish: compile tables -> took 690.657µs
20230423 19:35:40 [INFO] Start: compile tables
20230423 19:35:40 [INFO] Compiling [checks3 1/1] table of 12 + 1 = 13 bits
20230423 19:35:40 [INFO] Finish: compile tables -> took 274.568µs
20230423 19:35:40 [INFO] Finish: compile step LlsssStepExpand -> took 4.093533ms
...

Just the boring startup so far...

Code: Select all

...
20230423 19:35:40 [INFO] Start: compile step LlsssEndsEdbv3
20230423 19:35:46 [INFO] Finish: compile step LlsssEndsEdbv3 -> took 6.611724821s
...

~6s to load this ~85MB DB. This is way, way better than the RLE ingestion code.

Code: Select all

...
20230423 19:35:46 [INFO] Start: compile step LlsssEndsZero
20230423 19:35:46 [INFO] Finish: compile step LlsssEndsZero -> took 7.779µs
20230423 19:35:46 [INFO] Start: search proper
20230423 19:35:47 [INFO] VmPeak:	 1344668 kB
20230423 19:35:47 [INFO] Memory: total 256 B (spine store old_gens 56 B, spine store cur_gen 112 B, bcols 48 B, cols 40 B)
20230423 19:35:47 [INFO] Spine store sizes: old_gens [7], cur_gen 7
20230423 19:35:47 [INFO] Cols sizes: 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1
20230423 19:35:47 [INFO] Unique:
20230423 19:35:47 [INFO] | .***..* |         |         |         |         |
20230423 19:35:47 [INFO] | **.**.. | **...*. | .*..... |         |         |
20230423 19:35:47 [INFO] |         | *....*. | **....* | .**.... | .***... |
20230423 19:35:47 [INFO] |         |         |         | **.**.. | *..*... |
20230423 19:35:47 [INFO] Firstest:
20230423 19:35:47 [INFO] | .***..* |         |         |         |         |
20230423 19:35:47 [INFO] | **.**.. | **...*. | .*..... |         |         |
20230423 19:35:47 [INFO] |         | *....*. | **....* | .**.... | .***... |
20230423 19:35:47 [INFO] |         |         |         | **.**.. | *..*... |
20230423 19:35:47 [INFO] Random partial:
20230423 19:35:47 [INFO] | .***..* |         |         |         |         |
20230423 19:35:47 [INFO] | **.**.. | **...*. | .*..... |         |         |
20230423 19:35:47 [INFO] |         | *....*. | **....* | .**.... | .***... |
20230423 19:35:47 [INFO] |         |         |         | **.**.. | *..*... |
...

More usual output up through first partials. Skipping a bit eventually it hits...

Code: Select all

...
20230423 19:35:47 [INFO] End ("LlsssEndsEdbv3"):
20230423 19:35:47 [INFO] | .***..* |         |         |         |         |
20230423 19:35:47 [INFO] | **.**.. | **...*. | .*..... |         |         |
20230423 19:35:47 [INFO] | ...**.. | *....*. | **....* | .**.... | .***... |
20230423 19:35:47 [INFO] | ...**.. | ....... | ...**.. | **.**.. | *..*... |
20230423 19:35:47 [INFO] |         |         | ..**... | ..*.... | ....*.. |
...

This is the segment from the initial prompt to the slice that hit in the DB. It's gonna then spin for ~30s doing some one-time-precomputation that it has deferred to first result. Later results will not incur the cost (and neither will searches that have no results). In my testing this ~30s precomputation is most of the cost and later hits are pretty much instantaneous now.

Eventually it outputs some completions. All hits will output best by population (counting all live cells in all generations):

Code: Select all

...
20230423 19:36:19 [INFO] Completion [population]:
20230423 19:36:19 [INFO] | .....*..*........... |                      |                      |                      |                      |
20230423 19:36:19 [INFO] | .........*.......... | ........**.......... | .....*....*......... |                      |                      |
20230423 19:36:19 [INFO] | .....*..*........... | ........**.......... | .................... | ........**.......... | .....**.**.......... |
20230423 19:36:19 [INFO] | ........*........... | .......**........... | .......***.......... | .......**........... | .......*............ |
20230423 19:36:19 [INFO] | .......*............ | .................... | ......*............. | ......*..*.......... | .....**.*........... |
20230423 19:36:19 [INFO] | .....****........... | ......***........... | ......*.*........... | .....**............. | ......**............ |
20230423 19:36:19 [INFO] | .................... | ......*.*........... | ......*.*........... | ....*.*............. | ....*.**............ |
20230423 19:36:19 [INFO] | ..**....*........... | ..**................ | ...***.............. | ...*....*........... | .....*.............. |
20230423 19:36:19 [INFO] | ..*.*.*............. | ....**...*.......... | .*..****.*.......... | .*....*.*........... | ........**.......... |
20230423 19:36:19 [INFO] | .**.*..***.......... | .**...****.......... | .**......*.......... | *.......*........... | *.*..*.............. |
20230423 19:36:19 [INFO] | ...***..*.*......... | ..****.**........... | .**.**.............. | .**.*.*............. | .**.*..*............ |
20230423 19:36:19 [INFO] | .................... | ....*....*.......... | ....***..*.......... | ...**.*............. | ..*.*.*..*.......... |
20230423 19:36:19 [INFO] | .........*.......... | .......**........... | ......*..*.......... | ....*.*.***......... | ...**...*.*......... |
20230423 19:36:19 [INFO] | ......***........... | ......***........... | .....*...*.......... | ........**.......... | .......**.*......... |
20230423 19:36:19 [INFO] | ......*............. | .....**.*........... | ........*........... | .................... | .......**........... |
20230423 19:36:19 [INFO] | ......*.*........... | .....**............. | .................... | ......**............ | .....*.*............ |
20230423 19:36:19 [INFO] | ......**............ | ......**............ | .....***............ | .....***............ | .................... |
20230423 19:36:19 [INFO] | .................... | ........*........... | ......*.*........... | .....**.**.......... | .....*...*.......... |
20230423 19:36:19 [INFO] | ......***........... | ......*.*........... | ........**.......... | .......***.......... | ......**.*.......... |
20230423 19:36:19 [INFO] | .......**........... | ......*.*........... | .................... | .................... | .......*............ |
20230423 19:36:19 [INFO] | .................... | .................... | .................... | .......*............ | ......***........... |
20230423 19:36:19 [INFO] | .................... | .................... | ......***........... | ......***........... | .................... |
20230423 19:36:19 [INFO] | ....**..**.......... | .....*****.......... | .....*...*.......... | ......**.*.......... | .........*.......... |
20230423 19:36:19 [INFO] | ......**.*.......... | .....***.*.......... | .........*.......... | .....**.**.......... | .........*.......... |
20230423 19:36:19 [INFO] | .................... | ......*.*........... | .....**.*........... | .....****........... | ....*............... |
20230423 19:36:19 [INFO] | .....*...*.......... | .................... | .....*.*............ | .....*..*........... | ....**..**.......... |
20230423 19:36:19 [INFO] | .*..*............... | ....*.*............. | ......**............ | ....*...*........... | ...***.***.......... |
20230423 19:36:19 [INFO] | *...*.**............ | **..*.**............ | ...**.**............ | ...**...*........... | ...**..**........... |
20230423 19:36:19 [INFO] | .*...*.*............ | ....*............... | .*..*.**............ | ..*....*............ | .**....*............ |
20230423 19:36:19 [INFO] | .....****........... | ..*.**..*........... | ..*.**.............. | .**....**........... | .***..**.*.......... |
20230423 19:36:19 [INFO] | ..**..*............. | ..**....*........... | ..****..**.......... | ..*..*..**.......... | .****....*.......... |
20230423 19:36:19 [INFO] | ...****.*........... | ......*.*........... | ........*........... | ...*.*.*............ | ...*.*.*............ |
20230423 19:36:19 [INFO] | .*..*..**........... | ........**.......... | .....*..**.......... | ....*..*............ | ...**.*.*........... |
20230423 19:36:19 [INFO] | ....*.*.*........... | ...**.*.*........... | ...**...**.......... | ..*......*.......... | ...*..*............. |
20230423 19:36:19 [INFO] | *...**.............. | ...*...*............ | ..******............ | ..*...***........... | .**....**........... |
20230423 19:36:19 [INFO] | *...***............. | .*....*............. | .*....*............. | .*.................. | .****...*........... |
20230423 19:36:19 [INFO] | ..***............... | .**...**............ | .**..*..*........... | *..*****............ | ***.***............. |
20230423 19:36:19 [INFO] | ..*.*..**........... | ..*..*.**........... | .**.**..*........... | .*...*.............. | .*.................. |
20230423 19:36:19 [INFO] | ...**..*............ | ...**.*............. | ...**............... | ..**..**............ | ..**...*............ |
20230423 19:36:19 [INFO] | .......**........... | ......***........... | .....**.*........... | ....****............ | ...**...*........... |
20230423 19:36:19 [INFO] | .......*............ | .......*............ | ......*............. | .....***............ | ....*..*............ |
20230423 19:36:19 [INFO] | .........*.......... | ........*........... | .................... | .................... | .......**........... |
20230423 19:36:19 [INFO] | .........*.......... | .................... | ........**.......... | .......*.*.......... | .................... |
20230423 19:36:19 [INFO] | .................... | ........**.......... | .......***.......... | ..........*......... | ........***......... |
20230423 19:36:19 [INFO] | .....*..**.......... | ......**..*......... | .....***.*.......... | ....**...*.......... | .................... |
20230423 19:36:19 [INFO] | .....*.****......... | ....**.*............ | ....**.*............ | .......*............ | .................... |
20230423 19:36:19 [INFO] | .....*...**......... | .....*.....*........ | ....**..*........... | .................... | .....**............. |
20230423 19:36:19 [INFO] | ......***.*......... | ......***..*........ | .....*.....*........ | ....***..**......... | .....******......... |
20230423 19:36:19 [INFO] | .........**......... | ......*****......... | ......*..**......... | ......**.**......... | ...........*........ |
20230423 19:36:19 [INFO] | .....*.............. | .................... | .......***.......... | .......****......... | ......**............ |
20230423 19:36:19 [INFO] | .................... | .................... | .................... | .........*.......... | .......*.**......... |
20230423 19:36:19 [INFO] | .....*.............. | ......**............ | ......*.*........... | .......*............ | ......**.*.......... |
20230423 19:36:19 [INFO] | ......***.*......... | ......***........... | .....*..*........... | .....**.**.......... | .....**.**.......... |
20230423 19:36:19 [INFO] | ........*.*......... | ......*...*......... | ......*..*.......... | ......*..*.......... | .....***.**......... |
20230423 19:36:19 [INFO] | .......*.*.......... | .......*.*.......... | .......**........... | .........*.......... | ........***......... |
20230423 19:36:19 [INFO] | .......*............ | ......**............ | ......***........... | ......*..*.......... | .................... |
20230423 19:36:19 [INFO] | .......*..*......... | .................... | .......**........... | ......*............. | ......*..*.......... |
20230423 19:36:19 [INFO] | .................... | ........**.......... | ........**.......... | .......***.......... | .......***.......... |
20230423 19:36:19 [INFO] | ........**.......... | ........**.......... | .................... | .........*.......... | .........**......... |
20230423 19:36:19 [INFO] | .........*.......... | .........**......... | ..........*......... | .........*.......... | ........**.......... |
20230423 19:36:19 [INFO] | .......*.*.......... | .........*.......... | ........**.......... | ........*........... | ........**.......... |
20230423 19:36:19 [INFO] | .......*.**......... | .........*.*........ | ........**.*........ | .......*..*......... | .................... |
20230423 19:36:19 [INFO] | ..........**........ | ........*.**........ | ........*........... | .................... | .......*.*.......... |
20230423 19:36:19 [INFO] | ........*...*....... | ........*.***....... | .......**........... | .......***.......... | .......***.......... |
20230423 19:36:19 [INFO] | ........**...*...... | ........**..***..... | ........*......*.... | ........*........... | ..........*......... |
20230423 19:36:19 [INFO] | ..........*..**..... | ..........*..***.... | ........*.**....*... | ........*.**....*... | .......**.**........ |
20230423 19:36:19 [INFO] | ..........*....**... | .........**..*.**... | .........**..*...*.. | ........*..*........ | .........****....... |
20230423 19:36:19 [INFO] | .........*...*..*... | ..............*.**.. | .........*.......... | .............**..... | ............**.*.... |
20230423 19:36:19 [INFO] | ..............*.*... | ........*....**.**.. | .......***...**..... | .......*..*..***.... | ............*..*.... |
20230423 19:36:19 [INFO] | .......**.....***... | .......***....*.*... | .......***...**.**.. | .......*..*..*..*... | .........***.*..*... |
20230423 19:36:19 [INFO] | .......**.**........ | ..........*....*.... | ..........*....*.... | ..........*...***... | ..........**..***... |
20230423 19:36:19 [INFO] | ......**.*.......... | .........**......... | .........**......... | ........*.*......... | ........*.**...*.... |
20230423 19:36:19 [INFO] | ......***........... | .........*.......... | ........**.......... | ........***......... | .......**.*......... |
20230423 19:36:19 [INFO] | .......*.*.......... | ......*..*.......... | .................... | .......*............ | .......*............ |
20230423 19:36:19 [INFO] | ........**...**..... | ........***......... | .......**.*......... | .......**........... | ......*..*.......... |
20230423 19:36:19 [INFO] | ..........*......... | ........*.*....*.... | ........*.*...**.... | .......**.*......... | .......*............ |
20230423 19:36:19 [INFO] | .........**..***.... | .........*....**.... | .........*.......... | .........*....*..... | ........**...**..... |
20230423 19:36:19 [INFO] | ..........**...***.. | .............*.***.. | .............*...... | .............**..... | ..........*..**..... |
20230423 19:36:19 [INFO] | ..........***.....*. | ..........*.*..*.... | ...........***.*.... | ..........**...**... | ..........*...**.... |
20230423 19:36:19 [INFO] | ............*...*... | ..........*..*...... | .........**..****... | .........*.......... | ..........**....*... |
20230423 19:36:19 [INFO] | ...........**....... | ..........***..**... | .........**.****.*.. | ............*....*.. | .................**. |
20230423 19:36:19 [INFO] | .........**....**... | .........*..*..***.. | ........**..*.*..*.. | .................**. | ...........*.*..***. |
20230423 19:36:19 [INFO] | .........*.*...**.** | ........**.*...*..*. | ........**.**..*..*. | ...........***.*..*. | ............*...*.** |
20230423 19:36:19 [INFO] | ........*..*.....*.. | ........*..*....***. | .......**..*....***. | ................*.*. | ..........*....**.** |
20230423 19:36:19 [INFO] | ........***......... | ........*.*......... | .......**.**.....*.. | ..........**....***. | .........***....*.*. |
20230423 19:36:19 [INFO] | .........*.......... | ........***......... | ........*.*......... | .......**.**........ | ........*..*.....*.. |
20230423 19:36:19 [INFO] | .................... | .................... | .........*.......... | .........*.......... | ........***......... |
20230423 19:36:19 [INFO] | .................... | .................... | .................... | .................... | .................... |
20230423 19:36:19 [INFO] |                      |                      | .................... | .................... | .................... |
20230423 19:36:19 [INFO] Provenances:
20230423 19:36:19 [INFO]    296x "knightt-results/2c5-w12-n.rle"
20230423 19:36:19 [INFO]    131x "/home/amling/git/life-notes/ends/2c5/jslife-moving-2c5-1.rle"
...

At the bottom it outputs where the DB thinks it got each slice transition from (deduping and showing counts for runs). In this case the first 296 are from the knightt-results width 12 asymmetric collection and the last 131 are from jslife moving.

It will also compute a best right clearance result (breaking ties by population) and a best left clearance result and if they are distinct from the min population result then output them as well. In this case we have a distinct right clearance result but not a distinct left clearance result:

Code: Select all

...
20230423 19:36:19 [INFO] Completion [right clearance]:
20230423 19:36:19 [INFO] | ..........*..*... |                   |                   |                   |                   |
20230423 19:36:19 [INFO] | ..............*.. | .............**.. | ..........*....*. |                   |                   |
20230423 19:36:19 [INFO] | ..........*..*... | .............**.. | ................. | .............**.. | ..........**.**.. |
20230423 19:36:19 [INFO] | .............*... | ............**... | ............***.. | ............**... | ............*.... |
20230423 19:36:19 [INFO] | ............*.... | ................. | ...........*..... | ...........*..*.. | ..........**.*... |
20230423 19:36:19 [INFO] | ..........****... | ...........***... | ...........*.*... | ..........**..... | ...........**.... |
20230423 19:36:19 [INFO] | ................. | ...........*.*... | ...........*.*... | .........*.*..... | .........*.**.... |
20230423 19:36:19 [INFO] | .......**....*... | .......**........ | ........***...... | ........*....*... | ..........*...... |
20230423 19:36:19 [INFO] | .......*.*.*..... | .........**...*.. | ......*..****.*.. | ......*....*.*... | .............**.. |
20230423 19:36:19 [INFO] | ......**.*..***.. | ......**...****.. | ......**......*.. | .....*.......*... | .....*.*..*...... |
20230423 19:36:19 [INFO] | ........***..*.*. | .......****.**... | ......**.**...... | ......**.*.*..... | ......**.*..*.... |
20230423 19:36:19 [INFO] | ................. | .........*....*.. | .........***..*.. | ........**.*..... | .......*.*.*..*.. |
20230423 19:36:19 [INFO] | ..............*.. | ............**... | ...........*..*.. | .........*.*.***. | ........**...*.*. |
20230423 19:36:19 [INFO] | ...........***... | ...........***... | ..........*...*.. | .............**.. | ............**.*. |
20230423 19:36:19 [INFO] | ...........*..... | ..........**.*... | .............*... | ................. | ............**... |
20230423 19:36:19 [INFO] | ...........*.*... | ..........**..... | ................. | ...........**.... | ..........*.*.... |
20230423 19:36:19 [INFO] | ...........**.... | ...........**.... | ..........***.... | ..........***.... | ................. |
20230423 19:36:19 [INFO] | ................. | .............*... | ...........*.*... | ..........**.**.. | ..........*...*.. |
20230423 19:36:19 [INFO] | ...........***... | ...........*.*... | .............**.. | ............***.. | ...........**.*.. |
20230423 19:36:19 [INFO] | ............**... | ...........*.*... | ................. | ................. | ............*.... |
20230423 19:36:19 [INFO] | ................. | ................. | ................. | ............*.... | ...........***... |
20230423 19:36:19 [INFO] | ................. | ................. | ...........***... | ...........***... | ................. |
20230423 19:36:19 [INFO] | .........**..**.. | ..........*****.. | ..........*...*.. | ...........**.*.. | ..............*.. |
20230423 19:36:19 [INFO] | ...........**.*.. | ..........***.*.. | ..............*.. | ..........**.**.. | ..............*.. |
20230423 19:36:19 [INFO] | ................. | ...........*.*... | ..........**.*... | ..........****... | .........*....... |
20230423 19:36:19 [INFO] | ..........*...*.. | ................. | ..........*.*.... | ..........*..*... | .........**..**.. |
20230423 19:36:19 [INFO] | ......*..*....... | .........*.*..... | ...........**.... | .........*...*... | ........***.***.. |
20230423 19:36:19 [INFO] | .....*...*.**.... | .....**..*.**.... | ........**.**.... | ........**...*... | ........**..**... |
20230423 19:36:19 [INFO] | ......*...*.*.... | .........*....... | ......*..*.**.... | .......*....*.... | ......**....*.... |
20230423 19:36:19 [INFO] | ..........****... | .......*.**..*... | .......*.**...... | ......**....**... | ......***..**.*.. |
20230423 19:36:19 [INFO] | .......**..*..... | .......**....*... | .......****..**.. | .......*..*..**.. | ......****....*.. |
20230423 19:36:19 [INFO] | ........****.*... | ...........*.*... | .............*... | ........*.*.*.... | ........*.*.*.... |
20230423 19:36:19 [INFO] | ......*..*..**... | .............**.. | ..........*..**.. | .........*..*.... | ........**.*.*... |
20230423 19:36:19 [INFO] | .........*.*.*... | ........**.*.*... | ........**...**.. | .......*......*.. | ........*..*..... |
20230423 19:36:19 [INFO] | .....*...**...... | ........*...*.... | .......******.... | .......*...***... | ......**....**... |
20230423 19:36:19 [INFO] | .....*...***..... | ......*....*..... | ......*....*..... | ......*.......... | ......****...*... |
20230423 19:36:19 [INFO] | .......***....... | ......**...**.... | ......**..*..*... | .....*..*****.... | .....***.***..... |
20230423 19:36:19 [INFO] | .......*.*..**... | .......*..*.**... | ......**.**..*... | ......*...*...... | ......*.......... |
20230423 19:36:19 [INFO] | ........**..*.... | ........**.*..... | ........**....... | .......**..**.... | .......**...*.... |
20230423 19:36:19 [INFO] | ............**... | ...........***... | ..........**.*... | .........****.... | ........**...*... |
20230423 19:36:19 [INFO] | ............*.... | ............*.... | ...........*..... | ..........***.... | .........*..*.... |
20230423 19:36:19 [INFO] | ..............*.. | .............*... | ................. | ................. | ............**... |
20230423 19:36:19 [INFO] | ..............*.. | ................. | .............**.. | ............*.*.. | ................. |
20230423 19:36:19 [INFO] | ................. | .............**.. | ............***.. | ...............*. | .............***. |
20230423 19:36:19 [INFO] | ..........*..**.. | ...........**..*. | ..........***.*.. | .........**...*.. | ................. |
20230423 19:36:19 [INFO] | ..........*.****. | .........**.*.... | .........**.*.... | ............*.... | ................. |
20230423 19:36:19 [INFO] | ..........*...**. | ..........*.....* | .........**..*... | ................. | ..........**..... |
20230423 19:36:19 [INFO] | ...........***.*. | ...........***..* | ..........*.....* | .........***..**. | ..........******. |
20230423 19:36:19 [INFO] | ..............**. | ...........*****. | ...........*..**. | ...........**.**. | ................* |
20230423 19:36:19 [INFO] | ..........*...... | ................. | ............***.. | ............****. | ...........**.... |
20230423 19:36:19 [INFO] | ................. | ................. | ................. | ..............*.. | ............*.**. |
20230423 19:36:19 [INFO] | ..........*...... | ...........**.... | ...........*.*... | ............*.... | ...........**.*.. |
20230423 19:36:19 [INFO] | ...........***.*. | ...........***... | ..........*..*... | ..........**.**.. | ..........**.**.. |
20230423 19:36:19 [INFO] | .............*.*. | ...........*...*. | ...........*..*.. | ...........*..*.. | ..........***.**. |
20230423 19:36:19 [INFO] | ............*.*.. | ............*.*.. | ............**... | ..............*.. | .............***. |
20230423 19:36:19 [INFO] | ............*.... | ...........**.... | ...........***... | ...........*..*.. | ................. |
20230423 19:36:19 [INFO] | ............*..*. | ................. | ............**... | ...........*..... | ...........*..*.. |
20230423 19:36:19 [INFO] | ................. | .............**.. | .............**.. | ............***.. | ............***.. |
20230423 19:36:19 [INFO] | .............**.. | .............**.. | ...............*. | ..............*.. | ..............**. |
20230423 19:36:19 [INFO] | ...........***... | ...........*.**.. | ................. | ..............*.. | .............**.. |
20230423 19:36:19 [INFO] | .........***..... | ........**...*... | .............**.. | .............*... | .............**.. |
20230423 19:36:19 [INFO] | ........**.**.... | ............*.... | ........**..*.... | ..............*.. | ................. |
20230423 19:36:19 [INFO] | ........***...... | ........*...**... | ..............*.. | ........*..*..... | ..........***.... |
20230423 19:36:19 [INFO] | ..........*..**.. | ..........**.**.. | .........***...*. | .........*.**.... | ........**....... |
20230423 19:36:19 [INFO] | ............*.*.. | .........*..*.**. | .........*.**.... | .........*.**.... | .........*...*... |
20230423 19:36:19 [INFO] | .........****..*. | .........*....**. | ................. | ..........*..*... | ..........*..*... |
20230423 19:36:19 [INFO] | ..........***..*. | .............*.** | ..........*.**... | ............**... | .........**...*.. |
20230423 19:36:19 [INFO] | .........*...*.*. | .........*.*.*.** | ..........*.*.... | .........**.**... | .........**.***.. |
20230423 19:36:19 [INFO] | .........*...***. | ..........*....*. | .........*.....** | .........**....*. | .............*.*. |
20230423 19:36:19 [INFO] | ...........***... | ..........**.*... | .........*....*.. | ........***...**. | ........*.*...**. |
20230423 19:36:19 [INFO] | ...........*..... | ..........**.*... | .........*...*... | .............*... | .........*....*.. |
20230423 19:36:19 [INFO] | ..........*..*... | ..........***.... | ............*.... | ................. | ............*.... |
20230423 19:36:19 [INFO] | .........*.*..... | ........**....... | ........*........ | ...........**.... | ...........**.... |
20230423 19:36:19 [INFO] | ........**....... | ........**.**.... | .......*...**.... | ............*.... | ............**... |
20230423 19:36:19 [INFO] | .........*.**.... | ........**.**.... | .............*... | ............*.... | .........*.*..... |
20230423 19:36:19 [INFO] | ..........**..... | .........*.**.... | .........*....... | ........***...... | .........***..... |
20230423 19:36:19 [INFO] | .........*....... | .........*.*..... | ........**.*..... | ...........*..... | .........*.**.... |
20230423 19:36:19 [INFO] | ........*.*...... | ........*..*..... | ........***.*.... | ...........**.... | ................. |
20230423 19:36:19 [INFO] | ........****.*... | ........*....*... | .......***...*... | .......*..**.*... | ..........*...*.. |
20230423 19:36:19 [INFO] | ..........*.**... | ........*...**... | ........*...**... | .......*..*.***.. | .......**.*...*.. |
20230423 19:36:19 [INFO] | .........**...... | .........**...... | .........**..*... | ........*.*..*... | .........*....... |
20230423 19:36:19 [INFO] | ...........***... | ..........***.... | .........**.*.... | ............**... | ..........*.**... |
20230423 19:36:19 [INFO] | ................. | ............*.... | ..........*.*.... | .........**.*.... | .........**.**... |
20230423 19:36:19 [INFO] | ................. | ...........*..... | ...........*..... | ..........**..... | ............*.... |
20230423 19:36:19 [INFO] | ..........***.... | ...........**.... | ...........*.*... | ..........**..... | ................. |
20230423 19:36:19 [INFO] | ............*.... | ............**... | ...........*.*... | ...........*.*... | ...........*..... |
20230423 19:36:19 [INFO] | .............*... | .............*... | ..........**.**.. | .........*.*..... | ...........*..... |
20230423 19:36:19 [INFO] | .......*.*..**... | .........***.*... | ........**.*.**.. | .........*.*..... | ...........*..... |
20230423 19:36:19 [INFO] | ........**.**.... | ........**.*.*... | .............*... | ........****.**.. | ........*....*... |
20230423 19:36:19 [INFO] | ...........*..... | ........*****.... | ........*..**.... | ..........***.... | .......*....**... |
20230423 19:36:19 [INFO] | ........*........ | ................. | .......*..**..... | .......***....... | ........**.*..... |
20230423 19:36:19 [INFO] | ........*..*..... | .......**........ | .......*..**..... | .........*....... | .........**...... |
20230423 19:36:19 [INFO] | ........**....... | .......******.... | ..........****... | .........*..*.... | .........**...... |
20230423 19:36:19 [INFO] | ........*..**.... | ........*...**.*. | ..........*...... | ..........*...... | .........***..... |
20230423 19:36:19 [INFO] | .........****.*** | ........*...**.*. | ........**..**... | ........*..*..... | .........*....... |
20230423 19:36:19 [INFO] | .........**...... | .........*....... | .........**....*. | ........*........ | ........*........ |
20230423 19:36:19 [INFO] | ............***** | ..........*****.* | ..........****.*. | .........*****.*. | .........*****.*. |
20230423 19:36:19 [INFO] | ...........*...** | ...........*....* | ..............*.. | .............***. | ..........*....** |
20230423 19:36:19 [INFO] | ...........****.. | ..........**..*.. | .........*.*...*. | ............*..*. | ............**.** |
20230423 19:36:19 [INFO] | .....*..**..*.*.. | ......*..**....*. | ............****. | ...........*....* | ...........**.... |
20230423 19:36:19 [INFO] | ......****..***.. | ......*..****.*.. | .....**.*...****. | .....**.*...*.... | .....*..*...**.*. |
20230423 19:36:19 [INFO] | .......*...*..... | ......**..**..*.. | ......**.*....*.. | .....********.**. | .....*..*.....*.. |
20230423 19:36:19 [INFO] | ...........*..*.. | ...........*.*... | ..........**..... | ..........**.*... | ......***....*... |
20230423 19:36:19 [INFO] | ............**... | ............***.. | ............*.*.. | ...........*.*... | ..........**.*... |
20230423 19:36:19 [INFO] | ..............*.. | ..............*.. | ..............*.. | ..............**. | ............***.. |
20230423 19:36:19 [INFO] | ..............*** | ..............*.* | ..............*.. | .............*... | .............*... |
20230423 19:36:19 [INFO] | ............**..* | ............**..* | ............*.... | ..............**. | ...............*. |
20230423 19:36:19 [INFO] | .............*.*. | ............***.. | ............*.**. | .............***. | .............*..* |
20230423 19:36:19 [INFO] | ................. | ...............*. | ...............*. | .............*..* | .............*..* |
20230423 19:36:19 [INFO] | ..............**. | ..............**. | ..............**. | ..............**. | .............***. |
20230423 19:36:19 [INFO] | ..............**. | ................. | .............*... | ..............*.. | ..............*.. |
20230423 19:36:19 [INFO] | ............*.*.. | ...........**.**. | ................. | ............*.*.. | ..............*.. |
20230423 19:36:19 [INFO] | .......**..**.... | ................. | ............***.. | .............*... | .............**.. |
20230423 19:36:19 [INFO] | ...........***... | .........*...*... | ................. | ..............*.. | ............*.*.. |
20230423 19:36:19 [INFO] | .......***.*..... | .......*.....*... | ........*...**... | .......*....**... | .......**...**... |
20230423 19:36:19 [INFO] | ........***.*.... | .......*....*.... | ......**....*.... | .......**..*..... | .......**...*.... |
20230423 19:36:19 [INFO] | ..........*.*.... | .......**...**... | .........*..**... | ................. | ........***...... |
20230423 19:36:19 [INFO] | ......**..***.... | ......**.**.*.... | ..........*.**... | .........**..*... | ............*.... |
20230423 19:36:19 [INFO] | ......*..*....... | ......****.*..... | ......*..*.*..... | .......******.... | .......*...**.... |
20230423 19:36:19 [INFO] | .........*....... | ................. | .......**........ | .......**........ | .......*..**..... |
20230423 19:36:19 [INFO] | ................. | ................. | ................. | ................. | .......**........ |
20230423 19:36:19 [INFO] | .....*..*........ | .....*..*........ | ................. | ........*........ | .......**........ |
20230423 19:36:19 [INFO] | .....****........ | .....*..*........ | .......***....... | ......**.*....... | ......***........ |
20230423 19:36:19 [INFO] | .......*......... | ........*........ | .....**.**....... | .....*........... | .....*.*......... |
20230423 19:36:19 [INFO] | .....**.......... | .....**.*........ | .....**.*........ | .....**.......... | .....**.......... |
20230423 19:36:19 [INFO] | ......*.**....... | ......*.**....... | ........**....... | ........**....... | ........**....... |
20230423 19:36:19 [INFO] | ......*.*........ | .....**.*........ | .....**.*........ | .....**.*........ | .....**.......... |
20230423 19:36:19 [INFO] | ......*...*.*.... | ......*.*.*.*.... | ......*.*........ | ......*.**....... | ......*.**....... |
20230423 19:36:19 [INFO] | .......**.***.... | ......*.*.*.*.... | ......*.*...**... | ......*.*...**... | ......*.*........ |
20230423 19:36:19 [INFO] | .......**........ | .......*....*.... | .......*....*.... | .......*..*...... | .......*..*.**... |
20230423 19:36:19 [INFO] | .........***..... | ........****..... | ........*****.... | ........***.*.... | .......**.**..... |
20230423 19:36:19 [INFO] | ...........*..... | ...........*..... | ...........*..... | ........*........ | ........*........ |
20230423 19:36:19 [INFO] | ........*.*...... | ........***...... | ........*..*..... | ..........**..... | ..........**..... |
20230423 19:36:19 [INFO] | *..*...*.*....... | .......*.**...... | ......*...*...... | .........**...... | .........*.*..... |
20230423 19:36:19 [INFO] | *..*..*..*....... | *..**.***........ | .*.**....*....... | ..*......*....... | .*............... |
20230423 19:36:19 [INFO] | .***..*.......... | .***.***......... | .*......*........ | **..*...**....... | *..*...*.*....... |
20230423 19:36:19 [INFO] | ......*..*....... | ..*..**.......... | .***....*........ | .**....**........ | *.**...***....... |
20230423 19:36:19 [INFO] | ......*.*........ | .....**.**....... | ........**....... | ..*.............. | .**....**........ |
20230423 19:36:19 [INFO] | ......***........ | ......*.*........ | .....**.**....... | ......*..*....... | ......*.*........ |
20230423 19:36:19 [INFO] | ................. | .......*......... | .......*......... | ......***........ | ......***........ |
20230423 19:36:19 [INFO] | ................. | ................. | ................. | ................. | .......*......... |
20230423 19:36:19 [INFO] |                   | ................. | ................. | ................. | ................. |
20230423 19:36:19 [INFO] |                   |                   |                   |                   | ................. |
20230423 19:36:19 [INFO] Provenances:
20230423 19:36:19 [INFO]    596x "knightt-results/2c5-w12-n.rle"
20230423 19:36:19 [INFO]    43x "knightt-results/2c5-w11-n.rle"
20230423 19:36:19 [INFO]    55x "/home/amling/git/life-notes/ends/2c5/jslife-moving-2c5-1.rle"
...

This search is small enough that it dies out almost immediately, but if you run a wider search (e.g. 0/3/3) it will keep finding these same results one row further each time.

Let me know if you can stuck on any of the parts. I know it's a super unpolished mess still (having more or less just been written).

[Sokwe]

Can a LLSSS search be set up such that the edge of the search must be compatible with two specified slices? Specifically, I want to set up a 2c/5 search like the following:

Code: Select all

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

but it also must be compatible with the rightmost slice being empty. That is, the search must also satisfy the following input file:

Code: Select all

|                 |                 | ............... | ............... | ............... 
| ............... | ............... | ............... | ............... | ............... 
| ............... | ............... | ............... | ............... | ............... 
| ............... | ............... | ............... | ............... | ............... 
| ............... | ............... | ............... | ............... | ............... 
| ............... | ............... | ............... | ............... | ............... 
| ............... | ............... | ............... | ............... | ............... 
| ............... | ............... | ............... | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. | ...??????????.. 
| ...??????????.. | ...??????????.. |                 |                 |                 

I'm trying to test the viability of finding a 2c/6 wickstretcher similar to these partial results as I mentioned in the spaceship discussion thread. I am first experimenting at 2c/5 since it is easier. What I'm trying to do here is to find a sparker that can replace the HWSSs in the linked patterns. I found a very large 2c/5 example by specifying the input spark more specifically, but I specified the exact domino spark and kept the edge farther away from the wick:

Code: Select all

x = 45, y = 86, rule = B3/S23
11b3o17b3o$3b3o5bobo17bobo5b3o$2b2ob2o2bo3bo17bo3bo2b2ob2o$o2bo5bo2b2o
17b2o2bo5bo2bo$o2b2o3b2o25b2o3b2o2bo$7b3obo21bob3o$6bo2bo2bobo15bobo2b
o2bo$b3o2bo4b2obo15bob2o4bo2b3o$3b3o4bo3b2o13b2o3bo4b3o$4b4o2bo3bo15bo
3bo2b4o$4bo3b3o23b3o3bo$6b2o2bo2bo17bo2bo2b2o$2b2o4b2obo21bob2o4b2o$2b
o4b6o3b3o7b3o3b6o4bo$3bob2o2bo2bobo3bo7bo3bobo2bo2b2obo$4b2o4b2o2bo4bo
5bo4bo2b2o4b2o$3bo3b2o3bo4bobo2bo2bobo4bo3b2o3bo$5b4obobobob2obobobobo
b2obobobob4o$4bo2bob2o3b2o3bobobobo3b2o3b2obo2bo$7bo4b2o4b2obobob2o4b
2o4bo$3b2o2b4o3bo6bobo6bo3b4o2b2o$8b2o2bo2bo2b2obobob2o2bo2bo2b2o$8bo
6bo5bobo5bo6bo$7bob2o5b2o2b2ob2o2b2o5b2obo$7bobo6b3o2bobo2b3o6bobo$10b
4obo3bo5bo3bob4o$7b3ob2o3bo2bo5bo2bo3b2ob3o$6bo4bo4b2obo5bob2o4bo4bo$
5b2ob3o2b2obo11bob2o2b3ob2o$5b2o2bo2bo5b2o5b2o5bo2bo2b2o$5b2o11bo7bo
11b2o$6bo3b4o5bo5bo5b4o3bo$3bo3bo5bo3bo9bo3bo5bo3bo$2bobo7b2o2bo11bo2b
2o7bobo$b2obo3b2o6bo11bo6b2o3bob2o$3bo8bo19bo8bo$14bo15bo$3b2o5b2o2bo
15bo2b2o5b2o$2b4o3bo25bo3b4o$2bo2b2obo5b2o13b2o5bob2o2bo$5b3obo2b2o2bo
11bo2b2o2bob3o$11bo2bobo11bobo2bo$3b2o2b2ob6o13b6ob2o2b2o$10b5o15b5o$
3bo3b2o27b2o3bo$2bo12bo13bo12bo$2bo2bo4bo2b3o13b3o2bo4bo2bo$3bo5bo2b3o
15b3o2bo5bo$9bo4b2o13b2o4bo$4b2ob2o3bobo15bobo3b2ob2o$2bobobo31bobobo$
2bo2bo5b2o19b2o5bo2bo$3bob3o3b5o13b5o3b3obo$3bobo3b2o2b2o15b2o2b2o3bob
o$3b3o7bobo13bobo7b3o$2b4o9b2o11b2o9b4o$3b3o2b2o2b2o2bo11bo2b2o2b2o2b
3o$2b3obo2b2obo5b3o3b3o5bob2o2bob3o$3b2obob2o2b2o5b2o3b2o5b2o2b2obob2o
$5b2o2b3o2b2o4bo3bo4b2o2b3o2b2o$3bo2b2o2b2o3bo2b2o5b2o2bo3b2o2b2o2bo$
3bo2bo2bo6bob2o5b2obo6bo2bo2bo$4bo3b2o5b2o11b2o5b2o3bo$5bo4bo4b2o11b2o
4bo4bo$9bo3bo3bo9bo3bo3bo$7bo5bo2bo2b3ob3o2bo2bo5bo$17bo2b2ob2o2bo$11b
o4b5o3b5o4bo$10b3o6bo5bo6b3o$10bo23bo$12bo2bob2o7b2obo2bo$12b2o4b9o4b
2o$10bo10b3o10bo$10bo8b3ob3o8bo$17bo9bo$15bo4bo3bo4bo$14b2o4bo3bo4b2o$
13b2o15b2o$12b2o2b3o7b3o2b2o$11b2ob2o3bo5bo3b2ob2o$9b2obo2b4ob2ob2ob4o
2bob2o$12b2o6b2ob2o6b2o$14b3obo7bob3o$9bo3bo4bo7bo4bo3bo$11b3ob2o2bo5b
o2b2ob3o$20b5o!

Unfortunately, a solution of this size might not be findable at 2c/6, so I'm trying to expand the search space.

[amling]

Can a LLSSS search be set up such that the edge of the search must be compatible with two specified slices? Specifically, I want to set up a 2c/5 search like the following...

Not really, no. The way edges integrate into the rest of it requires them to pick actual cell values (although they don't have to be unique, e.g. the various symmetry edges, multiple values are independent for interaction with the rest of the search). The normal "single constant" edge picks them by demanding they be whatever is specified in the picture. With a lot of code I suppose you could let the edge pick any cells for its two columns so long as they were compatible with each of the now-"offscreen" slices you've given above. It would probably be rather a lot of code.

Also, it's a little worse than "two slices". One of your slices isn't really 2c/5, it's 5 consecutive generations of 4c/10 and you probably want to check compatibility of each generation with the other side as well (each of the two places it could align in the actual 4c/10 boundary).

I would probably try to come at your original problem with one hacky search or another to guess the two separating columns entirely so I could run a normal search with those specified columns. Some crummy ideas include:

(1) 2c/5 s2s search of some framing of the domino spark you think is good enough, take whatever boundary columns show up most often as the first "rows" of the s2s search. Could be which were extended the longest, could be human best guess from skimming partials, etc.

(2) 4c/10 b2f search with `LlsssFilterWeight1[Pd]` used to limit the number of non-2c/5 cells very harshly. You'd have to set it high enough to be able to handle the spark's interaction and to allow the very tips of the still life wick, but low enough that the actual continuation proper will be plain 2c/5. Here picking the boundary columns might be tricky since they could have actual strict 4c/10 contents in them, but you might still be able to find something strictly 2c/5 or at least something where searching some "one phase" version of it seems likely to produce a completion compatible with the true 4c/10 goal.

(3) 4c/10 s2s search from your exact 4c/10 interaction plan with `LlsssFilterWeight1[Pd]` used to limit the number of non-2c/5 cells. You'd use PD ends to find when it's been reduced to 2c/5 and then either continue that s2s or use it as edge columns in f2b turn as above.

All of these would "work" just as well with 2c/6 and 4/c12 although they're all crazy, crazy long shots.

[amling]

I just found and fixed a terrible bug in the EDBV3 ingestion code. Any databases for geometries with TILE_BITS > 1 (so e.g. s2s or with a common divisor like 2c/4) are likely not quite right and should be rebuilt. The bug was that I used integer division where I should have used `div_euclid`. The difference is in what happens for negative numbers. With TILE_BITS = 1 the divisions are the same and even with TILE_BITS > 1 for some geometries most slices will be unaffected by the mistake. When I rebuilt my c5-s2s and c4d-down databases I saw only very small differences, but my c4d-up database was mostly wrong (which is where I found the bug).

[amling]

Making the 2c/6 against-the-grain greyship exercised a few newer and/or less-used features of LLSSS that I thought I'd take the time to try to give a rough overview of:

(*) "Wrong answers only".

In this feature you provide an input file that is at least one extra W row wrong and LLSSS will try to extend the previous rows in a way that does not match the last row. This is especially useful with recentering which might otherwise find the cycle of a wick or a wave over and over again forever. It also can also break up the search space by "where" the row first mismatched the cycle meaning you can not include a first mismatch far from the relevant part (which might otherwise just start building a separate pattern while continuing the cycle).

To search with this you'd change `main` in `src/entry.rs` to call `main_llsss_recentering_wao` instead of `main_llsss`, edit whatever configuration in that main you need to, and then provide an appropriate input file and `--wao-idx` arguments to indicate which first error locations you want included (e.g. `--wao-idx ALL` for all).

(*) Awkward geometries.

As mentioned in the original brain dump, most searches run with U=X, but it doesn't have to be that way. Recentering with repeated undifferentiated columns can chimerically recombine them so long as they match and one beneficial side effect is it can be used to float the alignment of two parts of the pattern in integral multiples of whatever your cycle is (which can be as fine-grained as U). As an example, here is the input file that found the key piece of the 2c/6 side corner (traveling 2c/6 west):

Code: Select all

|  LLLLuMMMMMMMMMuuuuuuRRR |  LLLLuMMMMMMMMMuuuuuuRRR |  LLLuuMMMMMMMMuuuuuuuRRR | LLLLuMMMMMMMMMuuuuuuRRR  | LLLLuMMMMMMMMMuuuuuuRRR  | LLLuuMMMMMMMMuuuuuuuRRR  |
|  ....*.*.*.*.*.*.*..**** |  ....*.*.*.*.*.*.*..**** |  ....*.*.*.*.*.*..*.**** | .....*.*.*.*.*.*.******  | .....*.*.*.*.*.*.*.****  | ...*.*.*.*.*.*.*..*.***  |
|  ****..*.*.*.*.*.*...... |  ****..*.*.*.*.*........ |  ****..*.*.*.*.*.*...... | ******.*.*.*.*.*.*.....  | ****.*.*.*.*.*.*.......  | ***..*.*.*.*.*.*.......  |
|  ......*.*.*.*.********* |  ......*.*.*.*.*.******* |  ....*.*.*.*.*..*.****** | .....*.*.*.*.*..*******  | .....*.*.*.*.*..*******  | .....*.*.*.*..*.*******  |

L marks repeated left columns, M marks repeated middle columns, and R marks repeated right columns. "u" is special and means unique markers are made up for each spot. An input file like this, but with U=X would be able to float the alignment of the left and right halves by integral multiples of U=X so 2X which is where the vertical stripes agar first repeats. But with U=T it can float the alignment down to a single T since the cycle (vertical stripes) is a still life.

The upside here is I didn't have to write so many different alignments (just 4 = 2 absolute vertical alignment of left stripes * 2 absolute vertical alignment of right stripes).

The downside is this requires commenting in a bunch of sketchy rust macro code (each place in `git grep BIG`), setting the SL2 size to something larger (e.g. 7 for this geometry), and then the search generally is slow and uses more memory than an analogous search with U=X. In this case I took the best results from U=T searches and reran them in other more focused U=X searches.

(*) Constraints.

Some modes allow specifying extra constraints on cells. I took the best 2c/6 results, stripped them down to their p6 parts and filled the rest of the grid with half-period constraints to effectively run a c/3 search but allow (require) just those few 2c/6 cells.

Input file:

Code: Select all

|  LLLLLLuuuuuuuuuuRRR |  LLLLLLuuuuuuuuuuRRR |  LLLLLLuuuuuuuuuuRRR | LLLLLLuuuuuuuuuuRRR  | LLLLLLuuuuuuuuuuRRR  | LLLLLLuuuuuuuuuuRRR  |
|  ......*.*.*.*..**** |  ......*.*.*..*.**** |  ......*.*.*.******* | .......*.*.*.*.****  | .......*.*.*..*.***  | .......*.*.*..*****  |
|  ******..*.*........ |  ******..*.*.*...... |  ******..*.*.*...... | *******..*.*.......  | ********.*.*.......  | ******.*.*.*.......  |

Constraint file:

Code: Select all

|  LLLLLLuuuuuuuuuuRRR |  LLLLLLuuuuuuuuuuRRR |  LLLLLLuuuuuuuuuuRRR | LLLLLLuuuuuuuuuuRRR  | LLLLLLuuuuuuuuuuRRR  | LLLLLLuuuuuuuuuuRRR  |
|  HHHHHH*.*.*.*.HHHHH |  HHHHHH*.*.*.H*.*HHH |  HHHHHH*.*.*.**HHHHH | HHHHHH.*.*.*.*HHHHH  | HHHHHH.*.*.*H.*.HHH  | HHHHHH.*.*.*..HHHHH  |
|  HHHHHH.H*.*.HHHHHHH |  HHHHHH..*.*.*HHHHHH |  HHHHHHH.*.*.*HHHHHH | HHHHHH*H.*.*HHHHHHH  | HHHHHH**.*.*.HHHHHH  | HHHHHHH*.*.*.HHHHHH  |
|  HHHHHHHHHHHHHHHHHHH |  HHHHHHH*HHHH.HHHHHH |  HHHHHH*HH*.H.HHHHHH | HHHHHHHHHHHHHHHHHHH  | HHHHHHH.HHHH*HHHHHH  | HHHHHH.HH.*H*HHHHHH  |
|  HHHHHH*HHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH | HHHHHH.HHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  |
|  HHHHHHHHHHHHHHHHHHH |  HHHHHH.HHHHHHHHHHHH |  HHHHHHH.HHHHHHHHHHH | HHHHHHHHHHHHHHHHHHH  | HHHHHH*HHHHHHHHHHHH  | HHHHHHH*HHHHHHHHHHH  |
|  HHHHHHHHHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH | HHHHHHHHHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  |
|  HHHHHHHHHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH | HHHHHHHHHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  |
|  HHHHHHHHHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH |  HHHHHHHHHHHHHHHHHHH | HHHHHHHHHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  | HHHHHHHHHHHHHHHHHHH  |

I continued it several hundred more lines of H's just in case. Unfortunately there is no reasonable way to specify that. Also unfortunately constraints are applied per root label so it's important they match between constraint grid and input file (e.g. "u" at same U coordinate) and that they are unique per root label (e.g. all for L are the same).

(*) K-gram edges.

Another trick to let LLSSS recentering pick alignment for you. That same search above with all the H's was run with `kgram:2` edges with files like:

Code: Select all

|  .. |  .. |  .. | ..  | ..  | ..  |
|  ** |  ** |  ** | **  | **  | **  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  ** |  ** |  ** | **  | **  | **  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  ** |  ** |  ** | **  | **  | **  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  ** |  ** |  ** | **  | **  | **  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  .. |  .. |  .. | ..  | ..  | ..  |
|  .. |  .. |  .. | ..  | ..  | ..  |

This lets LLSSS walk down the edge extending it row by row to always locally look like some 3 W row neighborhood of the above. Effectively it means it got to choose [the W coordinate] where to put that transition from stripes to zeros. Combined with the left edge already U floating this meant it had a great deal of freedom. As a result I neither had to guess an alignment and commit to it, nor sketch endless input files with specific alignments.

(*) Arbitrary closures.

LLSSS recentering was originally conceived as a limited window to expand in but now it sort of works backwards. The implementation is it will walk an unlimited number of steps inward from its edges as long as those steps meet its "inertness" requirement (e.g. could be last rows are all zero, could be last rows are all some agar, etc.). Then it does some configured number of completely arbitrary steps inward (this is what we think of as the window size), then whatever has met in the middle is kept.

It can also do other closure steps in between and there are various notions of closure available. Most of these searches included a configurable number of c/3-only steps in between the background agar unlimited closure and the arbitrary steps center window. E.g. the critical search for the side corner had found its best partial in a configuration including 12 U=T c/3-only steps on each side (vaguely analogous to 4 U=X steps in other searches).



Let me know if people want to know more about the details of any of these. Unfortunately they're all pretty complicated, both in terms of their semantics and in terms of how to set up them up (either at all, or even worse to make effective use of them).

[pzq_alex]

Placeholder for the details of how the CA check works and in particular the table-makery and PEXT nonsense that speeds it up.

I assume these are least interesting of anything I'm going to write, but I'll come back and fill them in if someone wants to know.

I'd love to hear the pext bit twiddling. (But do tell me if writing about so many details bothers you!)

[amling]

Placeholder for the details of how the CA check works and in particular the table-makery and PEXT nonsense that speeds it up.

I assume these are least interesting of anything I'm going to write, but I'll come back and fill them in if someone wants to know.

I'd love to hear the pext bit twiddling. (But do tell me if writing about so many details bothers you!)

Ah yes, the CA checks. They have changed so much at this point and they are quite, quite complicated.

The shortest version is that PEXT lets us use a scalar mask to efficiently select a subset of bits from another scalar. So I might pext one scalar, 0bABCDEFGH with a mask like 0b01100010 and get back just those three bits, in order, like 0bBCG. This can be used to efficiently select out subsets of cells for counting and of course the mask can be something precomputed.

The next shortest version is that depending on circumstances some things may be counted more than once and rather than have two masks so I can select the same cell twice for counting I just select all relevant cells and look up in a table with the PEXTed value (which ranges from zero inclusive and 2^K exclusive where K is the number of bits set in the mask).

This works until your table has to be too big at which point it's now a few steps: (1) PEXT out all the cells that will be relevant in any CA check and assemble (shift and or) the selected parts into one big scalar (called "all data" in the code), (2) PEXT out subsets of those cells one at a time, looking up in tables, each of which represents some subset of the CA checks but isn't too big, (3) AND together all the answers that came out of the tables.

Finally, sometimes you're not just asking "is this OK", but asking "what values of these cells are legal". E.g. when LLSSS expanded a tile at a time it wanted the entire tile or LGOL generally steps 8 cells at a time. Even now LLSSS edges like, say, odd symmetry, want to pick multiple bits at a time (yes it's "one bit at a time", but there are two columns in the edge to pick those for). Now instead of the value in the table being just yes or no, it's one bit yes or no for each combination of cells we're picking. So e.g. for odd symmetry edge expansion, where we're picking two cells at a time, we are reading a 4-bit scalar out of the table. For LGOL stepping 8 cells at a time we're reading a 256 bit scalar, etc. These table reads are then ANDed together and each still-live bit indicates a legal possibility of the cells in question.

There of course a ton of details to fill in like how you specify the parameters of such a set of tables, how you divide up the CA checks into sets so that each set's table is not "too big", but while still minimizing the number of tables, how you optimize the table computation itself since it does take meaningful time, etc.

How much detail are you looking for here? This much should hopefully cover curiosity and might even cover an intent to incorporate PEXT into another program.

[amling]

The PD (period dividing) tools have changed somewhat since I last explained them and it might be worth refreshing the details on this thread.

All versions of the technique are the same goal: to reduce a high period problem (e.g. 4c/8) to a lower period that divides it (e.g. 2c/4). Generally to run lower period searches there has to be some sort of axis-aligned boundary 2 cells wide dividing the high period part the search can't see from the low period part it is then searching.

The very very first version of this was the simplest possible: run a high period LGOL search (that was all I had at the time) and if any partials (which, remember, LGOL keeps fully-reified individually) had 2 trailing low period Y rows then output them.

Unfortunately while 2 Y rows was technically enough to seed a low period search often such results ended up impossible to extend. I settled on generally requiring 4 Y rows, then pruning the partial results back to their first 2 Y rows, deduplicating them, and seeding low period searches with them. This worked well enough and it was how I found e.g. the results that would go on to be quartermax.

With LLSSS fixed board the same technique works well enough even though LLSSS's internal state doesn't actually keep the reified partials. It's still possible to do some fancy graph algorithms and generate the full set of reified PD partials with 4 Y rows, etc.

With LLSSS recentering though there is a problem in that it allows horizontally-repeating components and so there's no real notion of all partials. Initially I would output the thinnest PD partial after each row, eyeball the various results and try to forward some of them to low period searches to complete, but this is leaving a lot on the table.

I eventually sketched some hacks (more or less uncommitted) to take one of these reduced results and rerun the high period search that generated it but this time refuse to allow high period cell cohorts unless they corresponded to the input. This allowed the search to make more ad-hoc low period edits above the dividing line between the high period top and low period bottom. This was how I found e.g. that 2c/6 wick front.

The latest version, which was used to solve this 2c/8d backrake, is that when the initial high period search discovers there are partials that end with 2 low period Y rows it dumps out all of the graph nonsense that they are made of, thus capturing them all (where by "them all" I mean an upper bound on the regular language of them all). The exact format is complicated and not particularly important, but it allows a subsequent high period search to restrict itself to only low period cell cohorts and high period cell cohorts that in a sense were from the unrestricted search. This materially limits this second search's search space allowing me to run it much wider (although of course the extra width is all filled with low period stuff).

Unfortunately this stuff is all quite unpolished even by the, uh, standards of the codebase so I'm not entirely sure I can recommend trying to run it. I guess I just wanted the ideas out there...

[amling]

It’s a pity that Keith’s programs are not easily available to the public. Other people making clever use of its features would potentially open a lot of new use cases.

By this I assume you mean that his programs are not easily usable (and some experimental features might not be available). Keith's code is available here, and he discusses his techniques and explains how to use his code in this thread. He's been very helpful whenever I've asked a question, but there is still much about the use, much more the code, that I don't understand. I view it as an almost necessary consequence of a tool that's so powerful and feature-rich.

By this I mean that there is no readymade Windows executable that runs on a small laptop like WLS does.

Seriously: I don’t see a real user base so far. And this is a pity. I’m sure other people would come with new ideas and use the programs in ways Keith didn’t think about or just doesn’t have the time to try out!

You've completely lost me at "Windows".

Still, an occasional reminder to try to hack towards usability is helpful. Unfortunately "make CLIs that are usable by other human beings" is not exactly in my skill set.

I managed to rip out `TILE_BITS` entirely so the geometry can be dynamic as well (and is now a required first argument for all common `main_xxx` methods). Arguments are interpreted by `geom_by_name`, e.g. stuff like "2c4-f2b", "2c5-b2f", "3c7-s2s", "c4d-down", "2c8d-up". This does not work for all such speeds in general, just those I have programmed W choices for. It does cover every search I've ever run, but if you want to search for some higher vt stuff like 4c/9 you may have to go improve it (see `pick_vert_w`). Figuring out the shape of the input file sucks as much as ever.

I added `--rule` so this can be configured dynamically. For now it's only "S23/B3" style so if you want to do something weird like forbidden transitions you'll have to edit code.

I added `--ends` so this can be configured dynamically. Arguments are interpreted by `convert_ends`, may be separated by commas, and include things like "zero", "edbv3:/some/path.edbv3", "pd:2", "pd_lite:3", "s_periodic:0:0:1".

Unfortunately I'm not sure how best to manage the split between fixed-board and recentering. For now `main` still calls `main_llsss` (fixed board) directly and anyone wishing to run recentering (or goodness forbid "wrong answers only") will have to edit code.

[amling]

I did some more work wrestling rust's type system and 3p library ecosystem:

*) Reworked type system structure of recentering closures to allow them to be dynamic, e.g. `--left-closure zero,pd:2:10` to full-closure zeros then do 10 steps of 2-fold PD or `--left-closure u_copy` to allow horizontal stripes, etc. Values adjudicated by `convert_closures`.

*) Reworked type system structure of constraints to allow them to be dynamic. Something like `--constraint grid:file.pic:none` does what `--constraint-grid file.pic` used to. Also available is `pd:K` (e.g. `--constraint grid:file.pic:pd:2` to force 2-fold PD beyond the grid). It is unfortunate that there is probably a perf hit here. Searches with no constraint will be the same as always but searches with any constraints will dispatch them dynamically at runtime in some of the very tightest loops of the program. I have not actually benchmarked it, but it is something to be wary of.

*) Expanded use of `clap` to do subcommands. Now the default `main()` has subcommands like `llsss`, `llsss-recentering`, `edbv3-ingest`, etc. This also let me write a `grid-tool` which has made sketching input files for interesting geometries way, way easier. Subsubcommands `to-uwi` and `from-uwi` can switch back and forth between x/y/t coords and lu/lw/subtile_idx coords which makes it easier to figure out where to put the root labels, figure out what the staggering should look like to make it a lu-lw rectangle, etc. Subsubcommands `xflip`, `yflip`, `cw`, and `ccw` are nicer than UNIX `tac` and my crummy one-off clockwise rotation python script. Subsubcommand `pd-fold` can generate those pd-folded views I've been doing by labor-intensive editor nonsense for understanding higher period partials (e.g. folding 4c/8 to a 2c/4 view where disagreements are marked 'x' and 'o' instead).

*) Added PD rotor tree to `--ends` and `--constraint`. It's still extremely hard to understand and use but at least doesn't require building a custom binary any more.

All together these allow the default build as of `master` to cover maybe 90% of my searches and I suspect 100% of searches that anyone who is not me has ever run. It also seems like it has increased build times and binary sizes materially so if you're sensitive to either of those things it might be worth stripping `main()` down to just whatever your search actually is (and removing `debug = true` to trade error clarity for binary size or removing `lto = true` to trade some runtime performance for a lot of build time performance).

For my part I have a commonish set of options/configurations I've been copying around and building "solver" binaries with, but I have to build it for each combination of fixed/recentering and geometry which is a huge pain (I've just been keeping dozens of separate repos). Now I can unify them all into one generic solver binary which is going to save me a lot headache. Compiling the new binary is slow and big but it's way faster/smaller than 60+ copies.

[amling]

I ran some s2s searches for 2c/4 negative signals in perpendicular stripes. I guess I was hoping for some inspiration or start on a side corner for a hypothetical negative ship. Unsurprisingly nothing very nice turned up. Longest partial:

Code: Select all

|  .*.*.*.*.*.*.*.*.*.*.*.*.*.*.* |  .*.*.*.*.*.*.*.*.*.*.*.*.*.*.* | *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.  | *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.  |
|  .*.*.*.*.*.*.*.*.*.*.*.*.*.*.* |  .*.*.*.*.*.*.*.*.*.*.*.*.*.*.* | *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.  | *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.  |
|  .*.*.*.*.*.*.*.*.*.*.*..*.**.* |  .*.*.*.*.*.*.*.*.*.*.*..**.*.* | *.*.*.*.*.*.*.*.*.*.*.*..**.*.  | *.*.*.*.*.*.*.*.*.*.*.*..**.*.  |
|  .*.*.*.*.*.*.*.*.*.*.*.....*.* |  .*.*.*.*.*.*.*.*.*.*.*.....*.* | *.*.*.*.*.*.*.*.*.*.*.*.....*.  | *.*.*.*.*.*.*.*.*.*.*.......*.  |
|  .*.*.*.*.*.*.*.*.*.*..*****..* |  .*.*.*.*.*.*.*.*.*..*.******.* | *.*.*.*.*.*.*.*.*.*..******.*.  | *.*.*.*.*.*.*.*.*.*..*****..*.  |
|  .*.*.*.*.*.*.*.*.*.........*.* |  .*.*.*.*.*.*.*.*.*.........*.* | *.*.*.*.*.*.*.*.*.*.........*.  | *.*.*.*.*.*.*.*.*.*.......*.*.  |
|  .*.*.*.*.*.*.*..*.**********.* |  .*.*.*.*.*.*.*..*.********.*.* | *.*.*.*.*.*.*.*..*.*******..*.  | *.*.*.*.*.*.*.*..*********..*.  |
|  .*.*.*.*.*.*.*....*.....*..*.* |  .*.*.*.*.*.*.*....*...*....*.* | *.*.*.*.*.*.*.*........*..*.*.  | *.*.*.*.*.*.*..........*..*.*.  |
|  .*.*.*.*.*.*.**...*.*....*.*.* |  .*.*.*.*.*.*.**...**.....*.*.* | *.*.*.*.*.*.*.....***....**.*.  | *.*.*.*.*.*.*.....*.*....**.*.  |
|  .*.*.*.*.*.*.*..**......**.*.* |  .*.*.*.*.*.*.****..*....**.*.* | *.*.*.*.*.*.*....*.**.....*.*.  | *.*.*.*.*.*.*...**..*...*.*.*.  |
|  .*.*.*.*.*.*....**.*.....*.*.* |  .*.*.*.*.*..*..*.......*.*.*.* | *.*.*.*.*.*..**.**.....**.*.*.  | *.*.*.*.*.*.***.***....**.*.*.  |
|  .*.*.*.*.*......***...**.*.*.* |  .*.*.*.*.*........*...**.*.*.* | *.*.*.*.*.**..**........*.*.*.  | *.*.*.*.*.***.........*.*.*.*.  |
|  .*.*.*.*.*....**.......*.*.*.* |  .*.*.*.*.*...**......*.*.*.*.* | *.*.*.*.*.*..***.....**.*.*.*.  | *.*.*.*.*.**.*.*.....**.*.*.*.  |
|  .*.*.*.*.**..**.*...**.*.*.*.* |  .*.*.*.*.*.*.*...*..**.*.*.*.* | *.*.*.*.*..........*..*.*.*.*.  | *.*.*.*..*...*......*.*.*.*.*.  |
|  .*.*.*.*..**..****.*.*.*.*.*.* |  .*.*.*.*...*.**..*.*.*.*.*.*.* | *.*.*.*.......**....*.*.*.*.*.  | *.*.*.*..*....**..*.*.*.*.*.*.  |
|  .*.*.*.*..*......*.*.*.*.*.*.* |  .*.*.*...*.........*.*.*.*.*.* | *.*.*.*..**.***..**.*.*.*.*.*.  | *.*.*.**.*..*...***.*.*.*.*.*.  |
|  .*.*.*....**....**.*.*.*.*.*.* |  .*.*.*...**.*...**.*.*.*.*.*.* | *.*.*.*..***.**..**.*.*.*.*.*.  | *.*.*.*.*.......*.*.*.*.*.*.*.  |
|  .*.*.*.*..*.**.....*.*.*.*.*.* |  .*.*.*.*..*.**..**.*.*.*.*.*.* | *.*.*.*.*..*.**.*...*.*.*.*.*.  | *.*.*.**.*.*....*.*.*.*.*.*.*.  |
|  .*.*..*.*.*...*..*.*.*.*.*.*.* |  .*.*..***.*...*..*.*.*.*.*.*.* | *.*..*.....*.*.**.*.*.*.*.*.*.  | *.*.*..*..**.*....*.*.*.*.*.*.  |
|  .*.*.....**...****.*.*.*.*.*.* |  .*.....****..**..*.*.*.*.*.*.* | *.*..**....**...***.*.*.*.*.*.  | *.*....*..**.****.*.*.*.*.*.*.  |
|  .*.....*......*..*.*.*.*.*.*.* |  .*..**.*..*..**..*.*.*.*.*.*.* | *.**.**.*..*.*....*.*.*.*.*.*.  | *.*......*.*....*.*.*.*.*.*.*.  |
|  .*..******..*..*.*.*.*.*.*.*.* |  .*..**.*.*...***.*.*.*.*.*.*.* | *.*.***..**.....*.*.*.*.*.*.*.  | *.....******..*...*.*.*.*.*.*.  |
|  .**..*...*....*..*.*.*.*.*.*.* |  .**.......***....*.*.*.*.*.*.* | *.**.....*..***...*.*.*.*.*.*.  | *..***....*...***.*.*.*.*.*.*.  |
|  .*...*..*.*.****.*.*.*.*.*.*.* |  .*.......**....***.*.*.*.*.*.* |                                 |                                 |

Code: Select all

x = 49, y = 38, rule = B3/S23
obobobobobobobobobobobobobobobobobobobobobobobobo$obobobobobobobobobob
obobobobobobobobobobobobobobo$obobobobobobobobobobobobobobobobobobobob
obobobobo$obobobobobobobobobobobobobobobobobobobobobobobobo$obobobobob
obobobobobobobobobobobobobobobobobobobo$obobobobobobobobobobobobobobob
obobobobobobobobobo$obobobobobobobobobobobobobobobobobobobobobobobobo$
obobobobobobobobobobobobobobobobobobobobobobobobo$obobobobobobobobobob
obobobobobobobobobobobobobobo$obobobobobobobobobobobobobobobobobobobob
obobobobo$obobobobobobobobobobobobobobobobobobobobobobobobo$obobobobob
obobobobobobobobobobobobobobobobobobobo$obobobobobobobobobobobobobobob
obobobobobobobobobo$obobobobobobobobobobobobobobobobobobobobobobobobo$
obobobobobobobobobobobobobobobobobobobobobobobobo$obobobobobobobobobob
obobobobobobobobobobobobobobo$obobobobobobobobobobobobobobobo2bob2obob
obobobobo$obobobobobobobobobobobobobobobo5bobobobobobobo$obobobobobobo
bobobobobobobobo2b5o2bobobobobobo$obobobobobobobobobobobobobo9bobobobo
bobobo$obobobobobobobobobobobo2bob10obobobobobobo$obobobobobobobobobob
obo4bo5bo2bobobobobobobo$obobobobobobobobobobob2o3bobo4bobobobobobobob
o$obobobobobobobobobobobo2b2o6b2obobobobobobobo$obobobobobobobobobobo
4b2obo5bobobobobobobobo$obobobobobobobobobo6b3o3b2obobobobobobobobo$ob
obobobobobobobobo4b2o7bobobobobobobobobo$obobobobobobobobob2o2b2obo3b
2obobobobobobobobobo$obobobobobobobobo2b2o2b4obobobobobobobobobobobo$o
bobobobobobobobo2bo6bobobobobobobobobobobobo$obobobobobobobo4b2o4b2obo
bobobobobobobobobobo$obobobobobobobobo2bob2o5bobobobobobobobobobobo$ob
obobobobobo2bobobo3bo2bobobobobobobobobobobobo$obobobobobobo5b2o3b4obo
bobobobobobobobobobo$obobobobobo5bo6bo2bobobobobobobobobobobobo$obobob
obobo2b6o2bo2bobobobobobobobobobobobobo$obobobobob2o2bo3bo4bo2bobobobo
bobobobobobobobo$obobobobobo3bo2bobob4obobobobobobobobobobobobo!

The back connection is pretty nice but that front side is a mess, as has generally been true for such boundaries between perpendicular stripes in the front and vacuum in the back.

Some of the recent posts about possible phoenix periods made me notice this "LifeHistory" business and dig a little into the golly docs about it. I am still skeptical of it is a general interchange format as it's a pain to read and write but e.g. I could use it to show partials above like:

Code: Select all

x = 137, y = 24, rule = LifeHistory
F2.BABABABABABABABABABABABABABABA.F2.BABABABABABABABABABABABABABABA.F
.ABABABABABABABABABABABABABABAB2.F.ABABABABABABABABABABABABABABAB2.F$
F2.BABABABABABABABABABABABABABABA.F2.BABABABABABABABABABABABABABABA.F
.ABABABABABABABABABABABABABABAB2.F.ABABABABABABABABABABABABABABAB2.F$
F2.BABABABABABABABABABABA2BAB2ABA.F2.BABABABABABABABABABABA2B2ABABA.F
.ABABABABABABABABABABABA2B2ABAB2.F.ABABABABABABABABABABABA2B2ABAB2.F$
F2.BABABABABABABABABABABA5BABA.F2.BABABABABABABABABABABA5BABA.F.ABABA
BABABABABABABABABA5BAB2.F.ABABABABABABABABABABA7BAB2.F$F2.BABABABABAB
ABABABABA2B5A2BA.F2.BABABABABABABABABA2BAB6ABA.F.ABABABABABABABABABA
2B6ABAB2.F.ABABABABABABABABABA2B5A2BAB2.F$F2.BABABABABABABABABA9BABA.
F2.BABABABABABABABABA9BABA.F.ABABABABABABABABABA9BAB2.F.ABABABABABABA
BABABA7BABAB2.F$F2.BABABABABABABA2BAB10ABA.F2.BABABABABABABA2BAB8ABAB
A.F.ABABABABABABABA2BAB7A2BAB2.F.ABABABABABABABA2B9A2BAB2.F$F2.BABABA
BABABABA4BA5BA2BABA.F2.BABABABABABABA4BA3BA4BABA.F.ABABABABABABABA8BA
2BABAB2.F.ABABABABABABA10BA2BABAB2.F$F2.BABABABABABAB2A3BABA4BABABA.F
2.BABABABABABAB2A3B2A5BABABA.F.ABABABABABABA5B3A4B2ABAB2.F.ABABABABAB
ABA5BABA4B2ABAB2.F$F2.BABABABABABABA2B2A6B2ABABA.F2.BABABABABABAB4A2B
A4B2ABABA.F.ABABABABABABA4BAB2A5BABAB2.F.ABABABABABABA3B2A2BA3BABABAB
2.F$F2.BABABABABABA4B2ABA5BABABA.F2.BABABABABA2BA2BA7BABABABA.F.ABABA
BABABA2B2AB2A5B2ABABAB2.F.ABABABABABAB3AB3A4B2ABABAB2.F$F2.BABABABABA
6B3A3B2ABABABA.F2.BABABABABA8BA3B2ABABABA.F.ABABABABAB2A2B2A8BABABAB
2.F.ABABABABAB3A9BABABABAB2.F$F2.BABABABABA4B2A7BABABABA.F2.BABABABAB
A3B2A6BABABABABA.F.ABABABABABA2B3A5B2ABABABAB2.F.ABABABABAB2ABABA5B2A
BABABAB2.F$F2.BABABABAB2A2B2ABA3B2ABABABABA.F2.BABABABABABABA3BA2B2AB
ABABABA.F.ABABABABA10BA2BABABABAB2.F.ABABABA2BA3BA6BABABABABAB2.F$F2.
BABABABA2B2A2B4ABABABABABABA.F2.BABABABA3BAB2A2BABABABABABABA.F.ABABA
BA7B2A4BABABABABAB2.F.ABABABA2BA4B2A2BABABABABABAB2.F$F2.BABABABA2BA
6BABABABABABABA.F2.BABABA3BA9BABABABABABA.F.ABABABA2B2AB3A2B2ABABABAB
ABAB2.F.ABABAB2ABA2BA3B3ABABABABABAB2.F$F2.BABABA4B2A4B2ABABABABABABA
.F2.BABABA3B2ABA3B2ABABABABABABA.F.ABABABA2B3AB2A2B2ABABABABABAB2.F.A
BABABABA7BABABABABABABAB2.F$F2.BABABABA2BAB2A5BABABABABABA.F2.BABABAB
A2BAB2A2B2ABABABABABABA.F.ABABABABA2BAB2ABA3BABABABABAB2.F.ABABAB2ABA
BA4BABABABABABABAB2.F$F2.BABA2BABABA3BA2BABABABABABABA.F2.BABA2B3ABA
3BA2BABABABABABABA.F.ABA2BA5BABAB2ABABABABABABAB2.F.ABABA2BA2B2ABA4BA
BABABABABAB2.F$F2.BABA5B2A3B4ABABABABABABA.F2.BA5B4A2B2A2BABABABABABA
BA.F.ABA2B2A4B2A3B3ABABABABABAB2.F.ABA4BA2B2AB4ABABABABABABAB2.F$F2.B
A5BA6BA2BABABABABABABA.F2.BA2B2ABA2BA2B2A2BABABABABABABA.F.AB2AB2ABA
2BABA4BABABABABABAB2.F.ABA6BABA4BABABABABABABAB2.F$F2.BA2B6A2BA2BABAB
ABABABABABA.F2.BA2B2ABABA3B3ABABABABABABABA.F.ABAB3A2B2A5BABABABABABA
BAB2.F.A5B6A2BA3BABABABABABAB2.F$F2.B2A2BA3BA4BA2BABABABABABABA.F2.B
2A7B3A4BABABABABABABA.F.AB2A5BA2B3A3BABABABABABAB2.F.A2B3A4BA3B3ABABA
BABABABAB2.F$F2.BA3BA2BABAB4ABABABABABABABA.F2.BA7B2A4B3ABABABABABABA
.F33.F33.F!

Of course not going to work as well when I want to start marking up interesting features with a's, b's, o's, x's, exclamation points, question marks, etc., but that is done infrequently.

[dvgrn]

Of course not going to work as well when I want to start marking up interesting features with a's, b's, o's, x's, exclamation points, question marks, etc., but that is done infrequently.

Well, if you want more states to highlight more features, LifeHistory does have states 3, 4, and 5 -- and if you want more ON states than just 3 and 5, there's also LifeSuper. LifeViewer and Golly both support it, and both have shortcut keys to convert it to LifeHistory and/or to plain-vanilla Life when that's appropriate.