Searching algorithms

For general discussion about Conway's Game of Life.
User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Searching algorithms

Post by dvgrn » August 17th, 2015, 9:19 am

simsim314 wrote:I think I have the basic idea how to construct pretty fast integer converter.

For the parity reader, one need to send gliders to collide with SL and leave the SL but will shoot two gliders back. Now one can use this simple fact: in the following gliders position if the distance is even the left reaction will shoot back a glider, if odd the right one... we can shoot glider salvo accordingly to fix the remaining debris.
I haven't thought through all the details, but I think I understand the basic idea here. The metric you're trying to optimize is the number of ticks that it takes to return parity information from a faraway block.

I think that for this particular project, the parity read time is not a very useful quantity to optimize.

The original plan was to simply pull the encoded recipe block back to zero once and feeding the number of pulls, P, into a binary counter. Calcyman's suggestion was to use two push-and-pull SBM registers, and pull the blocks back log2(P) times and use the parity readings after each pull -- which is slower, but you can throw away the binary counter, which is another kind of simplicity. Calcyman's design will almost certainly reduce the value of N, the maximum number of gliders needed to construct anything glider-constructible.

This new proposal appears to add a nightmare tangle of complex circuitry, just to reduce the number of ticks it takes to read a sequence of parities from a given block position. If we're using this time-to-integer converter for the stated purpose of running a universal constructor to glider-construct larger objects, all that circuitry has to be constructed with gliders, which will hugely increase N.

Whatever N turns out to be, there will be no point in using this mechanism to build anything that can be constructed with fewer than N gliders. I'll do some proper estimates later today, but it seems clear that for an encoding of a slow-salvo construction of more than N synchronized gliders -- a Gemini spaceship, say, or very likely an HBK -- the block will be placed a frankly silly distance away as Kazyan says.

Frankly-silly distances are far enough away that in an actual pattern, Golly won't even be able to send a glider to interact with the block in a reasonable amount of time, at least not without a new specialized simulation algorithm. For example, if we could somehow encode the 38,380-glider recipe for an HBK using just one U.C. operation per resulting glider -- an underestimate by several orders of magnitude -- then the block would have to start at a distance of around 2^76760 cells from the U.C.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Searching algorithms

Post by simsim314 » August 17th, 2015, 4:58 pm

As more practical implementation of this approach, we could use static tape instead of remotely located block.

We have all that's needed for this purpose. The real life UC will work as follows:

0. Place a sequence of blocks (instead of single remotely located block) encoding binary operations using parity.
1. Read block parity of the closest block.
2. Shoot a sequence that will move the block out of the way for the next block.
3. Adjust the internal state according to the parity, for slow salvo.
4. Repeat 1.
5. At the end:
- for guns: move back all the blocks.
- for spaceships objects: move the block sequence into the new lane.

NOTE It's also possible to have some "workers" that move the block sequence few lanes toward base, thus increasing the replication speed in cost of design complexity.

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Searching algorithms

Post by chris_c » August 17th, 2015, 8:03 pm

I made a block to binary converter based on 18 p1920 guns. If the least significant bit of the number is 1 then the next glider will leave towards the NE otherwise to the SE. In the end the contraption gets stuck in the loop corresponding to x == 0 with gliders leaving towards the SE every 1920 generations.

The pattern is based on the following reactions that allow detection of the cases x == 0, x == 1 and x > 1:

Code: Select all

x = 174, y = 93, rule = B3/S23
2bo71bo72bo$3b2o70b2o71b2o$2b2o70b2o71b2o5$10bo71bo72bo$11bo71bo72bo$
9b3o69b3o70b3o3$15bo71bo72bo$13bobo69bobo70bobo$14b2o70b2o71b2o4$172b
2o$98b2o72b2o$25b2o71b2o$25b2o62$bo71bo72bo$b2o70b2o71b2o$obo69bobo70b
obo5$16b3o69b3o70b3o$18bo71bo72bo$17bo71bo72bo!
The 18 shotguns break down as: 5 for block detection, 4 for salvo selection, 2 for block copy, 4 (=2x2) for block pull and 3 for block push.

The block in the example below is at distance 341 from "home". 341 has binary representation 101010101 and so the gliders alternate between NE and SE until the final loop is reached.

Code: Select all

x = 1163, y = 1041, rule = B3/S23
1061b2o$1061b2o130$473b2o$474bo$474bobo$475b2o6$474b2o$474b2o4b2o$480b
2o4$479b2o$475b2o2b2o$474bobo$474bo12b2o$473b2o11bobo$486bo$485b2o5$
487b2o$486bobo$486bo$485b2o7$495b2o$495b2o2$502bob2o$502b2obo8$505b2o
5bo$504b3o3bo3bo$501bob2o5bo$501bo2bo4bo5bo$501bob2o9b2o$504b3o$505b2o
4$497b3o2$497bobo$496b5o$495b2o3b2o33b2o$495b2o3b2o34bo$536bobo$537b2o
$498bo$496b2o$459b2o8bo$459b2o6b3o25bo$466bo$451b2o13b2o28bo2bo36b2o$
452bo45b2o36b2o4b2o$452bobo87b2o$453b2o2$460b2o$460b2o79b2o$537b2o2b2o
$536bobo$455bo21bo8b2o48bo12b2o$454bobo20b3o6b2o47b2o11bobo$454b2o24bo
67bo$479b2o13b2o51b2o$494bo$463b2o27bobo$463b2o27b2o$487b2o$487b2o60b
2o$462b2o8bo75bobo$462b2o6b3o75bo$469bo77b2o$454b2o13b2o20bo$455bo34bo
bo$455bobo33b2o$456b2o$461b2o5bo$461b2o4b2o13b2o$467bobo12b2o73b2o$
557b2o2$458bo105bob2o$457bobo104b2obo$457b2o3$466b2o$466b2o3$466b2o98b
o$465bobo96bobo$455b2o7bo11b3o83b2o$455b2o7bo2bo4bo89b2o12b2o$464bo97b
2o12b2o$465bobo4b3o17b2o6b2o62bobo$466b2o5b2o16bo2bo4bo2bo63bo$473b2o
15b6o2b6o$471bobo17bo2bo4bo2bo$472bo10b2o7b2o6b2o57b3o$483bobo73b3o$
483bo74bo3bo$469b2o3b2o$469b2o3b2o81b2o3b2o32b2o$470b5o122bo$471bobo
123bobo$502b2o94b2o$471b3o16b3o2bo5bo3bo$486bo3bo9bo5bo3b2o$484bobo4bo
8bo3bob2o2b2o$476b2o4b2o16bo5bo14b2o8bo$469b2o5b2o4b2o17bo3bo15b2o6b3o
$470bo11b2o18b2o24bo68b2o$467b3o14bobo26b2o13b2o30b2o35b2o4b2o$467bo
18bo27bo45b2o41b2o$514bobo$515b2o$520b2o$520b2o80b2o$598b2o2b2o$597bob
o$597bo12b2o$517bo21bo8b2o46b2o11bobo$516bobo20b3o6b2o59bo$516b2o24bo
65b2o$541b2o13b2o$556bo$525b2o27bobo$525b2o27b2o$610b2o$547b2o60bobo$
524b2o8bo12b2o60bo$524b2o6b3o73b2o$531bo$516b2o13b2o20bo$517bo34bobo$
517bobo33b2o$518b2o2$525b2o17b2o72b2o$525b2o17b2o72b2o2$625bob2o$520bo
104b2obo$519bobo$519b2o15b2o$535b2o$537bo$528b2o$528b2o$791bo$627bobo
159b3o$528b2o96bo2bo4bo153bo49bo$527b3o8bo86b2o5b2o153bobo48b3o$517b2o
5bob2o9bob2o82b2o3bo8b2o149bo52bo$517b2o5bo2bo7b5o85b2o10b2o201b2o$
524bob2o7b3o88bo2bo223bo18bo5b2o12bo$527b3o97bobo156b2o63b3o18b3o3b2o
10b3o$528b2o23bo2bob2obo2bo221b2o62bo24bo13bo$552b2o2bo4bo2b2o284b2o
22b2o13b2o$544b2o7bo2bob2obo2bo56bo$544bobo74bo175b2o$544bo75bobo175bo
25bo11b2o$619b2ob2o174bobo21b3o11b2o25b2o$618bo5bo174b2o20bo41bo7b2o$
621bo199b2o38bobo8bo$531b2o3b2o80b2o3b2o236b2o9bobo$873b2o$532bo3bo14b
3o9b2o$533b3o15bo9bo2bo7bo47bo173bo$533b3o10bo5bo7bo7b2o3bo46bo76bo94b
3o$544b4o12bo6bo5bo8b2o8bo26bo78b2o91bo$538b2o3bobob2o11bo7b5o9b2o6b3o
104b2o92b2o38b2o$531b2o5b2o2bo2bob3o11bo2bo24bo241b2o26b2o$532bo10bobo
b2o14b2o9b2o13b2o30b2o236b2o43b2o$529b3o12b4o27bo45b2o281bo$529bo16bo
28bobo327b3o$576b2o127bo201bo$581b2o123bo$581b2o121b3o93b2o32b2o38b2o$
800b2o11b2o20bo39bo$813bo18b3o37b3o$710bo103b3o15bo39bo$578bo21bo8b2o
97bobo105bo65b2o$577bobo20b3o6b2o98b2o55b2o114b2o$577b2o24bo162b2o20b
2o6b2o$602b2o13b2o169bo7bo$617bo171b3o5b3o$586b2o27bobo134b2o37bo7bo$
586b2o27b2o135b2o2$608b2o$585b2o8bo12b2o170b2o$585b2o6b3o184b2o3b2o
107b2o$592bo140b2o50b2o101b2o4b2o$577b2o13b2o20bo118b2o153b2o$578bo34b
obo$578bobo33b2o170b2o$579b2o199b2o4bo$584b2o194b2o5b3o99b2o$584b2o19b
2o182bo99b2o2b2o$605b2o286bobo$769b2o110b2o12bo$769bobo109bobo11b2o$
581bo189bo111bo$580bobo188b2o110b2o$580b2o2$747bo$589b2o155bobo$589b2o
155b2o133b2o$881bobo$763b2o118bo$589b2o172bo58bo60b2o$588bobo14b2o157b
3o55b3o$578b2o7b3o15bobo158bo58bo$578b2o6b3o16bo154b2o62b2o$587b3o5bo
158b2o4bo58bo$588bobo4bobo17b2o6b2o129b2o5b3o53b3o$589b2o7bo14bo4bo2bo
4bo136bo52bo$613bo4bo2bo4bo189b2o55b2o$596b2o15bo4bo2bo4bo179b2o56b2o
7b2o$595bo10b2o7b2o6b2o182bo57bo$605b2o200bobo55bobo$607bo200b2o4b2o
44b2o4b2o$592b2o3b2o214bo2bo44bo20b2o$595bo218b2o45bobo18bo$592bo5bo
227b2o34b2o16bobo$593b2ob2o228b2o52b2o$594bobo17bo10bo$595bo17b2o9b2o$
595bo12bo4bobo7b2o4b2o2b2o$606bobo13b3o4b2o2b2o$599b2o4bobo15b2o4b2o$
592b2o5b2o3bo2bo16b2o$593bo11bobo17bo$590b3o13bobo203b2o3b2o32b2o$590b
o17bo204bo3bo20b2o11b2o$810b3o5b3o18bo$810bo9bo15b3o35b2o$836bo37b2o2b
2o$878bobo$880bo$880b2o80$696bo$696b2o$695bobo5$711b3o$713bo$712bo30$
376bo21bo$376b3o18bobo$379bo16bo3b2o6b2o$378b2o5b2o9bo3bob2o4bobo$385b
2o9bo3bob3o4b3o$397bobob2o2bo4b3o6b2o$398bo4b2o4b3o7b2o$408bobo$408b2o
2$378b2obob2o10bo$395bobo$378bo5bo10b2o2$379b2ob2o$381bo$400bo2bob2obo
2bo$388bo11b4ob2ob4o$373b2o12bo12bo2bob2obo2bo$366b3o4b2o12b3o$365b5o
6b2o$364bobo3bo5b3o$364b2o3bo6b2o8b2o$373b2o11b2o$373b2o3$375b2o$375b
2o3$366b2o$366bobo$367bo3$372b2o17b2o$372b2o17b2o2$365b2o$364bobo33b2o
$364bo34bobo$363b2o13b2o20bo$378bo$371b2o6b3o$371b2o8bo$396b2o$396b2o$
372b2o27b2o$372b2o27bobo$403bo$388b2o13b2o$363b2o24bo$363bobo20b3o6b2o
$364bo21bo8b2o4$367b2o$367b2o$362b2o$361bobo$361bo45b2o$360b2o13b2o30b
2o$375bo$368b2o6b3o$368b2o8bo2$407bo$405b2ob2o2$404bo5bo2$316bo19bo67b
2obob2o$316b3o17bobo$319bo19b2o6b2o$318b2o5b2o12b2o4bo3bo$325b2o12b2o
3bo5bo$336bobo4b2obo3bo8b2o$336bo7bo5bo8b2o$345bo3bo63bobo$347b2o64bo
3bo$318b2o3b2o5b2o5bo79bo5b2o$318b2o3b2o5b2o3b2o76bo4bo4b2o$319b5o4bo
7b2o79bo$320bobo5bo84bo3bo$399b2o12bobo$320b3o6b2obo$330bobo8b2o6b2o$
331bo2bo5bo2bo4bo2bo$332bo6b6o2b6o$313b2o17b3o5bo2bo4bo2bo$313bobo14b
2o9b2o6b2o53bo$308b2o6bo13b3o69b4o$304b2obo2bo2bo2bo14bo69b2o3bo4b2obo
$304b2o2b2o6bo84b5o5bob2o$313bobo87b2o$313b2o89bo$404bo2$315b2o$315b2o
3$306b2o$306bobo85b2o$307bo87bo$395bobo$396b2o$331b2o$310b2o19b2o$310b
2o$305b2o$304bobo33b2o52b2o$304bo34bobo53bo$303b2o13b2o20bo41b2o11bobo
$318bo64bo12b2o$311b2o6b3o61bobo$311b2o8bo12b2o48b2o2b2o$334b2o52b2o2$
312b2o27b2o$312b2o27bobo$343bo45b2o$328b2o13b2o38b2o4b2o$303b2o24bo53b
2o$303bobo20b3o6b2o$304bo21bo8b2o4$307b2o75b2o$307b2o74bobo$302b2o79bo
$301bobo78b2o$301bo45b2o$300b2o13b2o30b2o$315bo414b2o$308b2o6b3o411b2o
$308b2o8bo2$653b2o$346b3o304b2o76bo$730bobo$346bobo380bo3bo$345b5o380b
3o$344b2o3b2o377b2o3b2o$344b2o3b2o391b2o$653bo89bo$652b3o9b3o75bo$347b
o304b3o9b3o75b2o$345b2o318bo53bo$219bo17b2o411b2o3b2o8bo51bobo$219b3o
15bobo104bo7b2o296b2o3b2o8bo44b2o4bobo289bo$222bo9b2o4b3o12bo90bo7b3o
309bobo43b2o3bo2bo288b2o$221b2o5b4o2bo4b3o8b4o4bo89bo5b2obo5b2o351bobo
288bobo$222b3o3b3ob2o4b3o8b4o5bo86bo8bo2bo5b2o287b2o63bobo25b2o$223bob
o11bobo9bo2bo9b2o83b2o5b2obo46b2o246bobo9bobo32bo19bo25b2o268b2o$222bo
3bo10b2o10b4o9b2o88b3o50b2o244bo2b2o9bo31b3o315bobo$222b5o14bo8b4o98b
2o50bo248b2o10bo30bo318bo$221b2o3b2o12bo12bo399b2o10bo22b2o6b2o$222b5o
13b3o411bo9b3o21bobo$223b3o438b3o22bo$224bo423bo5bo38b4o$648bo5bo38b3o
bo57b2o6b2o$649bo3bo6bo33b2o5b2o53bo7bo$650b3o5bobo3b2o35b2o50b3o5b3o$
233bo117b2obo304b2o3b2o87bo7bo$233bobo10bo4bo99bob2o309b2o$233b2o9b2ob
4ob2o415b2o13b2o$217bo28bo4bo92b2o314bo7bobo13b2o$215bobo126b2o313b3o
7bo101b2o$213b2o443b2ob2o36b2o65b2o3b2o$207b2o4b2o484bobo64b2o$207b2o
4b2o486bo$215bobo14bobo416b2o48b2o$217bo14b2o417b2o112b2o12b2o$233bo
426bo105bo5b2o5bo$334b2o324bobo100b3o6b2o6b3o$218b2o115bo325bobo99bo
18bo$218b2o115bobo323bo2bo27b2o4bobo$336b2o323bobo28bo6b2o$650b2o8bobo
6bo20bobo6bo$209b2o438bobo8bo8bo20b2o21b2o$209bobo437bo18bobo42bo$210b
o437b2o17b2ob2o3b2o34bobo$334b2o330bo5bo2b2o34b2o$335bo333bo$234b2o86b
2o11bobo328b2o3b2o23b2o$213b2o19b2o87bo12b2o354b2o2b2o$213b2o108bobo
359b2o5b2o$208b2o114b2o2b2o338bo16b2o18b2o$207bobo33b2o83b2o338bo36b2o
6b2o$207bo34bobo422bo12bo32b2o$206b2o13b2o20bo435bobo$221bo306b2o149b
2o6b2o$214b2o6b3o104b2o197b2o139b2o16bo13bo$214b2o8bo12b2o84b2o4b2o
338b2o17b3o9bobo$237b2o84b2o365bo9b2o6b2o$605b2o101bo$215b2o27b2o359b
2o102b3o$215b2o27bobo464bo$246bo595b2o$231b2o13b2o594b2o$206b2o24bo91b
2o281b2o$206bobo20b3o6b2o83bobo190b2o10bo$207bo21bo8b2o83bo192bo10b3o
235b2o$322b2o193bo8b5o232bo2bo$516b2o7b2o3b2o$526b5o5bo57bo8b2o3b2o
152bo$210b2o314bo3bo3b4o56bo9b5o$210b2o315bobo3bobob2o9b2o43bobo8b2ob
2o154b2o$205b2o140b3o178bo3bo2bob3o8b2o44bo9b2ob2o156bo88b2o$204bobo
142bo183bobob2o55bo10b3o169bo77bo$204bo45b2o96bo164b2o19b4o56bo181bobo
62b5o8bo$203b2o13b2o30b2o76b2o183b2o21bo23bo33bo167b2o3b2o71bob3obo7b
2o$218bo108bobo230b3o30bobo166b2o3b2o66bo5bo3bo$211b2o6b3o107bo233bo
30bo168b5o8b3o55bobo5b3o33b2o$211b2o8bo128b2o210b2o6b2o22bo169bobo9b3o
43b2o10b2obo5bo34bob2o$349bobo217bobo205bo44b2o10b2ob2o42bo$351bo218bo
31bo161b3o67b2obo41bobo$602bobo3bo225bobo20b2o15bobo2b2o$327bo167b2o6b
2o59b2o36b2o3b3o167bo33bo23bo21b2o15b2o$327b2o166bo7bo53b2o5b2o40b5o
165b3o30b3o63bo161b2o$153bo18bobo75bo75bobo167b3o5b3o50b2o34b2o10bobob
obo164b3o29bo228b2o$153b3o15bo2bo74b3o82bo163bo7bo86b2o10b2o3b2o188b2o
6b2o$156bo13b2o10bo6bo58b5o81b2o432bo31bobo$155b2o5b2o4b2o3bo8bo5bobo
56b2o3b2o79bobo238b2o193bo6bobo22bo158b2o$162b2o6b2o9bo6b2obo56b5o321b
2o32bo158b3o7bo182b2o75b3o$171bo2bo2b2o9b2ob2o3b2o50bo3bo234b2o118bobo
153bo42b2o59b2o6b2o160b3o$172bobo2bo2b3o5b2obo4b2o51bobo235b2o3b2o65b
2o46bobo152b3o41b2o5b2o53bo7bo159bo3bo$177b4o7bobo59bo241b2o64bobo47bo
152b5o9bob2obo32b2o50b3o5b3o159bo5bo$158bo19b2o9bo64bo303bo48b2o151b2o
3b2o8bobo3bo83bo7bo162bo3bo$157b3o92b4o301b2o48b2o351bo76b3o9b2o$156b
5o90bobob2o9b2o211b2o12b2o112b2o173bo13b2o162bo11bo77bo$155bobobobo88b
o2bob3o8b2o212bo5b2o5bo109bo177bo14b2o161bobo10bo76bo$155b2o3b2o9bo79b
obob2o220b3o6b2o6b3o105b4o156b3o118b2o73b2ob2o86b2o$169b2o11b2o68b4o
221bo18bo104b2obobo155b3o46b2o65b2o3b2o72bo5bo8bo52bo$170b2o8bo4bo68bo
311b2o32b3obo2bo203bobo64b2o80bo10bobo50bobo$158bo20bo6bo380bo33b2obob
2o205bo143b2o3b2o53b2o3b2o3bo$157bobo18bo8bo379bobo32b4ob3o153b2o48b2o
156b3o43b2o3b2o3bo$157bobo18bo8bo357b2o21b2o33bo4bobo152b2o112b2o12b2o
129b2o3bo$154bo3bo19bo8bo358bo63bo157bo109bo5b2o5bo66b4o62bobo25b2o$
153b5o21bo6bo359bobo34b2o25b2o155bobo105b3o6b2o6b3o63bo2b2o8b3o32bo18b
o26b2o$152b2obobo4bobo15bo4bo361b2o34b2o181bob2o105bo18bo64bob2o41b3o$
141b2o8b3obo2bo3b2o18b2o403b2o3b2o171b2ob2o34b2o165bobo29bo$141b2o9b2o
bobo5bo90b2obo304b2o10b2o190bob2o34bo155b2o10bo22b2o6b2o$153b4o97bob2o
304b2o2b2o6b2o12bo3bo169b2o3bobo32bobo156bo33bobo$154bo411b2o21b3o169b
obo4bo33b2o21b2o145bo23bo$247b2o304b2o34b3o169bo63bo146bo$247b2o296b2o
6b2o205b2o25b2o34bobo129b2obob2o100b2o6b2o$152b2o8bo382b2o32bo198b2o3b
2o2b2o34b2o130bo5bo5bo40b2o53bo7bo$152b2o7bo416bobo198b5o172bo3bo7bo
31b2o6b2o50b3o5b3o$161b3o407b2o6b2o198b2ob2o12b2o10b2o147b3o6b3o31b2o
58bo7bo$558bo13bo16b2o188b2ob2o12b2o6b2o2b2o$143b2o412bobo9b3o17b2o
189b3o21b2o185b2o$143bobo404b2o6b2o9bo421b2o$144bo92b2o205b2o105bo273b
2o251b2o$238bo205b2o102b3o241bo25b2o5b2o179b2o65b2o3b2o$238bobo307bo
242bobo24b2o155bo30bobo64b2o$149b2o17b2o69b2o550b2o6b2o172bobo5bobo24b
o$149b2o17b2o351b2o258b2o16bo13bo144b2o14b2o6b2o24b2o$521b2o258b2o17b
3o9bobo143b2o22bo89b2o12b2o$142b2o658bo9b2o6b2o146bo104bo5b2o5bo$141bo
bo33b2o641bo146bobo100b3o6b2o6b3o$141bo34bobo58b2o582b3o142bo3b2o98bo
18bo$140b2o13b2o20bo60bo204b3o377bo142bo3b2o27b2o$155bo69b2o11bobo191b
2o8bo3bo519bo3b2o27bo$148b2o6b3o67bo12b2o191bo8bo5bo509b2o8bobo6bo20bo
bo$148b2o8bo12b2o53bobo204bo7b2obob2o508bobo9bo5b2ob2o18b2o21b2o$171b
2o54b2o2b2o199b2o522bo63bo$231b2o220b2o55bo444b2o16bo5bo2b2o34bobo$
149b2o27b2o264bo8bobo53b3o470b2o34b2o$149b2o27bobo262bobo2b2o6bo7b2o
42b2ob2o6b2o3b2o447b2obob2o$180bo262bobobo2bo2bo2bo7b2o41b3ob3o7b3o
479b2o$165b2o13b2o50b2o34b2o174bo3b2o6bo50b3ob3o6bo3bo474b2o2b2o$140b
2o24bo59b2o4b2o33bobo159b2o22bobo51b3ob3o7bobo468b2o5b2o$140bobo20b3o
6b2o52b2o41bo159b2o22b2o21bo30b3ob3o8bo469b2o$141bo21bo8b2o302b3o29b2o
b2o507b2o$479bo29b3o475bo25b2o5b2o$478b2o6b2o22bo475bobo24b2o$485bobo
498b2o6b2o$144b2o121bo218bo36b3o450b2o16bo13bo$144b2o81b2o38b2o241bo6b
obo456b2o17b3o9bobo$139b2o85bobo37bobo142b2o6b2o88bo7b2o4bobo471bo9b2o
6b2o$138bobo85bo184bo7bo53b2o34b3o6bo3b5o488bo$138bo45b2o39b2o185b3o5b
3o50b2o6b2o38b2o3b2o488b3o$137b2o13b2o30b2o228bo7bo58b2o38b2o3b2o490bo
$152bo31b2o$82bo20bo41b2o6b3o28bo305b2o$82b3o18bobo39b2o8bo27bobo304b
2o32bo$85bo18bobo7bo68bobo217b2o120b2o$84b2o5b2o11bo2bo6b2o68bo218b2o
3b2o65b2o$91b2o11bobo2b2o4b2o291b2o64bobo50bo$103bobo3b2o4b3o7b2o347bo
$103bo5b2o4b2o8b2o54b2o3b2o285b2o48bo2bo$114b2o65bobobobo207b2o12b2o
112b2o$114bo67b5o209bo5b2o5bo107b2o$84b2o3b2o11bo80b3o207b3o6b2o6b3o
103bobo$87bo13bo82bo208bo18bo102bo$84bo5bo10b3o378b2o31bo2bo591b2o$85b
2ob2o393bo31bo594b2o$86bobo394bobo30bobo5b2o$87bo373b2o21b2o31b2o5bobo
$87bo19b2o6b2o74b2o269bo63bo506b2o$105bo4bo2bo4bo71bobo269bobo34b2o25b
2o505b2o$94bo10bo4bo2bo4bo70b3o4b2ob3o261b2o34b2o$79b2o13bobo8bo4bo2bo
4bo69b3o4bo2b4o303b3o602b3o$79bobo12b2o11b2o6b2o72b3o4b2o280b2o24bo3bo
$74b2o4b3o107bobo285b2o2b2o19bo5bo600bobo$70b4o2bo4b3o107b2o289b2o5b2o
13bo3bo600b5o8b2o$70b3ob2o4b3o8b3o375b2o18b2o14b3o600b2o3b2o8bo$79bobo
379b2o6b2o34b3o537bo62b2o3b2o7bo$79b2o380b2o32bo548b3o75b2o$494bobo
535b3o8bobobo53b2o$487b2o6b2o534bo3bo7bobobo52b3o$81b2o391bo13bo16b2o
523bo5bo7b3o43b2o5bob2o9bobo$81b2o390bobo9b3o17b2o523bo5bo8bo44b2o5bo
2bo4bo6bo$188b2obo102b2o170b2o6b2o9bo547bo63bob2o5bo$188bob2o102b2o
171bo563bo3bo64b3o3bo4bo13b2o$72b2o390b3o565b3o10bo33bo21b2o5b2o15b2o$
72bobo106b2o281bo568bo10b3o30b3o$73bo8bo98b2o188b2o670bobobo28bo$81b3o
287b2o670bobobo20b2o6b2o$80b5o945b3o11b3o21bobo$79b2o3b2o11b2o931b3o
12bo23bo$78b3o3b3o10b2o930bo3bo$79b2o3b2o287b2o662bobo95b2o6b2o$71b2o
7b5o197b2o10bo733b2o3b2o3b2o41b2o53bo7bo$70bobo8b3o22b2o63b2o109bo10b
3o742bo34b2o6b2o50b3o5b3o$70bo11b3o20bobo64bo110bo8b5o776b2o58bo7bo$
69b2o13b2o20bo65bobo107b2o7b2o3b2o$84bo88b2o117b5o5bo57bo8b2o3b2o688b
2o$77b2o6b3o204bo3bo3b4o56bo9b5o689b2o$77b2o8bo12b2o191bobo3bobob2o9b
2o43bobo8b2ob2o670bo105b2o$100b2o192bo3bo2bob3o8b2o44bo9b2ob2o671b2o
31b2o65b2o3b2o$299bobob2o55bo10b3o671b2o32bobo64b2o$78b2o27b2o62b2o
106b2o19b4o56bo689b2o17b2o10bo$78b2o27bobo62bo106b2o21bo23bo33bo670b2o
17b2o16bobo10b2o$109bo49b2o11bobo151b3o30bobo669b2o37bo74b2o12b2o$94b
2o13b2o49bo12b2o154bo30bo676b2o107bo5b2o5bo$69b2o24bo64bobo165b2o6b2o
22bo676b3o103b3o6b2o6b3o$69bobo20b3o6b2o58b2o2b2o168bobo701b2obo100bo
18bo$70bo21bo8b2o62b2o169bo31bo670bo2bo29b2o$368bobo3bo664b2obo29bo$
261b2o6b2o97b2o3b3o654b2o5b3o30bobo$261bo7bo53b2o47b5o652bobo5b2o31b2o
21b2o$73b2o91b2o94b3o5b3o50b2o6b2o38bobobobo651bo63bo$73b2o85b2o4b2o
96bo7bo58b2o38b2o3b2o650b2o18b3o4b2o34bobo$68b2o90b2o885bo3bo3b2o34b2o
$67bobo270b2o17b3o684bo5bo12b2o$67bo45b2o225b2o17bo4bobo7bo671b2obob2o
23b2o$66b2o13b2o30b2o138b2o104bo2bo3bo6bobo696b2o2b2o$81bo171b2o3b2o
65b2o33bobo3bo6bobo691b2o3b2o$74b2o6b3o173b2o64bobo34b2ob2o8bo674bo17b
2o$74b2o8bo76b2o161bo48b2o673bobo12b3o27b2o$160bobo160b2o48b2o673bobo
9bo25b2o5b2o$113bo46bo84b2o12b2o112b2o674bo9bobo24b2o$113bo45b2o85bo5b
2o5bo109bo689b2o6b2o$112bobo128b3o6b2o6b3o105b4o677b2o16bo13bo$111b2ob
2o127bo18bo104b2obobo676b2o17b3o9bobo$16bo16b2o75bo5bo215b2o32b3obo2bo
696bo9b2o6b2o$16b3o12bo3bo77bo219bo33b2obob2o714bo$19bo10bo5bo13b2o58b
2o3b2o216bobo32b4ob3o713b3o$18b2o5b2o2b2obo3bo13b2o4b3o252b2o21b2o33bo
4bobo714bo$25b2o3bo5bo10b2o6b5o252bo63bo$21bo9bo3bo10b3o5bo3bobo51bo
199bobo34b2o25b2o$20bobo10b2o12b2o6bo3b2o51bo200b2o34b2o$19bo3bo14bobo
9b2o59bo241b2o3b2o$20b3o15b2o10b2o66bobo207b2o10b2o$18b2o3b2o14bo78bo
2bo206b2o2b2o6b2o12bo3bo$121b2o6b2o201b2o21b3o$113b2o4bo3b2o4b2o224b3o
$121b2o188b2o$118bo2bo189b2o5b2o25bo$32bo85bobo197b2o24bobo$30b2o305b
2o6b2o$31b2o6b2o3bo2bo3b2o271bo13bo16b2o$39b5o4b5o270bobo9b3o17b2o$14b
obo22b2o3bo2bo3b2o263b2o6b2o9bo$13bo2bo300bo$12b2o300b3o$4b2o4b2o3bo
298bo$4b2o6b2o12b2o89b2obo$13bo2bo9b2o89bob2o$14bobo$110b2o$110b2o$15b
2o$15b2o3$6b2o$6bobo$7bo92b2o107b2o$101bo107b2o$101bobo$12b2o17b2o69b
2o$12b2o17b2o253b2o$286b2o$5b2o$4bobo33b2o$4bo34bobo58b2o106b3o$3b2o
13b2o20bo60bo105bo3bo$18bo69b2o11bobo93b2o$11b2o6b3o67bo12b2o93bo8bo5b
o$11b2o8bo67bobo106bo7b2o3b2o$36b2o52b2o2b2o101b2o76bo$36b2o56b2o122b
2o54b3o$12b2o27b2o166b2o7bo2bo51b5o8b3o$12b2o27bobo164bo4b2o7bo6b2o54b
o3bo$43bo164bo6bo6bo6b2o53bo5bo$28b2o13b2o50b2o112b6o7bo62bo3bo$3b2o
24bo59b2o4b2o97b2o22bo2bo64b3o$3bobo20b3o6b2o52b2o103b2o22b2o21bo44b3o
$4bo21bo8b2o204b3o$244bo28b5o$243b2o6b2o21b3o$9b2o239bobo22bo$9b2o240b
o36b3o$90b2o191bo3b2ob2o$2b2o85bobo84b2o6b2o59b2o34b2o4b2ob2o$bobo85bo
86bo7bo53b2o5b2o35b2o3b5o$bo45b2o39b2o87b3o5b3o50b2o34b2o10b2o3b2o$2o
13b2o30b2o130bo7bo86b2o$15bo$8b2o6b3o236b2o$8b2o8bo236b2o$168b2o120b2o
$168b2o3b2o65b2o$173b2o64bobo$239bo$238b2o48b2o$160b2o12b2o112b2o$161b
o5b2o5bo107b2o$44b2o3b2o107b3o6b2o6b3o102bo2bo$46b3o109bo18bo101bo$45b
o3bo197b2o30bo$46bobo199bo30bo$47bo200bobo29bo2bo5b2o$226b2o21b2o31b2o
5bobo$52bo174bo63bo$50bobo174bobo5bo28b2o25b2o$49bobo11b2o163b2o4bo29b
2o4b3o$48bo2bo11b2o169b3o32bo3bo$49bobo191b2o23bo5bo$50bobo190b2o2b2o
19bo5bo$52bo194b2o5b2o15bo$254b2o13bo3bo$226b2o42b3o$226b2o5b2o25bo10b
o$233b2o24bobo$252b2o6b2o$239bo13bo16b2o$238bobo9b3o17b2o$51b2obo176b
2o6b2o9bo$51bob2o177bo$229b3o$44b2o183bo$44b2o4$140b2o$140b2o2$34b2o$
35bo181b2o$35bobo179b2o$36b2o$140bo$139b3o$139b3o$128b2o$34b2o92bo8b2o
3b2o$35bo93bo7b2o3b2o$22b2o11bobo90b2o75b3o$23bo12b2o111b2o53bo3bo9bo$
23bobo114bo8b2o53bo3bo8b3o$24b2o2b2o109bo5bo6b2o6b2o43b3o8b5o$28b2o
109bob2o3bo5b3o5b2o53b2o3b2o$140b6o6b2o62b5o$125b2o14b4o4b2o65bo3bo$
125b2o22b2o21bo44bobo$29b2o141b3o30b3o10bo$23b2o4b2o144bo28bo3bo$23b2o
149b2o6b2o20bo3bo$181bobo21b3o12bo$182bo35b2ob2o$213bo$107b2o6b2o59b2o
34bo4bo5bo$107bo7bo53b2o5b2o34b3o$24b2o82b3o5b3o50b2o46b2obob2o$23bobo
84bo7bo$23bo$22b2o162b2o$186b2o$99b2o104bo$99b2o3b2o65b2o32bobo$104b2o
64bobo32b2o$170bo30b2o$169b2o29bobo16b2o$91b2o12b2o94bo17b2o$92bo5b2o
5bo107b2o$89b3o6b2o6b3o104b2o$89bo18bo82bo18b2o$178b2o9b2o18b3o$179bo
10b2o18b2o$179bobo31b2o5b2o$157b2o21b2o31b2o5bobo$158bo63bo$158bobo34b
2o5bo19b2o$159b2o34b2o4b3o$200b5o$174b2o10b2o11b2o3b2o$174b2o2b2o6b2o$
178b2o$165b2o$157b2o6b2o34b3o$157b2o32bo9b3o$190bobo$183b2o6b2o$170bo
13bo16b2o$169bobo9b3o17b2o$162b2o6b2o9bo$163bo$160b3o$160bo!

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

