amling search program principles discussion / brain dump

For scripts to aid with computation or simulation in cellular automata.
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

amling wrote: February 15th, 2025, 2:09 am I've pushed it to codeberg as 20250214-autochoke-semsv1-04. Ideally, Sokwe, I'd hope to talk you into trying this cut of it and if we like it, ultimately merge this to master after maybe cleaning up a few things
I've tested it and it seems to do what I expect/want. I'm of course very supportive of including it in the master branch assuming that it really does not affect ordinary searches and it doesn't make the code much more difficult to maintain.
amling wrote: February 15th, 2025, 2:09 am I think for the purposes of desperate searches running out of memory and just wishing they could squeeze a little more out it's probably fine.
This is probably a useless nitpick, but that's not generally how I view this feature. Consider for example a 2c/2 side-to-side search in B2357/S3678. If I run a WAO search with mid_steps 25 it finishes quickly with no solutions. If I try again with mid_steps 26 it quickly finds a wide wing that then starts to shrink in width, causing a combinatorial explosion that slows the search. I wouldn't say I'm "desperate" In this case. I'm fairly confident I could find a complete spaceship by taking some partial results and continuing them at lower widths looking for a symmetric completion, but this is tedious and tends to give larger-than-necessary results. Instead, I can run the mid_steps 26 search with autochoke at a mere 10MB and quickly find an odd-glide-symmetric solution at w_pos 53:

Code: Select all

x = 27, y = 103, rule = B2357/S3678
17bo$15bo4bo2bo$14bob8o$13bo3bo4b3o$11bob3o4bo$10b2o4bo3b5o$10b2ob4obo
3b2o$8bo3b2obo2bo4bo$6bo2b3o2b5ob4obo$5bo7b11o$2bo2bob3obob2obo2bob3o$
ob5o2bo4b2ob2ob4o$o3b6obo2bo2b4o2bobo$bo3bob2obo4bo3b5o$b2o2bo5bo7b5o$
2b4obo3b2obob8o$2bobobo3b3o2bo4b4obo$bob2o2bo2b2o2bo5bob2o$bobo2b11o2b
3obo$bo3b4o2bo2b2o2b6o$2bob2obobo2b3obobob4obo$4bo3b2ob5o3b5o$4bob3o5b
10o$6b3o2b3o4bob4o$2bo5b2ob2o2b9obo$2bobob4o6b8o$4bobobo7b8o$4bo2b4obo
bobob6o$4bob2o6bob2ob5obo$6bo2b7o3b5o$6bo2b3obobobo3b3o$5bobo3b2ob3o4b
3o$5bobo3bo2b10obo$5bob2o2bo2b2o3b5o$5bo2bo2bo3bo3b5o$5bobo2bo5b8o$6b
3o3bobo2b7obo$7bo5b4ob2ob3o$8b2obobo3bobob3o$8b3o5b8o$7bobo3bob9obo$6b
o2b6ob2obob3o$6bobob2o2b3ob2ob3o$6bobob3ob2ob7o$6bo2bo3b11obo$6bo2bo3b
ob9o$6bobo2bo2b10o$6bobo2b13o$8bob2obob9obo$10bobob10o$12b3o2b7o$12b
12o$14b10obo$10bobo4b7o$8bo2bo3b9o$6bobo6b9o$6bobob2ob11obo$6bo2bobob
11o$6bo2b2obo2b9o$6bobobo2b11o$6bobo2b2o3bo2bob3obo$6bo9b4ob3o$7bobo4b
o2b7o$8bo3b5ob6o$8bo4bo3bobob3obo$7bob4o3b4ob3o$6bo2b2obo2b9o$5bobo2bo
b6ob5o$5bobob3obob2ob6obo$5bob5ob2o2b7o$5bo2bo2b2o3bob2ob3o$5bobob3o4b
3ob4o$6b8obobob5obo$7bob2o6b2ob4o$4bo2bob4o4b7o$4bobo3bobobobob6o$6b4o
b2obo3b6obo$2bo8b3o3b7o$2bobobob2o2bob2o2b6o$4bob3o2b2obobob2ob3o$4bo
2b2o2bo5b2ob4obo$5b2obob2o2b10o$2bob2obo2bo3b2o2b6o$bo2bo2b5o2b3o2b5o$
bobo4bo9b2ob3obo$bobobo4b3obob2o4b2o$2bobob5obo2b6ob2o$14bobo2bob3o$b
2o2b19obo$b4o6b3obob7o$o2bo2b2o6b2o2bob4o$o5b2obob3o9bo$2bo2bobobobobo
b2o4b3obo$5bo2bo2b2o2b4o2b3o$6bob2o4b5o4bo$8bo2b2o2b2o2bobo$10b2ob2o2b
o2b2o$10bo2bo3b2obo$11bo3bob2obob2o2bo$13b3o2bo3bo$14bob6o$15bo5bo3bo$
17bo!
I suspect an ordinary search would run out of memory before even reaching w_pos 53 on most personal computers.

This was going to be my srv2 example, but if you add autochoke to the master branch, then I'm going to include an autochoke section and use this example there instead. I'm still not sure how to incorporate the seam ripper into the tutorial. It's primarily useful when extending a partial result, so I might save it for after the partial result extension section.

Speaking of the tutorial, I was able to greatly reduce the length of the B0 section thanks to the improved ends detection. I also decided to move the tutorial to the tutorials section of the wiki, despite the "under construction" sections. The new link is here.
-Matthias Merzenich
User avatar
Katrina
Posts: 161
Joined: September 26th, 2024, 3:23 am

Re: amling search program principles discussion / brain dump

Post by Katrina »

Why does this not work? I am trying to extend a c/4 diagonal partial from ikpx2 (because it is being very slow)

Error:

Code: Select all

thread 'main' panicked at src/llsss/recentering/wao.rs:387:25:
assertion failed: already.is_none() || already == Some(key_tile)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Command:

Code: Select all

./rlife llsss-recentering-wao c4d-down golly.in 12 --rule 'B3/S23'
golly.in:

Code: Select all

| ...................................... | ...................................... | ...................................... | ...................................... | 
| ...................................... | ...........*.......................... | ..........**.......................... | ..........**.......................... | 
| ..........***......................... | ..........**.......................... | ..........*.*......................... | ...*.....**........................... | 
| ...**.....*........................... | ...**.....*.*......................... | ..***.....*........................... | ..****.....*.......................... | 
| ...*..*....*.......................... | ..**.*.*.............................. | ..*..**......*........................ | ..*..***.....**....................... | 
| ...*..*.*....**....................... | ...*..*......**....................... | ...*..**.....**....................... | .......*....*......................... | 
| ....**..*.....*....................... | ...*....*....**....................... | ..***..*.....**....................... | ..*.**................................ | 
| ...*.***.............................. | ...*...*.............................. | ...*..***..***........................ | ..***.*..*.*.......................... | 
| ...*.*.....*.......................... | ..**.*.*..***......................... | .......**.*.**........................ | ..........*.....*..................... | 
| ...*...*..**.**.*..................... | ..**...*..**.**.*..................... | .....*..**...*.***.................... | ...****...*.***.*..................... | 
| ...*****...*.**.***................... | ...***...*.*....**.................... | ..***.*..*............................ | ..**..*..**.*....*.................... | 
| .......***...*.*...................... | .......*.**.**.***.................... | ...*.*...*..****.*.................... | ..**.*..***..*........................ | 
| ...***...*....*....................... | ....*....*..*.*....................... | .........*....***..................... | ...........**......................... | 
| ............**........................ | ....*....*..**........................ | ........***.*.**...................... | ........***.....*..................... | 
| .........****...*..................... | .........*....*.*..................... | ..............*....................... | .........*....**...................... | 
| .........***..***..................... | ..............*.*..................... | .............*........................ | ............**........................ | 
| ..........*.***....................... | ............*......................... | ...........*.*.*...................... | .........***.*........................ | 
| .........*....*....................... | .........**.*..*...................... | ........***.*.*....................... | ........***.*......................... | 
| .........*...**....................... | ........**..***....................... | ........*...*.****.................... | ........*.**..*.**.................... | 
| .........*.*.*...**................... | ..........*..*..***................... | .........*......*.*................... | ............*.*.*.*................... | 
| .............*.*.*.................... | .............*...**................... | ............**....*...*............... | ............**.......**............... | 
| .............*.*......**.............. | .............*.*.....***.............. | ............**..*....**............... | ..............*.*.*..*.*.............. | 
| ..............**.*...**............... | .............*...**..*................ | .............*..***..*.*.............. | ...............***...*................ | 
| ..............****.*..*............... | ..............*..*.....*.............. | .............**....................... | ............**....*...*............... | 
| ...................*.*.*.............. | .............*..**...*.*...*.......... | .............*.***...*.....*.......... | .................*..**....*........... | 
| .............**...****..*.***......... | .............**......****.*.*......... | ............****.*..**..**.*.......... | ............*....*..***.**.**......... | 
| .............**...***...*.***......... | ............*..*.*...*..*............. | .............*.**....*..*..*.......... | ............**....*..**............... | 
| .............**...**.....***.......... | ...............*........*...*......... | ................*.***..***............ | ..............*...*.***..*............ | 
| ..............*....*....*............. | ..................***...*............. | ..............*.***.*..**............. | ................*.*.***............... | 
| ..............**.....*...*............ | ..............***.*.*...**...*........ | ..............*.*.....*..*..**........ | .............**.*.....**.*..**........ | 
| ................**.*....*...***....... | ...............**.**.****...**........ | ..............*.*.****...*..*.*....... | .................*.***.....**......... | 
| ...................**.**....*......... | ......................**....*.*....... | ............................*......... | ...................**........*........ | 
| ...................**.*......*........ | ......................**.............. | ........................*............. | .......................**............. | 
| ....................*.....*........... | .......................*.............. | .....................*.**............. | ....................******............ | 
| ....................****..*........... | ...................**.*..**........... | ...................**.*..*............ | ...................**....*............ | 
| ....................*.....**.......... | ...................*...**...*......... | ...................*..***.*.*......... | ...................*..*.*..*.......... | 
| ....................**..****.*........ | ....................**..*..**......... | ....................*...*...*......... | ........................*..*.*........ | 
| ........................*............. | ........................*.*.*.*....... | .........................*....*....... | .............................*........ | 
| .............................*.*...... | ............................***....... | ..............................*....... | ...............................*...... | 
| ............................**........ | ............................**........ | ...........................*....*..... | ........................*.***....*.... | 
| ........................**.*..*..*.... | ........................**..*.****.... | .......................***.**....**... | .......................***.***...**... | 
| ........................*.....**.***.. | .......................**..*..**.**... | .......................*..*..**...*... | .......................*..**..***..*.. | 
| ........................*.**....*..... | .........................*......*..*.. | ........................*....**.***... | ............................*.**.**... | 
| .............................*.*..*... | ............................*.*....... | ............................*......... | ............................*.**.*.... | 
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sokwe wrote: February 16th, 2025, 6:59 am
amling wrote: February 15th, 2025, 2:09 am I think for the purposes of desperate searches running out of memory and just wishing they could squeeze a little more out it's probably fine.
This is probably a useless nitpick, but that's not generally how I view this feature. Consider for example a 2c/2 side-to-side search in B2357/S3678. If I run a WAO search with mid_steps 25 it finishes quickly with no solutions. If I try again with mid_steps 26 it quickly finds a wide wing that then starts to shrink in width, causing a combinatorial explosion that slows the search. I wouldn't say I'm "desperate" In this case. I'm fairly confident I could find a complete spaceship by taking some partial results and continuing them at lower widths looking for a symmetric completion, but this is tedious and tends to give larger-than-necessary results. Instead, I can run the mid_steps 26 search with autochoke at a mere 10MB and quickly find an odd-glide-symmetric solution at w_pos 53:

Code: Select all

x = 27, y = 103, rule = B2357/S3678
17bo$15bo4bo2bo$14bob8o$13bo3bo4b3o$11bob3o4bo$10b2o4bo3b5o$10b2ob4obo
3b2o$8bo3b2obo2bo4bo$6bo2b3o2b5ob4obo$5bo7b11o$2bo2bob3obob2obo2bob3o$
ob5o2bo4b2ob2ob4o$o3b6obo2bo2b4o2bobo$bo3bob2obo4bo3b5o$b2o2bo5bo7b5o$
2b4obo3b2obob8o$2bobobo3b3o2bo4b4obo$bob2o2bo2b2o2bo5bob2o$bobo2b11o2b
3obo$bo3b4o2bo2b2o2b6o$2bob2obobo2b3obobob4obo$4bo3b2ob5o3b5o$4bob3o5b
10o$6b3o2b3o4bob4o$2bo5b2ob2o2b9obo$2bobob4o6b8o$4bobobo7b8o$4bo2b4obo
bobob6o$4bob2o6bob2ob5obo$6bo2b7o3b5o$6bo2b3obobobo3b3o$5bobo3b2ob3o4b
3o$5bobo3bo2b10obo$5bob2o2bo2b2o3b5o$5bo2bo2bo3bo3b5o$5bobo2bo5b8o$6b
3o3bobo2b7obo$7bo5b4ob2ob3o$8b2obobo3bobob3o$8b3o5b8o$7bobo3bob9obo$6b
o2b6ob2obob3o$6bobob2o2b3ob2ob3o$6bobob3ob2ob7o$6bo2bo3b11obo$6bo2bo3b
ob9o$6bobo2bo2b10o$6bobo2b13o$8bob2obob9obo$10bobob10o$12b3o2b7o$12b
12o$14b10obo$10bobo4b7o$8bo2bo3b9o$6bobo6b9o$6bobob2ob11obo$6bo2bobob
11o$6bo2b2obo2b9o$6bobobo2b11o$6bobo2b2o3bo2bob3obo$6bo9b4ob3o$7bobo4b
o2b7o$8bo3b5ob6o$8bo4bo3bobob3obo$7bob4o3b4ob3o$6bo2b2obo2b9o$5bobo2bo
b6ob5o$5bobob3obob2ob6obo$5bob5ob2o2b7o$5bo2bo2b2o3bob2ob3o$5bobob3o4b
3ob4o$6b8obobob5obo$7bob2o6b2ob4o$4bo2bob4o4b7o$4bobo3bobobobob6o$6b4o
b2obo3b6obo$2bo8b3o3b7o$2bobobob2o2bob2o2b6o$4bob3o2b2obobob2ob3o$4bo
2b2o2bo5b2ob4obo$5b2obob2o2b10o$2bob2obo2bo3b2o2b6o$bo2bo2b5o2b3o2b5o$
bobo4bo9b2ob3obo$bobobo4b3obob2o4b2o$2bobob5obo2b6ob2o$14bobo2bob3o$b
2o2b19obo$b4o6b3obob7o$o2bo2b2o6b2o2bob4o$o5b2obob3o9bo$2bo2bobobobobo
b2o4b3obo$5bo2bo2b2o2b4o2b3o$6bob2o4b5o4bo$8bo2b2o2b2o2bobo$10b2ob2o2b
o2b2o$10bo2bo3b2obo$11bo3bob2obob2o2bo$13b3o2bo3bo$14bob6o$15bo5bo3bo$
17bo!
I suspect an ordinary search would run out of memory before even reaching w_pos 53 on most personal computers.
Perhaps "desperate" was too strong. I think the core reasoning of "this search could not otherwise run at all" making weirdly different semantics about distance measurements acceptable is hopefully still true.