Re: Searching algorithms

Post by dvgrn » August 17th, 2015, 8:25 pm

simsim314 wrote:As more practical implementation of this approach, we could use static tape instead of remotely located block.
OK, now I'm definitely a little confused. Seems as if the topic was originally a universal universal constructor with a fixed number of cells:
simsim314 wrote:EDIT2 This is pretty amazing - constant cells universal constructor (meaning one can encode caterpillar using around few K cells).
But as soon as you're encoding recipes on a static tape, you've lost the constant-cells property.

Also, once you allow a static tape, why not allow multiple object types, for higher-density information storage?

Then it doesn't seem like a very big step to have a static tape that's really a freeze-dried salvo... which brings back the possibility of encoding relative timings directly on the tape.

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

Re: Searching algorithms

Post by dvgrn » August 18th, 2015, 9:34 pm

An interesting question for the U.C. stage of the fixed-number-of-gliders Constructor of Everything Constructible:

To my knowledge there has never been an optimized design for a single-arm universal constructor, where the thing to be minimized is the number of different glider locations in the combined PUSH/PULL/WHITE/BLACK glider salvos.

The closest approach was Paul Chapman's prototype Spartan universal constructor -- but we really didn't spend any time searching for the best combination of gliders. It was a prototype, so we just took the first thing that worked and ran with it. Here's what it looks like:

Send green gliders: PUSH
Send green & white gliders: PULL
Send green & yellow gliders: G0 (i.e., fire glider of parity 0, on black checkerboard squares)
Send green & red gliders: G1 (parity 1, a.k.a. white checkerboared squares)

Code: Select all

x = 38, y = 27, rule = LifeHistory
23.2E$22.E.E$24.E7.2A$31.A.A2.2C$33.A2.2C$21.D$21.2D$20.D.D$26.C$26.
2C3.A$25.C.C3.2A$30.A.A2$16.D$16.2D$15.D.D9$3E$2.E$.E!
[[ VIEWONLY THUMBNAIL ]]
The PUSH and PULL combination with just three gliders seems pretty lucky, but the others are just what could be found by hand with a small amount of effort. Seems as if there's sure to be something more efficient out there: a set of K gliders, where some subset does a PUSH(n), another subset does a PULL(m) with m relatively prime to n, another subset that does any PUSH or PULL operation plus a G0 glider, and a last subset that does any (the same or different) PUSH or PULL plus a G1 glider in the same direction.

A solution with K=6 gliders seems like a sure thing; K=5 seems like a fairly good bet, and K=4 is theoretically possible but I wouldn't expect to be that lucky. One obvious place to look is sets of gliders starting with a two-glider DEC3 consisting of two block pulls. The second of the two gliders retains a degree of freedom, so then it's a matter of picking a useful placement for that glider, and looking for third and fourth glider locations that allow subset salvos that produce clean sideways gliders.

Kazyan pointed out that a universal constructor is most likely still universal even if it can only fire P1 monochromatic salvos. If we can prove that, then we can get away with only PUSH, PULL, and G0 (or G1) operations, and we could use a blinker as an elbow instead of a block. This opens up another pair of gliders to start a search from, again with a degree of freedom to play with -- this time a PULL2:

Code: Select all

x = 10, y = 9, rule = LifeHistory
7.3C4$6.3C$8.C$.2C4.C$C.C$2.C!
With only three operations needed instead of four, K=4 starts looking a lot more likely, and K=3 becomes the unbelievably unlikely possibility.

In general, the lower a value of K we can get, the less circuitry we'll need to build a complete universal constructor connected to a sliding-block memory, and the lower N will turn out to be for the N-glider maximum needed for any glider construction.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Searching algorithms

Post by praosylen » August 19th, 2015, 8:45 am

If it doesn't matter how efficient the salvo encoding is, then it seems like we don't need a push1 and a pull1 to access every glider lane possible, only a relatively prime pair of distances. So couldn't we open up a new degree of freedom in our search by using a version of the trivial pull3, along with whatever non-multiple-of-three push is most convenient?
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

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

Re: Searching algorithms

Post by dvgrn » August 19th, 2015, 10:37 am

A for awesome wrote:If it doesn't matter how efficient the salvo encoding is, then it seems like we don't need a push1 and a pull1 to access every glider lane possible, only a relatively prime pair of distances. So couldn't we open up a new degree of freedom in our search by using a version of the trivial pull3, along with whatever non-multiple-of-three push is most convenient?
Exactly. Or if we try using a blinker elbow, a version of the trivial PULL2. That's a lot of options to search through, especially if we only need one clean glider-output reaction where it doesn't matter how the elbow moves.