I started running that search (mid_steps=26) out of curiosity and it's not looking good, having crossed 32 GB (and climbing very rapidly) just in the middle of w_pos 50. I may or may not edit in a note here when it finishes one way or the other. EDIT: Did not even complete w_pos 50[1] before hitting 60 GB limit.

This makes me wonder where I can/should be using this. All my attempts and tests so far have ended in weird bad pyramids getting wider and wider at the bottom like:

Code: Select all

x = 506, y = 121, rule = B2/SHistory
F.98B.F.98B.F.98B.F.98B.F.98B.F$F.98B.F.98B.F.98B.F.98B.F.98B.F$F.98B
.F.98B.F.98B.F.98B.F.78BA19B.F$F.80BA17B.F.98B.F.98B.F.77BABA18B.F.
76BABA19B.F$F.76BA21B.F.77BA3BA16B.F.76BABABA17B.F.75BA22B.F.74BA2B2A
BA17B.F$F.74BABA5BA15B.F.77BA3BABA14B.F.75BA2BA5BA13B.F.74BABA4BA16B.
F.73BA3BAB2A3BA13B.F$F.75BA6BA3BA11B.F.74BABA3BA2BA3BA10B.F.73BA5BABA
16B.F.74BA3BABAB3A13B.F.77BA7BA12B.F$F.80B2A5BA10B.F.74BAB2ABA4B3A11B
.F.83BA14B.F.73B2A4BABA2BA13B.F.76BA8BA12B.F$F.74BABABA3B3A13B.F.73BA
5BA6B3A9B.F.74BA5BA2BA14B.F.76B4A18B.F.72BABA6B2AB2A12B.F$F.74BA2BA3B
A5BA10B.F.76BA7B3A11B.F.73B3AB2A4BA14B.F.72BA3BA5BABA13B.F.75BA4BA2BA
14B.F$F.73BA4B3A5BA11B.F.74BA2BA6B2ABA10B.F.72BA5BA19B.F.79BA18B.F.
73BABAB2A4BA14B.F$F.81BABABA12B.F.72B3A2BA4BABABA11B.F.75BA11BA10B.F.
74BA3BA19B.F.79BA18B.F$F.73BA4BA19B.F.77BA3B2ABA13B.F.75B2ABABA17B.F.
98B.F.73B3A22B.F$F.78B3A17B.F.73B2A6BABA14B.F.75BAB2A19B.F.74BA23B.F.
75B2ABA3BA15B.F$F.74BA3BA3BABA13B.F.75BABA2B2ABA14B.F.85BA12B.F.76B3A
2BABA2BA11B.F.75BA6BA4BA10B.F$F.75BA11BA10B.F.74BABAB2A4BABA11B.F.81B
3ABA12B.F.87BA10B.F.76BAB5A3BA11B.F$F.76BABA5BABA11B.F.75BA22B.F.74BA
9BAB2A10B.F.80BA17B.F.79BABA4B3A9B.F$F.77BA8BA11B.F.76BABA3BABA2BA10B
.F.77BA3BABA14B.F.78BA3BA4BA10B.F.77BABA18B.F$F.82B2A5BA8B.F.74B2A5BA
16B.F.78BA6BA12B.F.77BA4BABA13B.F.81BA3B2A11B.F$F.74B2AB2A2BA16B.F.
76BA2B2A2B2A13B.F.73BA24B.F.78B2A3BABA12B.F.73B2A2BA20B.F$F.79BA5BA
12B.F.73BA7BA16B.F.79BA3B2A13B.F.73B2A5B3A15B.F.78BA6BA12B.F$F.73BA2B
3ABA17B.F.68BA12BA16B.F.67BA6BA5BABA15B.F.68BA15BA13B.F.67BA4BA2BA3BA
18B.F$F.67BABA4B2A3BABA16B.F.66BA5B2A24B.F.68BA11B2A16B.F.67BA4BABA4B
A2BA15B.F.66BA2BA3BA7BA16B.F$F.66BA2BABA26B.F.67BA8BA3BA17B.F.72B2A
24B.F.67B2A13BA15B.F.66BA4B3A4B3A17B.F$F.69BA5BA22B.F.65B2A31B.F.64BA
2BA10BAB2A16B.F.71BA7BA2BA15B.F.66BA2B2ABA8BABA14B.F$F.66BABA10BA5BA
12B.F.65BA8BAB3ABA17B.F.72BA8BA16B.F.67B2A2BA26B.F.70BABA8B3A14B.F$F.
66B3A5BABABA2BA16B.F.65BA3BA2B2ABABABA2BA15B.F.68BA2BA8BA2BA14B.F.82B
A15B.F.66BA4BA3B3A5BA14B.F$F.71BABA7BA16B.F.65BA3B2A4BAB2A3BA15B.F.
72B2A5B2A17B.F.67B4A3BAB2A6BA13B.F.81B3A14B.F$F.66B3A2BABA5B2A4BA12B.
F.65BA3B2A10BA2BA13B.F.68BA2BA3BAB2ABA4BA12B.F.73B2A6BA16B.F.66BA3BAB
A3BA2B2A17B.F$F.64BA3BA5BA3B2A4BA13B.F.65B2A6BABA5BABABA12B.F.63BA5B
2A5BA21B.F.67B2A4BA4B2A18B.F.63B4A5BA4BA2BA17B.F$F.68BAB2A3BA6BA15B.F
.63B2A9BA2BA2B2ABA14B.F.66BA5B2AB2A21B.F.62BAB2A11BA20B.F.69BA2BAB2A
3BA18B.F$F.63BA3BABA8BA2BA16B.F.71BA10BA15B.F.62BABA5BA2BA6BA2BA14B.F
.63BABAB2A2BA3B2A21B.F.62BA6B2ABABA2BA20B.F$F.69BA28B.F.62BA4BA3B2A
25B.F.68B2A28B.F.64BA2BA2BABA2BA22B.F.73B2A2BA20B.F$F.63B2A3BA2B2A25B
.F.69B2A27B.F.61B3A3BA5B2ABA21B.F.64BABA2BA2BA4BA20B.F.63BA3B2A4BA2BA
BA19B.F$F.65B3A8BA21B.F.62BA5BA2BABABABA20B.F.63BA3BA4BABABA21B.F.61B
A9BA6BA19B.F.64BABAB2A3BA3BA20B.F$F.62BA3BA6BA2BA21B.F.64BA3BA29B.F.
63BA3BA2BA4BAB2A19B.F.65BA3BABABA24B.F.61B2A4B2A5BA2B3A18B.F$F.65B3A
8BA21B.F.69BA3B2A2BA20B.F.63B3A2BA6B2A21B.F.62BA3B2A2B2ABA4BA19B.F.
63BA10BA2BA20B.F$F.68B2A4BA5BA17B.F.64BA11BA21B.F.70BA2B2A23B.F.63BAB
5A6BA21B.F.62BA12BABA20B.F$F.64BA10BA22B.F.68B2A6BA21B.F.67BA30B.F.
64BABA3B5A23B.F.76B2A20B.F$F.75BA22B.F.60BA7B3A3BABA21B.F.59BA3BABA5B
A5BA20B.F.58BA5BABA9BA21B.F.59BA7BA2BA3BA2BA20B.F$F.59BABA5BAB2A27B.F
.60BABABABABA2BA26B.F.58BA16BA22B.F.60BA3BA11BA21B.F.58BA2BA4BABA4B2A
2BA20B.F$F.63BABA4BA8BA18B.F.58B2A2BA3BABA29B.F.60BA9B3A25B.F.59BA2BA
4B2A4B2A23B.F.60B2A2B3A8BA22B.F$F.59BA4BA5BA3BA23B.F.63BABA3BA2BA25B.
F.61B2A4B2AB2ABA24B.F.63BA2BA31B.F.59B4A7BA4BA22B.F$F.72B2A24B.F.59B
2A3B2A4BA3BA23B.F.61B2A3BA5BA25B.F.60BA7B3A3BA23B.F.62B2ABA5BABABA22B
.F$F.60BA4BA5BA5BA20B.F.61BA2BA5BA2BA4BA19B.F.58BA3BA9BA2BA22B.F.63BA
BABA3BA2BA23B.F.62BA9BA25B.F$F.62BA2BABA3BA4B2A20B.F.59B2A2BA4BABABA
2BA22B.F.65BABA6BA23B.F.57BA5BA2BA5BA3BA21B.F.56BA10BA3BABABA22B.F$F.
58BA2BA2BA2BA7BA2BA19B.F.57BAB2A2BABA2BA3BA25B.F.56BA4B2A10BA2BA21B.F
.55BA4BA2BABA32B.F.54BABA2BAB2A3BA9B2A20B.F$F.58BA2BA11BAB2A21B.F.56B
A2BA4BA3BA8BA20B.F.55BA5BABABA6B4A22B.F.54BA5BA16BA20B.F.55BA9B2A31B.
F$F.55BABA3B3A5BA28B.F.56BABABA7BA4BAB2A21B.F.55BA7B2A4BA7BA20B.F.60B
A4BA2BA29B.F.66B2ABA7B2A19B.F$F.69BABABA6BA17B.F.57BA5BA3BA6BA23B.F.
55BA5B2A5BA4BA2BA21B.F.60BA6BABA2BA2BABA20B.F.71BABA4BA19B.F$F.57BABA
BA5B4A2BA24B.F.56BABA3BA35B.F.55BA3BA3B2ABA6B2A23B.F.56BA3BA6BA4BA4BA
20B.F.55BABABABA8BA7BA19B.F$F.55BA5BA10B2A3BA20B.F.53BA2BABA6BA8BABA
21B.F.54BA7BABA10BABA20B.F.53BA2BA9B4A2BA25B.F.55BABA18B3A19B.F$F.53B
2A6BA3B2A3B3A3BA3BA17B.F.55BA4BABABA12BA20B.F.52BA3BA8BA2B2A3B4A21B.F
.72BA4BA20B.F.52B2ABA8B2A4BA2BA2BA21B.F$F.64BA7BA25B.F.52BABA3B3A2BA
4B2A3BA24B.F.53BABA8BA7BA25B.F.52BA3B2A5BABABA2BA5BA21B.F.53B3A6BA9B
2ABABA20B.F$F.52BA5B2A4B5A2BA26B.F.62BA9BA25B.F.54BA3BA4BA4B2A3BA24B.
F.53BABA6BAB3A4BA2BA23B.F.52BABA2B2A8B3A2BA2BA22B.F$F.62B3A2BA30B.F.
51B3A6B2A36B.F.62BA3B2A4B2A24B.F.59BA4B2A3BABA26B.F.53BABA6BA4B2A3BAB
2A22B.F$F.52BA4B2A2BA2BA33B.F.56BA9B2A5BA24B.F.50BA9BABA2BA6BABA23B.F
.54BA8BA4BA6BA22B.F.49BA2B2A5B2ABA3B2AB2A5BA21B.F$F.57BA8BA5BABA3BA
19B.F.49BA2BA9BA2BA5BA3BA22B.F.53BABA11BA4BABA23B.F.49B4A7BA2BA2BA9BA
21B.F.53B2ABA5BABA2BA7BABA20B.F$F.49B3A4BAB4A8BA2B2A23B.F.54BA43B.F.
50BA2BA7B2A7BABAB3A21B.F.51BA3B2A20BA20B.F.49BA7BA4B3A6B2AB3A21B.F$F.
51BABAB2A2BA11BA2BA23B.F.48B2A11BA8BABA2BA22B.F.47BA4B2ABA15BA4BA21B.
F.51BA4BA6BA6BAB3A23B.F.47BABA2BA4BA4BABA6BA4B3A19B.F$F.47BA6BA43B.F.
46BA3B3A3BA16B3A22B.F.55BA4B3A13BA21B.F.47B3A13BA13BA20B.F.46BA4B2A3B
3A3BABA6B2AB3A21B.F$F.46BA3BA3BA7BA11BA23B.F.47BA7BA5BA7B2A2BA24B.F.
48BABAB3ABA5BA12BA22B.F.47BA3BA5BABA16BA21B.F.46BA2BA13B2A6BA5BA20B.F
$F.51B3A6BA5BA2B2A3B2A22B.F.45B3A6BA8BA9BA24B.F.48BA7BA3B3A2BA2BA2BA
26B.F.51B2A5BA5BA5BABA25B.F.46B3A8BABA3BA4B2ABA26B.F$F.46BA4BA5BA3BAB
A34B.F.56BA3BA3B2A3B2A2BABA22B.F.48BA6BA2B2A3BA7BA26B.F.47BA2BA13B5A
29B.F.48B2A3BA3B3A9BABA26B.F$F.51BABABA6BABA8BA24B.F.46B2A2BA6B2A13BA
25B.F.49BABA4BA3BA5BA2B3A26B.F.48BA3BA5BA4B3ABA30B.F.47BA2BA2BA3BA3B
2A35B.F$F.47BA4B2ABABA2B2A7BA2BA25B.F.50BA7B2A5BA7BA24B.F.45BA5BA4BA
7BA2BABA2BA25B.F.49BA2BA4BAB3A3B2A6BA24B.F.47BA2BA17BABA3BA23B.F$F.
50BA2B2A4BA2B3A33B.F.46BAB2A6BABA6BAB3A28B.F.50BA4BA4BA13BA23B.F.44BA
3BA2BA2BA4BA2B2A2B2A2B4A24B.F.45BABA4BA3B2A6BA4BA28B.F$F.45BA3BABA2BA
6B3A2BABA29B.F.44BABA9BA3BA4BA6B2A24B.F.43BA4B2A5BA3BAB2A4BA3BA26B.F.
42BABA2BA2BA3BABA9BA3BAB3A23B.F.41BA3BA5BABA4B3AB2ABA2B2A28B.F$F.45BA
2B4A3B2A10BA4B2A24B.F.44BABA14BABA5BABA26B.F.43BA3BA12BA4BA4BA2BA24B.
F.42BA6BA9BA7BA30B.F.48BABA4BA4B2A3BA5B2A2BA22B.F$F.50BAB2ABA11B2A2BA
26B.F.62B3A33B.F.45BABA13BA4BA4BA26B.F.42BA17BABA2BA8BA23B.F.59BA3BA
4BA29B.F$F.49BA2BA2B3A4B2ABA6BA3BA21B.F.48BA15BAB5A27B.F.42BABA2BABA
12BA8B3A24B.F.41BABA11BA5BABAB3A30B.F.49B2A2BA2BA16B2A23B.F$F.49BA8B
4A8BA27B.F.42B3A3BA3BA2BA8BA7B2A24B.F.41BA3BA8BABA6BA2BA4BA26B.F.42BA
5BAB4ABA5BA2B2ABABA3BA24B.F.40BA2BA3BA9BA2BA9BA27B.F$F.42B2ABA4B2A5BA
2BABA9BA25B.F.41BA4BABA6BA13BA28B.F.44B2A5B2A8BA3BA2BAB2A26B.F.40BA5B
A3BA3BAB2A4BA4BABA28B.F.41BA3BABA12BA11B2A24B.F$F.40BA2BABA3BA4BAB2A
12B2A3BA22B.F.47B2A2BA3BA5B4A4BA2BA25B.F.40BAB2A6BAB2A2BA8BA5BA26B.F.
45BA11B2A2BA2BABA2BA2BA25B.F.39BA6BA6B3A4BA2BA6BA2BA24B.F$F.41BA4BABA
8BA5BABA4BA27B.F.39BA3B3ABABA3B2A7BABA4BA2BABA23B.F.42BA8BA6B3A14BA
22B.F.38BA14BA3BA3BA4B3A5BA23B.F.56BA3BA2BA6BA2BABA22B.F$F.40B3A11BA
4BA2BA10BA24B.F.43BABAB2A2BA3B4ABA3BABA2B4A2BA22B.F.38B3A8B2A8BABA5B
2A5BA23B.F.41BA6BA3B3A7BA6BA5BA22B.F.40BABA14B2A4BABA4BA3BA23B.F$F.
44BA4B3A4BA4B2A4BA2BA2B2ABA21B.F.39BA3BA8BA4BA8BA4BA26B.F.48BABA2B2A
4BA3BA4BA29B.F.41BA16BA3BA3BA2BA28B.F.42BA2BA2B2ABA3BA4BA2BA3BA3BA26B
.F$F.40B2A11B2A3B3ABA3BA4BAB3A22B.F.43B2ABA4B2A2BABA6B2A2BABA27B.F.
39BABA3BA4BA15BA4BA26B.F.40BA3BABABA2BABA2BAB3A6BA2BABA25B.F.39BA2BA
7BABAB2A5BA3BA7BA24B.F$F.44BAB4A10BA2BABABA7BA22B.F.40B2ABA6BAB3A3BA
9BA29B.F.45BA3BA5B2A2BA11BA26B.F.39BA2BABA2B2ABA3BA10BABA2BABA25B.F.
40B2A4BA5B2AB2A3BA12BA24B.F$F.44BABA4BA8BAB2A4BA4BABA22B.F.43BA5BA2BA
5BA6BABA4BA3BA21B.F.40B2A4B2A6BA9BA3BA6BA22B.F.44BA3B3A6B2A10BA28B.F.
38B3ABA2BA5BA2BA4BA3BAB3A30B.F$F.51BA5BABA5BA7BA24B.F.45BAB3A8BA4BA2B
A8BA22B.F.44BABA3BA6BA11BAB4A23B.F.39BA3BA4B2A5B2ABA4B2A3BABA4BA22B.F
.40BABAB2A5BA7BA6BA4BA26B.F$F.38BA9B2ABABA7BA3BA7B2A23B.F.39BA19BA4BA
BAB2A2BA2BA22B.F.40BA3B2A3BA3B2A2BA5BA34B.F.41BA4BA3BA13B3AB2ABA26B.F
.37BA4BA4B2A8BA14BABA23B.F$F.39BA19BA8B2A4BA23B.F.40BA4BABA5B2A3BA16B
A22B.F.41BA2BA12BA2BA4B2A2BA4BABA21B.F.36BAB2A13BABA8BA8BA24B.F.35BAB
A6BABA7BA13B4A26B.F$F.39BA4BABA2BA3BA5BA38B.F.40BA2BA3B2A9BABA6BA30B.
F.36B3A2B2A12BABA15BABA22B.F.35BA3BA4B2A13BA3B4A5BA3BA21B.F.36BA15B2A
B2ABA14B3A22B.F$F.35BA2BA5BA2BA2B3A15BA8BA20B.F.36B2ABA3BA4B2A4BA18B
2A23B.F.35BA4BABABA5BA8BAB3A8BA25B.F.38B2A13BABA2BA16BA22B.F.34BA8BAB
A3B2A6BA4BA4BA3BA4BA21B.F$F.36BA8BA8BA18B2A23B.F.34BA2BA11BA12B2A8BA
25B.F.51B3ABA4BA13BA23B.F.34BAB3ABA2BA5B2A3BA3BA4B4A3BA27B.F.51BA3BAB
A40B.F$F.34BA10BA4BA2B3A6B2A3B2ABA2BA24B.F.35BA15B2A3BA3B2A7BA28B.F.
33BA3B2ABA7BA10BA5B2A3B4A24B.F.36BA2BA11BABA6BA37B.F.32BA19BABA2BA3BA
5BAB3A26B.F$F.40BA4B2A5BABABA2BABA11BA24B.F.34B3A2BABA7B3A8BA2B2AB4A
2BA25B.F.37BA17B2A16BA24B.F.32B3A4BA8B3A7B3A3B3A3BA3BA23B.F.35BA2BABA
3B2A15BABA5BA3BA24B.F$F.35BABA2BA3BA4BA3BABA9BA9BA22B.F.38B2ABABA2BA
9BABA2BA4BA3B3A3BA21B.F.33BA3BA11BABA7BA3BA13BA20B.F.44B2A4BABAB5A5B
3ABA5B2A22B.F.35BA7BA2B3A4BA7BABA7BABA24B.F$F.37BA5BA9BA5B2A6BA2B2A3B
A22B.F.34B2A6BA12B2A4BA3BA3BA2BA4BA20B.F.37BA6B2A7BA4BA5BAB3A6B2A21B.
F.33BABA7BA2BA9BA3BA8B2A27B.F.34BA5B2A5BA4BA5B2A3BA2B3A7BA21B.F$F.34B
A2BA5BA8BA2BA6BA3BA3BA2BA2BABA19B.F.38BA2BA2BA8B2A3BAB2ABA4BA3BABA23B
.F.34B2ABABA2BA2BA2B4A4B2ABA4BA4BABA5B2A19B.F.40B2ABA2BA5BA2BA7BA6BAB
AB2A3BA18B.F.33BA2BA14BA2BA4B2A3BA3BA7BA21B.F$F.35B2A3BABA15BA5BAB2A
2BA5BA21B.F.38BA5BA3B2AB3A7B2A15BA19B.F.37BA3BA14B2A7BA2BA4BA3BABA18B
.F.34B2A7BABABA3BA3BA3BA4BA2BA2BABA3BA21B.F.39BA12BABABA21BA19B.F$F.
33B2AB2A3BABA4B2A2BA9BA7BA5B2A20B.F.39B2A3BA5BA3B2ABABABABAB3A10BA19B
.F.41BABABABA10BA9BA29B.F.40BA23B4ABA2B3A4B2A17B.F.33BABA5BABA3B2A11B
A9BA5BA21B.F$F.35BAB2A4BA7B4ABA3BA9BABA3BA2BA18B.F.33BA5BABA5BABA5BA
7BA5BA5BA2BA19B.F.34BA10B2A3BA6B2ABA4BA5BA2BA4BA18B.F.33BA7BABA3BA13B
A2BA2BA5BABA22B.F.36BAB2A8B2ABA7BA10BA5B2A3BA16B.F$F.35B2ABA3B2A3BA3B
ABA7B2A35B.F.34BA4BA6BABA6B2A6BA4B4A3B2A21B.F.32BA5BA3BA19BA2B2A7BA
23B.F.31BABABABABA3B4A2B3A4BA2B2A3BA6B2A4B4A17B.F.30BA9BA6B2A3BA9BA4B
A2BA4B2A21B.F$F.37BA5BA3BA3B2A4B3A4BA2BABA5BA22B.F.32BAB2A4B2A2BABABA
5BA5BA4B2ABABA7B2A18B.F.31BA4BA2BA3BA5BA2BA4BA3BA10BA2B3A2BA17B.F.30B
A2BABA2BA14BA8BA2B2A4BA2BA3B2A18B.F.37BA3B2A4B2A7B2A5BA3BA2BA4BA22B.F
$F.31BABA3BAB2A9BA3BA7BA2BA4BA7B2A18B.F.30BA4BA5B2A3B2A4B2A3BA3BAB2A
2B3ABA8BA17B.F.29BA2BA3BA6B2A9BA17BA5BA19B.F.28BABA2BA5B2ABA2BA2BAB3A
4BAB2A4B2A7BA23B.F.31B2A2BA2BA2BA4B2A6BABA4BA2BA2BA4BA2BABABA18B.F$F.
31BA2B2AB2A2BA4BA12B2A5BA5BA6BA18B.F.30BA2BA11BABA13BAB2A2BAB3A26B.F.
28BA3BA2B2A3BA3BA3BABA2BA4B2A5B2A5BA2BA3B3A16B.F.34BA12BABAB2ABA2BA
15BA3BA20B.F.29BA3BA8B2A2BA9BA2B4A3B2A7B2A21B.F$F.37BAB2A5BA17BABA2BA
5BA5BA16B.F.27BAB3A3BA5BA3BA4B2A7B2A2BA10BABA2BA2BA15B.F.26BABA3BABAB
A7BA2BA4BA5BA12BA6BA19B.F.40BABA6BABABA8B3A3BA6BA5BA16B.F.30BA2B3A3BA
BA15B2A2BA15B2ABA17B.F$F.27B3A2B2A3BABA7B4ABA11BAB3A6BA4BABA15B.F.26B
A3BA5BA9BA4BA7B2A8BA6BABA19B.F.27B2A3BA2BABA3B2A2BABA9BA4B2A2B3A4B2A
4BA18B.F.25BA3BABA2BA3BA13B2A4BA2BA13BABA2BA17B.F.26B2A2BA4BA3B2ABA4B
AB3A2BABA7BA9BA6BA16B.F$F.26BA2BA8BA10BA6BA2B2A2BA10BA3B4A16B.F.30B2A
5BA4BA4BA3BA5B2A2BA2B3ABA4BA2BA21B.F.25BA10BABA4BA2BA2BA3BA8BA4BAB2AB
A2BA2B2A18B.F.27B2A6BA5BA5B2A7B2A18BA21B.F.26BA2B2A3BAB2A14B2A6B2A11B
A24B.F$F.23BA8BA7B3A14BA2BA12BABA5BA16B.F.24BA5BA7BA4BA4B2A2B2A7BA9BA
6BA3BA15B.F.23BABA11BA6BA12BABA2BA5B3ABA2BA3BABA16B.F.22BA13BA21BABA
12B2ABA21B.F.21BABA2BA2BA5BABA11BA5BA3BA12BA6BA18B.F$F.20BA4B2AB2A5BA
3BAB2A6BABAB3AB2A12B2ABA23B.F.19BA4BA2BA2B3A10BA4BABABA6BA5BABA2BA5B
2A2BA17B.F.20BA2BABA3BA8B2A4BA16B2A5BA2BA26B.F.19BA2BA4BA2BA6BA7BAB2A
7BA6BA3BA4BAB2A2BABA17B.F.18BAB2ABA12BA3B2A2BA4BA7B2AB3A3BA2BABA4BA
21B.F$F.18BA11BA2B2A5BA7BA8BA6BABABA2BABA2BABA2B2A2BA12B.F.20BA14BA3B
A2BA3BA2BABABABA5BA5BA11B2A17B.F.18BA5B3AB2A13BA3B2A7BABABA8BA5BABA
20B.F.19BA20B2A3BA4BA8BA2BA4B2ABA7BA19B.F.17BA2BAB2A6B3AB2ABABA2B2A3B
3A13BA2BA9BA4B4A13B.F$F.19BA6B3A17B2A3BA6B4A3BA3B3ABA2BABA2BA16B.F.
18BA6BA3BA3B2A18BA3BA9B2A6BA3B2A17B.F.24BA3BABA6B2A2B2A2BAB3ABA3B2A9B
A10BA3BA16B.F.17B2A4BA7BABAB2A3BA2B2A8BA16BA3B2A2BA3B2ABA12B.F.22BABA
B2A4BABA2BABA5BA19BA2BA4BA6BA3BABA11B.F$F.26BA16BA3BA4B2A5B2A4BA5B3A
24B.F.20B2A2BA4BA6B2A4BABA3BA2BA2BA13B2A6B2ABA6BA11B.F.17BA7BA4BA2B3A
2B2A7BABA2B2AB4A12BA3BA7B3A12B.F.18BA4BA2B2A8BA4B2A22B2A5BA5BAB3A3BA
11B.F.31BAB2A2BABA4BA3B4ABA4B2A7B2AB2A13BA12B.F$F.21B4ABA2BA6B2A3BA2B
ABA6BA7B5ABA6B2A4B3A2BABA10B.F.10BA7B3A7BA9BABAB2A4BA6BA2BA10B3A7BA3B
2A13B.F.11BA4B2A5BA2BA3BA3BA4BA10BA3BA10BA6BA3B2A2BA4BA12B.F.12BA5BA
3BAB2A6BA7BA7B2AB2A5B2A8B2A4BA3BA4BA14B.F.11BA4BA2BABA5BA5BA8BA7BA9BA
B2A6B2ABA6BA17B.F$F.9BABA2BA3B2A7BA4BA6BA5BABA6B2A2BA9B2A10BA3BABA11B
.F.8BABA4BABA2BA3B3ABA2BA2B2A5BABA4B2A11BA3B3A5BA24B.F.7BA4BA9BA6B2AB
A11BA9B2A4BA7B2AB2ABAB2A7BA12B.F.6BA3BA5B2A3BA11BA11BA15BAB3ABA2BA7BA
19B.F.7BABA2B2A4BABA6B4A13BAB2A5BA4B3ABA16BA3B2A13B.F$F.7BA8BA5BA9B3A
2BA2BA3BA4B4A21BA4BA3BA2BA11B.F.8B2A2B3A2B5AB2A2BA3BA3B2AB2A8BA6BAB3A
6BA8BAB2AB3ABA2BA10B.F.6BA4BA10BA20B2A2BA6BA7BABA3BA4BA11B2A11B.F.7BA
2BA2BA7BA2B2AB2AB2A13BA2B2AB2A14BA9BA6BA3BA9B.F.6BABA2BA4B2A8BA5BA3B
4A6B2A2BA9BAB2ABA2BAB3A3BA2BA3BABA12B.F$F.10B2A2BA6BA2B3A9BA8BA4BA2BA
4BA6BAB2A7BABA3BA15B.F.6B4A5BA11BA3BA5BA2B2A2BA9BA2BABA3BA5BA4BA2BABA
3BABA12B.F.10BABA10B2ABABA6BA13B3ABA8BA7BA4BA11B2A9B.F.9BA11BA7BA6B2A
B6A3BA6BA3BA11BABA3B2A5BA13B.F.18B2A3B2A6BA3BA9BABA2B2A6BABA5BA3BA5BA
2B3ABA14B.F$F.6BA2BAB3A8B2A2BA4BAB3A5BA11BA4BA4B4ABA6BA10B2A10B.F.16B
A4BA8BABA4BA12B2A2BA6BA9BA6BA6BA2BA9B.F.10BA6BA2BA2B2A2B2A7BABAB2A10B
A2BA2BABABA7BA3B4ABA3BA2BA11B.F.9BA8B2A2BA3BA2BA5BABA4BA10B2A4BA7B2A
2BA8B2A3BA12B.F.6B2A3BA5BA2B2A8BA3BA4BA7B2A3BA5BA11BA2B2A2B2A5BA2BA
10B.F$F.10B2AB3ABA8BA3BA5BA7B3A4BA6BA2B2A4B2ABABA3B2A8B2A10B.F.7BABA
6BA4B3ABABA3BA15BA5BA21BA8BA13B.F.19BA4BA14B2ABA5B2A12BA4B2A9BA2B3ABA
2B2A8B.F.6B2A2B2A6BA8B2A6BABA5BA3BA5B4A3BA2BA10BA5BA5B2A10B.F.8B2A3B
2A2BA3B3ABA4BA11BABA3BA12BA2BABA11BA3BA2BA4BA7B.F$F.5B2A5B2A6BA12B2A
12BA4BA5BAB2A8BA9BA3B2A2BA9B.F.4BA3B3A4BAB3A6B2AB3A3BAB2AB3A5BA2BABA
9BA3B2A7B2A3B2A6BA8B.F.3BA2B2A3BA2BA5B2AB2A9BA4BA3BA3BA6BA2B3A9B3A6BA
4BA14B.F.2BA9B2ABA6BA2BA2B2A3BA3BA6BA4BA3BA6BA3BA2BA9BABABA6B3A7B.F.
3BABA2B3A6B2A5BA5B3A10BA3B2ABA6BABA2B2AB2ABA5B3A9BA11B.F$F.3BA3B2A3BA
4BA2B2A5BA2BA7B3AB2A2B2A6BA2BA4BA19B2A2BABA9B.F.4B2A3B2A3BA3BA7BA5BA
2BA8BA11BAB2A9BAB4A4BABA16B.F.2BA10BA2BA3BA7B2A3BA3B2A3B2A8BA7BAB3A5B
A4BA15BA6B.F.3BA2BABA6BABA7BA4BABAB3A2BA5B2A4BA3B2A4BA3BA2BA3BABA2B3A
10BABA5B.F.2BA2BA6B2A4BA2B4A2BA9B2ABA3BA2BA2BABABA2B3A3B2AB2A3BA4BA4B
A5BA10B.F$F.7BABAB2A2BABA2BA6BAB3A2BA7B2A3BA6BABA4BA7BABAB2A3BA10BA8B
.F.2B3A5BA3BA4BA2BA3BA6BABA4BA16BA2BA2BA4BA8BA4B7AB2A6B.F.8BA4BA3BA2B
2ABABA5BA4BA7B2A6BA3BA7BA2BA2B2A3B2A2BA9BA2BA5B.F.6B2A8BA2BA2BA4BA2BA
2BABA5BA4BA10BABAB2A9BA5BABA7BA9B.F.3B2A10BA8B2A2BA3BA6BA2BA12BA7BA7B
A2BA12BA2BA2BA4B.F$F.3BA2BA5BABA2BA4BA11BA2B2A3BABAB3A3BA7BA2BA5BABA
6B2A5BA4BABA5B.F.4BA3BABA4BA2BA2BABA3BA3BA13BA5BABA7B2ABA3BA4B2A2BA2B
A6BA5BA4B.F.5BABA3BABA10BA3BA4BABABA3BA2BABA5BA5BA6BABABA2BA2BA3BA9B
2A7B.F.4BABABABA7BA6BA3BA4BA5BABA4BA11BA2BA10BA14BA2BABA4B.F.11BA3BA
7B2ABA4B2A2BA3BA6BA7BA2BA6B3ABA3BAB2ABABAB4A2BA2BA7B.F$F.4BABA6BA9BA
4BA5BA6B2A8BA4B2A6BA6BA9BA4B2AB2A2BA4B.F.3BA3BA6BAB3A2BA2BAB2A4BA2BAB
4A4BA13B2A4BA7BA2B3A3BA2BA6BA5B.F.4BA6BABA5B2A2BA6B2A4BA4BA2BABA4BABA
4BA3B2A2BA5BA2BA3BABA2BA9BA3B.F.8BABA3BA3BA5BA4BA2BA7BA9BA3B3A7B2ABAB
A4BABA5B2ABA3BA2B2ABA2B.F.5BA7BABA3BA2BA15BA3B2A5BABA16BABA6BA6BA6BA
6B.F$F.5BA4BABA4BA3BA3BABA4B2A6BA6BA5B3AB2A2B4A8B4A3BABA6B2A7B.F.9BAB
A2BABA9BA2BA8B2A2BA9BA6BA5BA19BA8BA3B.F.3B2AB2A10BA16B2A6BABABA3BA3B
2ABA10BAB2A6BA3BA2BA4B2A2BA2B.F.12BA3BA4BAB2A4B2ABA5B3ABA7BA13BABA3BA
3BA3BA2B2A6BA4BA3B.F.3BA5B2A2B2A3B2A6BABA14B3A5BA2BABA3B2ABA3B3ABA5BA
BA6B2A2BA4BA2B.F$F.5B2ABA4BA2BA5B2A4BA6B4A19BA4BA9BA12BA3BA4BA2B.F.4B
A2BABA4BA14B3AB2A7BA3B2A3BA3B2A8BA3B3A5BABA4BA3BA2BA2BA3B.F.16B2A3BAB
A4BA3BA5B2A12BABA2B3A3BA3B2A4BA6BA4BA3B2ABA5B.F.2BABA6BA3BA2BA3BA2B2A
3BA3BA9B2A3BA10B2A9BA2BA4BABABA3B2A4BA4B.F.6B2ABA11BA11BAB2A15B3ABA
15BA4BA12BA3BA3B.F$F.12B2A4B3A4B3ABABA8B2ABA2BA4B2A7B2A3BA2BAB2A2BA2B
A2B3AB2A3BA4BA3B.F.14BA2BA3B3A18BA12BA2BA4B2AB2A4B2A5BA10BA2BABA2B.F.
2BA3BA3BABA2BA8B2AB3AB2ABABA9B2AB2A2BA7B2A6BA5BA5BABA3BA10B.F.4B2AB3A
BA5BA17BAB2A2B2A8B2AB3A9B2A3BA2BA3BA11BA7B.F.12BABABA4BABABA2BAB4A5B
2A2BA5BA8BA3BABA7BA7BABAB2A2BA2BA2BA3B.F$F.6BA18BA4BA5BA2BA15B3A2BABA
4BA2BA9BA3BA2B2A4BA4B.F100.F100.F100.F100.F!
Maybe the problem is I need to be amending fixed width searches that have failed (presumably at the end of a line of fixed width searches of increasing sizes) rather than trying from-scratch mid_steps=XX searches?
Sokwe wrote: February 16th, 2025, 6:59 am
amling wrote: February 15th, 2025, 2:09 am I've pushed it to codeberg as 20250214-autochoke-semsv1-04. Ideally, Sokwe, I'd hope to talk you into trying this cut of it and if we like it, ultimately merge this to master after maybe cleaning up a few things
I've tested it and it seems to do what I expect/want. I'm of course very supportive of including it in the master branch assuming that it really does not affect ordinary searches and it doesn't make the code much more difficult to maintain.
Modern compilers and hardware are insane so I would not stake my life on it not affecting existing search performance, but the only change to the code of existing searches is to (a) keep those extra 2x 1/16 bcol-sized bit vectors and (b) call into an extra optional pre-reify step right before going on to reify. Any change in CPU performance all but has to be weird chaotic optimization changes which could just as easily get better as worse. Memory is more predictable and it is all but certain to make memory 1/8th bcol bigger which I think is acceptable.

In terms of maintainability it is all filed away in its own tiny hole of this "pre-reify callback" and so the only real burden on the main code is making visible what is available at that point which is a very, very light burden.

Committed and pushed. I've also finally fixed the memory parsing (on both this and the fixed board option) so you can say "--pre-reify-autochoke 10MB" instead of having to type out 10485760. Floating point numbers and all of KB/MB/GB/TB should also work e.g. "--pre-reify-autochoke 1.5GB". For now I did not add/require a "semsv1:" prefix. We can worry about that when and if I ever get around to writing other autochokes. As presumably they're all going to take memory limits maybe we'd just keep "--pre-reify-autochoke" as the memory limit for them all and add an optional "--pre-reify-autochoke-type" for those who want to pick the implementation details.

Thanks for all the brainstorming, testing, and feedback on this feature to help finally get it out the door.
Last edited by amling on February 16th, 2025, 3:04 pm, edited 1 time in total.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sylvani wrote: February 16th, 2025, 11:23 am Why does this not work? I am trying to extend a c/4 diagonal partial from ikpx2 (because it is being very slow)

Error:

Code: Select all

thread 'main' panicked at src/llsss/recentering/wao.rs:387:25:
assertion failed: already.is_none() || already == Some(key_tile)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Command:

Code: Select all