(My messages must be getting too high on the TL;DR scale again. I'm doing better with this post...)

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Searching algorithms

Post by chris_c » August 19th, 2015, 12:02 pm

Actually it was fairly easy to make a base 3 converter instead of binary. After that I plonked down some fairly brain-dead p1920 circuitry and that should be enough to make a block to P1 monochromatic salvo converter (EDIT: I mean slow salvo of course).

In the example below the block is 140 steps from home and the output sequence is Pull, Fire, Push, Pull, Fire, Push, Push, Push, Push, .... since 140 = 0000000012012 in base 3.

Code: Select all

x = 2448, y = 2077, rule = B3/S23
384b2o$385bo$385bobo$386b2o6$385b2o$385b2o4b2o$391b2o4$390b2o$386b2o2b
2o$385bobo$385bo12b2o$384b2o11bobo$397bo$396b2o5$398b2o$397bobo$397bo$
396b2o7$406b2o$406b2o2$413bob2o$413b2obo5$896b2o$897bo$897bobo5bo$415b
obo480b2o4bobo$415bo3bo483bob2o$419bo482b2ob2o10b2o$415bo4bo4b2o476bob
2o10b2o$419bo5b2o477bobo$415bo3bo485bo$415bobo7$406b2obob2o$446b2o$
406bo5bo34bo$447bobo$407b2ob2o36b2o$409bo2$370b2o8bo$370b2o6b3o$377bo$
362b2o13b2o30b2o36b2o321b2o$363bo45b2o36b2o4b2o315b2o$363bobo87b2o$
364b2o2$371b2o$371b2o79b2o$448b2o2b2o$447bobo$366bo21bo8b2o48bo12b2o$
365bobo20b3o6b2o47b2o11bobo$365b2o24bo67bo$390b2o13b2o51b2o$405bo$374b
2o27bobo$374b2o27b2o$398b2o$398b2o60b2o$373b2o8bo75bobo$373b2o6b3o75bo
$380bo77b2o$365b2o13b2o20bo$366bo34bobo$366bobo33b2o$367b2o$372b2o$
372b2o19b2o$393b2o73b2o$382bo85b2o$381b2o$369bo11bobo91bob2o$368bobo
104b2obo$368b2o3$377b2o$377b2o3$375b2o103bo$375b2o11bo90bobo$366b2o3bo
6b2o7bobo88bo3b2o$366bobo3bo5b3o97bo3b2o3b2o$367b5o6b2o8bo2bo86bo3b2o
3b2o$368b3o4b2o14bo87bobo$375b2o12bo12bo2bob2obo2bo66bo$390bo11b4ob2ob
4o$402bo2bob2obo2bo$383bo$381b2ob2o2$380bo5bo10b2o$397bobo107b2o$380b
2obob2o10bo72b3o35bo$469bo3bo34bobo$410b2o56bo5bo34b2o$410bobo56bo3bo$
400bo4b2o4b3o7b2o47b3o$399bobob2o2bo4b3o6b2o47b3o$387b2o9bo3bob3o4b3o
18b2o8bo$380b2o5b2o9bo3bob2o4bobo19b2o6b3o$381bo16bo3b2o6b2o27bo68b2o$
378b3o18bobo22b2o13b2o30b2o35b2o4b2o$378bo21bo24bo45b2o41b2o$425bobo$
426b2o$431b2o$431b2o80b2o$509b2o2b2o$508bobo$508bo12b2o$428bo21bo8b2o
46b2o11bobo$427bobo20b3o6b2o59bo$427b2o24bo65b2o$452b2o13b2o$467bo$
436b2o27bobo$436b2o27b2o$521b2o$458b2o60bobo$435b2o8bo12b2o60bo$435b2o
6b3o73b2o$442bo$427b2o13b2o20bo$428bo34bobo$428bobo33b2o$429b2o2$436b
2o17b2o72b2o$436b2o17b2o72b2o2$536bob2o$431bo104b2obo$430bobo$430b2o3$
439b2o9b2o$439b2o8b2o$451bo$539bo161bo$438bobo98bobo157b3o$438bo3bo99b
2o154bo49bo$428b2o12bo99b2o4b2o147bobo48b3o$428b2o8bo4bo98b2o4b2o148bo
52bo$442bo7b3o86bobo208b2o$438bo3bo7bo88bo223bo18bo5b2o12bo$438bobo10b
o14bobo2bobo222b2o63b3o18b3o3b2o10b3o$462b2obo2bo2bo2bob2o218b2o62bo
24bo13bo$444b3o19bobo2bobo286b2o22b2o13b2o$444b3o$443bo3bo259b2o$442bo
5bo9b2o248bo25bo11b2o$443bo3bo10bobo247bobo21b3o11b2o25b2o$444b3o11bo
70b2o3b2o173b2o20bo41bo7b2o$731b2o38bobo8bo$530bo3bo70bo165b2o9bobo$
472bobo56b3o72b2o175b2o$467b2o3bo2bo55b3o71b2o$460b2o2b2ob3o5b2o6b2o
219bo$459bobo3bo3bo3bo3b2o4b2o8b2o8bo198b3o$449b2o7bo8bobo5b2o16b2o6b
3o197bo$442b2o5b2o7bo2bo6b2o2bo2bo24bo200b2o38b2o$443bo14bo13bobo10b2o
13b2o30b2o79bo127b2o26b2o$440b3o16bobo24bo45b2o80bo154b2o43b2o$440bo
19b2o24bobo123b3o199bo$487b2o326b3o$492b2o323bo$492b2o124bo$616bobo91b
2o32b2o38b2o$617b2o91b2o11b2o20bo39bo$723bo18b3o37b3o$489bo21bo8b2o
202b3o15bo39bo$488bobo20b3o6b2o204bo65b2o$488b2o24bo161b2o114b2o$513b
2o13b2o146b2o20b2o6b2o$528bo169bo7bo$497b2o27bobo170b3o5b3o$497b2o27b
2o134b2o37bo7bo$662b2o$519b2o$496b2o8bo12b2o$496b2o6b3o183b2o$503bo
186b2o3b2o107b2o$488b2o13b2o20bo117b2o50b2o101b2o4b2o$489bo34bobo116b
2o153b2o$489bobo33b2o$490b2o204b2o$495b2o193b2o4bo$495b2o19b2o172b2o5b
3o99b2o$516b2o181bo99b2o2b2o$803bobo$679b2o110b2o12bo$492bo186bobo109b
obo11b2o$491bobo187bo111bo$491b2o188b2o110b2o3$500b2o155bo$500b2o154bo
bo$656b2o133b2o$791bobo$498b2o173b2o118bo$498b3o172bo58bo60b2o$489b2o
9b2obo170b3o55b3o$489bo5bo4bo2bo172bo58bo$494bo5b2obo15b2o149b2o62b2o$
490bo3bo3b3o18bobo142b2o4bo58bo$492bo5b2o19bo5bo2bob2obo2bo127b2o5b3o
53b3o$524b2o2bo4bo2b2o135bo52bo$525bo2bob2obo2bo189b2o55b2o$505b3o208b
2o56b2o7b2o$505b3o209bo57bo$504bo3bo208bobo55bobo$520b2o196b2o4b2o44b
2o4b2o$503b2o3b2o9b2o202bo2bo44bo20b2o$521bo202b2o45bobo18bo$736b2o34b
2o16bobo$533b2o201b2o52b2o$533bo2bo$523bo3b3o7bo6b2o$522b5o3bo6bo6b2o$
510b2o9b2ob2o3bo7bo$503b2o5b2o8b3ob2o3bo3bo2bo$504bo16b2ob4o5b2o$501b
3o18b4o$501bo21bo198b2o3b2o32b2o$723bo3bo20b2o11b2o$720b3o5b3o18bo$
720bo9bo15b3o35b2o$746bo37b2o2b2o$788bobo$790bo$790b2o13$831bob2o$831b
2obo$838b2o$838bobo$838bo3$826b2o5b2o$826b2o5b2o2$830b2o$830b2o4$846bo
6b2o$844b3o5bobo$843bo3bo$843bo4b3o6b2o$843b2obob3o6b2o$845bo3b2o43$
827b2o$828b2o$827bo4$604bo$604b2o$603bobo5$619b3o$621bo$620bo15$797b2o
$798b2o$797bo10$287bo18bobo$287b3o16bo3bo$290bo19bo7bo$289b2o5b2o8bo4b
o4b4o$296b2o12bo4bobob2o$306bo3bo3bo2bob3o8b2o$306bobo6bobob2o9b2o$
316b4o$318bo$289b2o3b2o11bo$289b2o3b2o11bobo$307b2o$291b3o$291b3o$292b
o$312b2o6b2o$300bo10bo2bo4bo2bo$299bo11bo2bo4bo2bo$284bo14b3o9bo2bo4bo
2bo444b2o$284b2o26b2o6b2o446b2o$279b2o4b2o480bo$275b2o2b2o4b3o$275b2o
2b2o4b2o10b2o$284b2o11b2o$284bo3$286b2o$286b2o3$277b2o$277bobo$278bo3$
283b2o17b2o$283b2o17b2o$731b2o$276b2o453b2o$275bobo33b2o$275bo34bobo$
274b2o13b2o20bo416b2o$289bo438b2o$282b2o6b3o$282b2o8bo438b2o$307b2o
422b2o$307b2o$283b2o27b2o423b2o$283b2o27bobo423b2o$314bo422bo$299b2o
13b2o405bo$274b2o24bo419bobo$274bobo20b3o6b2o411b2ob2o$275bo21bo8b2o
412bo2bo$720bo3bo$720bo2$278b2o$278b2o$273b2o$272bobo$272bo45b2o393b2o
5bo$271b2o13b2o30b2o393bo6b2o$286bo427bo$279b2o6b3o423b2o8b2o$279b2o8b
o433b2o3$318bo401b2o$317b3o400b2o$317b3o2$227bo11bo5b2o68b2o3b2o$227b
3o7bo3bo3b3o67b2o3b2o$230bo10bo5b2obo8bo$229b2o5bo5bo4bo2bo6bobo$236b
2o9b2obo5bobo58bo$245b3o7bo2bo11b2o44bobo$245b2o9bobo11b2o46bo$257bobo
56b2o5b2o$249bo9bo63b2o$229b2obob2o11b2o77b2o6b2o$229bo5bo4bobo5b2o62b
obo11b3o5b2o$230bo3bo4bo2bo67bobob2o10b2o$231b3o5bo2bo67bo3b2o7b2o$
239b3o67b2obo10b2o$238b3o14b4o51bo$238b3ob2o10b6o51bo4b2o$238b2o2b2o9b
8o$244bo7b2o6b2o50bo5bo$223bo17b2obo8b8o$222bobo16b3o10b6o52bo4bo$220b
2o3bo16bo12b4o53bo2bo$215b2o3b2o3bo87b3o6b2obo$215b2o3b2o3bo96bob2o$
222bobo$223bo91b2o$315b2o2$226b2o$226b2o3$217b2o$217bobo85b2o$218bo87b
o$306bobo$307b2o$242b2o$221b2o19b2o$221b2o$216b2o$215bobo33b2o52b2o$
215bo34bobo53bo$214b2o13b2o20bo41b2o11bobo$229bo64bo12b2o$222b2o6b3o
61bobo$222b2o8bo12b2o48b2o2b2o$245b2o52b2o2$223b2o27b2o$223b2o27bobo$
254bo45b2o$239b2o13b2o38b2o4b2o$214b2o24bo53b2o$214bobo20b3o6b2o$215bo
21bo8b2o4$218b2o75b2o$218b2o74bobo$213b2o79bo$212bobo78b2o$212bo45b2o$
211b2o13b2o30b2o$226bo$219b2o6b3o$219b2o8bo5$257b3o$256bo3bo$255bo5bo$
255b2obob2o3$258bo$130bo19b2o105bobo$130b3o16b3o105bobo$133bo12bob2o
15bo92bo4b2o$132b2o5b2o5bo2bo8b3o4bobo95bobo654bo$139b2o5bob2o16bobo
89b2o6bo7b2o643b2o$149b3o2b2o2bo7bo2bo3b2o82bo2bo2bo2bo7b2o643bobo$
150b2o2bo3bo7bobo4b2o83b2o6bo$155bo2bo6bobo95bobo48b2o611b2o$155b2o8bo
97b2o50b2o610bobo$134b3o177bo612bo$133bo3bo$132bo5bo$132b2obob2o8bo$
147bobo$147b2o9b4o$135bo21b6o$134bobo19b8o98b2obo$134bobo18b2o6b2o97bo
b2o$131bo3bo20b8o$130bobo24b6o92b2o$129bo3b2o11bobo9b4o93b2o$118b2o9bo
3b2o11b2o$118b2o9bo3b2o12bo$130bobo$131bo3$129b2o114b2o$129b2o115bo$
246bobo$247b2o$120b2o$120bobo$121bo2$245b2o$145b2o99bo$124b2o19b2o86b
2o11bobo$124b2o108bo12b2o$119b2o113bobo$118bobo33b2o79b2o2b2o$118bo34b
obo83b2o$117b2o13b2o20bo$132bo$125b2o6b3o303b2o$125b2o8bo12b2o90b2o
197b2o$148b2o84b2o4b2o$234b2o203bo$126b2o27b2o281bobo75b2o$126b2o27bob
o280bobo75b2o$157bo281bo265b2o$142b2o13b2o546b2o$117b2o24bo$117bobo20b
3o6b2o84b2o199b2obob2o74bo$118bo21bo8b2o83bobo190b2o7bo5bo73bobo109b2o
76bo$234bo192bo9bo3bo73bo3bo108b2o75b3o$233b2o193bo9b3o75b3o185bo3bo$
427b2o85b2o3b2o185bo$121b2o327b2o53bo197bo5bo$121b2o326bobo52b3o196bo
5bo$116b2o330bo6b2o2b2o42b2ob2o120bo75bo3bo8b2o$115bobo330bo2bo2bo2bob
2o41b3ob3o117b2ob2o74b3o10bo$115bo45b2o285bo6b2o45b3ob3o10bo197bo$114b
2o13b2o30b2o261b2o23bobo50b3ob3o10bo105bo5bo85b2o$129bo125b3o166b2o24b
2o19bo30b3ob3o6b3obo173b2o$122b2o6b3o28bo95bo213b3o29b2ob2o117b2obob2o
7b3o49bo3bo$122b2o8bo27bobo73b2o18bo217bo29b3o7bo124bobo43b2o3bo5bo$
160bobo72bobo235b2o6b2o22bo8b2obo121b3o43b2o2b2obo3bo$161bo75bo242bobo
33b2o108bo12b3o48bo5bo41bo2bo$481bo144bo2bo9b3o49bo3bo24b2o13b2obo2b2o
68b3o$258b2o366bo12b3o32bo18b2o25b2o13b2obo4bo67bo$158b2obob2o92bobo
146b2o6b2o59b2o39b2o3b2o106b2o8bobo30b3o60b2o75bo$158bo5bo94bo146bo7bo
53b2o5b2o39b2o3b2o107bo8b3o29bo65bo4b2o$159bo3bo243b3o5b3o50b2o47b5o
106bobo32b2o6b2o64b2ob2o$160b3o246bo7bo86bo2bo10bobo107b2o33bobo$505bo
2bo2b2o151bo$64bo19bo400b2o13b2o3bo3bo8b3o$64b3o17bobo148bo6bo242b2o
13bobo3bo2b2o112b2o3b2o39b2o59b2o6b2o$67bo19b2o6b2o138b2o5b2o154b2o
101bo121bo5bo39b2o5b2o53bo7bo$66b2o5b2o12b2o4bo3bo136bobo4bobo154b2o3b
2o65b2o35b3ob3o125b2o35b2o50b3o5b3o$73b2o12b2o3bo5bo69b2o233b2o64bobo
152bo3bo5bo6bo86bo7bo$84bobo4b2obo3bo8b2o58bobo299bo155b3o6bo3b3o$84bo
7bo5bo8b2o57bo6b2o2b2o289b2o48b2o113bo3bo6b2o13b2o$93bo3bo68bo2bo2bo2b
ob2o211b2o12b2o112b2o113bo3bo5bobo13b2o$95b2o69bo6b2o216bo5b2o5bo105b
2o121bo3bo6bo101b2o$66b2o3b2o12bo81bobo218b3o6b2o6b3o102bobo120b2ob2o
36b2o65b2o3b2o$66b2o3b2o10b2o83b2o218bo18bo97b2o6bo160bobo64b2o$67b5o
12b2o391b2o25bo2bo2bo2bo162bo$68bobo407bo21b3o2b2o6bo112b2o48b2o$478bo
bo19b3o7bobo6b2o105b2o112b2o12b2o$68b3o385b2o21b2o18bo3bo6b2o7bobo113b
2o104bo5b2o5bo$89b2o6b2o358bo40bo5bo16bo112bo3bo99b3o6b2o6b3o$88bo2bo
4bo2bo357bobo34b2o3bo3bo17b2o110bo5bo98bo18bo$76bobo8b6o2b6o357b2o34b
2o4b3o130bo3bob2o26b2o$61b2o13b2o10bo2bo4bo2bo65b2obo464bo5bo4bo22bo$
61bobo13bo11b2o6b2o66bob2o304b2o10b2o138b2o7bo3bo4bobo19bobo$56b2o6bo
408b2o2b2o6b2o137bobo8b2o5bo3bo18b2o21b2o$52b2obo2bo2bo2bo93b2o317b2o
145bo18b3o42bo$52b2o2b2o6bo93b2o304b2o157b2o16b2o3b2o2b2o34bobo$61bobo
392b2o6b2o184b2o34b2o$61b2o13bo379b2o32bo$75bo413bobo167b2o10b2o$75b3o
404b2o6b2o167b2o6b2o2b2o$63b2o404bo13bo16b2o165b2o$63b2o403bobo9b3o17b
2o$148b2o311b2o6b2o9bo207b2o$149bo205b2o105bo192bo25b2o5b2o$54b2o93bob
o202bobo102b3o192bobo24b2o$54bobo93b2o201b3o103bo194b2o6b2o$55bo297b2o
289b2o16bo13bo$353b2o77b2o210b2o17b3o9bobo$354bobo75b2o231bo9b2o6b2o$
60b2o17b2o274bo327bo$60b2o17b2o67b2o534b3o$149bo283bo252bo$53b2o81b2o
11bobo200b2o3b2o73bobo$52bobo33b2o47bo12b2o191b2o7b2o3b2o72bo3bo$52bo
34bobo47bobo203bo87b5o380b2o$51b2o13b2o20bo49b2o2b2o200bo9b3o73b2o3b2o
379b2o$66bo75b2o199b2o9b3o63b3o8b5o$59b2o6b3o285bo10b2o51bo3bo8b3o$59b
2o8bo12b2o282b2o51bo3bo9bo305b2o$82b2o279b2o6bo3b2o43b3o316b2o$143b2o
217b3o5bo3bobo$60b2o27b2o46b2o4b2o218b2o6b5o$60b2o27bobo45b2o201b2o24b
2o4b3o59bo382bo$91bo248b2o24b2o19bo43b2o383b3o$76b2o13b2o294b3o30b3o8b
3o381b5o8b2o$51b2o24bo312bo28bo3bo8b2o380bobobobo8bo$51bobo20b3o6b2o
304b2o6b2o20bo3bo8bo381b2o3b2o7bo$52bo21bo8b2o311bobo21b3o8bobo394b2o$
138b2o257bo33b2o317b3o54b2o$137bobo609bo3bo52bobo8bo$137bo184b2o6b2o
405b5o6bo5bo41b2o7b3o4b2ob2obo$55b2o79b2o184bo7bo53b2o46b2obob2o297bob
3obo53b2o6b3o4bo2b3obo$55b2o266b3o5b3o50b2o6b2o26b2o315bo3bo5bo7bo49b
3o4b2o3bo$50b2o273bo7bo58b2o26b2o3bo6bo5bo299b3o6bo7bo50bobo22b2o179b
2o$49bobo371b2o314bo45bo21b2o22b2o179b2o$49bo45b2o304b2o21b2o7b2ob2o
310bo5bo28b3o$48b2o13b2o30b2o304b2o32bo313bo3bo28bo$63bo250b2o434b3o
21b2o6b2o151b2o$56b2o6b3o247b2o3b2o65b2o349bo36bobo157bo2bo$56b2o8bo
252b2o64bobo349bo37bo158bo$385bo350bobo5bo189bo$384b2o48b2o299b2ob2o2b
obo96b2o6b2o83bobo$94b3o209b2o12b2o112b2o298bo5bo2b2o42b2o53bo7bo83bob
o$307bo5b2o5bo105b2o309bo13b2o26b2o6b2o50b3o5b3o85bo88b2o$94bobo207b3o
6b2o6b3o102b2o306b2o3b2o10b2o26b2o58bo7bo162b2o3b2o8bo$93b5o206bo18bo
94b5o6b2o516bo76bo$92b2o3b2o294b2o21bo6bo5b3o338b2o160b2o3b2o7b3o62bo
3bo8b2o$92b2o3b2o295bo21bo4b2o6b2o305bo33b2o160bo5bo64bo8b3o$394bobo
29b2o7b2o299bo120b2o144bobo6b3o$372b2o21b2o29b2o7bobo297bo49b2o65b2o3b
2o74bo3bo8b3o43b2o12b2o$95bo277bo63bo347bobo64b2o80b3o55b2o12b2o$93b2o
278bobo34b2o2b2o3b2o16b2o348bo158bobo57b2o$374b2o34b2o3b5o317b2o48b2o
157bobo54bobo21b2o$92bo7b2o314b3o318b2o112b2o12b2o114bo21bo23b2o$92bo
7b3o286b2o26bo325b2o107bo5b2o5bo80b3o30b3o$96bo5b2obo5b2o276b2o2b2o
348bobo103b3o6b2o6b3o109bo$93bo8bo2bo5b2o280b2o5b2o342b3o102bo18bo101b
2o6b2o$95b2o5b2obo274b2o18b2o343b3o30b2o158bo7b3o21bobo$100b3o269b2o6b
2o362b3o31bo157bobo8bo23bo$100b2o270b2o32bo329b2o5bobo30bobo158b2o$
405bobo327bobo5b2o31b2o21b2o236b2o6b2o$398b2o6b2o327bo63bo133bo49b2o
53bo7bo$385bo13bo16b2o316b2o25b2o34bobo132b3o40b2o6b2o50b3o5b3o$384bob
o9b3o17b2o337bo5b2o34b2o132b5o39b2o58bo7bo$205b2o170b2o6b2o9bo357b3o
173b2o3b2o8bo$205b2o171bo374b5o24b2o147b5o10bo19b2o$375b3o374b2o3b2o
19b2o2b2o147bo3bo8b3o19b2o$99b2obo102bo169bo377b5o13b2o5b2o152bobo118b
2o$99bob2o101bobo75b2o469bo3bo13b2o160bo47b2o65b2o3b2o$204bobo75b2o
470bobo42b2o180bobo64b2o$92b2o111bo549bo10bo25b2o5b2o151bo30bo$92b2o
671bobo24b2o139b2o16b2o30b2o$765b2o6b2o158b2o16bobo93b2o12b2o$202b2obo
b2o74bo471b2o16bo13bo152bo9b3o6bobo86bo5b2o5bo$193b2o7bo5bo73bobo470b
2o17b3o9bobo149bobo9b2o8b2o83b3o6b2o6b3o$193bo9bo3bo73bo3bo490bo9b2o6b
2o140b2o12b2o8bo84bo18bo$194bo9b3o75b3o509bo141b2o36b2o$193b2o85b2o3b
2o508b3o138b2o36bo$82b2o132b2o53bo525bo134b2o4bobo31bobo$83bo131bobo
52b3o658bobo6bo31b2o21b2o$83bobo128bo6b2o2b2o42b2ob2o657bo63bo$84b2o
128bo2bo2bo2bob2o41b3ob3o655b2o16b2o3b2o2b2o34bobo$214bo6b2o45b3ob3o
10bo662b2o3b2o2b2o34b2o$190b2o23bobo50b3ob3o10bo663b5o$190b2o24b2o19bo
30b3ob3o6b3obo664bobo13b2o10b2o$237b3o29b2ob2o692b2o6b2o2b2o$82b2o156b
o29b3o7bo669b3o21b2o$83bo155b2o6b2o22bo8b2obo$70b2o11bobo160bobo33b2o
711b2o$71bo12b2o161bo714bo25b2o5b2o$71bobo887bobo24b2o$72b2o2b2o94b2o
6b2o100b2o3b2o672b2o6b2o$76b2o94bo7bo53b2o46b2o3b2o662b2o16bo13bo$173b
3o5b3o50b2o6b2o31bo7b5o663b2o17b3o9bobo$175bo7bo58b2o30bo9bobo685bo9b
2o6b2o$274b3o713bo$77b2o172b2o31b3o704b3o$71b2o4b2o172b2o18b2o720bo$
71b2o91b2o105b3o$164b2o3b2o65b2o29b3ob2o$169b2o64bobo30b2o$235bo$234b
2o48b2o$156b2o12b2o112b2o$72b2o83bo5b2o5bo105b2o$71bobo80b3o6b2o6b3o
102bobo$71bo82bo18bo97b2o6bo$70b2o171b2o25bo2bo2bo2bo$244bo21b3o2b2o6b
o$244bobo19b3o7bobo6b2o$222b2o21b2o18bo3bo6b2o7bobo797b2o$223bo40bo5bo
16bo797b2o$223bobo34b2o3bo3bo17b2o796b2o$224b2o34b2o4b3o817bo$1008b2o
75bobo$239b2o10b2o755b2o75bobo$239b2o2b2o6b2o833bo$243b2o2$222b2o784bo
74b2o3b2o$222b2o5b2o25bo750b3o73bobobobo7b2o$229b2o24bobo748bo3bo73b5o
9bo$248b2o6b2o747bob3obo73b3o9bo$235bo13bo16b2o738b5o75bo10b2o$234bobo
9b3o17b2o751b3o52b2o$227b2o6b2o9bo771bo3bo51bobo$228bo788bo5bo41b3ob2o
4b3o$225b3o837b4o2bo4b3o$225bo790bo7bo44b2o4b3o$1005b2o2bo6bo7bo49bobo
23b2o$1007bobo44bo19b2o24b2o$1009b2o6bo5bo28b3o$1010b2o6bo3bo28bo$
1008bob2o7b3o21b2o6b2o$1008b3o32bobo$1044bo2$1003b2o3b2o39b2o59b2o6b2o
$1006bo42b2o5b2o53bo7bo$1003bo5bo46b2o50b3o5b3o$120b2o882b2ob2o6bobo
90bo7bo$120b2o883bobo8b2o$1006bo9bo22b2o$1006bo32b2o$118bo78b2o824bo
102b2o$119bo77b2o823b4o28b2o65b2o3b2o$119bo901bo4bo27bobo64b2o$1022bob
obo29bo$197b3o806b2o16b2o30b2o$117b2o3b2o73b3o806b2o112b2o12b2o$108b2o
10bo893b2o105bo5b2o5bo$108bo8bo5bo889bobo102b3o6b2o6b3o$109bo8b2ob2o
62b3o824b3o4b2o97bo18bo$108b2o9bobo73b2o3b2o809b3o4bo2bo2bo22b2o$120bo
9bobo51bo3bo7b5o811b3o4b2ob2obo21bo$120bo8bo2bo51bo3bo8b3o805b2o6bobo
6bo3bo18bobo$128b2o10b2o56bo805bobo7b2o6b5o18b2o21b2o$126b2o3bo8b2o43b
3o816bo16b2o3b2o40bo$128b2o5b2o866b2o17b5o3b2o34bobo798b2o$105b2o22bo
2bo4bo885b3o4b2o34b2o799bo$105b2o23bobo19bo32b3o836bo840bobo$152b3o
884b2o10b2o812b2o$155bo28bo3bo850b2o6b2o2b2o$154b2o6b2o20bo3bo8bo849b
2o$161bobo31b2o863b2o$162bo22b3o8b2o862b2o6b2o$1035bo32b2o$87b2o6b2o
59b2o876bobo829b2o$87bo7bo53b2o5b2o876b2o6b2o816b2o4b2o$88b3o5b3o50b2o
873b2o16bo13bo803b2o$90bo7bo87b2o9b2o3b2o820b2o17b3o9bobo$182b2obob2o
10b3o843bo9b2o6b2o$166b2o13bobobo12bo3bo860bo$166b2o13bo6bo10bobo862b
3o794b2o$79b2o101bo3bo4bobo6bo865bo794b2o2b2o$79b2o3b2o65b2o34bobobobo
1671bobo$84b2o64bobo1700b2o12bo$150bo1702bobo11b2o$149b2o48b2o1654bo$
71b2o12b2o112b2o1654b2o$72bo5b2o5bo99bo5bobo$69b3o6b2o6b3o95bo2bo3bo2b
o$69bo18bo98bo6b2o$158b2o23b2o3bo3bo3b2o$159bo34b2o1657b2o$149bo9bobo
29bo2bo5b2o1651bobo$137b2o9bo11b2o29bobo6bobo1652bo$138bo9b3o51bo1652b
2o$138bobo34b2o2b2o3b2o16b2o$139b2o34b2o2bobobobo$180b5o$154b2o25b3o$
154b2o2b2o22bo$158b2o5b2o$165b2o1678b2o$137b2o1706b2o$137b2o5b2o25bo$
144b2o24bobo1663b2obo$163b2o6b2o1663bob2o$150bo13bo16b2o$149bobo9b3o
17b2o$142b2o6b2o9bo$143bo$140b3o$140bo2$1837bo$1834b4o$1833b4o$51b2o
1773b2o5bo2bo$51b2o1773b2o5b4o$1834b4o$1837bo$128b2o$49b2o77b2o1714b2o
2$129bo$128bobo$128bobo$39b2o7b2o3b2o74bo1710b2o3b2o$39bo9b5o63bo1723b
5o$40bo8b2ob2o63bo1723b2ob2o$39b2o8b2ob2o62b3o7b2obob2o1708b2ob2o$50b
3o9bo63bo5bo1709b3o$59b4o64bo3bo$58b4o9b2o43b3o9b3o$58bo2bo9b2o44bo
1754bo8b2o$58b4o5bo49bo1754b3o6b2o$36b2o21b4o4bo49bo1757bo$36b2o24bo
20bo33bo1724b2o30b2o13b2o$83b3o30b3o1723b2o45bo$86bo1800bobo$85b2o6b2o
32bo1759b2o$92bobo21b3o7bo$93bo23bo8b3o1751b2o$117bo1762b2o$18b2o6b2o
59b2o$18bo7bo53b2o5b2o$19b3o5b3o50b2o1772b2o8bo21bo$21bo7bo99b5o1720b
2o6b3o20bobo$119bo8bob3obo1726bo24b2o$97b2o20bobo7bo3bo1712b2o13b2o$
97b2o20b2o9b3o1714bo$10b2o119bo1715bobo27b2o$10b2o3b2o65b2o1764b2o27b
2o$15b2o64bobo1769b2o$81bo1771b2o$80b2o30bo17b2o1737bo8b2o$2b2o12b2o
87bo5b3o16b2o1737b3o6b2o$3bo5b2o5bo86b2o6b2o10bo1748bo$3o6b2o6b3o84b2o
7bo3bo5b4o1723bo20b2o13b2o$o18bo93bobo2b2o4b4o1721bobo34bo$89b2o33bo2b
o1721b2o33bobo$90bo33b4o1756b2o$90bobo30b4o4b2o$68b2o21b2o30bo7bobo
1724b2o17b2o$69bo63bo1724b2o17b2o$69bobo34b2o2b2o3b2o16b2o$70b2o34b2o
2bo5bo$1883bo$85b2o10b2o12bo3bo1766bobo$85b2o2b2o6b2o13b3o1768b2o$89b
2o$76b2o$68b2o6b2o1796b2o$68b2o32bo1771b2o$101bobo$94b2o6b2o$81bo13bo
16b2o1762b2o$80bobo9b3o17b2o1760bo2bo7bo$73b2o6b2o9bo1780bo7b2o3bo$74b
o1798bo6bo5bo$71b3o1799bo7b5o$71bo1802bo2bo$1839bo2bo4bo2bo4b2o19b2o$
1837b3o2b6o2b3o2b2o$1839bo2bo4bo2bo2$1868b3o$1867b2ob2o$1854bo12b2ob2o
$1854b2o11b5o$1853bobo10b2o3b2o2$1841b2o$1840bobo$1830b2o7bo6b2o4bo$
1830b2o7bo2bo2bo2bo2bobo$1839bo6b3obob2o10b2o$1840bobo6b2ob2o10b2o5b2o
$1841b2o7bob2o17bo$1851bobo18b3o$1852bo21bo77$915bo$886b2o26bob5o$887b
o26bo2b4ob2o$887bobo25b3o$888b2o2$923b3o$892b3o27b2o3bo$892bo2bo24b2o
3bobo$892bob2o23bobo5bo$887b2o29bo4b3o$887bo29bo6bo$918bo$893b3o23b4o$
891b5o9b2o27bo$890b3o12b2o25bobo$890b2obo39b2o$888b3ob2o$887bobo24b2o$
887bo12b2o12b2o$886b2o11bobo$899bo$898b2o3$1598bo$1596b2o$900b2o695b2o
$899bobo$899bo$898b2o7$908b2o$908b2o2$915bob2o$915b2obo8$919b2o$918bo
3bo$917bo5bo$917bo3bob2o2b2o$917bo5bo3b2o$918bo3bo$919b2o7$910b3o$909b
o3bo$908bo5bo$908bo5bo$911bo$909bo3bo$910b3o$872b2o8bo28bo$872b2o6b3o$
879bo$864b2o13b2o30b2o$865bo45b2o$865bobo$866b2o$871b2o$871b2o81b2o$
955bo$955bobo$956b2o$868bo21bo8b2o$867bobo20b3o6b2o$867b2o24bo$892b2o
13b2o1249b2o$907bo1250bo$876b2o27bobo47b2o1199bobo$876b2o27b2o48b2o4b
2o1193b2o$900b2o59b2o$900b2o$875b2o8bo$875b2o6b3o$882bo77b2o$867b2o13b
2o20bo51b2o2b2o1195b2o$868bo34bobo49bobo1193b2o4b2o$868bobo33b2o49bo
12b2o1181b2o$869b2o83b2o11bobo$967bo$876b2o17b2o69b2o$876b2o17b2o1255b
2o$2152b2o2b2o$2156bobo$871bo1272b2o12bo$870bobo95b2o1174bobo11b2o$
870b2o95bobo1176bo$967bo1178b2o$890bo75b2o$879b2o8b2o$879b2o8bobo2$
2144b2o$880bo1263bobo$880bobo1263bo$868b2o11bobo92b2o1168b2o$868b2o11b
o2bo5b2o84b2o$881bobo6bobo$880bobo7bo92bob2o$880bo25b8o69b2obo$885bo
20bob4obo$884b3o19b8o$883bo3bo1248b2o$885bo1250b2o$882bo5bo8b3o$882bo
5bo8bo1229b2obo$883bo3bo10bo1228bob2o$884b3o97bo$982bobo$913bobo65bobo
$905b3o5bo3bo62bo2bo11b2o$900b2o2bo2bobo7bo5b2o56bobo11b2o$898bo2bo2b
2o7bo4bo4b2o57bobo$889b2o6bo19bo66bo$882b2o5b2o6bo10b3o2bo3bo1207bo$
883bo13bo15bobo63bo1144bobo$880b3o15bo2bo76bobo1142bob2o$880bo19b2o75b
o3bo1135b2o3b2ob2o$978b3o1136b2o4bob2o$976b2o3b2o1141bobo$2125bo7$940b
2o8bo76b2o$940b2o6b3o77bo$947bo7b3o70bobo1101b5o$932b2o13b2o8bo21b2o
48b2o1100bob3obo$933bo22bo22b2o1078bobo70bo3bo$933bobo1123b2o72b3o$
934b2o2bobo1119bo73bo$937bo2bo1222bo8b2o$937bo1225b3o6b2o$938bobo87b2o
1136bo$1028b2o4b2o1097b2o30b2o13b2o$1034b2o1097b2o45bo$936bo21bo8b2o
1209bobo$935bobo20b3o6b2o1209b2o$935b2o24bo1211b2o$960b2o13b2o56b2o
1138b2o$975bo53b2o2b2o$944b2o27bobo52bobo$944b2o27b2o53bo12b2o$968b2o
57b2o11bobo1102b2o8bo21bo$968b2o70bo1104b2o6b3o20bobo$943b2o8bo85b2o
1111bo24b2o$943b2o6b3o1183b2o13b2o$950bo1187bo$935b2o13b2o20bo1165bobo
27b2o$936bo34bobo1165b2o27b2o$936bobo33b2o67b2o$937b2o101bobo1103b2o$
942b2o96bo1105b2o12bo8b2o$942b2o19b2o74b2o1119b3o6b2o$963b2o1198bo$
2141bo20b2o13b2o$2140bobo34bo$939bo1200b2o33bobo$938bobo1234b2o$938b2o
1230b2o$1049b2o1098b2o19b2o$1049b2o1098b2o$947b2o$947b2o107bob2o$1056b
2obo1114bo$2173bobo$946bobo13b2o1210b2o$945bo2bo13bobo$936b2o6b2o16bo$
936b2o4b2o3bo1217b2o$944b2o1219b2o$945bo2bo$946bobo22b2o3bo2bo3b2o74b
2o$971b5o4b5o72bo2bo1106bo$963b2o6b2o3bo2bo3b2o71bo7b5o1095b4o$962b2o
92bo6bo5bo1093b4o9b2o$964bo91bo7b2o3bo1093bo2bo9b2o$1057bo2bo7bo1077b
3o14b4o5bo$1059b2o1087bo15b4o4bo$2129bo2b2o4b2o2bo4bo19bo$2128bo3b3o2b
3o3bo$950b2o3b2o14bo1157bo2b2o4b2o2bo17bo$952b3o15b2o10b2o1175b3o$951b
o3bo14bobo9b2o67b3o1104bo3bo$952bobo10b2o12b2o6bo3b2o57bo3bo1091bo10bo
b3obo$953bo9bo3bo10b3o5bo3bobo1153b2o10b5o$957b2o3bo5bo10b2o6b5o57bo5b
o1089bobo$950b2o5b2o2b2obo3bo13b2o4b3o58b2o3b2o$951bo10bo5bo13b2o$948b
3o12bo3bo1164b2o$948bo16b2o85bo1078b3o3b2obo$1051bobo1067b2o5bob2o5bo
3bo2bo$1013b2o8bo27bobo1067b2o5bo2bo4bo4bo2b2o$1013b2o6b3o27bo1076bob
2o4b4o5b2o8b2o$1020bo30bo1079b3o3bo7b3o7b2o5b2o$1005b2o13b2o29bo2bo
1077b2o11b2o15bo$1006bo45b2o1090b2o17b3o$1006bobo1135bo20bo$1007b2o2$
1014b2o$1014b2o2$1095b2o$1009bo21bo8b2o54bo$1008bobo20b3o6b2o54bobo$
1008b2o24bo62b2o$1033b2o13b2o$1048bo$1017b2o27bobo$1017b2o27b2o2$1039b
2o55b2o$1016b2o8bo12b2o55b2o4b2o$1016b2o6b3o75b2o$1023bo$1008b2o13b2o
20bo$1009bo34bobo$1009bobo33b2o54b2o$1010b2o85b2o2b2o$1096bobo$1017b2o
17b2o58bo12b2o$1017b2o17b2o57b2o11bobo$1108bo$1107b2o$1012bo$1011bobo$
1011b2o2$1109b2o$1020b2o86bobo$1020b2o86bo$1107b2o2$1021b2o$1020bo3bo$
1009b2o8bo5bo$1009b2o8bo3bob2o7bo$1019bo5b2o8bo$1020bo4b2o6b2o12bo6bo
62b2o$1021b2o3bo6bobo10b2o6b2o61b2o$1025bobo17b3o6b3o$1025bobo6bobo9b
2o6b2o68bob2o$1026bo8bo11bo6bo69b2obo$1035b2ob2o$1037bo$1023b2o3b2o8bo
$1023bo5bo2$1024bo3bo$1025b3o17bo2bo8bo$1045bo10bobo66b2o$1041bo2bo3b
2o5bo3b2o3b2o59bobo$1038b4o3b2obobo4bo3b2o3b2o54b2o4b3o$1030b2o5b4o14b
o3b2o58bo2bo4b3o6b2o$1023b2o5b2o5bo2bo8b2o5bobo61b2o4b3o7b2o$1024bo12b
4o16bo62b2o3bobo$1021b3o14b4o78bo4b2o$1021bo19bo77bobo$1119bobo$1120bo
3$1117b2o3b2o$1117bobobobo$1118b5o$1119b3o$1120bo4$1081b2o8bo$1081b2o
6b3o$1088bo$1073b2o13b2o30b2o$1074bo45b2o$1074bobo$1075b2o2$1082b2o$
1082b2o3$1077bo21bo8b2o$1076bobo20b3o6b2o$1076b2o24bo$1101b2o13b2o$
1116bo$1085b2o18b2o7bobo$1085b2o19b2o6b2o$1105bo3b2o$1109b2o$1084b2o8b
o$1084b2o6b3o$1091bo$1076b2o13b2o20bo$1077bo34bobo$1077bobo33b2o$1078b
2o$1083b2o$1083b2o19b2o$1104b2o3$1080bo$1079bobo$1079b2o3$1088b2o$
1088b2o3$1085bo$1083b4o$1077b2o3bobob2o$1077b2o2bo2bob3o14b2o13b2o$
1082bobob2o13bo2bo11bo4bo$1083b4o13bo14bo6bo$1085bo14b2o12bo8bo$1104b
2o8bo8bo$1104b2o8bo8bo$1115bo6bo$1116bo4bo$1094bo23b2o$1093b3o$1092b5o
1327b2o$1091bobobobo11b3o1312bo$1091b2o3b2o11bo1312bobo$1110bo9bo1301b
2o$1119bobo$1107bobo8bob2o10b2o$1107bo2bo6b2ob2o10b2o$1098b2o10b2o6bob
2o$1091b2o5b2o8bo3b2o5bobo$1092bo10b2o5b2o8bo1302b2o$1089b3o10bo4bo2bo
1306b2o4b2o$1089bo17bobo1307b2o4$2418b2o$2418b2o2b2o$2422bobo$2410b2o
12bo$2410bobo11b2o$2412bo$2412b2o3$1248b2o$1249bo$1249bobo1158b2o$
1250b2o1158bobo$2412bo$2412b2o4$1249b2o$1249b2o4b2o$1255b2o$2402b2o$
2402b2o2$1254b2o1137b2obo$1250b2o2b2o1137bob2o$1249bobo$1249bo12b2o$
1248b2o11bobo$1261bo$1260b2o3$2394b2o$2392bo2bo$1262b2o1127bo7b2o$
1261bobo1119b2o6bo6bo2bo$1261bo1121b2o6bo6bo2bo$1260b2o1130bo2bo5bo$
2394b2o5bo$2399bobo$2399bobo$2400bo3$1270b2o1125b2o3b2o$1270b2o1125bo
5bo2$1277bob2o1117bo3bo$1277b2obo1118b3o4$2429bo8b2o$2429b3o6b2o$2432b
o$2399b2o30b2o13b2o$1278b2o1119b2o45bo$1278bobo1163bobo$1273b2o6bo
1162b2o$1272bo2bo2bo2bo7b2o$1273b2o6bo7b2o1146b2o$1278bobo1156b2o$
1273bo4b2o$1272bobo$1272bobo1136b2o8bo21bo$1273bo1137b2o6b3o20bobo$
2418bo24b2o$2403b2o13b2o$1270b2obob2o1127bo$1270bo5bo1127bobo27b2o$
1271bo3bo1129b2o27b2o$1272b3o$2412b2o$2412b2o12bo8b2o$2426b3o6b2o$
2429bo$1234b2o8bo1162bo20b2o13b2o$1234b2o6b3o1161bobo24b2o8bo$1241bo
1164b2o24b3o6bobo$1226b2o13b2o30b2o1161bo4b2o$1227bo45b2o1159b2obo$
1227bobo1185b2o17b2o$1228b2o1185b2o2$1235b2o$1235b2o1203bo$1326b2o
1111bobo$1327bo1112b2o$1230bo21bo8b2o64bobo$1229bobo20b3o6b2o65b2o$
1229b2o24bo1175b2o$1254b2o13b2o1160b2o$1269bo$1238b2o27bobo$1238b2o27b
2o1165b2o$1262b2o63b2o1092bo11bo3bo$1262b2o63b2o4b2o1086bo10bo5bo3b2o$
1237b2o8bo85b2o1086bo10bo3bob2o2b2o$1237b2o6b3o1184bo5bo$1244bo1153bo
6bo27bo3bo$1229b2o13b2o20bo1130b2o6b2o10b2o15b2o$1230bo34bobo64b2o
1062b3o6b3o10b2o$1230bobo33b2o60b2o2b2o1063b2o6b2o10bo$1231b2o94bobo
1068bo6bo$1327bo12b2o$1238b2o17b2o67b2o11bobo1083b3o$1238b2o17b2o80bo
1084bo3bo$1338b2o1070bo$2410b2o11bo5bo$1233bo13b2o1160bobo11b2o3b2o$
1232bobo12bobo1150bo$1232b2o13bo1151bobo$1340b2o1045b2o9bo3b2o8bo$
1339bobo1045b2o9bo3b2o5b4o$1241b2o96bo1058bo3b2o4b4o9b2o$1241b2o95b2o
1059bobo6bo2bo9b2o5b2o$2400bo7b4o5bo10bo$2409b4o4bo11b3o$1238bo1173bo
18bo$1237bobo12bo$1230b2o3b2o3bo10bobo$1230b2o3b2o3bo11b2o$1235b2o3bo
29b4o74b2o$1237bobo29b6o73b2o$1238bo17bo11b8o$1255b2o10b2o6b2o78bob2o$
1255bobo10b8o79b2obo$1269b6o$1270b4o2$1246b3o$1245bo3bo$1244bo5bo12b2o
$1244b2obob2o11b2o$1264bo9bo82bo$1272bobo80bobo$1260b2o9bobo11b2o66b2o
$1260b3o7bo2bo11b2o66b2o12b2o$1251b2o9b2obo5bobo79b2o12b2o$1244b2o5bo
5bo4bo2bo6bobo80bobo$1245bo10bo5b2obo8bo82bo$1242b3o7bo3bo3b3o$1242bo
11bo5b2o$1350b3o$1350b3o$1349bo3bo2$1348b2o3b2o7$1312b2o8bo$1312b2o6b
3o66b2o$1319bo70bo$1304b2o13b2o30b2o37bobo$1305bo45b2o38b2o$1305bobo$
1306b2o$1311b2o$1311b2o2$1321bo68b2o$1320b2o68b2o4b2o$1308bo11bobo7bo
8b2o55b2o$1307bobo20b3o6b2o$1307b2o24bo$1332b2o13b2o$1347bo47b2o$1316b
2o27bobo43b2o2b2o$1316b2o27b2o43bobo$1340b2o48bo12b2o$1340b2o47b2o11bo
bo$1315b2o8bo76bo$1315b2o6b3o75b2o$1322bo$1307b2o13b2o20bo$1308bo34bob
o$1308bobo33b2o$1309b2o92b2o$1314b2o86bobo$1314b2o19b2o65bo$1335b2o64b
2o3$1311bo$1310bobo$1310b2o2$1411b2o$1319b2o90b2o$1319b2o$1418bob2o$
1418b2obo$1319b2o$1318b3o$1308b2o5bob2o17bo$1308b2o5bo2bo16bobo$1315bo
b2o16bo2bo$1318b3o17bo$1319b2o14bo2bo5bo2bob2obo2bo$1336b3o4b2o2bo4bo
2b2o63bobo$1335b2ob2o4bo2bob2obo2bo64bo3bo$1334b5o85bo$1334b4o82bo4bo
4b2o$1334bo89bo5b2o$1420bo3bo$1420bobo$1322b2o3b2o2$1323bo3bo14b3o9b2o
$1324b3o15bo9bo2bo7bo$1324b3o10bo5bo7bo7b2o3bo$1335b4o12bo6bo5bo$1329b
2o3bobob2o11bo7b5o47b2obob2o$1322b2o5b2o2bo2bob3o11bo2bo$1323bo10bobob
2o14b2o55bo5bo$1320b3o12b4o$1320bo16bo74b2ob2o$1414bo2$1375b2o8bo$
1375b2o6b3o$1382bo$1367b2o13b2o30b2o$1368bo45b2o$1368bobo$1369b2o$
1374b2o$1374b2o4$1371bo21bo8b2o$1370bobo20b3o6b2o$1370b2o24bo$1395b2o
13b2o$1410bo$1379b2o27bobo$1379b2o27b2o2$1401b2o$1378b2o8bo12b2o$1378b
2o6b3o$1385bo$1370b2o13b2o20bo$1371bo34bobo$1371bobo33b2o$1372b2o2$
1379b2o17b2o$1379b2o17b2o3$1374bo$1373bobo$1373b2o$1534bo$1532bobo$
1382b2o149b2o$1382b2o2$1533bo$1380b2o149bobo5bo$1380b2o150b2o6b2o37bob
o$1371b2o3bo6b2o13b2o139b2o38b2o$1371bobo3bo5b3o11bobo180bo$1372b5o6b
2o12bo$1373b3o4b2o128b2o$1380b2o16bo2bo5bo2bob2obo2bo92bo$1401bo5b4ob
2ob4o92bobo$1400b2o5bo2bob2obo2bo93b2o$1388bo$1386b2ob2o4bo$1396b2o$
1385bo5bo4b2o4b2o$1397bo4bobo$1385b2obob2o3b2o5bo108b2o$1511b2o4b2o$
1415b2o100b2o$1415bobo$1405bo4b2o4b3o7b2o$1404bobob2o2bo4b3o6b2o$1392b
2o9bo3bob3o4b3o97b2o$1385b2o5b2o9bo3bob2o4bobo94b2o2b2o$1386bo16bo3b2o
6b2o94bobo$1383b3o18bobo104bo12b2o$1383bo21bo104b2o11bobo$1523bo$1522b
2o5$1524b2o$1523bobo$1523bo$1522b2o7$1532b2o$1532b2o$1583bo$1539bob2o
38bobo482bo$1539b2obo39b2o480b2o$2065b2o7$1541bo$1539bobo$1537b2o$
1537b2o12b2o$1537b2o12b2o$1539bobo$1541bo3$1534b3o$1534b3o$1533bo3bo2$
1532b2o3b2o7$1496b2o8bo$1496b2o6b3o$1503bo$1488b2o13b2o30b2o$1489bo45b
2o$1489bobo$1490b2o$1495b2o$1495b2o4$1492bo21bo8b2o$1491bobo20b3o6b2o$
1491b2o24bo$1516b2o13b2o$1531bo$1500b2o27bobo$1500b2o27b2o$1518b2o4b2o
$1519b2o3b2o$1499b2o8bo8bo$1499b2o6b3o$1506bo$1491b2o13b2o20bo$1492bo
34bobo$1492bobo33b2o$1493b2o$1498b2o$1498b2o19b2o$1519b2o3$1495bo$
1494bobo$1494b2o3$1503b2o$1503b2o3$1503b2o$1502b3o10bo$1492b2o5bob2o$
1492b2o5bo2bo14b3o$1499bob2o14b2o$1502b3o11b2o$1503b2o6b3o2bo11bo2bob
2obo2bo$1510bo16b2o2bo4bo2b2o$1519b2o7bo2bob2obo2bo$1519bobo$1519bo4$
1506b2o3b2o2$1507bo3bo14b3o9b2o$1508b3o15bo9bo2bo7bo$1508b3o10bo5bo7bo
7b2o3bo$1519b4o12bo6bo5bo$1513b2o3bobob2o11bo7b5o$1506b2o5b2o2bo2bob3o
11bo2bo$1507bo10bobob2o14b2o$1504b3o12b4o$1504bo16bo13$1651b2o$1652bo$
1652bobo$1653b2o6$1652b2o$1652b2o4b2o$1658b2o4$1657b2o$1653b2o2b2o$
1652bobo$1652bo12b2o$1651b2o11bobo$1664bo$1663b2o5$1665b2o$1664bobo$
1664bo$1663b2o7$1673b2o$1673b2o2$1680bob2o$1680b2obo8$1681b2o$1681bobo
$1676b2o6bo$1675bo2bo2bo2bo7b2o$1676b2o6bo7b2o$1681bobo$1676bo4b2o$
1675bobo$1675bobo$1676bo3$1673b2obob2o$1673bo5bo$1674bo3bo$1675b3o5$
1637b2o8bo$1637b2o6b3o$1644bo$1629b2o13b2o30b2o$1630bo45b2o$1630bobo$
1631b2o2$1638b2o$1638b2o3$1633bo21bo8b2o$1632bobo20b3o6b2o$1632b2o24bo
$1657b2o13b2o$1672bo$1641b2o27bobo$1641b2o27b2o2$1663b2o$1640b2o8bo12b
2o$1640b2o6b3o$1647bo$1632b2o13b2o20bo$1633bo34bobo$1633bobo33b2o$
1634b2o2$1641b2o17b2o$1641b2o17b2o3$1636bo$1635bobo$1635b2o3$1644b2o$
1644b2o2$1657b3o$1641bo15bo$1640bobo15bo$1633b2o3b2o3bo$1633b2o3b2o3bo
$1638b2o3bo29b4o$1640bobo29b6o$1641bo17bo11b8o$1658b2o10b2o6b2o$1658bo
bo10b8o$1672b6o$1673b4o2$1649b3o$1648bo3bo$1647bo5bo12b2o$1647b2obob2o
11b2o$1667bo9bo$1675bobo$1663b2o9bobo11b2o$1663b3o7bo2bo11b2o$1654b2o
9b2obo5bobo$1647b2o5bo5bo4bo2bo6bobo$1648bo10bo5b2obo8bo$1645b3o7bo3bo
3b3o$1645bo11bo5b2o156$1976b2o$1976b2o!
I'm sure this monstrosity can be optimised a lot more.

EDIT2: I did eventually optimise by removing some guns and using cheaper p690 technology. This new pattern is probably glider constructible in around 1,000 gliders. Note that the operations have been swapped so that now we have PUSH = 0, PULL = 1 and FIRE = 2.

Code: Select all

x = 1235, y = 944, rule = B3/S23
303b2o$302bo2bo$305bo$305bo$303bobo$303bobo$304bo3$301b2o3b2o$301bo5bo
2$302bo3bo$291b2o10b3o$289bo3bo$288bo5bo$283b2o2b2obo3bo$283b2o3bo5bo$
289bo3bo$291b2o4$298b2o$297bobo$296b3o6bo$296b2ob3ob2ob2o$297b5ob2ob2o
28bo$299bo5bo29bobo$300b2ob2o2$335b3o$335b3o$299bo5bo30bo$298b2o5b2o$
297bob2o3b2obo$297bob2o3b2obo28bo$298b3o3b3o28b3o$298b3o3b3o28b3o3$
335bobo$336bo5$321b2o302b2o$321bo2bo300b2o$313b5o7bo$298b2o12bo5bo6bo$
298b2o12bo3b2o7bo$313bo7bo2bo$321b2o29b2o$353bo$353bobo7bo$332b3o19b2o
5bobo$331bo3bo23b2o12b2o$330bo5bo22b2o12b2o$330bo5bo22b2o$333bo27bobo$
331bo3bo27bo25bo$332b3o53b3o4b2o$333bo53bo3bo3b2o$387b2ob2o$387b2ob2o$
333b2o$333b2o52b2ob2o$387b2ob2o$387bo3bo$388b3o$389bo7$388bo7bo$387b4o
3b4o$387bo3bobo3bo$388bo2bobo2bo$388b3o3b3o2$688b2o$689bo$402bo286bobo
9bo$400b5o10bo274b2o9bobo$399bo2bob2o9b2o285bobo4b2o$398bo7bo9b2o284bo
2bo3b2o$399bo2bob2o5b2o2b2o285bobo$400b5o296bobo$402bo298bo2$411b2o2b
2o$398b2o16b2o7b2o$398b2o15b2o8b2o$415bo$302bo2bob2obo2bo$301b2o2bo4bo
2b2o12bo$302bo2bob2obo2bo12bobo$324b2o3bo9b2o$324b2o3bo9b2o$324b2o3bo$
326bobo$323bo3bo$322bobo$322bobo$323bo3$320b2obob2o$320bo5bo$321bo3bo$
322b3o8$323b2o$323b2o5$284b2o11b3ob3o9b2o$283bobo10bob2ob2obo7b2ob2o$
282bo6b2o4b2o7b2o7bo2bo$273b2o7bo2bo2bo2bo4bob2ob2obo8bo2bo$273b2o7bo
6b2o6b3ob3o10b2o$283bobo$284b2o28b2o$313bo2bo$288b3o5b2o15bo2bo6b2o$
288b3o5b2o14b2ob2o6b2o$287bo3bo21b2o$286bo5bo$287bo3bo$288b3o6$556bo$
554b3o$553bo49bo$552bobo48b3o$289b2o262bo52bo$289b2o314b2o$309b2o3bo2b
o3b2o295bo18bo5b2o12bo$309b5o4b5o12bo215b2o63b3o18b3o3b2o10b3o$309b2o
3bo2bo3b2o10b4o214b2o62bo24bo13bo$332bobob2o9b2o266b2o22b2o13b2o$331bo
2bob3o8b2o102bo$332bobob2o114bo109b2o$332b5o113b3o110bo25bo11b2o$331bo
3bo227bobo21b3o11b2o25b2o$330bobo126bo104b2o20bo41bo7b2o$330bobo124bob
o126b2o38bobo8bo$331bo126b2o166b2o9bobo$638b2o$463bo$328b2o3b2o129bo
94bo$328bobobobo127b3o92b3o$329b5o222bo$330b3o223b2o38b2o$331bo264b2o
26b2o$624b2o43b2o$458b2o209bo$458b2o210b3o$672bo2$565b2o32b2o38b2o$
331b2o232b2o11b2o20bo39bo$331b2o125b3o117bo18b3o37b3o$458b3o118b3o15bo
39bo$457bo3bo119bo65b2o$531b2o114b2o$306bo3bo145b2o3b2o68b2o20b2o6b2o$
292b2o11bobobobo8b4o229bo7bo$291bobo9b2o2bobo2b2o6bo2b2o229b3o5b3o$
290b3o4b2o4b2o7b2o7bo2b2o191b2o37bo7bo$281b2o6b3o4bo2bo3b2o2bobo2b2o7b
o2bo192b2o$281b2o7b3o4b2o6bobobobo10b2o$291bobo12bo3bo$292b2o28b2o221b
2o$297bo23bo2bo126bo93b2o3b2o107b2o$296bobo5b2o15bo2b2o5b2o116b4o45b2o
50b2o101b2o4b2o$295bo3bo4b2o14bo2b2o6b2o110b2o3bobob2o44b2o153b2o$295b
5o20b4o119b2o2bo2bob3o$294b2o3b2o147bobob2o97b2o$295b5o149b4o92b2o4bo$
296b3o152bo93b2o5b3o99b2o$297bo256bo99b2o2b2o$658bobo$534b2o110b2o12bo
$534bobo109bobo11b2o$536bo111bo$536b2o110b2o3$512bo$297b2o212bobo$297b
2o212b2o133b2o$646bobo$528b2o118bo$528bo58bo60b2o$529b3o55b3o$531bo58b
o$525b2o62b2o$519b2o4bo58bo$519b2o5b3o53b3o$528bo52bo$581b2o55b2o$571b
2o56b2o7b2o$572bo57bo$572bobo55bobo$573b2o4b2o44b2o4b2o$578bo2bo44bo
20b2o$579b2o45bobo18bo$591b2o34b2o16bobo$591b2o52b2o8$577b2o3b2o32b2o$
578bo3bo20b2o11b2o$575b3o5b3o18bo$575bo9bo15b3o35b2o$601bo37b2o2b2o$
643bobo$645bo$645b2o8$464b2o$434b2o28bobo$433bobo28bo$435bo5$436b3o$
438bo$437bo4$415b3o$417bo2b2o$416bo4b2o$402b2o16bo$403b2o$402bo32$457b
2o$457b2o7$456b3o$455bo3bo$548bo$454bo5bo85b5o10bo21b2o$454b2o3b2o84bo
2bob2o9b2o20bo2bo$544bo7bo9b2o14b2o7bo$447bo97bo2bob2o5b2o2b2o14bo2bo
6bo6b2o$444b4o98b5o27b2o7bo6b2o$422b2o12b2o5b4o101bo34bo2bo$422b2o12b
2o5bo2bo136b2o$443b4o4b2o2b2o100b2o2b2o16bo$444b4o5bo90b2o16b2o7b2o5b
3o$447bo96b2o15b2o8b2o4bo3bo$458bo102bo17bo$422b3o3b3o27bo117bo5bo$
422bo2bobo2bo27bo117bo5bo$421bo3bobo3bo145bo3bo$422bo2bobo2bo147b3o$
424bo3bo$422b2o5b2o19b2o$421b3o5b3o17bobo8bo$421b3o5b3o19bo7bobo65bo$
458bo3bo54b2o6bo2bo25bo$458bo3bo52bob3o5b5o24bobo$458bo3bo50b3o4bo4b3o
b2o16b2o8b2o$458bo3bo52bob3o6b2obo20bo6b2o4b2o$428b3o27bo3bo54b2o8b2o
18bo9b2o4b2o13b2o$428b3o27bo3bo88bo2bobo21b2o$427b5o27bobo65b2o22bo2bo
$426b2o3b2o27bo65b2obo$426b2o3b2o80b2o10b3ob2o9b2o7b2o$465b2o46b2o10b
5o10b2o6bo$464bobo58bo2bo$466bo60bo$426b2o3b2o112b2o3b2o$422b2o2b2o3b
2o112b2o3b2o$422b2o3b5o114b5o$428b3o116bobo$428b3o$547b3o$418b2o$416bo
2bo7b2o$407b2o6bo7b2o4bo$407b2o6bo6bo6bo$415bo7b6o$416bo2bo127b2o$418b
2o127b2o2$425b2o3b2o$426b5o$221b2o203b2ob2o$221b2o203b2ob2o$427b3o$
325bo$325b2o$310b3o11bobo$312bo$220b3o88bo$427b2o$220bobo204b2o$219b5o
$218b2o3b2o$218b2o3b2o2$243b2o3bo$221bo6b2o13b3obob2o4b2o149b2o$219b2o
7b2o13b3o4bo4b2o147bo2bo$246bo3bo$215bo2bo28b3o153bo$213bobo2bo10b2o3b
2o$205b2o4b2o9bo5b3o3b3o10b3o154b2o$205b2o4b2o6bo6b3o7b3o7bo3bo155bo$
211b2o8b2o3b3o7b3o4b3o4bo$213bobo10b3o7b3o4b3obob2o$215bo12b3o3b3o6b2o
3bo154b2o3b2o$229b2o3b2o167b2o3b2o$404b5o$405bobo2$396bo8b3o$396bobo$
371b2o12b2o12b2o$371b2o12b2o12b2o$399b2o$396bobo$396bo8$171b2o235b3o$
171b2o234bo3bo$371b2o5b2o26bo5bo$370bo2bo3bo2bo$373b2ob2o27bo7bo$372bo
bobobo26bo7bo$372bobobobo806b2o$370bo9bo25bo5bo772b2o$369bo11bo25bo3bo
$408b3o$171bo201b2ob2o$170b3o198bo2bobo2bo805b3o$169b5o197b3o3b3o805b
3o$168b2o3b2o1009bo3bo$169b5o1009bo5bo$169bo3bo4b6o5b4o12b2o164b2o811b
o3bo$170bobo5b4o7b2obo12b2o164b2o812b3o$171bo9b2obo7bo$166b2o15b2o5b2o
$165bobo127b4o866bo$155b2o7b3o4b2o10b2o5b2o87b2o14bo2b2o6b2o57b2o797bo
2bo$155b2o6b3o4bo2bo7b2obo7bo86b2o15bo2b2o5b2o57b3o783b2o10b5o10b2o$
164b3o4b2o8bo7b2obo68b3o3bo28bo2bo56b2o9b2obo780b2o9b2ob3o10b2o$165bob
o13b3o5b4o70bo4bo28b2o57bo5bo4bo2bo792bob2o$166b2o94bo3b3o12bo3bo75bo
5b2obo5b3o785b2o26b2o$280bobobobo10b2o58bo3bo3b3o8b3o812bobo$278b2o2bo
bo2b2o7bo2bo59bo5b2o8bo3bo784b2o8b2o14bo6b2o2b2o$278b2o7b2o7bo2b2o862b
ob2o6b3obo12bo2bo2bo2bob2o$278b2o2bobo2b2o6bo2b2o74b2o3b2o781b2ob3o4bo
4b3o10bo6b2o$280bobobobo8b4o864b5o5b3obo13bobo$281bo3bo878bo2bo6b2o16b
2o$1165bo$269b3o3b3o$269bo2bobo2bo$243b2o23bo3bobo3bo$242bobo3bo20bo2b
obo2bo$244bo3b2o21bo3bo$230bo16bobo19b2o5b2o$230b2o36b3o5b3o97b2o$229b
obo36b3o5b3o97b2o5$269b3o$269b3o931b2o$268b5o930b2o$267b2o3b2o$267b2o
3b2o2$1204bo$1203b3o$267b2o3b2o928bo3bo$267b2o3b2o2b2o923bob3obo$268b
5o3b2o924b5o$269b3o$269b3o2$1183b2o$1182bo$1169b2o10bo2b2o10b2o$1169b
2o10bo2bo11b2o$236b3o3bo938bobo$229b2o3b5o2bobo12b2o924b2o27bo$229b2o
2b2o3b2o3bo12b2o952b2o$234b2o3bo2bo939b2o9b2o14b2o4b2o2b2o$235bo3b3o
939bobo7b2o3bo11b3o4b2o2b2o$1181bo2bo6bo4bo12b2o4b2o$235bo3b3o939bo2b
2o5b2o3bo13b2o$234b2o3bo2bo939bo10b2o16bo$233b2o3b2o3bo939b2o$234b5o2b
obo$236b3o3bo7$89b2o$89b2o3$219b3o3b3o$219bo2bobo2bo989b2o$219b2obobob
2o989b2o$219b2o5b2o3$89bo1127b3o$88b3o1126b3o$87b5o129b2ob2o990bo3bo$
86b2o3b2o126bo2bobo2bo987bo5bo$87b5o20b4o103bobo3bobo988bo3bo$87bo3bo
4b2o14bo2b2o6b2o94b3o3b3o989b3o$88bobo5b2o15bo2b2o5b2o101b2o$89bo23bo
2bo109b2o$84b2o28b2o110b2o$83bobo12bo3bo1090b2o$73b2o7b3o4b2o6bobobobo
10b2o1067b2o7bobo15b2o$73b2o6b3o4bo2bo3b2o2bobo2b2o7bo2bo1066b2o6b2obo
15b2o$82b3o4b2o4b2o7b2o7bo2b2o1074b2o$83bobo9b2o2bobo2b2o6bo2b2o1076bo
30b2o$84b2o11bobobobo8b4o993bo113bobo$98bo3bo1004b2o84bo10b2o3b2o11bo
6b2o2b2o$1108b2o82b2o9bob2ob2obo10bo2bo2bo2bob2o$1191b2obo8bo7bo10bo6b
2o$1192bobo8bob2ob2obo11bobo$1193b2o9b2o3b2o13b2o$57b2o$57b2o4$55b2o
1150bobo$232b2o973b2o$232b2o974bo$189b2o333b2o$189bo334b2o$54b2o3b2o
126bobo22bo$55b5o127b2o22b2o$55b2ob2o137b2o11b3obo9b2o298bo$55b2ob2o
137b2o10b2o13b2o297b3o$56b3o151b2o310bo3bo$64b2o12b2o2bo4b2o2b2o73b2o
43bo312bo$64b2o12bob2o6b2ob2o73b2o353bo5bo$79bo6bobo122bo10bo256b2o40b
o5bo$54bo24b3o4b2o122b2o8b2obo254bo2bo40bo3bo$53bobo153b2o8b2ob3o256bo
41b3o$41b2o10b2obo22b3o4b2o122b3obo5bo2bo257bo$41b2o10b2ob2o21bo6bobo
122b2o8b2o256bobo$53b2obo21bob2o6b2o122bo266bobo61bo3bo$53bobo22b2o2bo
4b2o391bo50b2o9bo5bo9b2o$54bo476b2o9bo15b2o$138b2o402b2o3bo$137bobo
337b2o3b2o33b2o25b3o$139bo55b2o280bo5bo25bo7bo2bo$195bo312bo3b2o7bo22b
3o6bob2o$196b3o279bo3bo25bo5bo6bo20b2o3bo5bobobo$176b2o20bo268b2o10b3o
27b5o7bo20bo9bo4bo$176b2o287bo3bo47bo2bo5bobo13bo5bo4bobobo$69bo394bo
5bo46b2o8b2o14bo3bo5bob2o$70b2o387b2o2b2obo3bo56bo598bo$69b2o388b2o3bo
5bo655bobo$465bo3bo12bo643b2o$16b2o449b2o14b2o$16b2o126bo337b2o$142bob
o$140b2o12b2o$140b2o12b2o318b2o$140b2o332b2o$16bo118b2o5bobo$16bo117bo
bo7bo$15bobo116bo$14b2ob2o114b2o$13bo5bo$16bo$13b2o3b2o2$29bob2o156bob
o3bobo$15bo7b2o3bo2b2o2b3o12b2o106bo17b2o2bobo8bo3bo278b3o3b3o$15bo7b
2o3bo6b2o13b2o106bobo14b3obo3bo3bo11bo273bo2bo3bo2bo$14bo13b2o3b3o123b
obo12b2o6bo3bo3bo5bo3bo276bobo$9bo20bo3bo111b2o11bo2bo12bob5o5bo11bo
277bobo$7bobo34bo5bo95b2o11bobo14b3o12bo3bo281bobo$2o4bobo21bo3bo9bo5b
o107bobo28bobo3bobo275bo2bo3bo2bo$2o3bo2bo7b2o10b2o3b3o122bo17b3o295bo
7bo$6bobo19bo6b2o3b2o11b2o120bob5o$7bobo18bo2b2o2b3o131b2o3b2o6bo13b2o
$9bo19bob2o11bo5bo111bo6b2o4b3obo3bo12b2o$44bo5bo111bo13b2o2bobo298bo$
161bobo315b2ob2o$160b2ob2o$159bo5bo313b2ob2o37b2o$108bo53bo316bo3bo38b
o$107bobo49b2o3b2o314b3o39bobo8bo$106bob2o10b2o352b2o47b2o8bobo$105b2o
b2o10b2o352b2o60b2o4b2o$106bob2o51bo374b2o4b2o$101b2o4bobo51bo374b2o$
100bobo5bo51bo372bobo21b2o$100bo432bo23b2o20bo$99b2o476b3o$162b2o412bo
$162b2o412b2o6$601b3o$588b3o8b2obob2o$588bo3bo5bo5b2o$588bo4bo5b2obob
2o$589bo3bo7b3o$547b2o$547b2o40bo3bo$588bo4bo$578b2o8bo3bo12b2o$578b2o
8b3o14b2o$568b2o$568bobo$570bo$570b2o4$520bobo3bobo$485bo21b2o2bobo8bo
3bo$483b4o19b3obo3bo3bo11bo$57b2o12bo410bobob2o17b2o6bo3bo3bo5bo3bo$
58b2o11bobo403b2o2bo2bob3o17bob5o5bo11bo$57bo14bobo4b2o396b2o3bobob2o
19b3o12bo3bo$72bo2bo3b2o402b4o33bobo3bobo$72bobo410bo21b3o$60b2o9bobo
432bob5o$59bobo9bo428b2o3b2o6bo13b2o$59bo440b2o4b3obo3bo12b2o$58b2o
447b2o2bobo2$572b2o$573bo$490b2o3b2o76bobo6bo$574b2o4bobo$491bo3bo83bo
bo11b2o$492b3o83bo2bo11b2o$492b3o84bobo$580bobo$582bo$533b2o$533b2o$
493b2o$493b2o6$533b3o3b3o117b2o$532bo2bo3bo2bo114bo2bo$532b2obo3bob2o$
656bo2$657b2o$16b2o24b3o7b2o605bo$15bobo23bo4bo4bo2bo$14b3o4b2o17bo5bo
4bo2bo$5b2o6b3o4bo2bo17bo8bo3bo601b2o3b2o$5b2o7b3o4b2o19b2o8b2o602b2o
3b2o$15bobo522bo116b5o$16b2o24b2o8b2o484b2ob2o115bobo$21bo19bo8bo487b
2ob2o127b2o$20bobo5b2o10bo5bo8b2o601b3o8bobo$19bo3bo4b2o11bo4bo9bo480b
obobobo124bo6b2o2b2o$19b5o18b3o7bo615bo2bo2bo2bob2o$18b2o3b2o27bo2bo
482b2ob2o125bo6b2o$19b5o509b2o4b3o71b2o54bobo$20b3o510b2o5bo73bo55b2o$
21bo592bobo6bobo$615b2o4bo3bo$621bo12b2o$527b2o91bo4bo8b2o28b2o$527bob
o91bo42b2o$518b3ob2o4b3o90bo3bo$518b4o2bo4b3o91bobo$522b2o4b3o8bo$527b
obo9bo$21b2o504b2o9bobo$21b2o514b2ob2o76bo$536bo5bo76b2o$539bo78b2o$
536b2o3b2o2$566b2o$540bo25b2o60bobo$540bo88b2o26b2o5b2o$541bo87bo27bob
2ob2obo269bobo$658bobobobo270b2o$658bobobobo271bo$538b2o117bo7bo$538b
2o$566b3o3b3o$566bo2bobo2bo$565bo3bobo3bo83b2ob2o$565b4o3b4o81bo2bobo
2bo$566bo7bo82b3o3b3o$658bo5bo371bo$1034b2o$657b2o5b2o369b2o$657b2o5b
2o3$573bo$572b3o$571bo3bo$571b2ob2o$571b2ob2o2$571b2ob2o$571b2ob2o32b
2o$566b2o3bo3bo32b2o$566b2o4b3o$573bo3$560b2o$560bobo46bo$551b3ob2o4b
3o44b3o43bo$551b4o2bo4b3o43b3o41bobo$555b2o4b3o8bo80b2o$560bobo9bo33b
2o3b2o$560b2o9bobo32b2o3b2o$570b2ob2o25bo$569bo5bo23b2o$572bo15b2o8b2o
4b2o3bo344bo$569b2o3b2o12b2o7b3o4b2o2bobo49bobo290bo$598b2o4b2o2bobo
50b2o290b3o$599b2o8bo44bobo4bo$573bo26bo54b2o52b2o$573bo81bo53b2o$574b
o2$603b2o98bo5bo$571b2o30b2o5bo91b3o3b3o$571b2o36b3o90bob2ob2obo$608bo
bobo88b2o7b2o$609bo2bo88b2o7b2o$609b3o89b3o5b3o$610bo92b3ob3o$705bobo$
702bo2bobo2bo$701bo2bo3bo2bo$702b2o5b2o$603bo7bo2$601b3o7b3o$602b2ob2o
b2ob2o29b2o$603b3o3b3o21bo8b2o$604bo5bo21bo5bo6b2o6b2o$632bob2o3bo5b3o
5b2o$633b6o6b2o$634b4o4b2o$642b2o89b2o3b2o$720bo3b2o6b3o3b3o$630b2obob
2o81b2obob3o4b3o7b3o$718bo4b3o4b3o7b3o$630bo5bo81bo3bo7b3o7b3o$719b3o
10b3o3b3o$631b2ob2o97b2o3b2o$603b2o5b2o21bo85b3o$603b2o5b2o46b2o58bo3b
o$658b2o52b2o4bo4b3o13b2o$712b2o4b2obob3o13b2o$720bo3b2o$633b2o$633b2o
7$658b3o3b3o$657bo3bobo3bo$656bo3b2ob2o3bo$656bob2o5b2obo$658bo7bo4$
719bo$720b2o5bo$664b3o52b2o7bo$664bobo59b3o$663bo3bo$663bo3bo2$658b2o
4b3o$658b2o4$655bo$655bobo$643b2o11bobo5bo83b2o$643b2o11bo2bo3b3o83bo$
656bobo3bo3bo82bobo7bobo$655bobo6bo85b2o7bo3bo$655bo5bo5bo95bo5b2o$
661bo5bo91bo4bo4b2o$662bo3bo96bo$663b3o93bo3bo$759bobo3$711b3o$711b3o$
705b2o3b5o$705b2o2b2o3b2o$709b2o3b2o$663b2o$663b2o2$709b2o3b2o$709b2o
3b2o$710b5o$711b3o$711b3o5$704b3o5b3o$704b3o5b3o$705b2o5b2o$707bo3bo$
705bo2bobo2bo$704bo3bobo3bo$705bo2bobo2bo$705b3o3b3o5$705b2o101b2o$
705b2o101b2o4$699b2o$699bobo$690b2o2b2o6bo$690b2obo2bo2bo2bo$694b2o6bo
$699bobo8b3o$699b2o$710bobo$709b5o$708b2o3b2o$708b2o3b2o3$711bo$712b2o
2$714bo2$710bo2bo$710b2o11$862bobo$862b2o$863bo2$810b2o$809bo$810bobo$
811bo55$871b2o$871b2o10$796b3o$797bo$797bo$796b3o2$796b3o$796b3o2$796b
3o$797bo$797bo$796b3o!
Last edited by chris_c on December 9th, 2015, 11:54 am, edited 1 time in total.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Searching algorithms

Post by simsim314 » August 19th, 2015, 5:44 pm

chris_c wrote:Actually it was fairly easy to make a base 3 converter instead of binary
Wow! Congrats on the so elegant design for the limited cells UC! This is truly simple design, and amazing execution.

I've written a small script, that converts slow salvo operations into UC design.

Code: Select all

import golly as g 

block = g.parse("2o$2o!")
UC = g.parse("\
384b2o$385bo$385bobo$386b2o6$385b2o$385b2o4b2o$391b2o4$390b2o$386b2o2b\
2o$385bobo$385bo12b2o$384b2o11bobo$397bo$396b2o5$398b2o$397bobo$397bo$\
396b2o7$406b2o$406b2o2$413bob2o$413b2obo5$896b2o$897bo$897bobo5bo$415b\
obo480b2o4bobo$415bo3bo483bob2o$419bo482b2ob2o10b2o$415bo4bo4b2o476bob\
2o10b2o$419bo5b2o477bobo$415bo3bo485bo$415bobo7$406b2obob2o$446b2o$\
406bo5bo34bo$447bobo$407b2ob2o36b2o$409bo2$370b2o8bo$370b2o6b3o$377bo$\
362b2o13b2o30b2o36b2o$363bo45b2o36b2o4b2o$363bobo87b2o$364b2o2$371b2o$\
371b2o79b2o$448b2o2b2o$447bobo$366bo21bo8b2o48bo12b2o$365bobo20b3o6b2o\
47b2o11bobo$365b2o24bo67bo$390b2o13b2o51b2o$405bo$374b2o27bobo$374b2o\
27b2o$398b2o$398b2o60b2o$373b2o8bo75bobo$373b2o6b3o75bo$380bo77b2o$\
365b2o13b2o20bo$366bo34bobo$366bobo33b2o$367b2o$372b2o$372b2o19b2o$\
393b2o73b2o$382bo85b2o$381b2o$369bo11bobo91bob2o$368bobo104b2obo$368b\
2o3$377b2o$377b2o3$375b2o103bo$375b2o11bo90bobo$366b2o3bo6b2o7bobo88bo\
3b2o$366bobo3bo5b3o97bo3b2o3b2o$367b5o6b2o8bo2bo86bo3b2o3b2o$368b3o4b\
2o14bo87bobo$375b2o12bo12bo2bob2obo2bo66bo$390bo11b4ob2ob4o$402bo2bob\
2obo2bo$383bo$381b2ob2o2$380bo5bo10b2o$397bobo107b2o$380b2obob2o10bo\
72b3o35bo$469bo3bo34bobo$410b2o56bo5bo34b2o$410bobo56bo3bo$400bo4b2o4b\
3o7b2o47b3o$399bobob2o2bo4b3o6b2o47b3o$387b2o9bo3bob3o4b3o18b2o8bo$\
380b2o5b2o9bo3bob2o4bobo19b2o6b3o$381bo16bo3b2o6b2o27bo68b2o$378b3o18b\
obo22b2o13b2o30b2o35b2o4b2o$378bo21bo24bo45b2o41b2o$425bobo$426b2o$\
431b2o$431b2o80b2o$509b2o2b2o$508bobo$508bo12b2o$428bo21bo8b2o46b2o11b\
obo$427bobo20b3o6b2o59bo$427b2o24bo65b2o$452b2o13b2o$467bo$436b2o27bob\
o$436b2o27b2o$521b2o$458b2o60bobo$435b2o8bo12b2o60bo$435b2o6b3o73b2o$\
442bo$427b2o13b2o20bo$428bo34bobo$428bobo33b2o$429b2o2$436b2o17b2o72b\
2o$436b2o17b2o72b2o2$536bob2o$431bo104b2obo$430bobo$430b2o3$439b2o9b2o\
$439b2o8b2o$451bo$539bo161bo$438bobo98bobo157b3o$438bo3bo99b2o154bo49b\
o$428b2o12bo99b2o4b2o147bobo48b3o$428b2o8bo4bo98b2o4b2o148bo52bo$442bo\
7b3o86bobo208b2o$438bo3bo7bo88bo223bo18bo5b2o12bo$438bobo10bo14bobo2bo\
bo222b2o63b3o18b3o3b2o10b3o$462b2obo2bo2bo2bob2o218b2o62bo24bo13bo$\
444b3o19bobo2bobo286b2o22b2o13b2o$444b3o$443bo3bo259b2o$442bo5bo9b2o\
248bo25bo11b2o$443bo3bo10bobo247bobo21b3o11b2o25b2o$444b3o11bo70b2o3b\
2o173b2o20bo41bo7b2o$731b2o38bobo8bo$530bo3bo70bo165b2o9bobo$472bobo\
56b3o72b2o175b2o$467b2o3bo2bo55b3o71b2o$460b2o2b2ob3o5b2o6b2o219bo$\
459bobo3bo3bo3bo3b2o4b2o8b2o8bo198b3o$449b2o7bo8bobo5b2o16b2o6b3o197bo\
$442b2o5b2o7bo2bo6b2o2bo2bo24bo200b2o38b2o$443bo14bo13bobo10b2o13b2o\
30b2o79bo127b2o26b2o$440b3o16bobo24bo45b2o80bo154b2o43b2o$440bo19b2o\
24bobo123b3o199bo$487b2o326b3o$492b2o323bo$492b2o124bo$616bobo91b2o32b\
2o38b2o$617b2o91b2o11b2o20bo39bo$723bo18b3o37b3o$489bo21bo8b2o202b3o\
15bo39bo$488bobo20b3o6b2o204bo65b2o$488b2o24bo161b2o114b2o$513b2o13b2o\
146b2o20b2o6b2o$528bo169bo7bo$497b2o27bobo170b3o5b3o$497b2o27b2o134b2o\
37bo7bo$662b2o$519b2o$496b2o8bo12b2o$496b2o6b3o183b2o$503bo186b2o3b2o\
107b2o$488b2o13b2o20bo117b2o50b2o101b2o4b2o$489bo34bobo116b2o153b2o$\
489bobo33b2o$490b2o204b2o$495b2o193b2o4bo$495b2o19b2o172b2o5b3o99b2o$\
516b2o181bo99b2o2b2o$803bobo$679b2o110b2o12bo$492bo186bobo109bobo11b2o\
$491bobo187bo111bo$491b2o188b2o110b2o3$500b2o155bo$500b2o154bobo$656b\
2o133b2o$791bobo$498b2o173b2o118bo$498b3o172bo58bo60b2o$489b2o9b2obo\
170b3o55b3o$489bo5bo4bo2bo172bo58bo$494bo5b2obo15b2o149b2o62b2o$490bo\
3bo3b3o18bobo142b2o4bo58bo$492bo5b2o19bo5bo2bob2obo2bo127b2o5b3o53b3o$\
524b2o2bo4bo2b2o135bo52bo$525bo2bob2obo2bo189b2o55b2o$505b3o208b2o56b\
2o7b2o$505b3o209bo57bo$504bo3bo208bobo55bobo$520b2o196b2o4b2o44b2o4b2o\
$503b2o3b2o9b2o202bo2bo44bo20b2o$521bo202b2o45bobo18bo$736b2o34b2o16bo\
bo$533b2o201b2o52b2o$533bo2bo$523bo3b3o7bo6b2o$522b5o3bo6bo6b2o$510b2o\
9b2ob2o3bo7bo$503b2o5b2o8b3ob2o3bo3bo2bo$504bo16b2ob4o5b2o$501b3o18b4o\
$501bo21bo198b2o3b2o32b2o$723bo3bo20b2o11b2o$720b3o5b3o18bo$720bo9bo\
15b3o35b2o$746bo37b2o2b2o$788bobo$790bo$790b2o13$831bob2o$831b2obo$\
838b2o$838bobo$838bo3$826b2o5b2o$826b2o5b2o2$830b2o$830b2o4$846bo6b2o$\
844b3o5bobo$843bo3bo$843bo4b3o6b2o$843b2obob3o6b2o$845bo3b2o43$827b2o$\
828b2o$827bo4$604bo$604b2o$603bobo5$619b3o$621bo$620bo15$797b2o$798b2o\
$797bo10$287bo18bobo$287b3o16bo3bo$290bo19bo7bo$289b2o5b2o8bo4bo4b4o$\
296b2o12bo4bobob2o$306bo3bo3bo2bob3o8b2o$306bobo6bobob2o9b2o$316b4o$\
318bo$289b2o3b2o11bo$289b2o3b2o11bobo$307b2o$291b3o$291b3o$292bo$312b\
2o6b2o$300bo10bo2bo4bo2bo$299bo11bo2bo4bo2bo$284bo14b3o9bo2bo4bo2bo\
444b2o$284b2o26b2o6b2o446b2o$279b2o4b2o480bo$275b2o2b2o4b3o$275b2o2b2o\
4b2o10b2o$284b2o11b2o$284bo3$286b2o$286b2o3$277b2o$277bobo$278bo3$283b\
2o17b2o$283b2o17b2o$731b2o$276b2o453b2o$275bobo33b2o$275bo34bobo$274b\
2o13b2o20bo416b2o$289bo438b2o$282b2o6b3o$282b2o8bo438b2o$307b2o422b2o$\
307b2o$283b2o27b2o423b2o$283b2o27bobo423b2o$314bo422bo$299b2o13b2o405b\
o$274b2o24bo419bobo$274bobo20b3o6b2o411b2ob2o$275bo21bo8b2o412bo2bo$\
720bo3bo$720bo2$278b2o$278b2o$273b2o$272bobo$272bo45b2o393b2o5bo$271b\
2o13b2o30b2o393bo6b2o$286bo427bo$279b2o6b3o423b2o8b2o$279b2o8bo433b2o\
3$318bo401b2o$317b3o400b2o$317b3o2$227bo11bo5b2o68b2o3b2o$227b3o7bo3bo\
3b3o67b2o3b2o$230bo10bo5b2obo8bo$229b2o5bo5bo4bo2bo6bobo$236b2o9b2obo\
5bobo58bo$245b3o7bo2bo11b2o44bobo$245b2o9bobo11b2o46bo$257bobo56b2o5b\
2o$249bo9bo63b2o$229b2obob2o11b2o77b2o6b2o$229bo5bo4bobo5b2o62bobo11b\
3o5b2o$230bo3bo4bo2bo67bobob2o10b2o$231b3o5bo2bo67bo3b2o7b2o$239b3o67b\
2obo10b2o$238b3o14b4o51bo$238b3ob2o10b6o51bo4b2o$238b2o2b2o9b8o$244bo\
7b2o6b2o50bo5bo$223bo17b2obo8b8o$222bobo16b3o10b6o52bo4bo$220b2o3bo16b\
o12b4o53bo2bo$215b2o3b2o3bo87b3o6b2obo$215b2o3b2o3bo96bob2o$222bobo$\
223bo91b2o$315b2o2$226b2o$226b2o3$217b2o$217bobo85b2o$218bo87bo$306bob\
o$307b2o$242b2o$221b2o19b2o$221b2o$216b2o$215bobo33b2o52b2o$215bo34bob\
o53bo$214b2o13b2o20bo41b2o11bobo$229bo64bo12b2o$222b2o6b3o61bobo$222b\
2o8bo12b2o48b2o2b2o$245b2o52b2o2$223b2o27b2o$223b2o27bobo$254bo45b2o$\
239b2o13b2o38b2o4b2o$214b2o24bo53b2o$214bobo20b3o6b2o$215bo21bo8b2o4$\
218b2o75b2o$218b2o74bobo$213b2o79bo$212bobo78b2o$212bo45b2o$211b2o13b\
2o30b2o$226bo$219b2o6b3o$219b2o8bo5$257b3o$256bo3bo$255bo5bo$255b2obob\
2o3$258bo$130bo19b2o105bobo$130b3o16b3o105bobo$133bo12bob2o15bo92bo4b\
2o$132b2o5b2o5bo2bo8b3o4bobo95bobo654bo$139b2o5bob2o16bobo89b2o6bo7b2o\
643b2o$149b3o2b2o2bo7bo2bo3b2o82bo2bo2bo2bo7b2o643bobo$150b2o2bo3bo7bo\
bo4b2o83b2o6bo$155bo2bo6bobo95bobo48b2o611b2o$155b2o8bo97b2o50b2o610bo\
bo$134b3o177bo612bo$133bo3bo$132bo5bo$132b2obob2o8bo$147bobo$147b2o9b\
4o$135bo21b6o$134bobo19b8o98b2obo$134bobo18b2o6b2o97bob2o$131bo3bo20b\
8o$130bobo24b6o92b2o$129bo3b2o11bobo9b4o93b2o$118b2o9bo3b2o11b2o$118b\
2o9bo3b2o12bo$130bobo$131bo3$129b2o114b2o$129b2o115bo$246bobo$247b2o$\
120b2o$120bobo$121bo2$245b2o$145b2o99bo$124b2o19b2o86b2o11bobo$124b2o\
108bo12b2o$119b2o113bobo$118bobo33b2o79b2o2b2o$118bo34bobo83b2o$117b2o\
13b2o20bo$132bo$125b2o6b3o303b2o$125b2o8bo12b2o90b2o197b2o$148b2o84b2o\
4b2o$234b2o203bo$126b2o27b2o281bobo75b2o$126b2o27bobo280bobo75b2o$157b\
o281bo265b2o$142b2o13b2o546b2o$117b2o24bo$117bobo20b3o6b2o84b2o199b2ob\
ob2o74bo$118bo21bo8b2o83bobo190b2o7bo5bo73bobo109b2o76bo$234bo192bo9bo\
3bo73bo3bo108b2o75b3o$233b2o193bo9b3o75b3o185bo3bo$427b2o85b2o3b2o185b\
o$121b2o327b2o53bo197bo5bo$121b2o326bobo52b3o196bo5bo$116b2o330bo6b2o\
2b2o42b2ob2o120bo75bo3bo8b2o$115bobo330bo2bo2bo2bob2o41b3ob3o117b2ob2o\
74b3o10bo$115bo45b2o285bo6b2o45b3ob3o10bo197bo$114b2o13b2o30b2o261b2o\
23bobo50b3ob3o10bo105bo5bo85b2o$129bo125b3o166b2o24b2o19bo30b3ob3o6b3o\
bo173b2o$122b2o6b3o28bo95bo213b3o29b2ob2o117b2obob2o7b3o49bo3bo$122b2o\
8bo27bobo73b2o18bo217bo29b3o7bo124bobo43b2o3bo5bo$160bobo72bobo235b2o\
6b2o22bo8b2obo121b3o43b2o2b2obo3bo$161bo75bo242bobo33b2o108bo12b3o48bo\
5bo41bo2bo$481bo144bo2bo9b3o49bo3bo24b2o13b2obo2b2o68b3o$258b2o366bo\
12b3o32bo18b2o25b2o13b2obo4bo67bo$158b2obob2o92bobo146b2o6b2o59b2o39b\
2o3b2o106b2o8bobo30b3o60b2o75bo$158bo5bo94bo146bo7bo53b2o5b2o39b2o3b2o\
107bo8b3o29bo65bo4b2o$159bo3bo243b3o5b3o50b2o47b5o106bobo32b2o6b2o64b\
2ob2o$160b3o246bo7bo86bo2bo10bobo107b2o33bobo$505bo2bo2b2o151bo$64bo\
19bo400b2o13b2o3bo3bo8b3o$64b3o17bobo148bo6bo242b2o13bobo3bo2b2o112b2o\
3b2o39b2o59b2o6b2o$67bo19b2o6b2o138b2o5b2o154b2o101bo121bo5bo39b2o5b2o\
53bo7bo$66b2o5b2o12b2o4bo3bo136bobo4bobo154b2o3b2o65b2o35b3ob3o125b2o\
35b2o50b3o5b3o$73b2o12b2o3bo5bo69b2o233b2o64bobo152bo3bo5bo6bo86bo7bo$\
84bobo4b2obo3bo8b2o58bobo299bo155b3o6bo3b3o$84bo7bo5bo8b2o57bo6b2o2b2o\
289b2o48b2o113bo3bo6b2o13b2o$93bo3bo68bo2bo2bo2bob2o211b2o12b2o112b2o\
113bo3bo5bobo13b2o$95b2o69bo6b2o216bo5b2o5bo105b2o121bo3bo6bo101b2o$\
66b2o3b2o12bo81bobo218b3o6b2o6b3o102bobo120b2ob2o36b2o65b2o3b2o$66b2o\
3b2o10b2o83b2o218bo18bo97b2o6bo160bobo64b2o$67b5o12b2o391b2o25bo2bo2bo\
2bo162bo$68bobo407bo21b3o2b2o6bo112b2o48b2o$478bobo19b3o7bobo6b2o105b\
2o112b2o12b2o$68b3o385b2o21b2o18bo3bo6b2o7bobo113b2o104bo5b2o5bo$89b2o\
6b2o358bo40bo5bo16bo112bo3bo99b3o6b2o6b3o$88bo2bo4bo2bo357bobo34b2o3bo\
3bo17b2o110bo5bo98bo18bo$76bobo8b6o2b6o357b2o34b2o4b3o130bo3bob2o26b2o\
$61b2o13b2o10bo2bo4bo2bo65b2obo464bo5bo4bo22bo$61bobo13bo11b2o6b2o66bo\
b2o304b2o10b2o138b2o7bo3bo4bobo19bobo$56b2o6bo408b2o2b2o6b2o137bobo8b\
2o5bo3bo18b2o21b2o$52b2obo2bo2bo2bo93b2o317b2o145bo18b3o42bo$52b2o2b2o\
6bo93b2o304b2o157b2o16b2o3b2o2b2o34bobo$61bobo392b2o6b2o184b2o34b2o$\
61b2o13bo379b2o32bo$75bo413bobo167b2o10b2o$75b3o404b2o6b2o167b2o6b2o2b\
2o$63b2o404bo13bo16b2o165b2o$63b2o403bobo9b3o17b2o$148b2o311b2o6b2o9bo\
207b2o$149bo205b2o105bo192bo25b2o5b2o$54b2o93bobo202bobo102b3o192bobo\
24b2o$54bobo93b2o201b3o103bo194b2o6b2o$55bo297b2o289b2o16bo13bo$353b2o\
77b2o210b2o17b3o9bobo$354bobo75b2o231bo9b2o6b2o$60b2o17b2o274bo327bo$\
60b2o17b2o67b2o534b3o$149bo283bo252bo$53b2o81b2o11bobo200b2o3b2o73bobo\
$52bobo33b2o47bo12b2o191b2o7b2o3b2o72bo3bo$52bo34bobo47bobo203bo87b5o\
380b2o$51b2o13b2o20bo49b2o2b2o200bo9b3o73b2o3b2o379b2o$66bo75b2o199b2o\
9b3o63b3o8b5o$59b2o6b3o285bo10b2o51bo3bo8b3o$59b2o8bo12b2o282b2o51bo3b\
o9bo305b2o$82b2o279b2o6bo3b2o43b3o316b2o$143b2o217b3o5bo3bobo$60b2o27b\
2o46b2o4b2o218b2o6b5o$60b2o27bobo45b2o201b2o24b2o4b3o59bo382bo$91bo\
248b2o24b2o19bo43b2o383b3o$76b2o13b2o294b3o30b3o8b3o381b5o8b2o$51b2o\
24bo312bo28bo3bo8b2o380bobobobo8bo$51bobo20b3o6b2o304b2o6b2o20bo3bo8bo\
381b2o3b2o7bo$52bo21bo8b2o311bobo21b3o8bobo394b2o$138b2o257bo33b2o317b\
3o54b2o$137bobo609bo3bo52bobo8bo$137bo184b2o6b2o405b5o6bo5bo41b2o7b3o\
4b2ob2obo$55b2o79b2o184bo7bo53b2o46b2obob2o297bob3obo53b2o6b3o4bo2b3ob\
o$55b2o266b3o5b3o50b2o6b2o26b2o315bo3bo5bo7bo49b3o4b2o3bo$50b2o273bo7b\
o58b2o26b2o3bo6bo5bo299b3o6bo7bo50bobo22b2o179b2o$49bobo371b2o314bo45b\
o21b2o22b2o179b2o$49bo45b2o304b2o21b2o7b2ob2o310bo5bo28b3o$48b2o13b2o\
30b2o304b2o32bo313bo3bo28bo$63bo250b2o434b3o21b2o6b2o151b2o$56b2o6b3o\
247b2o3b2o65b2o349bo36bobo157bo2bo$56b2o8bo252b2o64bobo349bo37bo158bo$\
385bo350bobo5bo189bo$384b2o48b2o299b2ob2o2bobo96b2o6b2o83bobo$94b3o\
209b2o12b2o112b2o298bo5bo2b2o42b2o53bo7bo83bobo$307bo5b2o5bo105b2o309b\
o13b2o26b2o6b2o50b3o5b3o85bo88b2o$94bobo207b3o6b2o6b3o102b2o306b2o3b2o\
10b2o26b2o58bo7bo162b2o3b2o8bo$93b5o206bo18bo94b5o6b2o516bo76bo$92b2o\
3b2o294b2o21bo6bo5b3o338b2o160b2o3b2o7b3o62bo3bo8b2o$92b2o3b2o295bo21b\
o4b2o6b2o305bo33b2o160bo5bo64bo8b3o$394bobo29b2o7b2o299bo120b2o144bobo\
6b3o$372b2o21b2o29b2o7bobo297bo49b2o65b2o3b2o74bo3bo8b3o43b2o12b2o$95b\
o277bo63bo347bobo64b2o80b3o55b2o12b2o$93b2o278bobo34b2o2b2o3b2o16b2o\
348bo158bobo57b2o$374b2o34b2o3b5o317b2o48b2o157bobo54bobo21b2o$92bo7b\
2o314b3o318b2o112b2o12b2o114bo21bo23b2o$92bo7b3o286b2o26bo325b2o107bo\
5b2o5bo80b3o30b3o$96bo5b2obo5b2o276b2o2b2o348bobo103b3o6b2o6b3o109bo$\
93bo8bo2bo5b2o280b2o5b2o342b3o102bo18bo101b2o6b2o$95b2o5b2obo274b2o18b\
2o343b3o30b2o158bo7b3o21bobo$100b3o269b2o6b2o362b3o31bo157bobo8bo23bo$\
100b2o270b2o32bo329b2o5bobo30bobo158b2o$405bobo327bobo5b2o31b2o21b2o\
236b2o6b2o$398b2o6b2o327bo63bo133bo49b2o53bo7bo$385bo13bo16b2o316b2o\
25b2o34bobo132b3o40b2o6b2o50b3o5b3o$384bobo9b3o17b2o337bo5b2o34b2o132b\
5o39b2o58bo7bo$205b2o170b2o6b2o9bo357b3o173b2o3b2o8bo$205b2o171bo374b\
5o24b2o147b5o10bo19b2o$375b3o374b2o3b2o19b2o2b2o147bo3bo8b3o19b2o$99b\
2obo102bo169bo377b5o13b2o5b2o152bobo118b2o$99bob2o101bobo75b2o469bo3bo\
13b2o160bo47b2o65b2o3b2o$204bobo75b2o470bobo42b2o180bobo64b2o$92b2o\
111bo549bo10bo25b2o5b2o151bo30bo$92b2o671bobo24b2o139b2o16b2o30b2o$\
765b2o6b2o158b2o16bobo93b2o12b2o$202b2obob2o74bo471b2o16bo13bo152bo9b\
3o6bobo86bo5b2o5bo$193b2o7bo5bo73bobo470b2o17b3o9bobo149bobo9b2o8b2o\
83b3o6b2o6b3o$193bo9bo3bo73bo3bo490bo9b2o6b2o140b2o12b2o8bo84bo18bo$\
194bo9b3o75b3o509bo141b2o36b2o$193b2o85b2o3b2o508b3o138b2o36bo$82b2o\
132b2o53bo525bo134b2o4bobo31bobo$83bo131bobo52b3o658bobo6bo31b2o21b2o$\
83bobo128bo6b2o2b2o42b2ob2o657bo63bo$84b2o128bo2bo2bo2bob2o41b3ob3o\
655b2o16b2o3b2o2b2o34bobo$214bo6b2o45b3ob3o10bo662b2o3b2o2b2o34b2o$\
190b2o23bobo50b3ob3o10bo663b5o$190b2o24b2o19bo30b3ob3o6b3obo664bobo13b\
2o10b2o$237b3o29b2ob2o692b2o6b2o2b2o$82b2o156bo29b3o7bo669b3o21b2o$83b\
o155b2o6b2o22bo8b2obo$70b2o11bobo160bobo33b2o711b2o$71bo12b2o161bo714b\
o25b2o5b2o$71bobo887bobo24b2o$72b2o2b2o94b2o6b2o100b2o3b2o672b2o6b2o$\
76b2o94bo7bo53b2o46b2o3b2o662b2o16bo13bo$173b3o5b3o50b2o6b2o31bo7b5o\
663b2o17b3o9bobo$175bo7bo58b2o30bo9bobo685bo9b2o6b2o$274b3o713bo$77b2o\
172b2o31b3o704b3o$71b2o4b2o172b2o18b2o720bo$71b2o91b2o105b3o$164b2o3b\
2o65b2o29b3ob2o$169b2o64bobo30b2o$235bo$234b2o48b2o$156b2o12b2o112b2o$\
72b2o83bo5b2o5bo105b2o$71bobo80b3o6b2o6b3o102bobo$71bo82bo18bo97b2o6bo\
$70b2o171b2o25bo2bo2bo2bo$244bo21b3o2b2o6bo$244bobo19b3o7bobo6b2o$222b\
2o21b2o18bo3bo6b2o7bobo797b2o$223bo40bo5bo16bo797b2o$223bobo34b2o3bo3b\
o17b2o796b2o$224b2o34b2o4b3o817bo$1008b2o75bobo$239b2o10b2o755b2o75bob\
o$239b2o2b2o6b2o833bo$243b2o2$222b2o784bo74b2o3b2o$222b2o5b2o25bo750b\
3o73bobobobo7b2o$229b2o24bobo748bo3bo73b5o9bo$248b2o6b2o747bob3obo73b\
3o9bo$235bo13bo16b2o738b5o75bo10b2o$234bobo9b3o17b2o751b3o52b2o$227b2o\
6b2o9bo771bo3bo51bobo$228bo788bo5bo41b3ob2o4b3o$225b3o837b4o2bo4b3o$\
225bo790bo7bo44b2o4b3o$1005b2o2bo6bo7bo49bobo23b2o$1007bobo44bo19b2o\
24b2o$1009b2o6bo5bo28b3o$1010b2o6bo3bo28bo$1008bob2o7b3o21b2o6b2o$\
1008b3o32bobo$1044bo2$1003b2o3b2o39b2o59b2o6b2o$1006bo42b2o5b2o53bo7bo\
$1003bo5bo46b2o50b3o5b3o$120b2o882b2ob2o6bobo90bo7bo$120b2o883bobo8b2o\
$1006bo9bo22b2o$1006bo32b2o$118bo78b2o824bo102b2o$119bo77b2o823b4o28b\
2o65b2o3b2o$119bo901bo4bo27bobo64b2o$1022bobobo29bo$197b3o806b2o16b2o\
30b2o$117b2o3b2o73b3o806b2o112b2o12b2o$108b2o10bo893b2o105bo5b2o5bo$\
108bo8bo5bo889bobo102b3o6b2o6b3o$109bo8b2ob2o62b3o824b3o4b2o97bo18bo$\
108b2o9bobo73b2o3b2o809b3o4bo2bo2bo22b2o$120bo9bobo51bo3bo7b5o811b3o4b\
2ob2obo21bo$120bo8bo2bo51bo3bo8b3o805b2o6bobo6bo3bo18bobo$128b2o10b2o\
56bo805bobo7b2o6b5o18b2o21b2o$126b2o3bo8b2o43b3o816bo16b2o3b2o40bo$\
128b2o5b2o866b2o17b5o3b2o34bobo798b2o$105b2o22bo2bo4bo885b3o4b2o34b2o\
799bo$105b2o23bobo19bo32b3o836bo840bobo$152b3o884b2o10b2o812b2o$155bo\
28bo3bo850b2o6b2o2b2o$154b2o6b2o20bo3bo8bo849b2o$161bobo31b2o863b2o$\
162bo22b3o8b2o862b2o6b2o$1035bo32b2o$87b2o6b2o59b2o876bobo829b2o$87bo\
7bo53b2o5b2o876b2o6b2o816b2o4b2o$88b3o5b3o50b2o873b2o16bo13bo803b2o$\
90bo7bo87b2o9b2o3b2o820b2o17b3o9bobo$182b2obob2o10b3o843bo9b2o6b2o$\
166b2o13bobobo12bo3bo860bo$166b2o13bo6bo10bobo862b3o794b2o$79b2o101bo\
3bo4bobo6bo865bo794b2o2b2o$79b2o3b2o65b2o34bobobobo1671bobo$84b2o64bob\
o1700b2o12bo$150bo1702bobo11b2o$149b2o48b2o1654bo$71b2o12b2o112b2o\
1654b2o$72bo5b2o5bo99bo5bobo$69b3o6b2o6b3o95bo2bo3bo2bo$69bo18bo98bo6b\
2o$158b2o23b2o3bo3bo3b2o$159bo34b2o1657b2o$149bo9bobo29bo2bo5b2o1651bo\
bo$137b2o9bo11b2o29bobo6bobo1652bo$138bo9b3o51bo1652b2o$138bobo34b2o2b\
2o3b2o16b2o$139b2o34b2o2bobobobo$180b5o$154b2o25b3o$154b2o2b2o22bo$\
158b2o5b2o$165b2o1678b2o$137b2o1706b2o$137b2o5b2o25bo$144b2o24bobo\
1663b2obo$163b2o6b2o1663bob2o$150bo13bo16b2o$149bobo9b3o17b2o$142b2o6b\
2o9bo$143bo$140b3o$140bo2$1837bo$1834b4o$1833b4o$51b2o1773b2o5bo2bo$\
51b2o1773b2o5b4o$1834b4o$1837bo$128b2o$49b2o77b2o1714b2o2$129bo$128bob\
o$128bobo$39b2o7b2o3b2o74bo1710b2o3b2o$39bo9b5o63bo1723b5o$40bo8b2ob2o\
63bo1723b2ob2o$39b2o8b2ob2o62b3o7b2obob2o1708b2ob2o$50b3o9bo63bo5bo\
1709b3o$59b4o64bo3bo$58b4o9b2o43b3o9b3o$58bo2bo9b2o44bo1754bo8b2o$58b\
4o5bo49bo1754b3o6b2o$36b2o21b4o4bo49bo1757bo$36b2o24bo20bo33bo1724b2o\
30b2o13b2o$83b3o30b3o1723b2o45bo$86bo1800bobo$85b2o6b2o32bo1759b2o$92b\
obo21b3o7bo$93bo23bo8b3o1751b2o$117bo1762b2o$18b2o6b2o59b2o$18bo7bo53b\
2o5b2o$19b3o5b3o50b2o1772b2o8bo21bo$21bo7bo99b5o1720b2o6b3o20bobo$119b\
o8bob3obo1726bo24b2o$97b2o20bobo7bo3bo1712b2o13b2o$97b2o20b2o9b3o1714b\
o$10b2o119bo1715bobo27b2o$10b2o3b2o65b2o1764b2o27b2o$15b2o64bobo1769b\
2o$81bo1771b2o$80b2o30bo17b2o1737bo8b2o$2b2o12b2o87bo5b3o16b2o1737b3o\
6b2o$3bo5b2o5bo86b2o6b2o10bo1748bo$3o6b2o6b3o84b2o7bo3bo5b4o1723bo20b\
2o13b2o$o18bo93bobo2b2o4b4o1721bobo34bo$89b2o33bo2bo1721b2o33bobo$90bo\
33b4o1756b2o$90bobo30b4o4b2o$68b2o21b2o30bo7bobo1724b2o17b2o$69bo63bo\
1724b2o17b2o$69bobo34b2o2b2o3b2o16b2o$70b2o34b2o2bo5bo$1883bo$85b2o10b\
2o12bo3bo1766bobo$85b2o2b2o6b2o13b3o1768b2o$89b2o$76b2o$68b2o6b2o1796b\
2o$68b2o32bo1771b2o$101bobo$94b2o6b2o$81bo13bo16b2o1762b2o$80bobo9b3o\
17b2o1760bo2bo7bo$73b2o6b2o9bo1780bo7b2o3bo$74bo1798bo6bo5bo$71b3o\
1799bo7b5o$71bo1802bo2bo$1839bo2bo4bo2bo4b2o19b2o$1837b3o2b6o2b3o2b2o$\
1839bo2bo4bo2bo2$1868b3o$1867b2ob2o$1854bo12b2ob2o$1854b2o11b5o$1853bo\
bo10b2o3b2o2$1841b2o$1840bobo$1830b2o7bo6b2o4bo$1830b2o7bo2bo2bo2bo2bo\
bo$1839bo6b3obob2o10b2o$1840bobo6b2ob2o10b2o5b2o$1841b2o7bob2o17bo$\
1851bobo18b3o$1852bo21bo77$915bo$886b2o26bob5o$887bo26bo2b4ob2o$887bob\
o25b3o$888b2o2$923b3o$892b3o27b2o3bo$892bo2bo24b2o3bobo$892bob2o23bobo\
5bo$887b2o29bo4b3o$887bo29bo6bo$918bo$893b3o23b4o$891b5o9b2o27bo$890b\
3o12b2o25bobo$890b2obo39b2o$888b3ob2o$887bobo24b2o$887bo12b2o12b2o$\
886b2o11bobo$899bo$898b2o3$1598bo$1596b2o$900b2o695b2o$899bobo$899bo$\
898b2o7$908b2o$908b2o2$915bob2o$915b2obo8$919b2o$918bo3bo$917bo5bo$\
917bo3bob2o2b2o$917bo5bo3b2o$918bo3bo$919b2o7$910b3o$909bo3bo$908bo5bo\
$908bo5bo$911bo$909bo3bo$910b3o$872b2o8bo28bo$872b2o6b3o$879bo$864b2o\
13b2o30b2o$865bo45b2o$865bobo$866b2o$871b2o$871b2o81b2o$955bo$955bobo$\
956b2o$868bo21bo8b2o$867bobo20b3o6b2o$867b2o24bo$892b2o13b2o1249b2o$\
907bo1250bo$876b2o27bobo47b2o1199bobo$876b2o27b2o48b2o4b2o1193b2o$900b\
2o59b2o$900b2o$875b2o8bo$875b2o6b3o$882bo77b2o$867b2o13b2o20bo51b2o2b\
2o1195b2o$868bo34bobo49bobo1193b2o4b2o$868bobo33b2o49bo12b2o1181b2o$\
869b2o83b2o11bobo$967bo$876b2o17b2o69b2o$876b2o17b2o1255b2o$2152b2o2b\
2o$2156bobo$871bo1272b2o12bo$870bobo95b2o1174bobo11b2o$870b2o95bobo\
1176bo$967bo1178b2o$890bo75b2o$879b2o8b2o$879b2o8bobo2$2144b2o$880bo\
1263bobo$880bobo1263bo$868b2o11bobo92b2o1168b2o$868b2o11bo2bo5b2o84b2o\
$881bobo6bobo$880bobo7bo92bob2o$880bo25b8o69b2obo$885bo20bob4obo$884b\
3o19b8o$883bo3bo1248b2o$885bo1250b2o$882bo5bo8b3o$882bo5bo8bo1229b2obo\
$883bo3bo10bo1228bob2o$884b3o97bo$982bobo$913bobo65bobo$905b3o5bo3bo\
62bo2bo11b2o$900b2o2bo2bobo7bo5b2o56bobo11b2o$898bo2bo2b2o7bo4bo4b2o\
57bobo$889b2o6bo19bo66bo$882b2o5b2o6bo10b3o2bo3bo1207bo$883bo13bo15bob\
o63bo1144bobo$880b3o15bo2bo76bobo1142bob2o$880bo19b2o75bo3bo1135b2o3b\
2ob2o$978b3o1136b2o4bob2o$976b2o3b2o1141bobo$2125bo7$940b2o8bo76b2o$\
940b2o6b3o77bo$947bo7b3o70bobo1101b5o$932b2o13b2o8bo21b2o48b2o1100bob\
3obo$933bo22bo22b2o1078bobo70bo3bo$933bobo1123b2o72b3o$934b2o2bobo\
1119bo73bo$937bo2bo1222bo8b2o$937bo1225b3o6b2o$938bobo87b2o1136bo$\
1028b2o4b2o1097b2o30b2o13b2o$1034b2o1097b2o45bo$936bo21bo8b2o1209bobo$\
935bobo20b3o6b2o1209b2o$935b2o24bo1211b2o$960b2o13b2o56b2o1138b2o$975b\
o53b2o2b2o$944b2o27bobo52bobo$944b2o27b2o53bo12b2o$968b2o57b2o11bobo\
1102b2o8bo21bo$968b2o70bo1104b2o6b3o20bobo$943b2o8bo85b2o1111bo24b2o$\
943b2o6b3o1183b2o13b2o$950bo1187bo$935b2o13b2o20bo1165bobo27b2o$936bo\
34bobo1165b2o27b2o$936bobo33b2o67b2o$937b2o101bobo1103b2o$942b2o96bo\
1105b2o12bo8b2o$942b2o19b2o74b2o1119b3o6b2o$963b2o1198bo$2141bo20b2o\
13b2o$2140bobo34bo$939bo1200b2o33bobo$938bobo1234b2o$938b2o1230b2o$\
1049b2o1098b2o19b2o$1049b2o1098b2o$947b2o$947b2o107bob2o$1056b2obo\
1114bo$2173bobo$946bobo13b2o1210b2o$945bo2bo13bobo$936b2o6b2o16bo$936b\
2o4b2o3bo1217b2o$944b2o1219b2o$945bo2bo$946bobo22b2o3bo2bo3b2o74b2o$\
971b5o4b5o72bo2bo1106bo$963b2o6b2o3bo2bo3b2o71bo7b5o1095b4o$962b2o92bo\
6bo5bo1093b4o9b2o$964bo91bo7b2o3bo1093bo2bo9b2o$1057bo2bo7bo1077b3o14b\
4o5bo$1059b2o1087bo15b4o4bo$2129bo2b2o4b2o2bo4bo19bo$2128bo3b3o2b3o3bo\
$950b2o3b2o14bo1157bo2b2o4b2o2bo17bo$952b3o15b2o10b2o1175b3o$951bo3bo\
14bobo9b2o67b3o1104bo3bo$952bobo10b2o12b2o6bo3b2o57bo3bo1091bo10bob3ob\
o$953bo9bo3bo10b3o5bo3bobo1153b2o10b5o$957b2o3bo5bo10b2o6b5o57bo5bo\
1089bobo$950b2o5b2o2b2obo3bo13b2o4b3o58b2o3b2o$951bo10bo5bo13b2o$948b\
3o12bo3bo1164b2o$948bo16b2o85bo1078b3o3b2obo$1051bobo1067b2o5bob2o5bo\
3bo2bo$1013b2o8bo27bobo1067b2o5bo2bo4bo4bo2b2o$1013b2o6b3o27bo1076bob\
2o4b4o5b2o8b2o$1020bo30bo1079b3o3bo7b3o7b2o5b2o$1005b2o13b2o29bo2bo\
1077b2o11b2o15bo$1006bo45b2o1090b2o17b3o$1006bobo1135bo20bo$1007b2o2$\
1014b2o$1014b2o2$1095b2o$1009bo21bo8b2o54bo$1008bobo20b3o6b2o54bobo$\
1008b2o24bo62b2o$1033b2o13b2o$1048bo$1017b2o27bobo$1017b2o27b2o2$1039b\
2o55b2o$1016b2o8bo12b2o55b2o4b2o$1016b2o6b3o75b2o$1023bo$1008b2o13b2o\
20bo$1009bo34bobo$1009bobo33b2o54b2o$1010b2o85b2o2b2o$1096bobo$1017b2o\
17b2o58bo12b2o$1017b2o17b2o57b2o11bobo$1108bo$1107b2o$1012bo$1011bobo$\
1011b2o2$1109b2o$1020b2o86bobo$1020b2o86bo$1107b2o2$1021b2o$1020bo3bo$\
1009b2o8bo5bo$1009b2o8bo3bob2o7bo$1019bo5b2o8bo$1020bo4b2o6b2o12bo6bo\
62b2o$1021b2o3bo6bobo10b2o6b2o61b2o$1025bobo17b3o6b3o$1025bobo6bobo9b\
2o6b2o68bob2o$1026bo8bo11bo6bo69b2obo$1035b2ob2o$1037bo$1023b2o3b2o8bo\
$1023bo5bo2$1024bo3bo$1025b3o17bo2bo8bo$1045bo10bobo66b2o$1041bo2bo3b\
2o5bo3b2o3b2o59bobo$1038b4o3b2obobo4bo3b2o3b2o54b2o4b3o$1030b2o5b4o14b\
o3b2o58bo2bo4b3o6b2o$1023b2o5b2o5bo2bo8b2o5bobo61b2o4b3o7b2o$1024bo12b\
4o16bo62b2o3bobo$1021b3o14b4o78bo4b2o$1021bo19bo77bobo$1119bobo$1120bo\
3$1117b2o3b2o$1117bobobobo$1118b5o$1119b3o$1120bo4$1081b2o8bo$1081b2o\
6b3o$1088bo$1073b2o13b2o30b2o$1074bo45b2o$1074bobo$1075b2o2$1082b2o$\
1082b2o3$1077bo21bo8b2o$1076bobo20b3o6b2o$1076b2o24bo$1101b2o13b2o$\
1116bo$1085b2o18b2o7bobo$1085b2o19b2o6b2o$1105bo3b2o$1109b2o$1084b2o8b\
o$1084b2o6b3o$1091bo$1076b2o13b2o20bo$1077bo34bobo$1077bobo33b2o$1078b\
2o$1083b2o$1083b2o19b2o$1104b2o3$1080bo$1079bobo$1079b2o3$1088b2o$\
1088b2o3$1085bo$1083b4o$1077b2o3bobob2o$1077b2o2bo2bob3o14b2o13b2o$\
1082bobob2o13bo2bo11bo4bo$1083b4o13bo14bo6bo$1085bo14b2o12bo8bo$1104b\
2o8bo8bo$1104b2o8bo8bo$1115bo6bo$1116bo4bo$1094bo23b2o$1093b3o$1092b5o\
1327b2o$1091bobobobo11b3o1312bo$1091b2o3b2o11bo1312bobo$1110bo9bo1301b\
2o$1119bobo$1107bobo8bob2o10b2o$1107bo2bo6b2ob2o10b2o$1098b2o10b2o6bob\
2o$1091b2o5b2o8bo3b2o5bobo$1092bo10b2o5b2o8bo1302b2o$1089b3o10bo4bo2bo\
1306b2o4b2o$1089bo17bobo1307b2o4$2418b2o$2418b2o2b2o$2422bobo$2410b2o\
12bo$2410bobo11b2o$2412bo$2412b2o3$1248b2o$1249bo$1249bobo1158b2o$\
1250b2o1158bobo$2412bo$2412b2o4$1249b2o$1249b2o4b2o$1255b2o$2402b2o$\
2402b2o2$1254b2o1137b2obo$1250b2o2b2o1137bob2o$1249bobo$1249bo12b2o$\
1248b2o11bobo$1261bo$1260b2o3$2394b2o$2392bo2bo$1262b2o1127bo7b2o$\
1261bobo1119b2o6bo6bo2bo$1261bo1121b2o6bo6bo2bo$1260b2o1130bo2bo5bo$\
2394b2o5bo$2399bobo$2399bobo$2400bo3$1270b2o1125b2o3b2o$1270b2o1125bo\
5bo2$1277bob2o1117bo3bo$1277b2obo1118b3o4$2429bo8b2o$2429b3o6b2o$2432b\
o$2399b2o30b2o13b2o$1278b2o1119b2o45bo$1278bobo1163bobo$1273b2o6bo\
1162b2o$1272bo2bo2bo2bo7b2o$1273b2o6bo7b2o1146b2o$1278bobo1156b2o$\
1273bo4b2o$1272bobo$1272bobo1136b2o8bo21bo$1273bo1137b2o6b3o20bobo$\
2418bo24b2o$2403b2o13b2o$1270b2obob2o1127bo$1270bo5bo1127bobo27b2o$\
1271bo3bo1129b2o27b2o$1272b3o$2412b2o$2412b2o12bo8b2o$2426b3o6b2o$\
2429bo$1234b2o8bo1162bo20b2o13b2o$1234b2o6b3o1161bobo24b2o8bo$1241bo\
1164b2o24b3o6bobo$1226b2o13b2o30b2o1161bo4b2o$1227bo45b2o1159b2obo$\
1227bobo1185b2o17b2o$1228b2o1185b2o2$1235b2o$1235b2o1203bo$1326b2o\
1111bobo$1327bo1112b2o$1230bo21bo8b2o64bobo$1229bobo20b3o6b2o65b2o$\
1229b2o24bo1175b2o$1254b2o13b2o1160b2o$1269bo$1238b2o27bobo$1238b2o27b\
2o1165b2o$1262b2o63b2o1092bo11bo3bo$1262b2o63b2o4b2o1086bo10bo5bo3b2o$\
1237b2o8bo85b2o1086bo10bo3bob2o2b2o$1237b2o6b3o1184bo5bo$1244bo1153bo\
6bo27bo3bo$1229b2o13b2o20bo1130b2o6b2o10b2o15b2o$1230bo34bobo64b2o\
1062b3o6b3o10b2o$1230bobo33b2o60b2o2b2o1063b2o6b2o10bo$1231b2o94bobo\
1068bo6bo$1327bo12b2o$1238b2o17b2o67b2o11bobo1083b3o$1238b2o17b2o80bo\
1084bo3bo$1338b2o1070bo$2410b2o11bo5bo$1233bo13b2o1160bobo11b2o3b2o$\
1232bobo12bobo1150bo$1232b2o13bo1151bobo$1340b2o1045b2o9bo3b2o8bo$\
1339bobo1045b2o9bo3b2o5b4o$1241b2o96bo1058bo3b2o4b4o9b2o$1241b2o95b2o\
1059bobo6bo2bo9b2o5b2o$2400bo7b4o5bo10bo$2409b4o4bo11b3o$1238bo1173bo\
18bo$1237bobo12bo$1230b2o3b2o3bo10bobo$1230b2o3b2o3bo11b2o$1235b2o3bo\
29b4o74b2o$1237bobo29b6o73b2o$1238bo17bo11b8o$1255b2o10b2o6b2o78bob2o$\
1255bobo10b8o79b2obo$1269b6o$1270b4o2$1246b3o$1245bo3bo$1244bo5bo12b2o\
$1244b2obob2o11b2o$1264bo9bo82bo$1272bobo80bobo$1260b2o9bobo11b2o66b2o\
$1260b3o7bo2bo11b2o66b2o12b2o$1251b2o9b2obo5bobo79b2o12b2o$1244b2o5bo\
5bo4bo2bo6bobo80bobo$1245bo10bo5b2obo8bo82bo$1242b3o7bo3bo3b3o$1242bo\
11bo5b2o$1350b3o$1350b3o$1349bo3bo2$1348b2o3b2o7$1312b2o8bo$1312b2o6b\
3o66b2o$1319bo70bo$1304b2o13b2o30b2o37bobo$1305bo45b2o38b2o$1305bobo$\
1306b2o$1311b2o$1311b2o2$1321bo68b2o$1320b2o68b2o4b2o$1308bo11bobo7bo\
8b2o55b2o$1307bobo20b3o6b2o$1307b2o24bo$1332b2o13b2o$1347bo47b2o$1316b\
2o27bobo43b2o2b2o$1316b2o27b2o43bobo$1340b2o48bo12b2o$1340b2o47b2o11bo\
bo$1315b2o8bo76bo$1315b2o6b3o75b2o$1322bo$1307b2o13b2o20bo$1308bo34bob\
o$1308bobo33b2o$1309b2o92b2o$1314b2o86bobo$1314b2o19b2o65bo$1335b2o64b\
2o3$1311bo$1310bobo$1310b2o2$1411b2o$1319b2o90b2o$1319b2o$1418bob2o$\
1418b2obo$1319b2o$1318b3o$1308b2o5bob2o17bo$1308b2o5bo2bo16bobo$1315bo\
b2o16bo2bo$1318b3o17bo$1319b2o14bo2bo5bo2bob2obo2bo$1336b3o4b2o2bo4bo\
2b2o63bobo$1335b2ob2o4bo2bob2obo2bo64bo3bo$1334b5o85bo$1334b4o82bo4bo\
4b2o$1334bo89bo5b2o$1420bo3bo$1420bobo$1322b2o3b2o2$1323bo3bo14b3o9b2o\
$1324b3o15bo9bo2bo7bo$1324b3o10bo5bo7bo7b2o3bo$1335b4o12bo6bo5bo$1329b\
2o3bobob2o11bo7b5o47b2obob2o$1322b2o5b2o2bo2bob3o11bo2bo$1323bo10bobob\
2o14b2o55bo5bo$1320b3o12b4o$1320bo16bo74b2ob2o$1414bo2$1375b2o8bo$\
1375b2o6b3o$1382bo$1367b2o13b2o30b2o$1368bo45b2o$1368bobo$1369b2o$\
1374b2o$1374b2o4$1371bo21bo8b2o$1370bobo20b3o6b2o$1370b2o24bo$1395b2o\
13b2o$1410bo$1379b2o27bobo$1379b2o27b2o2$1401b2o$1378b2o8bo12b2o$1378b\
2o6b3o$1385bo$1370b2o13b2o20bo$1371bo34bobo$1371bobo33b2o$1372b2o2$\
1379b2o17b2o$1379b2o17b2o3$1374bo$1373bobo$1373b2o$1534bo$1532bobo$\
1382b2o149b2o$1382b2o2$1533bo$1380b2o149bobo5bo$1380b2o150b2o6b2o37bob\
o$1371b2o3bo6b2o13b2o139b2o38b2o$1371bobo3bo5b3o11bobo180bo$1372b5o6b\
2o12bo$1373b3o4b2o128b2o$1380b2o16bo2bo5bo2bob2obo2bo92bo$1401bo5b4ob\
2ob4o92bobo$1400b2o5bo2bob2obo2bo93b2o$1388bo$1386b2ob2o4bo$1396b2o$\
1385bo5bo4b2o4b2o$1397bo4bobo$1385b2obob2o3b2o5bo108b2o$1511b2o4b2o$\
1415b2o100b2o$1415bobo$1405bo4b2o4b3o7b2o$1404bobob2o2bo4b3o6b2o$1392b\
2o9bo3bob3o4b3o97b2o$1385b2o5b2o9bo3bob2o4bobo94b2o2b2o$1386bo16bo3b2o\
6b2o94bobo$1383b3o18bobo104bo12b2o$1383bo21bo104b2o11bobo$1523bo$1522b\
2o5$1524b2o$1523bobo$1523bo$1522b2o7$1532b2o$1532b2o$1583bo$1539bob2o\
38bobo482bo$1539b2obo39b2o480b2o$2065b2o7$1541bo$1539bobo$1537b2o$\
1537b2o12b2o$1537b2o12b2o$1539bobo$1541bo3$1534b3o$1534b3o$1533bo3bo2$\
1532b2o3b2o7$1496b2o8bo$1496b2o6b3o$1503bo$1488b2o13b2o30b2o$1489bo45b\
2o$1489bobo$1490b2o$1495b2o$1495b2o4$1492bo21bo8b2o$1491bobo20b3o6b2o$\
1491b2o24bo$1516b2o13b2o$1531bo$1500b2o27bobo$1500b2o27b2o$1518b2o4b2o\
$1519b2o3b2o$1499b2o8bo8bo$1499b2o6b3o$1506bo$1491b2o13b2o20bo$1492bo\
34bobo$1492bobo33b2o$1493b2o$1498b2o$1498b2o19b2o$1519b2o3$1495bo$\
1494bobo$1494b2o3$1503b2o$1503b2o3$1503b2o$1502b3o10bo$1492b2o5bob2o$\
1492b2o5bo2bo14b3o$1499bob2o14b2o$1502b3o11b2o$1503b2o6b3o2bo11bo2bob\
2obo2bo$1510bo16b2o2bo4bo2b2o$1519b2o7bo2bob2obo2bo$1519bobo$1519bo4$\
1506b2o3b2o2$1507bo3bo14b3o9b2o$1508b3o15bo9bo2bo7bo$1508b3o10bo5bo7bo\
7b2o3bo$1519b4o12bo6bo5bo$1513b2o3bobob2o11bo7b5o$1506b2o5b2o2bo2bob3o\
11bo2bo$1507bo10bobob2o14b2o$1504b3o12b4o$1504bo16bo13$1651b2o$1652bo$\
1652bobo$1653b2o6$1652b2o$1652b2o4b2o$1658b2o4$1657b2o$1653b2o2b2o$\
1652bobo$1652bo12b2o$1651b2o11bobo$1664bo$1663b2o5$1665b2o$1664bobo$\
1664bo$1663b2o7$1673b2o$1673b2o2$1680bob2o$1680b2obo8$1681b2o$1681bobo\
$1676b2o6bo$1675bo2bo2bo2bo7b2o$1676b2o6bo7b2o$1681bobo$1676bo4b2o$\
1675bobo$1675bobo$1676bo3$1673b2obob2o$1673bo5bo$1674bo3bo$1675b3o5$\
1637b2o8bo$1637b2o6b3o$1644bo$1629b2o13b2o30b2o$1630bo45b2o$1630bobo$\
1631b2o2$1638b2o$1638b2o3$1633bo21bo8b2o$1632bobo20b3o6b2o$1632b2o24bo\
$1657b2o13b2o$1672bo$1641b2o27bobo$1641b2o27b2o2$1663b2o$1640b2o8bo12b\
2o$1640b2o6b3o$1647bo$1632b2o13b2o20bo$1633bo34bobo$1633bobo33b2o$\
1634b2o2$1641b2o17b2o$1641b2o17b2o3$1636bo$1635bobo$1635b2o3$1644b2o$\
1644b2o2$1657b3o$1641bo15bo$1640bobo15bo$1633b2o3b2o3bo$1633b2o3b2o3bo\
$1638b2o3bo29b4o$1640bobo29b6o$1641bo17bo11b8o$1658b2o10b2o6b2o$1658bo\
bo10b8o$1672b6o$1673b4o2$1649b3o$1648bo3bo$1647bo5bo12b2o$1647b2obob2o\
11b2o$1667bo9bo$1675bobo$1663b2o9bobo11b2o$1663b3o7bo2bo11b2o$1654b2o\
9b2obo5bobo$1647b2o5bo5bo4bo2bo6bobo$1648bo10bo5b2obo8bo$1645b3o7bo3bo\
3b3o$1645bo11bo5b2o115$1995b2o$1995b2o40$1976b2o$1976b2o!\
")

operations = g.getstring("Please enter slow salvo oeprations left to righ \nPush = 0, Shoot = 1, Pull = 2", "110120")


decimal = 0

for i in xrange(0, len(operations)):
	decimal *= 3
	decimal += int(operations[i])
g.new("")
g.putcells(UC)
g.putcells(block, 630 + decimal, 211 - decimal)
g.fit()
@dvgrn - Regarding my suggestion about static tape, I wasn't talking about limited cells UC. I was talking about the option to use this same technology, to design executable patterns, obviously with unbounded size. We could for example "Giminize" Chris's design.

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

Re: Searching algorithms

Post by dvgrn » August 19th, 2015, 8:39 pm

simsim314 wrote:@dvgrn - Regarding my suggestion about static tape, I wasn't talking about limited cells UC. I was talking about the option to use this same technology, to design executable patterns, obviously with unbounded size. We could for example "Giminize" Chris's design.
There's a static tape in Golly's Patterns/Life/Signal-Circuitry/constructor-memory-tape.rle. Paul Chapman and I discussed designs back and forth for several years, but never really found anything that was worth building. It's so much less efficient to encode recipes in digital form on a static tape, that the overall size of the design had a tendency to explode.

For a Geminization of Chris's decoder, presumably we'd have to end up with a copy of the static tape some distance away, where the copy of the circuitry could act on it. Gemini's glider-stream data moves to the new location pretty much automatically, but with a static tape it seems like we'd need a lot of extra circuitry to make the copy.

It was partly the fact that the Gemini design simply threw away three-quarters of the circuitry in constructor-memory-tape.rle, that made it such a huge leap forward... I'm not so sure it's a good idea to go back, at least unless we can do something really new like a 2D memory array, or callable subroutines. The limited-cells UC doesn't need anything like this -- add more circuitry of any kind, and it will just increase N, with no practical good effects.

An interesting trick along the static-tape line might create a new ultra-slow knightship, though. If we found a tape-reading reaction that produced a glider and a new block at (2,1) -- let's say (if a block codes for a 1 and empty space codes for a 0) -- then the tape could tell the U.C. to build slow salvo-seeds, or synchronized-salvo seeds for that matter, that would shoot down the U.C. and rebuild it at a (2,1) offset. I''d certainly love to see a pattern like that in operation!

Some diamond-shaped Geminoid spaceship designs could use a similar trick, and the amount of circuitry that.would have to be destroyed and rebuilt is actually quite small... but different at each of the four corners of the diamond, so probably each corner would read a different quarter of the construction recipe, maybe using chains of three semi-Snarks.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Searching algorithms

Post by praosylen » September 17th, 2015, 5:05 pm

I have an idea for a nonexhaustive but faster version of the WLS/JLS algorithm. It works essentially the same, but throws away branches that appear unlikely to be completed, and discounts trivial stator variants or disconnected solutions. It is likely to be significantly faster with things like finding high-period patterns (because such searches contain many unpromising branches that waste a lot of time) or finding low-period ships where small examples are already known (because once the small example is found, the search wastes time trying to add cells way behind it that do not interact with it in any way). I am not sure how to measure a criterion for determining which branches are promising, but I think with some modification there would be some way to implement this. However, I don't know how much of a performance boost would be gained.

In case you're wondering, I basically took everything I disliked about JLS and figured out a possible way to improve it. This was not really any special insight; I prune searches manually sometimes and I figured it might be easier to have an automated way to do that.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

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

Re: Searching algorithms

Post by dvgrn » September 17th, 2015, 6:05 pm

A for awesome wrote:I have an idea for a nonexhaustive but faster version of the WLS/JLS algorithm. It works essentially the same, but throws away branches that appear unlikely to be completed, and discounts trivial stator variants or disconnected solutions.
The variant of this idea that I've been trying to get a handle on for years, is a hash-enabled WLS/JLS. The key would be successful partitioning of the problem: if there were a way to monitor the search and recognize that a lot of searches were being duplicated because Section A was actually completely independent of Section B, then it would be possible to run a Section A search just once, and a Section B search just once.

Then you could simply output the result that any Section A solution could be combined with any Section B solution, and safely skip a huge chunk of the search space.

Roughly speaking, this could theoretically speed things up from O(n^2) to O(2n), I suppose, which would be a Really Really Big Improvement (sorry for the technical math jargon). The problem is that there are ridiculous numbers of possible Sections A and B, and I don't see how to record them all in a hash table, or to check in a reasonable amount of time whether JLS/WLS has entered the kind of brain-dead loop that it would be so nice to avoid.

So far, it seems as if a very clever helper algorithm would be needed to do this: HLPR, let's call it, short for Human-Like Pattern Recognition. If you can specify that algorithm in a way that can be converted into code, you'll definitely have something! Unfortunately it seems to be a really tough problem.

Another nice trick might be a human-assisted Blind Watchmaker-type utility, that would run small snippets of different possible searches, and display the partial results for a human to review and pick the ones that look the most promising. Maybe that would make it easier to zero in on the interesting parts of a search space -- with enough practice, anyway.

EDIT: Added some related notes in another thread about SAT solvers, a set of algorithms developed mostly just in the last ten years that have been impressively successful when applied to Conway's Life search problems.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Searching algorithms

Post by wildmyron » October 7th, 2015, 6:24 am

A for awesome wrote:I have an idea for a nonexhaustive but faster version of the WLS/JLS algorithm. It works essentially the same, but throws away branches that appear unlikely to be completed, and discounts trivial stator variants or disconnected solutions.
I have been musing over a version of JLS which could discard disconnected solutions for quite some time, particularly after watching many high period searches in B2/S0 for speed c ships/puffers become hopelessly bogged down by umpteen permutations of non-interacting moons. I believe the constraint system in JLS is well suited to implementing such a restriction of the search, but I haven't invested enough time to gain the required familiarity with JLS' code. My idea to implement this constraint is to determine the number of connected blobs in the current partial solution and backtrack when the number of blobs is larger than the allowed value. A connected blob includes all On cells in a group wherever there is less than a two cell gap between them in any one time step, or two On cells are neighbours in adjacent time steps (where first and last time step are considered adjacent whenever a periodic solution is sought). If any cell in a blob is within two cells of an unknown cell then that blob is not yet complete. All incomplete blobs are collectively counted as a single blob. I believe this constraint could be tested at the completion of each layer and whilst it would add some computational overhead it could make many searches which are currently intractable without manual pruning possible to run to completion.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Searching algorithms

Post by praosylen » October 7th, 2015, 9:01 am

wildmyron wrote:
A for awesome wrote:I have an idea for a nonexhaustive but faster version of the WLS/JLS algorithm. It works essentially the same, but throws away branches that appear unlikely to be completed, and discounts trivial stator variants or disconnected solutions.
I have been musing over a version of JLS which could discard disconnected solutions for quite some time, particularly after watching many high period searches in B2/S0 for speed c ships/puffers become hopelessly bogged down by umpteen permutations of non-interacting moons. I believe the constraint system in JLS is well suited to implementing such a restriction of the search, but I haven't invested enough time to gain the required familiarity with JLS' code. My idea to implement this constraint is to determine the number of connected blobs in the current partial solution and backtrack when the number of blobs is larger than the allowed value. A connected blob includes all On cells in a group wherever there is less than a two cell gap between them in any one time step, or two On cells are neighbours in adjacent time steps (where first and last time step are considered adjacent whenever a periodic solution is sought). If any cell in a blob is within two cells of an unknown cell then that blob is not yet complete. All incomplete blobs are collectively counted as a single blob. I believe this constraint could be tested at the completion of each layer and whilst it would add some computational overhead it could make many searches which are currently intractable without manual pruning possible to run to completion.
I was thinking it might be possible instead to not allow changing cells from a known solution that cannot interact with the aforementioned solution. This approach would successfully find all solutions, including supported ones, while eliminating most disjoint ones.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Searching algorithms

Post by praosylen » November 10th, 2015, 5:38 pm

I am considering the idea of a tile-based search algorithm for spaceships (and possibly oscillators, but that would be less useful). In order to fully explain it, I will have to define a few things first:
  • Tile: A square subsection of the search area, extends in time and space. They can be skewed in time (shifted 1 square after n gens, possibly multiple times) if the displacement in one period of the ships desired is greater than 1.

    Corner tile: A tile with two adjacent constrained edges.

    Edge tile: A tile with one constrained edge.

    .
  • Constrained edge: An edge of a tile that is required to behave as if the neighboring tile (and the diagonally adjacent tiles) is filled with vacuum or a repetitive agar.
  • Solve: To find a set of states for a tile that match the search criteria (with some deterministic sequential algorithm that I haven't determined yet), including all constraints imposed by constrained edges and neighboring tiles.
  • Complete an edge: To solve a tile on the edge of the search as a corner tile.
The algorithm is as follows:
Find all solutions that fit within one tile (I.E. have 4 constrained edges). If there are more than a limit that is input as a search parameter, then you are done (in fact, if the amount of solutions found ever exceeds the limit, the search is over). Next, solve Tile 1 with 3 constrained edges, if possible. If successful, try to complete partial with the tile adjacent to the unconstrained edge. Enumerate all solutions of this type (if there are any). Then, remove the constraint on the edge opposite the original tile, and try to solve. For every solution, go to the next tile and try to solve it with 3, then 2 constrained edges as before. When the number of tiles exceeds the dimension of the search, do not solve the final tile with only 2 constrained edges. When this phase is done, return to Tile 1 and try to solve with 2 adjacent constrained edges. If there are no solutions, than spaceships of this type are impossible. If there are solutions, go to one of the tiles adjacent to tile #1 and try to solve that with one constrained edge, a continuation of Tile 1's constrained edge. If unsuccessful, try the next solution of tile 1. Then, repeat this procedure with the other tile adjacent to Tile 1. Next, solve tiles in diagonal rows across the search area. If at any time there is no solution to a tile, return to the tiles adjacent to them and try different solutions for them. Always remember unsolvable combinations of tiles, and never try to reuse them. If you can solve an edge tile as a corner tile, try that first (only try this if you are at the limits of the search bounding area). This restricts the bounding area of the search and forces all tiles in the same orthogonal row as that one to have a continuation of that tile's constrained edge. If both edges have been completed and you are at the corner of the search area, solve the last tile as a corner tile and enumerate all solutions as complete solutions to the search, afterwards returning to the previous tiles to try different combinations. If you exhaust all possible states for tile 1, the search is complete.

I apologize for the long and unoptimized algorithm; I could not find any way to improve it without making it impossible to explain (there may be huge errors or gaps in my explanation that I haven't found; I haven't checked). I still have some things that need to be worked out, such as whether the tile size is input or automatically derived from the other search parameters, or exactly how to solve the tiles or how to skew them in time to move with the ship. I do think this search algorithm could have significant advantages over conventional algorithms, especially in large searches wherein normal algorithms would just keep trying the same futile combinations of cells in one corner of the search every time they changed something somewhere else. Somebody check my math, but I think that this could lead to improvements in runtime on the order of O(n^(2^d)), where d is the smaller dimension (in tiles) of the search.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Searching algorithms

Post by calcyman » August 20th, 2016, 10:10 am

dvgrn wrote:Frankly-silly distances are far enough away that in an actual pattern, Golly won't even be able to send a glider to interact with the block in a reasonable amount of time, at least not without a new specialized simulation algorithm. For example, if we could somehow encode the 38,380-glider recipe for an HBK using just one U.C. operation per resulting glider -- an underestimate by several orders of magnitude -- then the block would have to start at a distance of around 2^76760 cells from the U.C.
I think you underestimate the power of HashLife -- 2^76760 cells seems comfortably within reach. After all, the quadtree will look something like:

(((([...], 0, 0, 0), 0, 0, 0), 0, 0, 0), 0, 0, (0, 0, 0, (0, 0, 0, (0, 0, 0, [...]))))

and take roughly 2 * 76760 nodes to store -- that's only a few megabytes of memory, and you're not going to be generating many new nodes when you run the behemoth.

I haven't tested this, but one proof-of-concept would be to run Caber Tosser in Golly's hlife algorithm with 'Hyperspeed' enabled and leave it running overnight.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Searching algorithms

Post by praosylen » January 21st, 2017, 3:57 pm

I recently came up with an extremely speculative idea for an oscillator and/or spaceship searching method. It was inspired by a simple observation I made a while back: For any synchronous two-dimensional cellular automaton (call it rule O), there is at least one anisotropic 3-dimensional automaton (call it rule S) with the same number of states as rule O for which stable patterns correspond exactly to the full histories of patterns in rule O. This is a relatively simple transformation to make, and it basically crystallizes the time dimension in rule O into a spatial dimension in rule S. If rule S is run on a grid periodic with period n in its third dimension and offset by (i,j), a stable pattern (a wick in non-periodic rule S) corresponds to a (i,j)c/n spaceship in rule O. In the degenerate case of i and j being zero, it corresponds to a period-n oscillator.
This is simply a restatement of the initial problem of finding oscillators and spaceships in rule O when rules O and S are defined as above. However, by adding one or more extra states to rule S, the problem's behavior changes. In particular, if given any rule O, a rule S can be constructed with more states than rule O so that the following conditions can be met, random soups in rule S on a periodic grid could evolve into stable configurations with regularity, corresponding to rule O oscillators or spaceships.

These conditions are:
  • Random soups in periodic rule S do not tend to die out overwhelmingly.
  • The extra rule S state does not strongly invade and permeate patterns composed of normal states.
  • The extra rule S state or states cannot "cap" an incomplete pattern consisting of normal states, i.e. no stable patterns can exist that contain the extra state or states.
  • Rule S is not explosive on the required periodic grid.
  • Rule S oscillators are uncommon or impossible.
If such a rule O/rule S pair were found, all that would remain would be to create some apgsearch/gsearch/cs-like program that generates starting patterns in periodic rule S and evolves them until a stable pattern or stable patterns are formed, and then to output the rule O equivalent pattern. I could see this as useful to generate small spaceships of a particular speed, although I am not sure enough about the dynamics of three-dimensional CAs, especially anisotropic ones, to say for sure what the distribution of spaceships generated would be.

This is, of course, mostly speculative, and I do not have any working example of a rule O/rule S pair that meets the conditions. I don't consider it likely that a valid rule S even exists for any given rule O that would be at all useful (not trivially equivalent to the action of an existing search program), let alone that such a rule could be reliably generated. But I do believe that the payoff if this approach truly works would be great enough that it's worth looking into.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

JohanB
Posts: 16
Joined: June 10th, 2016, 11:59 pm

Re: Searching algorithms

Post by JohanB » April 11th, 2017, 8:38 am

Genetic algorithms are total failure for GOL. On the other hand statistical based algorithms are good direction which wasn't explored well enough yet.
I'm currently doing a master's in CS in this subject.

As and when things progress to a postable state I'll keep you updated.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Searching algorithms

Post by praosylen » May 14th, 2017, 10:43 am

What about a variant of the lifesrc algorithm that divides the cell array in half along the axis which is being searched, first trying to solve one half and then the other? Something like this:

Code: Select all

x = 50, y = 20, rule = LifeHistory
50A$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48DA$A48DA
$A48DA$A48DA$A48DA$A48DA$A48DA$A48DA$A48DA$50A!
Instead of trying to run a width-18 asymmetric search on the entire space, it runs a width-9 search on the blue cells and then runs width-9 searches on the red cells for all of the other solutions. In JLS (I'm not familiar with lifesrc itself or WLS) this could be achieved by a modification to allow a custom search ordering.

Would this approach actually result in significant speedup for wide searches? My instinct says it would, but I'm not entirely sure.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Searching algorithms

Post by wildmyron » May 15th, 2017, 5:39 am

A for awesome wrote:What about a variant of the lifesrc algorithm that divides the cell array in half along the axis which is being searched, first trying to solve one half and then the other? Something like this:

Code: Select all

x = 50, y = 20, rule = LifeHistory
50A$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48BA$A48DA$A48DA
$A48DA$A48DA$A48DA$A48DA$A48DA$A48DA$A48DA$50A!
Instead of trying to run a width-18 asymmetric search on the entire space, it runs a width-9 search on the blue cells and then runs width-9 searches on the red cells for all of the other solutions. In JLS (I'm not familiar with lifesrc itself or WLS) this could be achieved by a modification to allow a custom search ordering.

Would this approach actually result in significant speedup for wide searches? My instinct says it would, but I'm not entirely sure.
I don't believe you could get any benefit from this kind of cell ordering because there is very little constraint on the solutions for the first half of the search. Consider a search which might find the following c/3 ship with a width of 12 (a contrived example, but illustrative):

Code: Select all

x = 37, y = 12, rule = LifeHistory
4.2A4.5D5.A4.A.A$10.5D4.A.A2.2A.A.2A3.A.A$2.2A2.A3.5D4.A3.A8.A2.A$.A
8.5D4.9A4.A2.2A$2A4.3A.5D5.A8.2A$.A4.3A.5D2.A4.7A$.3A8.A4.A4.A5.A$2.A
6.2A.A3.A.A4.4A3.2A.A$4.A4.A2.3A9.A5.A.A$2.2A4.2A.4A2.A6.2A$2.2A5.A2.
A3.A8.A$4.A5.2A14.A!
The search would be set to find partial solutions in the top six rows before searching the bottom half. I presume you would require an On cell in the top half of the first row. Because the bottom half of the rows aren't completed there are many partial results for the top half which would need to be searched through before there is any hope of completing the bottom half. As the ship above shows, the lack of constraints means the search could not exclude partials with unconnected segments and would therefore attempt completing a combinatorial number of partials for the top half where there might not be any hope of completing the partial based on the top half of the first segment. I apologise for being a bit unclear in my explanation - hopefully you can see what I mean. If you try such a search in JLS or WLS with the bottom half of rows set to "Don't Care" I think it will be immediately apparent what I mean. I suppose you might somewhat remedy this if you require all the cells in the top half to be in a connected segment, at the cost of not finding ships such as the example above. Even with that I think that the benefit from only searching half the rows will be lost to the widening of the search space by having unconstrained rows - especially if you allow the ship to be reasonably long. This alludes to another problem caused by a need to predetermine the maximum length of the ship - too short and there won't be a solution, too long and the duration of the search will become prohibitive.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Bullet51
Posts: 663
Joined: July 21st, 2014, 4:35 am

Re: Searching algorithms

Post by Bullet51 » August 8th, 2022, 5:34 am

I've recently come up with an idea about spaceship searching:
dvgrn wrote:
September 17th, 2015, 6:05 pm
The key would be successful partitioning of the problem: if there were a way to monitor the search and recognize that a lot of searches were being duplicated because Section A was actually completely independent of Section B, then it would be possible to run a Section A search just once, and a Section B search just once.
The keyword is "independent". Say you want to prove that the last two rows

Code: Select all

11011100
10011001
cannot be extended. You set out to try all combinations at the X places.

Code: Select all

11011100
10011001
XXXXXXXX
Say this position is ruled out, where the search process does not even query the rightmost bit of the third row:

Code: Select all

11011100
10011001
00111100
Then the search process proves that this position is not extendable, no matter what X is. There is no need to search X=1 anymore.

Code: Select all

11011100
10011001
0011110X
If such a process is carried out in a SAT routine, it would make the SAT solver a CDCL solver. However, spaceship search is rarely completed in a single SAT call. The majority of spaceship search programs uses DFS, BFS, or a combination of these. In this sense the "bit-independent" heuristic may be useful compared to vanilla DFS or BFS algorithms, as long as ruling out <A>X<B> takes less time than ruling out <A>0<B> followed with <A>1<B>.

An advanced version of this heuristic may be using a multi-armed bandit to determine whether to disprove <A>X<B> without case-splitting on X or <A>0<B> then <A>1<B>.

EDIT: The disproof of 00111100 does not necessarily generalize to 0011110X, but it's very probable that it can be transferred to 00111101. So the search program may learn something from the disproof of 00111100, e.g. the correct branching order. This is akin to the Killer heuristic in chess programming.
Last edited by Bullet51 on August 10th, 2022, 11:57 pm, edited 3 times in total.
Still drifting.

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: Searching algorithms

Post by pzq_alex » August 10th, 2022, 5:06 am

Bullet51 wrote:
August 8th, 2022, 5:34 am
I've recently come up with an idea about spaceship searching:
dvgrn wrote:
September 17th, 2015, 6:05 pm
The key would be successful partitioning of the problem: if there were a way to monitor the search and recognize that a lot of searches were being duplicated because Section A was actually completely independent of Section B, then it would be possible to run a Section A search just once, and a Section B search just once.
The keyword is "independent". Say you want to prove that the last two rows

Code: Select all

11011100
10011001
cannot be extended. You set out to try all combinations at the X places.

Code: Select all

11011100
10011001
XXXXXXXX
Say this position is ruled out, where the search process does not even query the rightmost bit of the third row:

Code: Select all

11011100
10011001
00111100
Then the search process proves that this position is not extendable, no matter what X is. There is no need to search X=1 anymore.

Code: Select all

11011100
10011001
0011110X
If such a process is carried out in a SAT routine, it would make the SAT solver a CDCL solver. However, spaceship search is rarely completed in a single SAT call. The majority of spaceship search programs uses DFS, BFS, or a combination of these. In this sense the "bit-independent" heuristic may be useful compared to vanilla DFS or BFS algorithms, as long as ruling out <A>X<B> takes less time than ruling out <A>0<B> followed with <A>1<B>.

An advanced version of this heuristic may be using a multi-armed bandit to determine whether to disprove <A>X<B> without case-splitting on X or <A>0<B> then <A>1<B>.
ikpx2 already sort of does this. It performs a “deep lookahead” on each node, using a SAT solver. The lookahead depth is typically 30.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

Bullet51
Posts: 663
Joined: July 21st, 2014, 4:35 am

Re: Searching algorithms

Post by Bullet51 » August 10th, 2022, 11:39 pm

pzq_alex wrote:
August 10th, 2022, 5:06 am
ikpx2 already sort of does this. It performs a “deep lookahead” on each node, using a SAT solver. The lookahead depth is typically 30.
The point is that similar nodes could be ruled out by the same proof, or at least similar proofs. Does ikpx2 transfer UNSAT proofs between different nodes, or the nodes are so dissimilar that they require totally different UNSAT proofs?
Still drifting.

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: Searching algorithms

Post by pzq_alex » August 11th, 2022, 12:09 am

Bullet51 wrote:
August 10th, 2022, 11:39 pm
pzq_alex wrote:
August 10th, 2022, 5:06 am
ikpx2 already sort of does this. It performs a “deep lookahead” on each node, using a SAT solver. The lookahead depth is typically 30.
The point is that similar nodes could be ruled out by the same proof, or at least similar proofs. Does ikpx2 transfer UNSAT proofs between different nodes, or the nodes are so dissimilar that they require totally different UNSAT proofs?
The point is, if two similar rows can be ruled out by similar proofs, they would both get ruled out by the SAT solver in the lookahead step.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

Bullet51
Posts: 663
Joined: July 21st, 2014, 4:35 am

Re: Searching algorithms

Post by Bullet51 » August 11th, 2022, 1:04 am

pzq_alex wrote:
August 11th, 2022, 12:09 am
The point is, if two similar rows can be ruled out by similar proofs, they would both get ruled out by the SAT solver in the lookahead step.
But what if they are in different nodes?
Still drifting.

Post Reply