./rlife llsss-recentering-wao c4d-down golly.in 12 --rule 'B3/S23'
golly.in:

Code: Select all

| ...................................... | ...................................... | ...................................... | ...................................... | 
| ...................................... | ...........*.......................... | ..........**.......................... | ..........**.......................... | 
| ..........***......................... | ..........**.......................... | ..........*.*......................... | ...*.....**........................... | 
| ...**.....*........................... | ...**.....*.*......................... | ..***.....*........................... | ..****.....*.......................... | 
| ...*..*....*.......................... | ..**.*.*.............................. | ..*..**......*........................ | ..*..***.....**....................... | 
| ...*..*.*....**....................... | ...*..*......**....................... | ...*..**.....**....................... | .......*....*......................... | 
| ....**..*.....*....................... | ...*....*....**....................... | ..***..*.....**....................... | ..*.**................................ | 
| ...*.***.............................. | ...*...*.............................. | ...*..***..***........................ | ..***.*..*.*.......................... | 
| ...*.*.....*.......................... | ..**.*.*..***......................... | .......**.*.**........................ | ..........*.....*..................... | 
| ...*...*..**.**.*..................... | ..**...*..**.**.*..................... | .....*..**...*.***.................... | ...****...*.***.*..................... | 
| ...*****...*.**.***................... | ...***...*.*....**.................... | ..***.*..*............................ | ..**..*..**.*....*.................... | 
| .......***...*.*...................... | .......*.**.**.***.................... | ...*.*...*..****.*.................... | ..**.*..***..*........................ | 
| ...***...*....*....................... | ....*....*..*.*....................... | .........*....***..................... | ...........**......................... | 
| ............**........................ | ....*....*..**........................ | ........***.*.**...................... | ........***.....*..................... | 
| .........****...*..................... | .........*....*.*..................... | ..............*....................... | .........*....**...................... | 
| .........***..***..................... | ..............*.*..................... | .............*........................ | ............**........................ | 
| ..........*.***....................... | ............*......................... | ...........*.*.*...................... | .........***.*........................ | 
| .........*....*....................... | .........**.*..*...................... | ........***.*.*....................... | ........***.*......................... | 
| .........*...**....................... | ........**..***....................... | ........*...*.****.................... | ........*.**..*.**.................... | 
| .........*.*.*...**................... | ..........*..*..***................... | .........*......*.*................... | ............*.*.*.*................... | 
| .............*.*.*.................... | .............*...**................... | ............**....*...*............... | ............**.......**............... | 
| .............*.*......**.............. | .............*.*.....***.............. | ............**..*....**............... | ..............*.*.*..*.*.............. | 
| ..............**.*...**............... | .............*...**..*................ | .............*..***..*.*.............. | ...............***...*................ | 
| ..............****.*..*............... | ..............*..*.....*.............. | .............**....................... | ............**....*...*............... | 
| ...................*.*.*.............. | .............*..**...*.*...*.......... | .............*.***...*.....*.......... | .................*..**....*........... | 
| .............**...****..*.***......... | .............**......****.*.*......... | ............****.*..**..**.*.......... | ............*....*..***.**.**......... | 
| .............**...***...*.***......... | ............*..*.*...*..*............. | .............*.**....*..*..*.......... | ............**....*..**............... | 
| .............**...**.....***.......... | ...............*........*...*......... | ................*.***..***............ | ..............*...*.***..*............ | 
| ..............*....*....*............. | ..................***...*............. | ..............*.***.*..**............. | ................*.*.***............... | 
| ..............**.....*...*............ | ..............***.*.*...**...*........ | ..............*.*.....*..*..**........ | .............**.*.....**.*..**........ | 
| ................**.*....*...***....... | ...............**.**.****...**........ | ..............*.*.****...*..*.*....... | .................*.***.....**......... | 
| ...................**.**....*......... | ......................**....*.*....... | ............................*......... | ...................**........*........ | 
| ...................**.*......*........ | ......................**.............. | ........................*............. | .......................**............. | 
| ....................*.....*........... | .......................*.............. | .....................*.**............. | ....................******............ | 
| ....................****..*........... | ...................**.*..**........... | ...................**.*..*............ | ...................**....*............ | 
| ....................*.....**.......... | ...................*...**...*......... | ...................*..***.*.*......... | ...................*..*.*..*.......... | 
| ....................**..****.*........ | ....................**..*..**......... | ....................*...*...*......... | ........................*..*.*........ | 
| ........................*............. | ........................*.*.*.*....... | .........................*....*....... | .............................*........ | 
| .............................*.*...... | ............................***....... | ..............................*....... | ...............................*...... | 
| ............................**........ | ............................**........ | ...........................*....*..... | ........................*.***....*.... | 
| ........................**.*..*..*.... | ........................**..*.****.... | .......................***.**....**... | .......................***.***...**... | 
| ........................*.....**.***.. | .......................**..*..**.**... | .......................*..*..**...*... | .......................*..**..***..*.. | 
| ........................*.**....*..... | .........................*......*..*.. | ........................*....**.***... | ............................*.**.**... | 
| .............................*.*..*... | ............................*.*....... | ............................*......... | ............................*.**.*.... | 
Pursuant to my policy about error messages reaching users I have changed this to output, well, something, but it's not likely to really help here. You almost certainly do not mean to be running recentering WAO mode here and your error is several misunderstandings downstream of that. Recentering modes reads the first W row as roots, which are all periods so they're all identical but then WAO requires the last row of to-be-avoided bits be unique per root which it of course is not since the roots are all the same.

If you want to try to extend this partial with fixed board mode it could theoretically be run as is but it's way wider than desirable. You all but have to add extra W rows with question marks marking where you want the search to be. You also probably want to extend the board with more zeros to the right to allow expanding the search window that direction. Something like...

Code: Select all

$ cat fixed.in
| ........................................................ | ........................................................ | ........................................................ | ........................................................ |
| ........................................................ | ...........*............................................ | ..........**............................................ | ..........**............................................ |
| ..........***........................................... | ..........**............................................ | ..........*.*........................................... | ...*.....**............................................. |
| ...**.....*............................................. | ...**.....*.*........................................... | ..***.....*............................................. | ..****.....*............................................ |
| ...*..*....*............................................ | ..**.*.*................................................ | ..*..**......*.......................................... | ..*..***.....**......................................... |
| ...*..*.*....**......................................... | ...*..*......**......................................... | ...*..**.....**......................................... | .......*....*........................................... |
| ....**..*.....*......................................... | ...*....*....**......................................... | ..***..*.....**......................................... | ..*.**.................................................. |
| ...*.***................................................ | ...*...*................................................ | ...*..***..***.......................................... | ..***.*..*.*............................................ |
| ...*.*.....*............................................ | ..**.*.*..***........................................... | .......**.*.**.......................................... | ..........*.....*....................................... |
| ...*...*..**.**.*....................................... | ..**...*..**.**.*....................................... | .....*..**...*.***...................................... | ...****...*.***.*....................................... |
| ...*****...*.**.***..................................... | ...***...*.*....**...................................... | ..***.*..*.............................................. | ..**..*..**.*....*...................................... |
| .......***...*.*........................................ | .......*.**.**.***...................................... | ...*.*...*..****.*...................................... | ..**.*..***..*.......................................... |
| ...***...*....*......................................... | ....*....*..*.*......................................... | .........*....***....................................... | ...........**........................................... |
| ............**.......................................... | ....*....*..**.......................................... | ........***.*.**........................................ | ........***.....*....................................... |
| .........****...*....................................... | .........*....*.*....................................... | ..............*......................................... | .........*....**........................................ |
| .........***..***....................................... | ..............*.*....................................... | .............*.......................................... | ............**.......................................... |
| ..........*.***......................................... | ............*........................................... | ...........*.*.*........................................ | .........***.*.......................................... |
| .........*....*......................................... | .........**.*..*........................................ | ........***.*.*......................................... | ........***.*........................................... |
| .........*...**......................................... | ........**..***......................................... | ........*...*.****...................................... | ........*.**..*.**...................................... |
| .........*.*.*...**..................................... | ..........*..*..***..................................... | .........*......*.*..................................... | ............*.*.*.*..................................... |
| .............*.*.*...................................... | .............*...**..................................... | ............**....*...*................................. | ............**.......**................................. |
| .............*.*......**................................ | .............*.*.....***................................ | ............**..*....**................................. | ..............*.*.*..*.*................................ |
| ..............**.*...**................................. | .............*...**..*.................................. | .............*..***..*.*................................ | ...............***...*.................................. |
| ..............****.*..*................................. | ..............*..*.....*................................ | .............**......................................... | ............**....*...*................................. |
| ...................*.*.*................................ | .............*..**...*.*...*............................ | .............*.***...*.....*............................ | .................*..**....*............................. |
| .............**...****..*.***........................... | .............**......****.*.*........................... | ............****.*..**..**.*............................ | ............*....*..***.**.**........................... |
| .............**...***...*.***........................... | ............*..*.*...*..*............................... | .............*.**....*..*..*............................ | ............**....*..**................................. |
| .............**...**.....***............................ | ...............*........*...*........................... | ................*.***..***.............................. | ..............*...*.***..*.............................. |
| ..............*....*....*............................... | ..................***...*............................... | ..............*.***.*..**............................... | ................*.*.***................................. |
| ..............**.....*...*.............................. | ..............***.*.*...**...*.......................... | ..............*.*.....*..*..**.......................... | .............**.*.....**.*..**.......................... |
| ................**.*....*...***......................... | ...............**.**.****...**.......................... | ..............*.*.****...*..*.*......................... | .................*.***.....**........................... |
| ...................**.**....*........................... | ......................**....*.*......................... | ............................*........................... | ...................**........*.......................... |
| ...................**.*......*.......................... | ......................**................................ | ........................*............................... | .......................**............................... |
| ....................*.....*............................. | .......................*................................ | .....................*.**............................... | ....................******.............................. |
| ....................****..*............................. | ...................**.*..**............................. | ...................**.*..*.............................. | ...................**....*.............................. |
| ....................*.....**............................ | ...................*...**...*........................... | ...................*..***.*.*........................... | ...................*..*.*..*............................ |
| ....................**..****.*.......................... | ....................**..*..**........................... | ....................*...*...*........................... | ........................*..*.*.......................... |
| ........................*............................... | ........................*.*.*.*......................... | .........................*....*......................... | .............................*.......................... |
| .............................*.*........................ | ............................***......................... | ..............................*......................... | ...............................*........................ |
| ............................**.......................... | ............................**.......................... | ...........................*....*....................... | ........................*.***....*...................... |
| ........................**.*..*..*...................... | ........................**..*.****...................... | .......................***.**....**..................... | .......................***.***...**..................... |
| ........................*.....**.***.................... | .......................**..*..**.**..................... | .......................*..*..**...*..................... | .......................*..**..***..*.................... |
| ........................*.**....*....................... | .........................*......*..*.................... | ........................*....**.***..................... | ............................*.**.**..................... |
| .............................*.*..*..................... | ............................*.*......................... | ............................*........................... | ............................*.**.*...................... |
| ........................????????????.................... | ........................????????????.................... | ........................????????????.................... | ........................????????????.................... |
| ........................????????????.................... | ........................????????????.................... | ........................????????????.................... | ........................????????????.................... |
| ........................????????????.................... | ........................????????????.................... | ........................????????????.................... | ........................????????????.................... |
| ........................????????????.................... | ........................????????????.................... | ........................????????????.................... | ........................????????????.................... |

Code: Select all

rlife llsss c4d-down fixed.in
You can add --top-pad, --left-pad, and --right-pad to widen the search.

If you want to try to extend this partial with recentering mode that can also be done as-is but is going to do something undesirable for several reasons. Generally you want to add enough zero left/right to have 3 columns of them, and add root labels "LLLuuuu...uuuuRRR" at the beginning:

Code: Select all

$ cat rc.in
| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRR |
| ........................................ | ........................................ | ........................................ | ........................................ |
| ........................................ | ............*........................... | ...........**........................... | ...........**........................... |
| ...........***.......................... | ...........**........................... | ...........*.*.......................... | ....*.....**............................ |
| ....**.....*............................ | ....**.....*.*.......................... | ...***.....*............................ | ...****.....*........................... |
| ....*..*....*........................... | ...**.*.*............................... | ...*..**......*......................... | ...*..***.....**........................ |
| ....*..*.*....**........................ | ....*..*......**........................ | ....*..**.....**........................ | ........*....*.......................... |
| .....**..*.....*........................ | ....*....*....**........................ | ...***..*.....**........................ | ...*.**................................. |
| ....*.***............................... | ....*...*............................... | ....*..***..***......................... | ...***.*..*.*........................... |
| ....*.*.....*........................... | ...**.*.*..***.......................... | ........**.*.**......................... | ...........*.....*...................... |
| ....*...*..**.**.*...................... | ...**...*..**.**.*...................... | ......*..**...*.***..................... | ....****...*.***.*...................... |
| ....*****...*.**.***.................... | ....***...*.*....**..................... | ...***.*..*............................. | ...**..*..**.*....*..................... |
| ........***...*.*....................... | ........*.**.**.***..................... | ....*.*...*..****.*..................... | ...**.*..***..*......................... |
| ....***...*....*........................ | .....*....*..*.*........................ | ..........*....***...................... | ............**.......................... |
| .............**......................... | .....*....*..**......................... | .........***.*.**....................... | .........***.....*...................... |
| ..........****...*...................... | ..........*....*.*...................... | ...............*........................ | ..........*....**....................... |
| ..........***..***...................... | ...............*.*...................... | ..............*......................... | .............**......................... |
| ...........*.***........................ | .............*.......................... | ............*.*.*....................... | ..........***.*......................... |
| ..........*....*........................ | ..........**.*..*....................... | .........***.*.*........................ | .........***.*.......................... |
| ..........*...**........................ | .........**..***........................ | .........*...*.****..................... | .........*.**..*.**..................... |
| ..........*.*.*...**.................... | ...........*..*..***.................... | ..........*......*.*.................... | .............*.*.*.*.................... |
| ..............*.*.*..................... | ..............*...**.................... | .............**....*...*................ | .............**.......**................ |
| ..............*.*......**............... | ..............*.*.....***............... | .............**..*....**................ | ...............*.*.*..*.*............... |
| ...............**.*...**................ | ..............*...**..*................. | ..............*..***..*.*............... | ................***...*................. |
| ...............****.*..*................ | ...............*..*.....*............... | ..............**........................ | .............**....*...*................ |
| ....................*.*.*............... | ..............*..**...*.*...*........... | ..............*.***...*.....*........... | ..................*..**....*............ |
| ..............**...****..*.***.......... | ..............**......****.*.*.......... | .............****.*..**..**.*........... | .............*....*..***.**.**.......... |
| ..............**...***...*.***.......... | .............*..*.*...*..*.............. | ..............*.**....*..*..*........... | .............**....*..**................ |
| ..............**...**.....***........... | ................*........*...*.......... | .................*.***..***............. | ...............*...*.***..*............. |
| ...............*....*....*.............. | ...................***...*.............. | ...............*.***.*..**.............. | .................*.*.***................ |
| ...............**.....*...*............. | ...............***.*.*...**...*......... | ...............*.*.....*..*..**......... | ..............**.*.....**.*..**......... |
| .................**.*....*...***........ | ................**.**.****...**......... | ...............*.*.****...*..*.*........ | ..................*.***.....**.......... |
| ....................**.**....*.......... | .......................**....*.*........ | .............................*.......... | ....................**........*......... |
| ....................**.*......*......... | .......................**............... | .........................*.............. | ........................**.............. |
| .....................*.....*............ | ........................*............... | ......................*.**.............. | .....................******............. |
| .....................****..*............ | ....................**.*..**............ | ....................**.*..*............. | ....................**....*............. |
| .....................*.....**........... | ....................*...**...*.......... | ....................*..***.*.*.......... | ....................*..*.*..*........... |
| .....................**..****.*......... | .....................**..*..**.......... | .....................*...*...*.......... | .........................*..*.*......... |
| .........................*.............. | .........................*.*.*.*........ | ..........................*....*........ | ..............................*......... |
| ..............................*.*....... | .............................***........ | ...............................*........ | ................................*....... |
| .............................**......... | .............................**......... | ............................*....*...... | .........................*.***....*..... |
| .........................**.*..*..*..... | .........................**..*.****..... | ........................***.**....**.... | ........................***.***...**.... |
| .........................*.....**.***... | ........................**..*..**.**.... | ........................*..*..**...*.... | ........................*..**..***..*... |
| .........................*.**....*...... | ..........................*......*..*... | .........................*....**.***.... | .............................*.**.**.... |
| ..............................*.*..*.... | .............................*.*........ | .............................*.......... | .............................*.**.*..... |
You're then also going to need to set LLSSS_INIT_CA_CHECKS to run it due to how long it is:

Code: Select all

env LLSSS_INIT_CA_CHECKS=false rlife llsss-recentering c4d-down rc.in 13
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I was thinking more about seams between agars and especially WAO. So far I've gotten along sketching the WAO input files for these by hand (figure out all distinct W phase alignments, etc.), but maybe we could ... not do that?

Defining a seam for programmatic purposes is complicated but I think doable. The computer ultimately needs to know:

(*) Left agar and alignment. Now that we have an encoded definition of agar there is a lot of supporting code that already just exists.

(*) Right agar and alignment.

(*) Three basis vectors. Two generate the shift symmetries of the seam and the last defines left/right orientation.

(*) The cell values for some middling range. These have to be consistent under the alleged shift symmetries, but also some how define what is "left" and what is "right" and of course it all has to be consistent and ideally unique modulo the two shift symmetries.

But really a lot of this I think can be inferred if you provide just left/right agar names, a big, big pile of known cell values and three good enough vectors. In particular the agar alignments, the exact unique canonical basis vectors, and the exact collection of unique cell values can all be worked out.

I'm imagining that you'd do something like semi-carelessly dump out a good-enough, big-enough grid like:

Code: Select all

$ cat 1.in
| **********............... | **********............... |
| ..........*.............. | ...........*............. |
| ************............. | ************............. |
| ............*............ | .............*........... |
| **************........... | **************........... |
| ..............*.......... | ...............*......... |
| ****************......... | ****************......... |
| ................*........ | .................*....... |
And feed this to some sort of hypothetical analyzer:

Code: Select all

$ rlife analyze-seam --left-agar horizontal-stripes --right-agar zero --vu 1:0:0 --vv 1:0:2 --vw 0:-2:4 1.in > 1.seam
Here vv and vw are some shift symmetries which are small enough to make the picture big enough and vu is the orientation-defining third vector.

This would dump out some sort of definition/analysis of it you could then use for other fun stuff:

(*) It should be pretty easy to generate starting grids for it (in every phase/alignment and of course deduped where rephasings would be identical). Similar to "@agar", this may lump several could-have-been-disjoint searches together, but I think the convenience will be worth it and I think filtering to subsets of WAO idxs should be able to separate them if it matters.

(*) It should also be pretty easy to compile the data down to an LlsssEndsNfa-backed ends to detect if you reach the seam.

(*) Finally, it might be in range to compile the data down to something to detect a split where one side is the seam. This means you've found the seam but also there is some sort of extra branch you'd have to solve. This would be a more cleaned up and legit version of the sort of tricks discussed back here. It's tricky business to do with an NFA because you have to encode the wildcard right of the split which means the NFA size is gonna be something like 2^(2N) where N is the T component of your velocity. We probably also want to look for such a split a few W rows back similar to SRV2 rather than just at the very end. It might be preferrable to just do the analysis more carefully ourselves and show a thinnest split (again like SRV2) instead of the giant mess of all the chunks that could possibly be assembled into a theoretical split (that is what an LlsssEndsNfa-backed ends would show). Definitely TBD for this bullet point...
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I just finished a sketch of another way to try to find interesting partials. Often when searching one direction I'll be hoping for a 90 degree turn to a better direction, like b2f to s2s, s2s to f2b, or up to down (diagonal). So far I've spotted these in the various partials output by hand but I realized it might be in range to do this automatically.

The exact algorithm in terms of how it floods reachability through the state file is complicated but basically it looks for an all-zero path from the lower left corner to one side of the turn and an all-zero path from the lower right corner to the other side. As is these "sides" are required to be 2x2 blocks of zeros in the same vertical slice of 2 columns (really AF2-1 columns and one W overlap of W rows). Conceivably this could be strengthened to requiring bigger blocks of zeros (AF2 wide instead of AF2-1 wide and really any W depth we'd want). It could also be weakened to allow the 2x2 blocks to be offset by one horizontally the way they're much more likely to show up (where the turn is sort of incomplete but it's still at least leaning the right way). For now I think 2x2 blocks is a reasonable starting point.

As an example consider searching c2-s2s from the space non-filler edge:

Code: Select all

$ cat 2.in
| LLLuuuRRR | LLLuuuRRR |
| ....*.... | ...*..... |
| ...***... | ...***... |
Even as low as mid_steps=9 can find this rightward turn:

Code: Select all

LlsssMonitorTurninator (turn height 4)
|       SS         |       SS         |
| LLLLLLLLLLuuuRRR | LLLLLLLLLLuuuRRR |
| xx.........*..xx | xx........*...xx |
| xx........***.xx | xx........***.xx |
| xx.......*...*xx | xx.......*....xx |
| xx......*..*..xx | xx......***.*.xx |
| xx......*..*..xx | xx.....**.*.*.xx |
| xx......**...*xx | xx......**....xx |
| xx........***xxx | xx........***xxx |
| xx........*.xxxx | xx..........xxxx |
| xx.......**.xxxx | xx.......**.xxxx |
| xx......*...xxxx | xx.....**...xxxx |
| xx.....**...xxxx | xx.....**...xxxx |
| xx....*....*xxxx | xx...*...**.xxxx |
| xx...*****.*xxxx | xx...****.*.xxxx |
| xx..*...xxxxxxxx | xx..*...xxxxxxxx |
| xx..****xxxxxxxx | xx.****.xxxxxxxx |
| xx.*....xxxxxxxx | xx*....*xxxxxxxx |
| xx***..*xxxxxxxx | xx*..*..xxxxxxxx |
| xx.***xxxxxxxxxx | xx*..*xxxxxxxxxx |
| xxx.*.xxxxxxxxxx | xxx*..xxxxxxxxxx |
| xxxx.***.*xxxxxx | xxxx****.*xxxxxx |
| xxxxx*..**xxxxxx | xxxxx*...*xxxxxx |
| xxxxxx**..xxxxxx | xxxxxx*...xxxxxx |
| xxxxxx.*****xxxx | xxxxxx******xxxx |
| xxxxxxxx...*xxxx | xxxxxxxx....xxxx |
| xxxxxxxx.*.**xxx | xxxxxxxx*....xxx |
Here the critical 2 columns are marked with "S" and it's marked the "path" from the corners into the critical column with x's. It's kind of hard to read but if you look at just those two columns, you can see a 2x4 block of cells sandwiched between some x's. I agree with its judgement: this could be turn f2b and the apparent width at that point would be 4 (well, it's measured in W rows but for c2-s2s it's the same as cells).

TBD performance testing, optimization, and actually figuring out use in real world projects.

EDIT: Well, performance is definitely a little bad and I'm not sure I can make it acceptable. Like it's making test searches 2x to 3x slower which I think might be too bitter a pill to swallow for how much of a long shot the kind of partials it looks for are in most cases.

As another example, here is it working with a different agar to find a right turn from ascending max edge:

Code: Select all

$ cat 3.in
| LLLuuRRR | LLLuuRRR |
| ....*... | ...*.... |
| ...***** | ...***** |
E.g. this:

Code: Select all

rlife llsss-recentering c2-s2s 3.in --right-inertness agar:horizontal-stripes --right-edge agar:horizontal-stripes --partials turninator:right:zero:horizontal-stripes 15
Can find this:

Code: Select all

20250220 15:20:17 [INFO] LlsssMonitorTurninator (turn height 1)
20250220 15:20:17 [INFO] |                   SS     |                   SS     |
20250220 15:20:17 [INFO] | LLLLLLLLLuuRRRRRRRRRRRRR | LLLLLLLLLuuRRRRRRRRRRRRR |
20250220 15:20:17 [INFO] | xx........*.......xxxxxx | xx.......*........xxxxxx |
20250220 15:20:17 [INFO] | xx.......*********oooooo | xx.......*********oooooo |
20250220 15:20:17 [INFO] | xx....**..........xxxxxx | xx....*.*.........xxxxxx |
20250220 15:20:17 [INFO] | xx...*...*********oooooo | xx...*************oooooo |
20250220 15:20:17 [INFO] | xx..*...*.........xxxxxx | xx..**............xxxxxx |
20250220 15:20:17 [INFO] | xx..*.....********oooooo | xx.**....*********oooooo |
20250220 15:20:17 [INFO] | xx..***...*.......xxxxxx | xx..*.*...*.......xxxxxx |
20250220 15:20:17 [INFO] | xx...*.*....******oooooo | xx.....*...*******oooooo |
20250220 15:20:17 [INFO] | xx...**..*..*.....xxxxxx | xx..**......*.....xxxxxx |
20250220 15:20:17 [INFO] | xx.*...**..xx.****oooooo | xx***.***..xx*****oooooo |
20250220 15:20:17 [INFO] | xx**.......xxx*...xxxxxx | xx*..*.....xxx*...xxxxxx |
20250220 15:20:17 [INFO] | xx.******..xxxx***oooooo | xx*..****..xxxx***oooooo |
20250220 15:20:17 [INFO] | xxx.*....*.xxxx.*.xxxxxx | xxx*.......xxxx*..xxxxxx |
20250220 15:20:17 [INFO] | xxxx.***...xxxxx.*oooooo | xxxx***.*..xxxxx**oooooo |
20250220 15:20:17 [INFO] | xxxxx*...*.xxxxxx*xxxxxx | xxxxx*...*.xxxxxx*xxxxxx |
20250220 15:20:17 [INFO] | xxxxxx.***.xxxxxxxoooooo | xxxxxx**...xxxxxxxoooooo |
20250220 15:20:17 [INFO] | xxxxxxx****xxxxxxx.*xxxx | xxxxxxx*..*xxxxxxx*.xxxx |
20250220 15:20:17 [INFO] | xxxxxxxx..*xxxxxxxxxoooo | xxxxxxxx*.*xxxxxxxxxoooo |
20250220 15:20:17 [INFO] | xxxxxxxxxxxxxxxxxxxx.*xx | xxxxxxxxxxxxxxxxxxxx*.xx |
20250220 15:20:17 [INFO] | xxxxxxxxxxxxxxxxxxxx..oo | xxxxxxxxxxxxxxxxxxxx..oo |
EDIT2: I've checked it in and pushed to codeberg. It's pretty standalone and a low enough weight on the rest of the codebase that I'm just gonna include it as is. Unclear if I will ever get performance better. Please let me know if you take it for a spin how it turns out.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I've plumbed the LLSSS env stuff together all the way up to all the CLI argument parsing and all the way down to all the readers so they can now be specified by (somewhat verbose) CLI arguments. For example with "show-env":

Code: Select all

$ rlife show-env --llsss-env LLSSS_HALT_ON_ENDS=true --llsss-env LLSSS_MAX_TABLE_SIZE=9
LLSSS_HALT_ON_ENDS: true (from CLI argument)
LLSSS_HOLLOW_PRESPLIT_TARGET: 100 (default)
LLSSS_INIT_CA_CHECKS: true (default)
LLSSS_MAX_TABLE_SIZE: 9 (from CLI argument)
LLSSS_RC_ENDS_FULL: true (default)
$
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

amling wrote: February 22nd, 2025, 4:37 pm I whipped up a quick hack for LLSSS to jointly forbid a specific grid (like how WCAF jointly forbids all columns to extend as a cycle)...
This is invoked like `--filters forbid_grid:whatever.grid`. Roots and alignment are similar to how grid constraint works. Cells have to be ".", "*", or "W". It is billed as forbidding that grid but the exact semantic is spines are considered "interesting" if they mismatch the grid and then like WCAF it discards parts of the state that cannot be connected to any interesting spine.
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: Seeds

Post by Sokwe »

amling wrote: February 22nd, 2025, 4:37 pm a completed 3c/5 ship...
Incredible! This is the first known spaceship in a Life-like CA without B0 that travels at a speed between c and c/2, but not at 2c/3.
amling wrote: February 22nd, 2025, 4:37 pm I whipped up a quick hack for LLSSS to jointly forbid a specific grid (like how WCAF jointly forbids all columns to extend as a cycle) and restarted that line of searches (I also started searches for a back to that wick).
amling wrote: February 22nd, 2025, 4:41 pm This is invoked like `--filters forbid_grid:whatever.grid`. Roots and alignment are similar to how grid constraint works. Cells have to be ".", "*", or "W". It is billed as forbidding that grid but the exact semantic is spines are considered "interesting" if they mismatch the grid and then like WCAF it discards parts of the state that cannot be connected to any interesting spine.
I'm not sure I fully understand this. Is it sort of like the inverse of a constraints grid? Can you show the forbidden grid search setup in this case?
-Matthias Merzenich
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sokwe wrote: February 22nd, 2025, 6:09 pm
amling wrote: February 22nd, 2025, 4:37 pm I whipped up a quick hack for LLSSS to jointly forbid a specific grid (like how WCAF jointly forbids all columns to extend as a cycle) and restarted that line of searches (I also started searches for a back to that wick).
amling wrote: February 22nd, 2025, 4:41 pm This is invoked like `--filters forbid_grid:whatever.grid`. Roots and alignment are similar to how grid constraint works. Cells have to be ".", "*", or "W". It is billed as forbidding that grid but the exact semantic is spines are considered "interesting" if they mismatch the grid and then like WCAF it discards parts of the state that cannot be connected to any interesting spine.
I'm not sure I fully understand this. Is it sort of like the inverse of a constraints grid? Can you show the forbidden grid search setup in this case?
Uh, I can although the files are huge. I've attached them to this post. This was run as...

Code: Select all

rlife llsss-recentering 3c5-f2b --rule 'B2/S' p2.in --left-edge odd --left-closure gridz:p2.bg --filters forbid_grid:p2.bad --top-pad 20 --left-pad 14 --right-pad 41 --ends bg,s_periodic:0:-5:5,s_periodic:0:-4:4,s_periodic:0:-3:3,s_periodic:0:1:1 25
Most of that is setting up a normal odd search with a bunch of extra s_periodic ends that never turned up anything. "p2.bg" and its use as "--left-closure gridz:p2.bg" are allowing discounts for partials that match the grid as it was and probably aren't really necessary in this case and especially not necessary to understand the forbid_grid invocation.

If you compare p2.in and p2.bad you can see they have identical U sizes and identical roots. Once the search has proceeded at least to the depth of p2.bad it will start filtering similar to WCAF: every spine is marked as interesting or not depending on whether it matches the cells in p2.bad (a mismatch is considered interesting). Then interesting spines are rolled up to interesting bcol entries (AF1 width slices of pattern, or in this case 2 Y column slices of pattern) and then those are smeared left/right to find bcol entries that could (still) be part of a partial with an interesting spine. Any bcol entries that are not (i.e. are only part of partials that completely match the grid) are dropped.

The net effect in this case is that partials that extend the forbidden grid are eventually dropped. Note they're not dropped immediately as every part of the grid is part of a partial that does not globally mismatch it at least for a while (similar to how WCAF does not force a nonzero first row immediately). In a sufficiently bad case (especially one with, say, a lot of small ships), I could imagine a forbidden grid never getting dropped by staying around as part of other partials forever.
Attachments
p2.tar.bz2
(29.01 KiB) Downloaded 41 times
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

Completely unrelated to the above discussion, I was looking for a p7 oscillator that could activate the odd traffic stop to reduce the p35 gun. Consider the following partial result:

Code: Select all

x = 28, y = 63, rule = B3/S23
8bo$7bobo$8bo2$6b5o$5bo4bo$4bo2bo$bo2bob2o$obobo5bo$bo2bo4bobo8bo$4b2o
2bo2bo6b3o$9b2o6bo$13bo3b2o$13bo$13bo2$15b3o2$8b2o3bo7bo$7bobo3bo5b3o$
7bo5bo4bo$6b2o7b2o2bo$14bo2b2obo$12b2o6b3o$8bo2bobo3b3o3bo$8b4obobo4bo
bo$12bo2bo2b3ob2o$10b2o3bo7bo$10bo4bob4obo$8bobo4bo4bob2o$8b2o4b2ob2ob
o2bo$13b2o2bob2obo$12b2o3bo3bo$11b2o2b2ob2o$11b2obo3bo$12bo2b2o3bo$7b
2obobo4b3obo$7bob2obo2b2o4bo$13b2obo2b2o$14bobobo$13b2obobo$8b2ob2obob
ob2o$9bob2o2bo4bo$8bo7b4o2b2o$9b2ob4o4b2o2bo$10bobo2bobobo2b3o$10bo2bo
2b3o2bo$11b2o4b3o2bo$17b3ob2o2$17b3ob2o$15bo6bo$14bob6o4b2o$15bo6b3o2b
o$19bobo3b2o$21bob2o$21b2obo$21bo$19b2o$22b2o$19bo$20b2obo$20b2obo!
Notice that there are points where the rotor gets fairly thin. Is there a way to use LLSSS to search for extensions in which the rotor stays thin while the stator is unrestricted?

Normally when using JLS I will restrict the width of the rotor to some small amount, bounded by two columns of period-1 cells, which are themselves bounded by "don't care cells". something like this:

Code: Select all

XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
This prevents the search from wasting time finding numerous functionally equivalent stators within the 'X' cells.
-Matthias Merzenich
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sokwe wrote: February 22nd, 2025, 7:14 pm Completely unrelated to the above discussion, I was looking for a p7 oscillator that could activate the odd traffic stop to reduce the p35 gun. Consider the following partial result:

Code: Select all

x = 28, y = 63, rule = B3/S23
8bo$7bobo$8bo2$6b5o$5bo4bo$4bo2bo$bo2bob2o$obobo5bo$bo2bo4bobo8bo$4b2o
2bo2bo6b3o$9b2o6bo$13bo3b2o$13bo$13bo2$15b3o2$8b2o3bo7bo$7bobo3bo5b3o$
7bo5bo4bo$6b2o7b2o2bo$14bo2b2obo$12b2o6b3o$8bo2bobo3b3o3bo$8b4obobo4bo
bo$12bo2bo2b3ob2o$10b2o3bo7bo$10bo4bob4obo$8bobo4bo4bob2o$8b2o4b2ob2ob
o2bo$13b2o2bob2obo$12b2o3bo3bo$11b2o2b2ob2o$11b2obo3bo$12bo2b2o3bo$7b
2obobo4b3obo$7bob2obo2b2o4bo$13b2obo2b2o$14bobobo$13b2obobo$8b2ob2obob
ob2o$9bob2o2bo4bo$8bo7b4o2b2o$9b2ob4o4b2o2bo$10bobo2bobobo2b3o$10bo2bo
2b3o2bo$11b2o4b3o2bo$17b3ob2o2$17b3ob2o$15bo6bo$14bob6o4b2o$15bo6b3o2b
o$19bobo3b2o$21bob2o$21b2obo$21bo$19b2o$22b2o$19bo$20b2obo$20b2obo!
Notice that there are points where the rotor gets fairly thin. Is there a way to use LLSSS to search for extensions in which the rotor stays thin while the stator is unrestricted?

Normally when using JLS I will restrict the width of the rotor to some small amount, bounded by two columns of period-1 cells, which are themselves bounded by "don't care cells". something like this:

Code: Select all

XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
XXXX11777711XXXX
This prevents the search from wasting time finding numerous functionally equivalent stators within the 'X' cells.
Let's fix a slice to discuss trying to solve, say this width 3 rotor pulled from the middle (r/R are rotor cells off/on):

Code: Select all

| ...**.*.*rr..***.*... | ...**.*.*Rr..***.*... | ...**.*.*rr..***.*... | ...**.*.*rr..***.*... | ...**.*.*rR..***.*... | ...**.*.*rR..***.*... | ...**.*.*rr..***.*... |
| ...*.**.*.rR*....*... | ...*.**.*.RR*....*... | ...*.**.*.rr*....*... | ...*.**.*.rR*....*... | ...*.**.*.RR*....*... | ...*.**.*.rr*....*... | ...*.**.*.Rr*....*... |
You can search something like what you suggest with fixed board and edges "pd" and "any". The exact semantics of CA checks near the boundary may or may not match JLS, but presumably it's close.

Code: Select all

$ cat 1.pre  # still r/R
| .*rr..** | .*Rr..** | .*rr..** | .*rr..** | .*rR..** | .*rR..** | .*rr..** |
| .*.rR*.. | .*.RR*.. | .*.rr*.. | .*.rR*.. | .*.RR*.. | .*.rr*.. | .*.Rr*.. |
$ cat 1.in
| .*....** | .**...** | .*....** | .*....** | .*.*..** | .*.*..** | .*....** |
| .*..**.. | .*.***.. | .*...*.. | .*..**.. | .*.***.. | .*...*.. | .*.*.*.. |
$ rlife llsss p7 1.in --left-edge pd:7:any --right-edge pd:7:any
...
The "any" edge is unrestricted (other than CA checks) while the "pd" edge wraps another edge and restricts it to further demand all cell cohorts meet some period division. In this case division in 7 makes them still lifes.

This however is not generally how I would approach limiting rotor cells. I've not had great luck with "any" in any form and you lose recentering. Also I'm not convinced for LSSS descendants that deduping stators is super valuable due to how partials are split into strips and each strip is only kept once even if there are ridiculously many legal combinations of them.

How would I do it? For starters, let's talk about input files. As is this could be...

Code: Select all

$ cat 2.pre
| LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR |
| ...**.*.*rr..***.*... | ...**.*.*Rr..***.*... | ...**.*.*rr..***.*... | ...**.*.*rr..***.*... | ...**.*.*rR..***.*... | ...**.*.*rR..***.*... | ...**.*.*rr..***.*... |
| ...*.**.*.rR*....*... | ...*.**.*.RR*....*... | ...*.**.*.rr*....*... | ...*.**.*.rR*....*... | ...*.**.*.RR*....*... | ...*.**.*.rr*....*... | ...*.**.*.Rr*....*... |
$ cat 2.in
| LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuRRR |
| ...**.*.*....***.*... | ...**.*.**...***.*... | ...**.*.*....***.*... | ...**.*.*....***.*... | ...**.*.*.*..***.*... | ...**.*.*.*..***.*... | ...**.*.*....***.*... |
| ...*.**.*..**....*... | ...*.**.*.***....*... | ...*.**.*...*....*... | ...*.**.*..**....*... | ...*.**.*.***....*... | ...*.**.*...*....*... | ...*.**.*.*.*....*... |
$
If you really want to let it pick its own starting stator you can wildcard it (with default wildcard config "7" is a 7-fold PD wildcard, i.e. stator here):

Code: Select all

$ cat 3.pre
| LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR |
| ..777.*rr..*777.. | ..777.*Rr..*777.. | ..777.*rr..*777.. | ..777.*rr..*777.. | ..777.*rR..*777.. | ..777.*rR..*777.. | ..777.*rr..*777.. |
| ..777.*.rR*.777.. | ..777.*.RR*.777.. | ..777.*.rr*.777.. | ..777.*.rR*.777.. | ..777.*.RR*.777.. | ..777.*.rr*.777.. | ..777.*.Rr*.777.. |
$ cat 3.in
| LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR | LLLLLuuuuuuuRRRRR |
| ..777.*....*777.. | ..777.**...*777.. | ..777.*....*777.. | ..777.*....*777.. | ..777.*.*..*777.. | ..777.*.*..*777.. | ..777.*....*777.. |
| ..777.*..**.777.. | ..777.*.***.777.. | ..777.*...*.777.. | ..777.*..**.777.. | ..777.*.***.777.. | ..777.*...*.777.. | ..777.*.*.*.777.. |
$
Note even though it's only seemingly 3 columns of wildcards it's really any width in the state as all width 3 slices are generated and allowed to combine in any way (that pass those pesky init CA checks long input files have problems with). Key in that is that "u"s are distinct from each other (they are special cased in the code) while "L"s are not. If you find this generating bad stators that you can't solve northward you might add more rows northward or more specified columns of stator outwards. Beware that initialization with wildcards is going to expand the wildcard for 3 columns at a time so if you make this 10 rows tall it's going to make a pile of the 2^(3*10) combined cell values before trying to join it with itself and restrict it down. Maybe not too dangerous here but can get dangerous quickly with full "W" wildcards.

Now let's talk about steps. mid_steps are arbitrary steps and represent how much full p7 stuff you get. You probably want to add extra closures/inertness to get stator that doesn't count towards it.

The biggest choice is to include "--inertness pd:7". With this, stator is limitless and looks likes zeros to most features. Before any mid_steps are counted stator is fully closured, SRV2 looks for chokes and splits only counting rotor, etc.

Smaller is to include a fixed number of PD steps on the sides. For example "--left-closure pd:7:4 --right-closure pd:7:4" to include 4 stator steps on each side. What "4" covers is complicated both in terms of the difference between steps and columns but also the inexactness of the process where all sorts of extra chimerism will almost certainly occur. I've often used around 4 but still gotten fairly large stators.

For PD projects I've usually just run separate lines of increasing mid_steps for a few fixed values for PD steps. Something like one line for PD inertness, one line for 4 steps, one line for 8 steps, and maybe one line for 12 steps. For some projects I've run PD inertness with increasing mid_steps until I figure out the minimum viable mid_steps and then run with that mid_steps fixed and increasing PD steps one by one. You should of course play around with it and figure out what works for your geometry, partial, memory constraints, etc.

I would make sure to include `pd_lite` ends to know the moment the partial is reduced to just a stator (but presumably re-include `bg` just in case).

Actual fully-specified searches you could run with the above input files:

Code: Select all

$ rlife llsss-recentering p7 2.in --inertness pd:7 --ends bg,pd_lite:7 04
$ rlife llsss-recentering p7 3.in --left-closure pd:7:08 --right-closure pd:7:08 --ends bg,pd_lite:7 04
shuich01
Posts: 53
Joined: March 27th, 2021, 8:40 pm
Location: The Milky Way

Re: amling search program principles discussion / brain dump

Post by shuich01 »

I tried to build LLSSS but it failed to compile because of an error:

Code: Select all

error[E0599]: no function or associated item named `new` found for struct `PriorityQueue` in the current scope
   --> src/llsss/ends.rs:670:60
    |
670 | ...                   let mut queue = PriorityQueue::new();
    |                                                      ^^^ function or associated item not found in `PriorityQueue<_, _, _>`
    |
note: if you're trying to build a new `PriorityQueue<_, _, _>` consider using one of the following associated functions:      PriorityQueue::<I, P, H>::with_default_hasher
      PriorityQueue::<I, P, H>::with_capacity_and_default_hasher
      PriorityQueue::<I, P, H>::with_hasher
      PriorityQueue::<I, P, H>::with_capacity_and_hasher
   --> /home/murasame/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/priority-queue-1.4.0/src/priority_queue/mod.rs:136:5
    |
136 |     pub fn with_default_hasher() -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
141 |     pub fn with_capacity_and_default_hasher(capacity: usize) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
153 |     pub fn with_hasher(hash_builder: H) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
162 |     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: H) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following traits define an item `new`, perhaps you need to implement one of them:
            candidate #1: `Dedupe`
            candidate #2: `LlsssJcolFullBuilder`
help: there is a method `ne` with a similar name, but with different arguments
   --> /rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/core/src/cmp.rs:261:5

For more information about this error, try `rustc --explain E0599`.
warning: `rlife` (bin "rlife") generated 2 warnings
error: could not compile `rlife` (bin "rlife") due to 1 previous error; 2 warnings emitted
Still wandering ...
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

shuich01 wrote: February 24th, 2025, 9:26 am I tried to build LLSSS but it failed to compile because of an error:

Code: Select all

error[E0599]: no function or associated item named `new` found for struct `PriorityQueue` in the current scope
   --> src/llsss/ends.rs:670:60
    |
670 | ...                   let mut queue = PriorityQueue::new();
    |                                                      ^^^ function or associated item not found in `PriorityQueue<_, _, _>`
    |
note: if you're trying to build a new `PriorityQueue<_, _, _>` consider using one of the following associated functions:      PriorityQueue::<I, P, H>::with_default_hasher
      PriorityQueue::<I, P, H>::with_capacity_and_default_hasher
      PriorityQueue::<I, P, H>::with_hasher
      PriorityQueue::<I, P, H>::with_capacity_and_hasher
   --> /home/murasame/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/priority-queue-1.4.0/src/priority_queue/mod.rs:136:5
    |
136 |     pub fn with_default_hasher() -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
141 |     pub fn with_capacity_and_default_hasher(capacity: usize) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
153 |     pub fn with_hasher(hash_builder: H) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
162 |     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: H) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following traits define an item `new`, perhaps you need to implement one of them:
            candidate #1: `Dedupe`
            candidate #2: `LlsssJcolFullBuilder`
help: there is a method `ne` with a similar name, but with different arguments
   --> /rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/core/src/cmp.rs:261:5

For more information about this error, try `rustc --explain E0599`.
warning: `rlife` (bin "rlife") generated 2 warnings
error: could not compile `rlife` (bin "rlife") due to 1 previous error; 2 warnings emitted
Interesting... Could you please post complete answers to all of the following:
  • What version of rustc/cargo? I.e. what is the complete output of `cargo --version` and `rustc --version`?
  • What exactly did you do to build it? Everything from the initial clone. Every command you ran in or near the directory in question.
  • What was the complete output of the build? In particular what version of priority-queue did it build? Cargo.toml specifies "=1.4.0" and I am pretty sure that method ("new") exists in 1.4.0. I guess I see 1.4.0 in a path in the error above but I just can't believe it.
  • Is the repo dirty? What is the complete output of `git status --long`?
  • Have you ever done anything else with rust ever? On this machine? I notice that the "new" method is gated behind "cfg(has_std)" while the functions it recommends instead are not. This is getting into wild, wild guess territory, but is some configuration for some other project leaking into this build?
EDIT: I dug a little on this "has_std". priority-queue uses another crate called "autocfg" to set it when the standard library is available, but autocfg's decision-making skills on this are questionable at best based on 5 minutes of googling "help autocfg detected wrong" or the like. Unfortunately this is probably beyond my ability to debug other insane people's garbage code running on a computer I can't even see.

As one possible hack you could rip priority-queue out, either deleting the only feature that uses it (EDBV3), or coding a replacement. Another possible idea is to boil the mis-detection of has_std down to a repro that you can bring to the autocfg folks. A third possibility is to try to make a copy of autocfg's detection logic and see if you can figure out why it's going wrong.

EDIT2: The more I pulled on the thread of autocfg's details the less happy I was about depending on it, especially for a simple priority queue I use in one place. I've just now replaced it with less than 50 lines of code wrapping a map and a set. It's still used transitively by num-traits but for something perhaps less damaging (deciding if f64::total_cmp exists and I don't think we rely on any of the code it generates depending on that). This might fix it for you but I would still appreciate knowing for sure what happened here and it might be worth fixing for your ability to run rust projects in general.
shuich01
Posts: 53
Joined: March 27th, 2021, 8:40 pm
Location: The Milky Way

Re: amling search program principles discussion / brain dump

Post by shuich01 »

amling wrote: February 24th, 2025, 1:14 pm
shuich01 wrote: February 24th, 2025, 9:26 am I tried to build LLSSS but it failed to compile because of an error:

Code: Select all

error[E0599]: no function or associated item named `new` found for struct `PriorityQueue` in the current scope
   --> src/llsss/ends.rs:670:60
    |
670 | ...                   let mut queue = PriorityQueue::new();
    |                                                      ^^^ function or associated item not found in `PriorityQueue<_, _, _>`
    |
note: if you're trying to build a new `PriorityQueue<_, _, _>` consider using one of the following associated functions:      PriorityQueue::<I, P, H>::with_default_hasher
      PriorityQueue::<I, P, H>::with_capacity_and_default_hasher
      PriorityQueue::<I, P, H>::with_hasher
      PriorityQueue::<I, P, H>::with_capacity_and_hasher
   --> /home/murasame/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/priority-queue-1.4.0/src/priority_queue/mod.rs:136:5
    |
136 |     pub fn with_default_hasher() -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
141 |     pub fn with_capacity_and_default_hasher(capacity: usize) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
153 |     pub fn with_hasher(hash_builder: H) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
162 |     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: H) -> Self {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following traits define an item `new`, perhaps you need to implement one of them:
            candidate #1: `Dedupe`
            candidate #2: `LlsssJcolFullBuilder`
help: there is a method `ne` with a similar name, but with different arguments
   --> /rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/core/src/cmp.rs:261:5

For more information about this error, try `rustc --explain E0599`.
warning: `rlife` (bin "rlife") generated 2 warnings
error: could not compile `rlife` (bin "rlife") due to 1 previous error; 2 warnings emitted
Interesting... Could you please post complete answers to all of the following:
  • What version of rustc/cargo? I.e. what is the complete output of `cargo --version` and `rustc --version`?
  • What exactly did you do to build it? Everything from the initial clone. Every command you ran in or near the directory in question.
  • What was the complete output of the build? In particular what version of priority-queue did it build? Cargo.toml specifies "=1.4.0" and I am pretty sure that method ("new") exists in 1.4.0. I guess I see 1.4.0 in a path in the error above but I just can't believe it.
  • Is the repo dirty? What is the complete output of `git status --long`?
  • Have you ever done anything else with rust ever? On this machine? I notice that the "new" method is gated behind "cfg(has_std)" while the functions it recommends instead are not. This is getting into wild, wild guess territory, but is some configuration for some other project leaking into this build?
EDIT: I dug a little on this "has_std". priority-queue uses another crate called "autocfg" to set it when the standard library is available, but autocfg's decision-making skills on this are questionable at best based on 5 minutes of googling "help autocfg detected wrong" or the like. Unfortunately this is probably beyond my ability to debug other insane people's garbage code running on a computer I can't even see.

As one possible hack you could rip priority-queue out, either deleting the only feature that uses it (EDBV3), or coding a replacement. Another possible idea is to boil the mis-detection of has_std down to a repro that you can bring to the autocfg folks. A third possibility is to try to make a copy of autocfg's detection logic and see if you can figure out why it's going wrong.

EDIT2: The more I pulled on the thread of autocfg's details the less happy I was about depending on it, especially for a simple priority queue I use in one place. I've just now replaced it with less than 50 lines of code wrapping a map and a set. It's still used transitively by num-traits but for something perhaps less damaging (deciding if f64::total_cmp exists and I don't think we rely on any of the code it generates depending on that). This might fix it for you but I would still appreciate knowing for sure what happened here and it might be worth fixing for your ability to run rust projects in general.
ok it's solved now by using the new repo, thanks :)
Still wandering ...
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

Is there a way to use --max-pop while extending a partial result?
-Matthias Merzenich
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sokwe wrote: February 25th, 2025, 10:41 pm Is there a way to use --max-pop while extending a partial result?
Not easily without some minor code changes and a recompile. The 3 behaviors it enables I believe would all work with non-WAO recentering but their exact semantics are weird enough that I did not hook them up there.

If you really want to swing it without a code change you could maybe do it. You could frame your partial one row higher than it should be and corrupt the last row so you can run WAO (and so the real partial is a mismatch on the first corrupted row), and then use a constraint to enforce the exact continuation to be the intended one in the last row.

What, uh, were you thinking of using it for?
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

amling wrote: February 25th, 2025, 10:49 pm What, uh, were you thinking of using it for?
In the past, I had wanted to minimize certain components of large c/3 spaceships. However, in this case I was thinking of extending the following 2c/5 partial result to see if I could find any even-symmetric ships with population less than 100 (only two were known), and especially if I could find one with population less than 70:

Code: Select all

|            |            |            | .......... | .......... |
| uuuuuuuRRR | .......... | .......... | ....*..... | ....*..... |
| .......... | ....*..... | ...***.... | ...*.*.... | ..**.**... |
| ...***.... | ...***.... | ...*.*.... | ..**.**... | ..**...... |
| ..*..*.... | ..*..*.... | ..*..*.... | ..*..**... | .......... |
| ..***..... | ***.*..... | ..*.**.... | ***.**.... |            |
| ..*....... | ..*.*..... |            |            |            |
I actually ran the recentering search with mid_steps 14 with the thought that the shortest result would probably be a fairly small ship, and indeed I discovered this 72-cell ship, which makes it the second smallest known even-symmetric 2c/5 (tied with another ship):

Code: Select all

x = 28, y = 17, rule = B3/S23
10bo6bo$9b3o4b3o$9bo2bo2bo2bo$10bob4obo$10bobo2bobo2$7b2obo6bob2o$7bo
2b2o4b2o2bo2$6bo3bo6bo3bo$2bo3b3o2b2o2b2o2b3o3bo$bobo20bobo$2ob2o18b2o
b2o$bo24bo$bo24bo$bo2bo18bo2bo$2bo22bo!
Ideally, I would want to run some limited-width max-pop searches, but I'm not sure my craptop has enough memory to do so. I don't think there has really been any searching for even-symmetric 2c/5 ships above width 22 before.
-Matthias Merzenich
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

I'm having problems with the following search setup:

Code: Select all

./rlife llsss --rule 'B3/S23' 2c5-f2b 1.in --left-pad 3
1.in:

Code: Select all

|                           |                           |                           | ......................... | ......................... |
| ......................... | ......................... | ..........*.............. | ..........*.............. | .........***............. |
| ..........*.............. | .........***............. | .........*.*............. | ........**.**............ | .........*..*............ |
| .........***............. | .........*.*............. | ........**.**............ | ...........**............ | ............*............ |
| .........*..*............ | ........*....*........... | ........**..*............ | ........***.............. | .........**..*........... |
| .........*****........... | ........*....*........... | ............**........... | ............**........... | .........*..**........... |
| .........***.*........... | .............**.......... | ........**............... | .............*........... | .........*..**........... |
| ........**.*..*.......... | ........**.*.**.......... | ..............*.......... | ........***.............. | ......******............. |
| .......*.....*........... | ......*.....*............ | ......*..*.**............ | .....***..**............. | .....*.....*............. |
| ......****.*............. | ......***...*............ | .....***...***........... | .....*.**.*..*........... | .....*..****............. |
| .....*......*............ | ....*.......*............ | .....*.*....*............ | .......*??????????....... | ....*..*??????????....... |
| ....*********............ | ....*...??????????....... | ....**..??????????....... | ....***.??????????....... | ....***.??????????....... |
| ....*..*??????????....... | ...**...??????????....... | ........??????????....... | .....*..??????????....... | ....***.??????????....... |
| ...*....??????????....... | ...***.*??????????....... | ......*.??????????....... | ........??????????....... | ........??????????....... |
| ....*.*.??????????....... | ....**..??????????....... | ...*....??????????....... | ........??????????....... | ........??????????....... |
| .....*..??????????....... | .....*..??????????....... | ......*.??????????....... | ....**..??????????....... | ....**..??????????....... |
| ........??????????....... | ....**..??????????....... | ....**..??????????....... | ...*..*.??????????....... | ....**..??????????....... |
| ....**..??????????....... | ....*...??????????....... | ...***..??????????....... | ........??????????....... | ....*...??????????....... |
| ...*....??????????....... | ...*....??????????....... | ...**...??????????....... | ...*.*..??????????....... | ........??????????....... |
| ....**..??????????....... | ....*...??????????....... | ........??????????....... | ........??????????....... | ........??????????....... |
| ........??????????....... | ........??????????....... |                           |                           |                           |
This search stops at w_pos 58, which puts it just about where the start_file ends. Here are the final displayed partial results:

Code: Select all

Unique:
|                   |                   |                   | ...***...*....... | ..***...***...... |
| ..***..**........ | ..*.....*........ | ..*......*....... | .*.......*....... | ..*.*....*....... |
| ..*.**.*..*...... | ..*..****........ | .*********....... | .*.....*.*??..... | .**.....?*??..... |
| ....*............ | .*..**...???..... | .*..**.*.????.... | **.....?.???..... | .......??????.... |
| .***....?????.... | .***.....????.... | *.......????..... | ***.*..??????.... | ...*...??????.... |
| ..*....??????.... | .***...??????.... | .*.*....??????... | .**....???????... | *.....????????... |
| .......??????.... | ......???????.... | ..*...????????... | ..*...????????... | ...*..????????... |
| ......????????... | .....??????????.. | .....??????????.. | .**..??????????.. | .**..??????????.. |
| .**..??????????.. | .**..??????????.. | .**..??????????.. | .*...??????????.. | ***..??????????.. |
| *..*.??????????.. | .*??.??????????.. | *...???????????.. | *...???????????.. | **?.???????????.. |
| ...?.??????????.. | .*?????????????.. | .*?????????????.. | .*.????????????.. | ....???????????.. |
| *.*????????????.. | ...????????????.. | ..?????????????.. | ...????????????.. |                   |
| ...????????????.. | ..?????????????.. |                   |                   |                   |
Firstest:
|                   |                   |                   | ...***...*....... | ..***...***...... |
| ..***..**........ | ..*.....*........ | ..*......*....... | .*.......*....... | ..*.*....*....... |
| ..*.**.*..*...... | ..*..****........ | .*********....... | .*.....*.**...... | .**.....***...... |
| ....*............ | .*..**...*....... | .*..**.*.*....... | **............... | ........*........ |
| .***....*.*...... | .***.....*....... | *.......***...... | ***.*..*......... | ...*............. |
| ..*.....*........ | .***.....*....... | .*.*....**.*..... | .**....*...**.... | *......*..***.... |
| ...........*..... | .........****.... | ..*.....**.**.... | ..*.....**.*.*... | ...*...*.*.*.*... |
| ........*.***.... | .......*..*..*... | ............**... | .**....*.*...*... | .**....*.....**.. |
| .**...**...*.**.. | .**....*.*....*.. | .**...**.*.*..*.. | .*......**.*.*... | ***......*....... |
| *..*......*.***.. | .*.*...*.**.*.*.. | *...*....***..... | *...**...*.*..... | **..**...*.*..... |
| ...*....*.*...... | .****....*..*.... | .*.**....*.*.*... | .*...*...*.*..... | ......*....*.*... |
| *.*..*......*.... | .........*....... | ..***........*... | ....*.*.....***.. |                   |
| ..........*.*.... | .....*.......**.. |                   |                   |                   |
Random partial:
|                   |                   |       SS          | ...***...*....... | ..***...***...... |
| ..***..**........ | ..*.....*........ | ..*......*....... | .*.......*....... | ..*.*....*....... |
| ..*.**.*..*...... | ..*..****........ | .*********....... | .*.....*.**...... | .**.....***...... |
| ....*............ | .*..**...*....... | .*..**.*.*....... | **............... | ........*.*...... |
| .***....*.*...... | .***.....*....... | *.......***...... | ***.*...*.*...... | ...*.....***..... |
| ..*.....*........ | .***....*.*...... | .*.*......*...... | .**.......**..... | *..........*..... |
| .........*.*..... | ..........*...... | ..*.......*...... | ..*......**...... | ...*............. |
| ...........*..... | ..........***.... | ..........***.... | .**......**.*.... | .**.........**... |
| .**.........*.... | .**..........*... | .**.......*..*... | .*........*.**... | ***.....*.*.**... |
| *..*.......***... | .**........***... | *.......**....*.. | *.......**....... | **.....*..*.**... |
| .........*....*.. | .*.....******.*.. | .**....*......... | .*.....***...*... | ......**..*.**... |
| *.*...***.*...*.. | .......**.*...... | ......*...*.**... | ...*.**..*..**... |                   |
| .........*....... | ...**..**....*... |                   |                   |                   |
With so many undetermined cells in the "unique" view, the search should be able to get farther than this. It seems like it should at least be able to get to this longer partial result, which is what I used to build the start_file:

Code: Select all

x = 15, y = 27, rule = B3/S23
7bo$6bobo$5b2ob2o$5b2o2bo$9b2o$5b2o$11bo$3bo2bob2o$2b3o3b3o$2bobo4bo$b
2o6b2o$8bobo$3bo$o7b2ob2o$3bo4b3o$b2o5bobo$3o7b3o$2o5b2o4bo$8bobo2bo$
11bo$8bobobo$8bob2o$11b2obo$11b3o$10bo$8bob2o$7b5o!
-Matthias Merzenich
User avatar
DroneBetter
Posts: 139
Joined: December 1st, 2021, 5:16 am
Location: the OEIS headquarters
Contact:

Re: amling search program principles discussion / brain dump

Post by DroneBetter »

amling wrote: February 10th, 2025, 3:24 pm I rigged up the G label weights and @maxpop and pushed it all. Perhaps consider it provisional while we decide if we like it.

Now the original search up-thread can be run as:

Code: Select all

$ rlife llsss-recentering-wao c3-f2b '@maxpop:asym' --max-pop 00:30 --ends none XX
this command seems to break when replacing the speed with a diagonal one, saying

Code: Select all

assertion `left == right` failed
  left: Vec3(1, -1, 0)
 right: Vec3(1, 0, 0)
which changes to

Code: Select all

  left: -1
 right: 0
when using the suffix -down instead of -f2b.

for what it's worth, in particular I would like to know whether the known minpop-60 c/3d in sqrtreprule, xq3_y31u94czx8gs2220o08db8kz6fcjh9e6a21zx1331, is minimal.
miaow
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

DroneBetter wrote: February 26th, 2025, 5:42 am
amling wrote: February 10th, 2025, 3:24 pm I rigged up the G label weights and @maxpop and pushed it all. Perhaps consider it provisional while we decide if we like it.
this command seems to break when replacing the speed with a diagonal one, saying

...

for what it's worth, in particular I would like to know whether the known minpop-60 c/3d in sqrtreprule, xq3_y31u94czx8gs2220o08db8kz6fcjh9e6a21zx1331, is minimal.
The quoted post does say diagonal geometries are not going to work, although there is no particular reason why asymmetric searches couldn't.

I've fixed the code to allow "@maxpop:asym" for any geometry (and just pushed it). The survivors of the asserts you hit have been labelled with "@maxpop:SSS magic grid can only be used with simple orthogonal parallel geometries" where SSS is whatever symmetry was attempted.

Even so I am not sure I would hold out hope for reaching population 60 in reasonable memory. If you can spare the time please do let me know how it goes.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sokwe wrote: February 26th, 2025, 3:30 am I'm having problems with the following search setup:

...

This search stops at w_pos 58, which puts it just about where the start_file ends.

...

With so many undetermined cells in the "unique" view, the search should be able to get farther than this
Thank you for all the details although I'm suspicious you may have edited some of them as the command has no geometry? Nonetheless it is easy enough to reproduce locally.

It ending at the end of the input grid is of course instantly suspicious and this is definitely broken. The short version is you should add 4 more W rows of zeros to the end of the file.

Unfortunately it's a big case of the computer perfectly doing exactly what I told it to do, each part of which seemed like a reasonable decision locally, but which when taken together are silently confusing. Ultimately this was broken when I did the "bg" changes. The old "zero" edge would dump zeros on the end with no regard to context but the new "bg" edge has a more general problem to solve, namely it has to figure out the agar's alignment. This sort of alignment guessing has to be done in a lot of places and the common data they have available to them is an AF1 U row wide by W overlap W row tall block of cell values (2x2 in all generations in common geometries) so this is what they use.

The default edge is "pic:bg" and when this search reaches the end of the grid and the "pic" edge hands it off to the "bg" edge the, last 10 W rows still have nonzero parts and so the "bg" edge silently drops the only edge slice as unextendable for that agar. While this silent drop is not useful to anyone right now, I had envisioned/planned that edges could be handing off to each other more generally, like you might somehow say "even symmetric for ten rows, then bg" and when even hands off to bg, bg would need to silently drop the slices that even produced that don't match bg at their tips.

For this search it's easy: add the missing 4 W rows of zeros so that the hand off works. As for how we help ourselves not get caught by this again, I am not so sure. The parts all have very theoretically-general jobs and so none of them really has enough of the picture to realize the problem.
User avatar
DroneBetter
Posts: 139
Joined: December 1st, 2021, 5:16 am
Location: the OEIS headquarters
Contact:

Re: amling search program principles discussion / brain dump

Post by DroneBetter »

I'm afraid LLSSS in non-floating width mode is not exhaustive for symmetrical diagonals.

My copy (cloned at 2025-02-21) terminates with no spaceships found with the command

Code: Select all

./rlife llsss --rule 'B3/S12' --left-edge odd --filters wcaf c4d-f2b @zero:12
in 75 seconds; the search area is 24 half-diagonals wide, of which 1 is a duplicate to the left of the line of symmetry and 4 are the right margin, leaving logical width 19 and as such total width 37, even though there is a w37 gutter-preserving one, xq4_y7g46331oa1gio048gzy71s08x1q3a2qo18zgoc02204k4i10g933x188508zj90c48g0gg33y2g8704cc2332q903z02g471f0qo9086011tozx121w2y0106v0ggzyb5401, that it discovers in a gutter search. Width 41 also terminates with nothing in 337s, but 45 has xq4_y3qigd85z0c107590cz2s449y3o0gz04d9gwng065pgc54y5ok0kzy2308960444y2ai0o7406zy616c0689eg108915 (which is incidentally the smallest known by population).

How wide-reaching is this and which other categories of width disproof results will need to be recomputed?

also, I would appreciate greatly if diagonal width could specify on the granularity of half- instead of full-diagonals in a future version :mrgreen: thank you
miaow
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

DroneBetter wrote: March 6th, 2025, 1:09 am there is a w37 gutter-preserving one, xq4_y7g46331oa1gio048gzy71s08x1q3a2qo18zgoc02204k4i10g933x188508zj90c48g0gg33y2g8704cc2332q903z02g471f0qo9086011tozx121w2y0106v0ggzyb5401, that it discovers in a gutter search.
This ship is width-47, not width-37. The second ship you posted, found in the width-45 search, is narrower.
-Matthias Merzenich
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

DroneBetter wrote: March 6th, 2025, 1:09 am also, I would appreciate greatly if diagonal width could specify on the granularity of half- instead of full-diagonals in a future version :mrgreen: thank you
Yes, well the diagonal geometries are all a nightmare and I would not count on anything making that better. If you recompile with AF2=5 and use something like raw:1:0:0:-1:-1:4:0:0:1 (U=X, W=T) instead then widths will be in half diagonals although who knows how that geometry will perform. In built-in AF2=3 c4d-f2b you're stuck with U=X-Y which is two half diagonals wide unavoidably. If you were sufficiently dedicated you could draw a constraint file with a half diagonal of forced zeros to make a search effectively one thinner but it would be somewhat manual and you'd have to make the constraint longer than the search without knowing how long that was going to be ahead of time.
Post Reply