Clearing Ash

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
mscibing
Posts: 105
Joined: May 18th, 2010, 8:30 pm

Clearing Ash

Post by mscibing » July 25th, 2021, 11:30 pm

I was thinking about ways constructed patterns could clear the ash around them, and I have a partial strategy. It has some limitations:
  • It needs some free space around the ash field to work in.
  • It can't completely prevent secondary gliders/spaceships from being produced as the ash is being cleared; anything important in the way of this secondary radiation will need to be armored (i.e. riprap).
The idea is to send a volley along the face of the ash to edge-delete objects from the ash. Making this work will require finding a volley that is good at edge-deleting many common objects. This is the best I've found so far but unfortunately it seems to blow up a little too often to make net progress:

Code: Select all

x = 15, y = 18, rule = B3/S23
12b3o$14bo$13bo$9b2o$8bobo$10bo10$2o$b2o$o!
Deleting many common objects:

Code: Select all

x = 225, y = 237, rule = B3/S23
223bo$133bo58b2o28bobo$102b2o29bo28b3o26bo2bo27bobo$102b2o29bo58b2o29b
o4$102b3o27b3o27b3o27b3o27b3o$104bo29bo29bo29bo29bo$103bo29bo29bo29bo
29bo$99b2o28b2o28b2o28b2o28b2o$98bobo27bobo27bobo27bobo27bobo$100bo29b
o29bo29bo29bo10$90b2o28b2o28b2o28b2o28b2o$91b2o28b2o28b2o28b2o28b2o$
90bo29bo29bo29bo29bo17$132b3o$134bo$133bo$129b2o$128bobo$130bo61b3o$
194bo$193bo$189b2o$188bobo$190bo5$120b2o$121b2o$120bo3$180b2o$181b2o$
180bo12$162b3o$164bo$163bo$159b2o$158bobo$160bo10$150b2o$151b2o$150bo
13$132b3o$134bo$133bo$129b2o$128bobo$130bo10$120b2o$121b2o$120bo17$
102b3o$104bo$103bo$99b2o$98bobo$100bo10$90b2o$91b2o$90bo3$72b3o$74bo$
73bo$69b2o$68bobo$70bo10$60b2o$61b2o$60bo17$42b3o$44bo$43bo$39b2o$38bo
bo$40bo10$30b2o$31b2o$30bo9$12b3o$14bo$13bo$9b2o$8bobo$10bo10$2o$b2o$o
!
To keep the volley at the ash face we can use a simple algorithm:
IF the volley has reached the other side with the first glider intact:
- We're away from the face. Advance one half diagonal for the next volley.
OTHERWISE
- We don't know if the interaction with the volley has added any objects beyond the current half-diagonal. Retreat many half diagonals for the next volley.

In fact most of the volleys will be away from the ash face and won't interact with the ash at all. I didn't show such "probe" volleys in the example above. But this algorithm will mean that almost all interactions with ash objects will be edge interactions.

Some other complications:
- The ash may well launch glider back to where the volley came from. It's probably a good idea to arrange for any construction elbows to be well away from the launch area immediately after launch.
- On the other side of the ash face there is some risk of the detection mechanism for the first glider being fouled by a stray glider from the ash. I don't have a good solution for this. Any leftover gliders from the volley should probably be cleaned up as well but doing so without fouling on stray gliders will by tricky.
- The interaction of the volleys with the ash may produce crystals or other cyclic behaviour. For example, without the third glider, these two gliders have a block -> loaf -> barge -> ship -> block cycle:

Code: Select all

x = 7, y = 6, rule = B3/S23
4b3o$6bo$5bo$b2o$obo$2bo!
It should be possible to detect and deploy countermeasures to known crystals by keeping a history of the half-diagonals ash was encountered on. But this will greatly complicate the circuitry.
-- Andrew Wade

Jormungant
Posts: 605
Joined: May 27th, 2016, 1:01 am

Re: Clearing Ash

Post by Jormungant » July 26th, 2021, 3:35 pm

I have thought about this problem before, and it is a lot harder than it seems. The issue is that one needs to constrain what the "ash" is allowed to be with a set properties, and ensure that whatever interaction with it one considers, these must guaranty that these properties are retained, otherwise nothing prevents further inaction to work as intended, and soon a myriad of angry gliders will come back to annihilate what ever structure one engineered that woke them from their slumber.

The best I could think of is that the ash can only be blocks and blinkers, nothing else, and moreover the "hamming distance" between any active cell must be at least 4, ex:

Code: Select all

x = 77, y = 14, rule = LifeHistory
2$35.A$28.3A4.A$35.A$25.2A15.3A$25.2A11.2A$38.2A$22.2A5.2A3.2A24.3A$
2.3A3.3A11.2A5.2A3.2A20.2A11.2A3.3A$56.2A11.2A!
The only reason this might work is the following work to clean new orthogonal rows:

Code: Select all

x = 161, y = 18, rule = LifeHistory
2$78.2C14.2C16.2C18.2C17.2C$78.2C14.2C16.2C18.2C17.2C2$12.2C17.2C14.
2C18.2C7.6C10.6C12.6C14.6C13.6C$7.2C.C2.C12.2C.C2.C9.2C.C2.C13.2C.C2.
C6.C6.C8.C6.C10.C6.C12.C6.C11.C6.C$6.CDC.3C12.CDC.3C9.CDC.3C13.CDC.3C
7.C.4C.C8.C.4C.C10.C.4C.C12.C.4C.C11.C.4C.C$5.C3DC14.C3DC11.C3DC15.C
3DC9.2C.C2DC.2C6.2C.C2DC.2C8.2C.C2DC.2C10.2C.C2DC.2C9.2C.C2DC.2C$4.C
5DC12.C5DC9.C5DC13.C5DC10.C4DC10.C4DC12.C4DC14.C4DC13.C4DC$3.C3DC3DC
10.C3DC3DC7.C3DC3DC11.C3DC3DC7.2C6D2C6.2C6D2C8.2C6D2C10.2C6D2C9.2C6D
2C$2.C4DC4DC8.C4DC4DC5.C4DC4DC9.C4DC4DC6.C3D2C3DC6.C3D2C3DC8.C3D2C3DC
10.C3D2C3DC9.C3D2C3DC$2.2C3DC3D2C8.2C3DC3D2C5.2C3DC3D2C9.2C3DC3D2C4.C
.C3D2C3DC.C2.C.C3D2C3DC.C4.C.C3D2C3DC.C6.C.C3D2C3DC.C5.C.C3D2C3DC.C$
72.2C10.2C2.2C10.2C4.2C10.2C6.2C10.2C5.2C10.2C$8.2A16.2A13.2A17.2A14.
2A15.2A17.2A19.2A18.2A!
Now, if the initial condition is not so an orthogonal half-plane is empty, then one would need new diagonal rows. The hamming distance is no longer sufficient, one would also need to disallow active cells that have hamming distance 4 that are diagonal to each-other, and use the following:

Code: Select all

x = 127, y = 116, rule = LifeHistory
16$102.2C$103.C$101.C$101.2C$9.2C38.2C53.2C$10.C39.C50.3CDC$8.C39.C
52.C5D$8.2C38.2C51.7D$11.2C38.2C49.D2C3D2C$8.3CDC35.3CDC49.A2DC3DC$8.
C5D34.C5D49.AC3DC3.2C$8.7D33.7D45.2A3.3DC.C2.C$9.2DC3D2C32.D2C3D2C42.
A.A4.D2C.2C$10.DC4DC32.A2DC3DC44.2A$11.C3DC3.2C29.AC3DC3.2C$9.C2.3DC.
C2.C31.3DC.C2.C$13.D2C.2C34.D2C.2C$49.2A$48.A5$105.2C$27.2C38.2C37.C$
28.C39.C35.C$26.C39.C37.2C$26.2C38.2C39.2C$29.2C38.2C33.3CDC$26.3CDC
35.3CDC33.C5D$26.C5D34.C5D32.7D$26.7D33.7D32.D2C3D2C$27.6D2C32.2DC3D
2C30.A2DC3DC$28.3C3DC33.CDC3DC31.AC3DC3.2C$29.4DC3.2C29.ADC2DC3.2C24.
2A3.3DC.C2.C$27.C2.3DC.C2.C30.A3DC.C2.C23.A.A4.D2C.2C$31.D2C.2C34.D2C
.2C27.2A$67.2A$66.A14$53.C2.C$53.4C2$51.8C$51.C6.C$53.4C$52.2C2D2C2.
2C$52.6DC2.C$52.6D2C.C.2C$53.D2C3DC.C.C$54.2C3DC.C.C$52.C2.3D2C.C.2C$
56.2DC2.C$60.2C9$80.C2.C$80.4C2$78.8C$78.C6.C$80.4C$79.2C2D2C2.2C$79.
6DC2.C$79.6D2C.C.2C$80.D2C3DC.C.C$81.2C3DC.C.C$82.3D2C.C.2C$80.C2.2DC
2.C$87.2C!
In practice, this additional constraint is only needed for blinkers, blocks can be removed in 135 degree corners.

One could think of having some king of armor that could be rebuilt, so allowing the "cleaning" structure to flee in one direction leaving behind defenses, but if you allow someone to "engeneer" the ash against your defense strategy, it is very likely it will prevail, but it could be a good challenge too. I thought this could absorb gliders quite well:

Code: Select all

x = 359, y = 102, rule = LifeHistory
13$12.2C$12.C.C2$14.C.C55.2C$72.C.C$16.C.C19.4C55.C$38.C3.C31.C.C19.C
$18.C.C17.C57.C3.C$39.C36.C.C17.4C$20.C.C$78.C.C$22.C.C$80.C.C$24.C.C
$82.C.C$26.C.C$84.C.C$28.C.C$31.C54.C.C$30.2C$88.C.C$91.C$90.2C6$232.
C.C$232.2C$233.C$208.2C$208.C.C2$210.C.C2$212.C.C2$214.C.C$339.C$216.
C.C120.C.C$339.2C$218.C.C94.2C$17.2C296.C.C$17.C.C55.2C143.C.C$75.C.C
239.C.C$19.C.C200.C.C$42.4C31.C.C21.C217.C.C$21.C.C18.C3.C53.C123.C.C
$42.C36.C.C18.C3.C122.C93.C.C$23.C.C17.C56.4C122.2C$81.C.C239.C.C$25.
C.C$83.C.C239.C.C$27.C.C$85.C.C239.C.C$29.C.C$87.C.C239.C.C$31.C.C$
89.C.C239.C.C$33.C.C298.C$36.C54.C.C239.2C$35.2C57.C$93.2C!

mscibing
Posts: 105
Joined: May 18th, 2010, 8:30 pm

Re: Clearing Ash

Post by mscibing » August 2nd, 2021, 7:33 pm

Jormungant wrote:
July 26th, 2021, 3:35 pm
I have thought about this problem before, and it is a lot harder than it seems. The issue is that one needs to constrain what the "ash" is allowed to be with a set properties, and ensure that whatever interaction with it one considers, these must guaranty that these properties are retained, otherwise nothing prevents further inaction to work as intended, and soon a myriad of angry gliders will come back to annihilate what ever structure one engineered that woke them from their slumber.
My hope was that if "blow-ups" were rare enough the cleaning algorithm could still make net progress. But it's now looking very unlikely that I'll be able to find a suitable volley configuration. What I'm finding is that it takes a lot of ash to properly evaluate a volley--I've now found a couple of volleys configurations that are capable of clearing the ash from acorn in one of its orientations but are hopeless in the general case.
Jormungant wrote:
July 26th, 2021, 3:35 pm
I thought this could absorb gliders quite well:
<snip>
I like that. Only a few cases to consider when resetting the armor.
-- Andrew Wade

mscibing
Posts: 105
Joined: May 18th, 2010, 8:30 pm

Re: Clearing Ash

Post by mscibing » September 4th, 2021, 12:20 pm

I've made some progress in clearing ash. Sending volleys along the face of the ash wasn't working out, but probing the ash in a raster scan is working much better. "Probe" is maybe not the right word as the volley doesn't return enough information to tell you want you encountered; it returns only one bit of information that can be used to back-off the scan when needed.

Here is an example of a probe with common target objects. The probe colliding with the toad is an example of the probe causing a "blow-up" that would trigger the algorithm to back-off:

Code: Select all

x = 1405, y = 578, rule = LifeHistory
20.2A2.2A2.2A2.2A62.2A2.2A30.2A34.2A2.2A62.2A2.2A2.2A162.2A2.2A2.2A$
20.2A2.2A2.2A2.2A62.2A2.2A30.2A34.2A2.2A62.2A2.2A2.2A162.2A2.2A2.2A3$
24.2A2.2A66.2A2.2A26.2A2.2A34.2A2.2A66.2A2.2A166.2A2.2A$24.2A2.2A66.
2A2.2A26.2A2.2A34.2A2.2A66.2A2.2A166.2A2.2A3$24.2A2.2A98.2A2.2A106.2A
2.2A166.2A2.2A74.2A2.2A$24.2A2.2A98.2A2.2A106.2A2.2A166.2A2.2A74.2A2.
2A3$24.2A2.2A18.2A2.2A6.2A2.2A2.2A22.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A
2.2A22.2A2.2A2.2A22.2A2.2A2.2A2.2A30.2A2.2A54.2A2.2A6.2A2.2A2.2A14.2A
2.2A6.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A22.2A2.2A2.2A2.
2A2.2A26.2A2.2A$24.2A2.2A18.2A2.2A6.2A2.2A2.2A22.2A2.2A2.2A18.2A2.2A
2.2A2.2A2.2A2.2A22.2A2.2A2.2A22.2A2.2A2.2A2.2A30.2A2.2A54.2A2.2A6.2A
2.2A2.2A14.2A2.2A6.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A
22.2A2.2A2.2A2.2A2.2A26.2A2.2A3$24.2A2.2A22.2A2.2A10.2A2.2A22.2A2.2A
26.2A2.2A34.2A2.2A34.2A2.2A26.2A2.2A58.2A2.2A10.2A2.2A14.2A2.2A2.2A6.
2A2.2A10.2A2.2A14.2A2.2A14.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A$24.2A2.2A
22.2A2.2A10.2A2.2A22.2A2.2A26.2A2.2A34.2A2.2A34.2A2.2A26.2A2.2A58.2A
2.2A10.2A2.2A14.2A2.2A2.2A6.2A2.2A10.2A2.2A14.2A2.2A14.2A2.2A6.2A2.2A
14.2A2.2A14.2A2.2A3$24.2A2.2A22.2A2.2A10.2A2.2A22.2A2.2A26.2A2.2A34.
2A2.2A22.2A2.2A2.2A2.2A2.2A26.2A2.2A58.2A2.2A10.2A2.2A14.2A2.2A10.2A
2.2A10.2A2.2A14.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A2.2A2.2A2.2A2.2A2.2A
$24.2A2.2A22.2A2.2A10.2A2.2A22.2A2.2A26.2A2.2A34.2A2.2A22.2A2.2A2.2A
2.2A2.2A26.2A2.2A58.2A2.2A10.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A14.2A2.
2A14.2A2.2A10.2A2.2A10.2A2.2A2.2A2.2A2.2A2.2A2.2A3$24.2A2.2A22.2A2.2A
10.2A2.2A22.2A2.2A26.2A2.2A34.2A2.2A18.2A2.2A10.2A2.2A26.2A2.2A58.2A
2.2A10.2A2.2A14.2A2.2A26.2A2.2A14.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A$
24.2A2.2A22.2A2.2A10.2A2.2A22.2A2.2A26.2A2.2A34.2A2.2A18.2A2.2A10.2A
2.2A26.2A2.2A58.2A2.2A10.2A2.2A14.2A2.2A26.2A2.2A14.2A2.2A14.2A2.2A
10.2A2.2A10.2A2.2A3$24.2A2.2A22.2A2.2A10.2A2.2A22.2A2.2A26.2A2.2A34.
2A2.2A18.2A2.2A10.2A2.2A26.2A2.2A58.2A2.2A10.2A2.2A14.2A2.2A26.2A2.2A
14.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A42.2A2.2A$24.2A2.2A22.2A2.2A10.2A
2.2A22.2A2.2A26.2A2.2A34.2A2.2A18.2A2.2A10.2A2.2A26.2A2.2A58.2A2.2A
10.2A2.2A14.2A2.2A26.2A2.2A14.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A42.2A
2.2A3$24.2A2.2A22.2A2.2A10.2A2.2A22.2A2.2A26.2A2.2A6.2A2.2A22.2A2.2A
18.2A2.2A10.2A2.2A26.2A2.2A58.2A2.2A10.2A2.2A14.2A2.2A26.2A2.2A14.2A
2.2A14.2A2.2A10.2A2.2A10.2A2.2A14.2A2.2A22.2A2.2A$24.2A2.2A22.2A2.2A
10.2A2.2A22.2A2.2A26.2A2.2A6.2A2.2A22.2A2.2A18.2A2.2A10.2A2.2A26.2A2.
2A58.2A2.2A10.2A2.2A14.2A2.2A26.2A2.2A14.2A2.2A14.2A2.2A10.2A2.2A10.
2A2.2A14.2A2.2A22.2A2.2A3$20.2A2.2A2.2A2.2A18.2A2.2A10.2A2.2A18.2A2.
2A2.2A2.2A26.2A2.2A2.2A22.2A2.2A2.2A2.2A18.2A2.2A2.2A6.2A2.2A18.2A2.
2A2.2A2.2A54.2A2.2A2.2A2.2A2.2A14.2A2.2A2.2A2.2A26.2A2.2A2.2A2.2A2.2A
18.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A$20.2A2.2A2.2A2.2A18.2A2.2A
10.2A2.2A18.2A2.2A2.2A2.2A26.2A2.2A2.2A22.2A2.2A2.2A2.2A18.2A2.2A2.2A
6.2A2.2A18.2A2.2A2.2A2.2A54.2A2.2A2.2A2.2A2.2A14.2A2.2A2.2A2.2A26.2A
2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A3$304.2A2.
2A$304.2A2.2A3$304.2A2.2A$304.2A2.2A3$300.2A2.2A2.2A2.2A$300.2A2.2A2.
2A2.2A16$387.E$386.E.E$386.E.E$387.E2$382.2E7.2E$381.E2.E5.E2.E$319.E
62.2E7.2E136.2E67.2E768.E$249.E68.E.E66.E140.E2.E65.E2.E65.E70.E210.
2E69.2E68.E66.2E209.E2.E$178.3E68.E68.E.E65.E.E67.2E70.E.E67.E.E64.E.
E68.E.E67.E70.E70.E.E67.E.E67.E.E64.E2.E66.2E70.2E68.E2.E$106.2E141.E
69.E65.E2.E66.E2.E70.E69.E65.E2.E66.E2.E66.E.E68.E.E70.E69.E69.E65.E
2.E66.E.E68.E.E70.E$106.2E278.2E68.2E208.2E68.2E68.2E68.2E278.2E68.2E
68.2E2$50.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A$49.A.A67.A.A67.A.A67.A.A67.A
.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A
67.A.A67.A.A67.A.A67.A.A$51.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A
6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A
61.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A61.A6.2A$58.A.A67.A.A67.A.A
67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.
A.A67.A.A67.A.A67.A.A67.A.A67.A.A$58.A69.A69.A69.A69.A69.A69.A69.A69.
A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A7$44.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A$45.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A$44.A69.A69.A69.A69.A69.
A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A18$72.2A68.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A$72.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A
67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.
A.A67.A.A$72.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.
A69.A69.A69.A69.A69.A2$13.A69.A69.A69.A69.A69.A69.A69.A69.A69.A69.A
69.A69.A69.A69.A69.A69.A69.A69.A69.A$13.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A$12.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A
67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A67.A.A$8.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A68.2A$8.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A3$6.2A68.2A68.2A68.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A$6.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A2$3.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A$3.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A2$2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A$2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A23$20.2A2.2A2.2A2.2A22.2A2.2A2.
2A282.2A2.2A$20.2A2.2A2.2A2.2A22.2A2.2A2.2A282.2A2.2A3$16.2A2.2A10.2A
2.2A22.2A2.2A238.2A2.2A6.2A2.2A22.2A2.2A2.2A$16.2A2.2A10.2A2.2A22.2A
2.2A238.2A2.2A6.2A2.2A22.2A2.2A2.2A3$12.2A2.2A18.2A22.2A2.2A238.2A2.
2A6.2A2.2A18.2A2.2A2.2A2.2A30.2A2.2A$12.2A2.2A18.2A22.2A2.2A238.2A2.
2A6.2A2.2A18.2A2.2A2.2A2.2A30.2A2.2A3$12.2A2.2A42.2A2.2A22.2A2.2A2.2A
2.2A2.2A18.2A2.2A2.2A2.2A18.2A2.2A6.2A2.2A2.2A14.2A2.2A10.2A2.2A14.2A
2.2A6.2A2.2A2.2A50.2A2.2A2.2A2.2A2.2A2.2A2.2A22.2A2.2A30.2A2.2A$12.2A
2.2A42.2A2.2A22.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A18.2A2.2A6.2A2.2A
2.2A14.2A2.2A10.2A2.2A14.2A2.2A6.2A2.2A2.2A50.2A2.2A2.2A2.2A2.2A2.2A
2.2A22.2A2.2A30.2A2.2A3$12.2A2.2A42.2A2.2A18.2A2.2A14.2A2.2A26.2A2.2A
18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.
2A26.2A2.2A$12.2A2.2A42.2A2.2A18.2A2.2A14.2A2.2A26.2A2.2A18.2A2.2A10.
2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A26.2A2.2A
3$12.2A2.2A42.2A2.2A18.2A2.2A2.2A2.2A2.2A2.2A2.2A14.2A2.2A2.2A2.2A2.
2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A
2.2A26.2A2.2A$12.2A2.2A42.2A2.2A18.2A2.2A2.2A2.2A2.2A2.2A2.2A14.2A2.
2A2.2A2.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A
50.2A2.2A6.2A2.2A26.2A2.2A3$12.2A2.2A42.2A2.2A18.2A2.2A30.2A2.2A10.2A
2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.
2A2.2A26.2A2.2A$12.2A2.2A42.2A2.2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.
2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A26.2A
2.2A3$12.2A2.2A18.2A22.2A2.2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.2A10.
2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A46.2A2.2A2.2A2.2A2.2A2.2A2.
2A22.2A2.2A30.2A2.2A$12.2A2.2A18.2A22.2A2.2A18.2A2.2A30.2A2.2A10.2A2.
2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A46.2A2.2A2.2A
2.2A2.2A2.2A2.2A22.2A2.2A30.2A2.2A3$16.2A2.2A10.2A2.2A22.2A2.2A18.2A
2.2A14.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A
18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A26.2A2.2A30.2A2.2A$16.2A2.2A10.2A
2.2A22.2A2.2A18.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A
10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A26.2A2.2A30.2A2.
2A3$20.2A2.2A2.2A2.2A22.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A2.2A
2.2A6.2A2.2A14.2A2.2A10.2A2.2A14.2A2.2A2.2A6.2A2.2A14.2A2.2A2.2A2.2A
2.2A54.2A2.2A6.2A2.2A18.2A2.2A2.2A2.2A2.2A2.2A$20.2A2.2A2.2A2.2A22.2A
2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A6.2A2.2A14.2A2.2A10.2A
2.2A14.2A2.2A2.2A6.2A2.2A14.2A2.2A2.2A2.2A2.2A54.2A2.2A6.2A2.2A18.2A
2.2A2.2A2.2A2.2A2.2A3$232.2A2.2A$232.2A2.2A3$232.2A2.2A$232.2A2.2A3$
228.2A2.2A2.2A2.2A$228.2A2.2A2.2A2.2A16$387.E$386.E.E$386.E.E$387.E2$
382.2D7.DE205.2B$319.A61.EA.DB4.DA.E134.AB67.4B$318.ADA60.ADC2B2.3BDE
A133.ABCD66.B2DB135.B.3B136.3B68.B140.B64.5B138.3B$50.B.2B66.B.2B55.B
10.B.2B55.D10.B.2B53.ADBCB8.B.2B48.A3BAC5B7.B.2B53.B12.B.2B53.AE.BDB
7.B.2B52.BD2BDB8.B.2B51.AE13.B.2B51.2BD2B2A8.B.2B66.B.2B52.3B2A9.B.2B
53.B2D2B8.B.2B55.2D9.B.2B54.BD2B8.B.2B48.4B2D3B9.B.2B52.A13.B.2B52.5B
9.B.2B$48.7B63.7B53.CEC7.7B53.BDB7.7B52.BCADB6.7B49.2BCAD2B7.7B51.2DB
9.7B52.BD.D2B5.7B51.2BDBDB6.7B49.AD.E10.7B50.BDBDABA6.7B51.DB10.7B51.
BDA2BA6.7B52.BDBD2B5.7B52.BD.D2B5.7B52.BDBD2B5.7B46.4BD2BD2B7.7B50.ED
A10.7B51.B2D2B7.7B$47.10B49.2D9.10B52.B7.10B52.DB6.10B49.3BD3B4.10B
47.BD2BD2B6.10B48.D2BD8.10B49.3BD4B3.10B49.3BD3B4.10B47.ADA.D8.10B47.
BD2BDBA6.10B48.DAEA8.10B48.BDBD2A2B4.10B49.3BD3B4.10B50.2BD3B4.10B50.
2BD3B4.10B45.3BD2BD3B5.10B48.E.DA8.10B48.BDBD2B6.10B$42.2B2.12B48.2DB
3.2B2.12B54.2B2.12B51.2B.2B2.12B49.7B2.12B47.B2D2B2.2B2.12B47.B2D2B2.
2B2.12B49.7B2.12B48.8B2.12B47.A2D2B2.2B2.12B47.B2D2B2.2B2.12B48.2DB3.
2B2.12B47.B2D6B2.12B49.7B2.12B49.7B2.12B49.7B2.12B44.4B2D3B.2B2.12B
48.2CB3.2B2.12B47.B2D3B.2B2.12B$40.13B2A3B48.3B.13B2A3B52.13B2A3B50.
15B2A3B50.15B2A3B48.3B.13B2A3B48.3B.13B2A3B50.15B2A3B50.15B2A3B48.3B.
13B2A3B48.3B.13B2A3B48.3B.13B2A3B47.18B2A3B50.15B2A3B50.15B2A3B50.15B
2A3B45.20B2A3B48.3B.13B2A3B47.18B2A3B$38.14BABA3B48.16BABA3B50.14BABA
3B51.13BABA3B51.13BABA3B48.16BABA3B48.16BABA3B51.13BABA3B51.13BABA3B
48.16BABA3B48.16BABA3B48.16BABA3B48.16BABA3B51.13BABA3B51.13BABA3B51.
13BABA3B45.19BABA3B48.16BABA3B48.16BABA3B$37.17BA4B2.2A44.17BA4B2.2A
44.17BA4B2.2A45.16BA4B2.2A45.16BA4B2.2A44.17BA4B2.2A44.17BA4B2.2A45.
16BA4B2.2A45.16BA4B2.2A44.17BA4B2.2A44.17BA4B2.2A44.17BA4B2.2A44.17BA
4B2.2A45.16BA4B2.2A45.16BA4B2.2A45.16BA4B2.2A39.22BA4B2.2A44.17BA4B2.
2A44.17BA4B2.2A$38.22B.A.A44.22B.A.A44.22B.A.A44.22B.A.A44.22B.A.A44.
22B.A.A44.22B.A.A44.22B.A.A44.22B.A.A44.22B.A.A44.22B.A.A44.22B.A.A
44.22B.A.A44.22B.A.A44.22B.A.A44.22B.A.A39.27B.A.A44.22B.A.A44.22B.A.
A$40.21BA48.21BA48.21BA48.21BA48.21BA48.21BA48.21BA48.21BA48.21BA48.
21BA48.21BA48.21BA48.21BA48.21BA48.21BA48.21BA42.3B3.21BA48.21BA48.
21BA$42.7B.7B.2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.
2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B
52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B52.7B.7B.2B44.3B5.7B.7B.2B52.7B.7B.
2B52.7B.7B.2B$42.6B2.7B55.6B2.7B55.6B2.7B55.6B2.7B55.6B2.7B55.6B2.7B
55.6B2.7B55.6B2.7B55.6B2.7B55.6B2.7B55.6B2.7B55.6B2.7B55.6B2.7B55.6B
2.7B55.6B2.7B55.6B2.7B48.B6.6B2.7B55.6B2.7B55.6B2.7B$41.13B57.13B57.
13B57.13B57.13B57.13B57.13B57.13B57.13B57.13B57.13B57.13B57.13B57.13B
57.13B57.13B57.13B57.13B57.13B$40.5B.6B58.5B.6B58.5B.6B58.5B.6B58.5B.
6B58.5B.6B58.5B.6B58.5B.6B58.5B.6B58.5B.6B58.5B.6B58.5B.6B58.5B.6B58.
5B.6B58.5B.6B58.5B.6B58.5B.6B58.5B.6B58.5B.6B$39.5B3.4B58.5B3.4B58.5B
3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B
58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B3.4B58.5B
3.4B58.5B3.4B$38.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B
56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B
3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B56.5B3.6B$37.5B3.2B2A4B54.5B
3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B
2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B
54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.5B3.2B2A4B54.
5B3.2B2A4B54.5B3.2B2A4B$36.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B
3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B
2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B
52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B52.5B3.4B2A4B$35.
5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B
50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.
4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA
3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B50.5B4.3BA3.4B$34.5B5.
2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.
4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B
48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B48.
5B5.2B6.4B48.5B5.2B6.4B48.5B5.2B6.4B$33.5B15.4B46.5B15.4B46.5B15.4B
46.5B15.4B46.5B15.4B46.5B15.4B46.5B15.4B46.5B15.4B46.5B15.4B46.5B15.
4B46.5B15.4B46.5B15.4B46.5B15.4B46.5B15.4B46.5B15.4B46.5B15.4B46.5B
15.4B46.5B15.4B46.5B15.4B$32.5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B44.
5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B
44.5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B44.5B17.4B44.5B17.
4B44.5B17.4B$31.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B
19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.
5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B42.5B19.4B$
30.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.
4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B
21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B40.5B21.4B$29.5B23.4B38.
5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B
38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.
4B38.5B23.4B38.5B23.4B38.5B23.4B38.5B23.4B$28.5B25.4B36.5B25.4B36.5B
25.4B36.5B25.4B36.5B25.4B36.5B25.4B36.5B25.4B36.5B25.4B36.5B25.4B36.
5B25.4B36.5B25.4B36.5B25.4B36.5B25.4B36.5B25.4B36.5B25.4B36.5B25.4B
36.5B25.4B36.5B25.4B36.5B25.4B$27.5B27.4B34.5B27.4B34.5B27.4B34.5B27.
4B34.5B27.4B34.5B27.4B34.5B27.4B34.5B27.4B34.5B27.4B34.5B27.4B34.5B
27.4B34.5B27.4B34.5B27.4B34.5B27.4B34.5B27.4B34.5B27.4B34.5B27.4B34.
5B27.4B34.5B27.4B$26.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B
32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.
4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B29.4B32.5B
29.4B$25.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.
5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B
30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B30.5B31.4B$24.5B33.
4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B
33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.
5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B28.5B33.4B$23.5B35.4B26.5B35.4B
26.5B35.4B26.5B35.4B26.5B35.4B26.5B35.4B26.5B35.4B26.5B35.4B26.5B35.
4B26.5B35.4B26.5B35.4B26.5B35.4B26.5B35.4B26.5B35.4B26.5B35.4B26.5B
35.4B26.5B35.4B26.5B35.4B26.5B35.4B$22.5B37.4B24.5B37.4B24.5B37.4B24.
5B37.4B24.5B37.4B24.5B37.4B24.5B37.4B24.5B37.4B24.5B37.4B24.5B37.4B
24.5B37.4B24.5B37.4B24.5B37.4B24.5B37.4B24.5B37.4B24.5B37.4B24.5B37.
4B24.5B37.4B24.5B37.4B$21.5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.5B
39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.
5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B22.5B39.4B
22.5B39.4B$20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.
4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B
41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B20.5B41.4B$19.
5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B
18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.
4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B18.5B43.4B$18.5B45.4B16.5B
45.4B16.5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B16.
5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B
16.5B45.4B16.5B45.4B16.5B45.4B16.5B45.4B$17.5B47.4B2.2A10.5B47.4B2.2A
10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B2.
2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B
2.2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.4B2.2A10.5B47.
4B2.2A10.5B47.4B2.2A10.5B47.4B2.2A$16.5B49.4B.A.A8.5B49.4B.A.A8.5B49.
4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A
.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.
5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B49.4B.A.A8.5B
49.4B.A.A$15.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.
4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B
51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA9.5B51.4BA$
14.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.
2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B
53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B10.5B53.2B$13.3BAB65.3BA
B65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB65.3B
AB65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB65.3BAB$12.4B2A64.4B2A64.
4B2A64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A
64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A64.4B2A$10.5BA.A62.5BA.A62.
5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A
62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A62.5BA.A$10.
5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B
65.5B65.5B65.5B65.5B65.5B$8.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B
65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.
B65.3B.B65.3B.B65.3B.B$8.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B
67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B3$6.2A68.2A68.2A68.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A$6.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A2$3.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A$3.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A2$2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A$2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A23$20.2A2.2A2.2A2.2A22.2A2.2A2.2A274.2A2.2A2.2A2.2A2.2A$20.2A
2.2A2.2A2.2A22.2A2.2A2.2A274.2A2.2A2.2A2.2A2.2A3$16.2A2.2A10.2A2.2A
22.2A2.2A238.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A$16.2A2.2A10.2A2.2A22.2A
2.2A238.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A3$12.2A2.2A18.2A22.2A2.2A238.
2A2.2A6.2A2.2A34.2A2.2A22.2A2.2A$12.2A2.2A18.2A22.2A2.2A238.2A2.2A6.
2A2.2A34.2A2.2A22.2A2.2A3$12.2A2.2A42.2A2.2A22.2A2.2A2.2A2.2A2.2A18.
2A2.2A2.2A2.2A18.2A2.2A6.2A2.2A2.2A14.2A2.2A10.2A2.2A14.2A2.2A6.2A2.
2A2.2A50.2A2.2A2.2A2.2A2.2A2.2A2.2A26.2A2.2A26.2A2.2A$12.2A2.2A42.2A
2.2A22.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A18.2A2.2A6.2A2.2A2.2A14.2A
2.2A10.2A2.2A14.2A2.2A6.2A2.2A2.2A50.2A2.2A2.2A2.2A2.2A2.2A2.2A26.2A
2.2A26.2A2.2A3$12.2A2.2A42.2A2.2A18.2A2.2A14.2A2.2A26.2A2.2A18.2A2.2A
10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A26.2A2.
2A$12.2A2.2A42.2A2.2A18.2A2.2A14.2A2.2A26.2A2.2A18.2A2.2A10.2A2.2A10.
2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A26.2A2.2A3$12.2A2.
2A42.2A2.2A18.2A2.2A2.2A2.2A2.2A2.2A2.2A14.2A2.2A2.2A2.2A2.2A18.2A2.
2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A22.2A
2.2A$12.2A2.2A42.2A2.2A18.2A2.2A2.2A2.2A2.2A2.2A2.2A14.2A2.2A2.2A2.2A
2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.
2A2.2A22.2A2.2A3$12.2A2.2A42.2A2.2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.
2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A18.2A
2.2A$12.2A2.2A42.2A2.2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A
10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A18.2A2.2A3$12.2A
2.2A18.2A22.2A2.2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A
2.2A10.2A2.2A18.2A2.2A10.2A2.2A46.2A2.2A2.2A2.2A2.2A2.2A2.2A10.2A2.2A
42.2A2.2A$12.2A2.2A18.2A22.2A2.2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.2A
10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A46.2A2.2A2.2A2.2A2.2A2.
2A2.2A10.2A2.2A42.2A2.2A3$16.2A2.2A10.2A2.2A22.2A2.2A18.2A2.2A14.2A2.
2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.
2A2.2A50.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A22.2A2.2A$16.2A2.2A10.2A2.2A
22.2A2.2A18.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A
2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A22.
2A2.2A3$20.2A2.2A2.2A2.2A22.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A
2.2A2.2A6.2A2.2A14.2A2.2A10.2A2.2A14.2A2.2A2.2A6.2A2.2A14.2A2.2A2.2A
2.2A2.2A54.2A2.2A6.2A2.2A14.2A2.2A2.2A2.2A2.2A2.2A2.2A$20.2A2.2A2.2A
2.2A22.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A6.2A2.2A14.2A
2.2A10.2A2.2A14.2A2.2A2.2A6.2A2.2A14.2A2.2A2.2A2.2A2.2A54.2A2.2A6.2A
2.2A14.2A2.2A2.2A2.2A2.2A2.2A2.2A3$232.2A2.2A$232.2A2.2A3$232.2A2.2A$
232.2A2.2A3$228.2A2.2A2.2A2.2A$228.2A2.2A2.2A2.2A16$387.E$386.E.E$
386.E.E$387.E2$382.2D7.DE205.2B$319.A61.EA.DB4.DA.E134.AB67.4B$53.B.
2B66.B.2B66.B.2B66.B.2B51.ADA12.B.2B44.ADC2B2.3BDEA9.B.2B66.B.2B50.AB
CD12.B.2B50.B2DB12.B.2B66.B.2B49.B.3B12.B.2B66.B.2B50.4B12.B.2B51.B
14.B.2B66.B.2B52.B13.B.2B47.5B14.B.2B66.B.2B50.3B13.B.2B$50.8B62.8B
51.B10.8B51.D10.8B49.ADBCB8.8B44.A3BAC5B7.8B49.B12.8B49.AE.BDB7.8B48.
BD2BDB8.8B47.AE13.8B47.2BD2B2A8.8B62.8B48.6B8.8B49.B2D2B8.8B51.2D9.8B
50.BD2B8.8B44.4B2D3B9.8B48.A13.8B48.5B9.8B$48.12B58.12B48.CEC7.12B48.
BDB7.12B47.BCADB6.12B44.2BCAD2B7.12B46.2DB9.12B47.BD.D2B5.12B46.2BDBD
B6.12B44.AD.E10.12B45.BDBDABA6.12B46.DB10.12B46.BD4B6.12B47.BDBD2B5.
12B47.BD.D2B5.12B47.BDBD2B5.12B41.4BD2BD2B7.12B45.EDA10.12B46.B2D2B7.
12B$45.16B45.2D7.16B48.B5.16B48.DB4.16B45.3BD3B2.16B43.BD2BD2B4.16B
44.D2BD6.16B45.3BD4B.16B45.3BD3B2.16B43.ADA.D6.16B43.BD2BDBA4.16B44.D
AEA6.16B44.BDBD4B2.16B45.3BD3B2.16B46.2BD3B2.16B46.2BD3B2.16B41.3BD2B
D3B3.16B44.E.DA6.16B44.BDBD2B4.16B$42.19B45.2DB3.19B51.19B48.2B.19B
46.24B44.B2D2B2.19B44.B2D2B2.19B46.24B45.25B44.A2D2B2.19B44.B2D2B2.
19B45.2DB3.19B44.B2D23B46.24B46.24B46.24B41.4B2D3B.19B45.2CB3.19B44.B
2D3B.19B$40.21B45.3B.21B49.21B47.23B47.23B45.3B.21B45.3B.21B47.23B47.
23B45.3B.21B45.3B.21B45.3B.21B44.26B47.23B47.23B47.23B42.28B45.3B.21B
44.26B$38.13B2A9B44.15B2A9B46.13B2A9B47.12B2A9B47.12B2A9B44.15B2A9B
44.15B2A9B47.12B2A9B47.12B2A9B44.15B2A9B44.15B2A9B44.15B2A9B44.15B2A
9B47.12B2A9B47.12B2A9B47.12B2A9B41.18B2A9B44.15B2A9B44.15B2A9B$37.13B
ABA10B44.13BABA10B44.13BABA10B45.12BABA10B45.12BABA10B44.13BABA10B44.
13BABA10B45.12BABA10B45.12BABA10B44.13BABA10B44.13BABA10B44.13BABA10B
44.13BABA10B45.12BABA10B45.12BABA10B45.12BABA10B39.18BABA10B44.13BABA
10B44.13BABA10B$38.14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B
44.14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B44.
14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B44.14BA
6B2A3B44.14BA6B2A3B39.19BA6B2A3B44.14BA6B2A3B44.14BA6B2A3B$40.19BABAB
47.19BABAB47.19BABAB47.19BABAB47.19BABAB47.19BABAB47.19BABAB47.19BABA
B47.19BABAB47.19BABAB47.19BABAB47.19BABAB47.19BABAB47.19BABAB47.19BAB
AB47.19BABAB41.3B3.19BABAB47.19BABAB47.19BABAB$42.17BA52.17BA52.17BA
52.17BA52.17BA52.17BA52.17BA52.17BA52.17BA52.17BA52.17BA52.17BA52.17B
A52.17BA52.17BA52.17BA44.3B5.17BA52.17BA52.17BA$42.15B55.15B55.15B55.
15B55.15B55.15B55.15B55.15B55.15B55.15B55.15B55.15B55.15B55.15B55.15B
55.15B48.B6.15B55.15B55.15B$41.14B56.14B56.14B56.14B56.14B56.14B56.
14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B
56.14B$40.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B
56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B$39.7B.8B54.7B.
8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.
7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B
$38.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B
.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B
52.7B.10B52.7B.10B52.7B.10B52.7B.10B$37.7B.12B50.7B.12B50.7B.12B50.7B
.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B
50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.
12B$36.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B
.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B
48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A11B48.7B.B2A
11B48.7B.B2A11B48.7B.B2A11B$35.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B
2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.
8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.
7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.
2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B46.7B2.2B2AB2.8B$34.7B3.BA6.
8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B
44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.
7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B44.7B3.
BA6.8B44.7B3.BA6.8B44.7B3.BA6.8B$33.7B13.8B42.7B13.8B42.7B13.8B42.7B
13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.
7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B
42.7B13.8B42.7B13.8B$32.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.
8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B
15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.
7B15.8B$31.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B
38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.
8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B$30.7B
19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.
7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B
36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B$29.7B21.8B34.7B21.
8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B
21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.
7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B$28.7B23.8B32.7B23.8B32.7B23.8B
32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.
8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B
23.8B32.7B23.8B32.7B23.8B$27.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.
7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B
30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.
8B30.7B25.8B$26.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B
27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.
7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B$
25.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.
8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B
29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B$24.7B31.8B24.
7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B
24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.
8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B$23.7B33.8B22.7B33.8B22.7B
33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.
7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B
22.7B33.8B22.7B33.8B22.7B33.8B$22.7B35.8B20.7B35.8B20.7B35.8B20.7B35.
8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B
35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.
7B35.8B20.7B35.8B$21.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B
18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.
8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B
37.8B$20.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.
7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B
16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B$19.7B41.
8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B
41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.
7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B$18.7B43.8B12.7B43.8B
12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.
8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B
43.8B12.7B43.8B12.7B43.8B12.7B43.8B$17.7B45.8B10.7B45.8B10.7B45.8B10.
7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B
10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.
8B10.7B45.8B10.7B45.8B$16.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B
47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.
3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A
3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B8.7B47.3B2A3B$
15.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.
7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B
49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.
2BABAB8.7B49.2BABAB8.7B49.2BABAB8.7B49.2BABAB$14.7B51.BA10.7B51.BA10.
7B51.BA10.7B51.BA10.7B51.BA10.7B51.BA10.7B51.BA10.7B51.BA10.7B51.BA
10.7B51.BA10.7B51.BA10.7B51.BA10.7B51.BA10.7B51.BA10.7B51.BA10.7B51.B
A10.7B51.BA10.7B51.BA10.7B51.BA$13.7B63.7B63.7B63.7B63.7B63.7B63.7B
63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B$12.2BA4B
63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2B
A4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B63.2BA4B
63.2BA4B$10.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B
2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B
62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B62.4B2A2B$10.3BABA64.3BABA64.3BAB
A64.3BABA64.3BABA64.3BABA64.3BABA64.3BABA64.3BABA64.3BABA64.3BABA64.
3BABA64.3BABA64.3BABA64.3BABA64.3BABA64.3BABA64.3BABA64.3BABA$8.7B63.
7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B
63.7B63.7B63.7B63.7B$8.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.
6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B$8.5B65.5B65.5B65.5B
65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.
5B65.5B$8.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B
66.4B66.4B66.4B66.4B66.4B66.4B66.4B$6.3B.B65.3B.B65.3B.B65.3B.B65.3B.
B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B.B65.3B
.B65.3B.B65.3B.B65.3B.B65.3B.B$6.3B67.3B67.3B67.3B67.3B67.3B67.3B67.
3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B2$3.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A68.2A$3.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A2$2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A$2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.
2A68.2A68.2A68.2A68.2A68.2A23$20.2A2.2A2.2A2.2A22.2A2.2A2.2A274.2A2.
2A2.2A2.2A2.2A$20.2A2.2A2.2A2.2A22.2A2.2A2.2A274.2A2.2A2.2A2.2A2.2A3$
16.2A2.2A10.2A2.2A22.2A2.2A238.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A$16.2A
2.2A10.2A2.2A22.2A2.2A238.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A3$12.2A2.2A
18.2A22.2A2.2A238.2A2.2A6.2A2.2A34.2A2.2A22.2A2.2A$12.2A2.2A18.2A22.
2A2.2A238.2A2.2A6.2A2.2A34.2A2.2A22.2A2.2A3$12.2A2.2A42.2A2.2A22.2A2.
2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A18.2A2.2A6.2A2.2A2.2A14.2A2.2A10.2A2.
2A14.2A2.2A6.2A2.2A2.2A50.2A2.2A2.2A2.2A2.2A2.2A2.2A30.2A2.2A22.2A2.
2A$12.2A2.2A42.2A2.2A22.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A18.2A2.2A
6.2A2.2A2.2A14.2A2.2A10.2A2.2A14.2A2.2A6.2A2.2A2.2A50.2A2.2A2.2A2.2A
2.2A2.2A2.2A30.2A2.2A22.2A2.2A3$12.2A2.2A42.2A2.2A18.2A2.2A14.2A2.2A
26.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A
2.2A6.2A2.2A22.2A2.2A2.2A2.2A$12.2A2.2A42.2A2.2A18.2A2.2A14.2A2.2A26.
2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A
6.2A2.2A22.2A2.2A2.2A2.2A3$12.2A2.2A42.2A2.2A18.2A2.2A2.2A2.2A2.2A2.
2A2.2A14.2A2.2A2.2A2.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A
2.2A10.2A2.2A50.2A2.2A6.2A2.2A34.2A2.2A$12.2A2.2A42.2A2.2A18.2A2.2A2.
2A2.2A2.2A2.2A2.2A14.2A2.2A2.2A2.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.
2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A34.2A2.2A3$12.2A2.2A42.2A2.
2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.
2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A34.2A2.2A$12.2A2.2A42.2A2.2A18.2A2.2A
30.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A
2.2A50.2A2.2A6.2A2.2A34.2A2.2A3$12.2A2.2A18.2A22.2A2.2A18.2A2.2A30.2A
2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A
46.2A2.2A2.2A2.2A2.2A2.2A2.2A30.2A2.2A22.2A2.2A$12.2A2.2A18.2A22.2A2.
2A18.2A2.2A30.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.
2A2.2A10.2A2.2A46.2A2.2A2.2A2.2A2.2A2.2A2.2A30.2A2.2A22.2A2.2A3$16.2A
2.2A10.2A2.2A22.2A2.2A18.2A2.2A14.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A
10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A50.2A2.2A6.2A2.2A14.2A2.
2A14.2A2.2A22.2A2.2A$16.2A2.2A10.2A2.2A22.2A2.2A18.2A2.2A14.2A2.2A10.
2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A10.2A2.2A10.2A2.2A18.2A2.2A10.2A2.2A
50.2A2.2A6.2A2.2A14.2A2.2A14.2A2.2A22.2A2.2A3$20.2A2.2A2.2A2.2A22.2A
2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A18.2A2.2A2.2A6.2A2.2A14.2A2.2A10.2A
2.2A14.2A2.2A2.2A6.2A2.2A14.2A2.2A2.2A2.2A2.2A54.2A2.2A6.2A2.2A18.2A
2.2A2.2A2.2A$20.2A2.2A2.2A2.2A22.2A2.2A2.2A2.2A18.2A2.2A2.2A2.2A2.2A
18.2A2.2A2.2A6.2A2.2A14.2A2.2A10.2A2.2A14.2A2.2A2.2A6.2A2.2A14.2A2.2A
2.2A2.2A2.2A54.2A2.2A6.2A2.2A18.2A2.2A2.2A2.2A3$232.2A2.2A$232.2A2.2A
3$232.2A2.2A$232.2A2.2A3$228.2A2.2A2.2A2.2A$228.2A2.2A2.2A2.2A16$397.
E$396.E.E$396.E.E$397.E2$392.2D7.DE205.2B$329.A61.EA.DB4.DA.E134.AB
67.4B$63.B.2B66.B.2B66.B.2B66.B.2B51.ADA12.B.2B44.ADC2B2.3BDEA9.B.2B
66.B.2B50.ABCD12.B.2B50.B2DB12.B.2B66.B.2B49.B.3B12.B.2B66.B.2B50.4B
12.B.2B51.B14.B.2B66.B.2B52.B13.B.2B47.5B14.B.2B66.B.2B50.3B13.B.2B$
60.8B62.8B51.B10.8B51.D10.8B49.ADBCB8.8B44.A3BAC5B7.8B49.B12.8B49.AE.
BDB7.8B48.BD2BDB8.8B47.AE13.8B47.2BD4B8.8B62.8B48.6B8.8B49.B2D2B8.8B
51.2D9.8B50.BD2B8.8B44.4B2D3B9.8B48.A13.8B48.5B9.8B$58.12B58.12B48.CE
C7.12B48.BDB7.12B47.BCADB6.12B44.2BCAD2B7.12B46.2DB9.12B47.BD.D2B5.
12B46.2BDBDB6.12B44.AD.E10.12B45.BDBD5B4.12B46.DB10.12B46.BD4B6.12B
47.BDBD2B5.12B47.BD.D2B5.12B47.BDBD2B5.12B41.4BD2BD2B7.12B45.EDA10.
12B46.B2D2B7.12B$55.16B45.2D7.16B48.B5.16B48.DB4.16B45.3BD3B2.16B43.B
D2BD2B4.16B44.D2BD6.16B45.3BD4B.16B45.3BD3B2.16B43.ADA.D6.16B43.BD2BD
5B.16B44.DAEA6.16B44.BDBD4B2.16B45.3BD3B2.16B46.2BD3B2.16B46.2BD3B2.
16B41.3BD2BD3B3.16B44.E.DA6.16B44.BDBD2B4.16B$52.19B45.2DB3.19B51.19B
48.2B.19B46.24B44.B2D2B2.19B44.B2D2B2.19B46.24B45.25B44.A2D2B2.19B44.
B2D23B45.2DB3.19B44.B2D23B46.24B46.24B46.24B41.4B2D3B.19B45.2CB3.19B
44.B2D3B.19B$50.21B45.3B.21B49.21B47.23B47.23B45.3B.21B45.3B.21B47.
23B47.23B45.3B.21B45.25B45.3B.21B44.26B47.23B47.23B47.23B42.28B45.3B.
21B44.26B$48.12B2A10B44.14B2A10B46.12B2A10B47.11B2A10B47.11B2A10B44.
14B2A10B44.14B2A10B47.11B2A10B47.11B2A10B44.14B2A10B44.14B2A10B44.14B
2A10B44.14B2A10B47.11B2A10B47.11B2A10B47.11B2A10B41.17B2A10B44.14B2A
10B44.14B2A10B$47.14B2A10B44.14B2A10B44.14B2A10B45.13B2A10B45.13B2A
10B44.14B2A10B44.14B2A10B45.13B2A10B45.13B2A10B44.14B2A10B44.14B2A10B
44.14B2A10B44.14B2A10B45.13B2A10B45.13B2A10B45.13B2A10B39.19B2A10B44.
14B2A10B44.14B2A10B$48.12BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B44.12BA7B
2A4B44.12BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B
44.12BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B44.
12BA7B2A4B44.12BA7B2A4B39.17BA7B2A4B44.12BA7B2A4B44.12BA7B2A4B$50.17B
2A4B47.17B2A4B47.17B2A4B47.17B2A4B47.17B2A4B47.17B2A4B47.17B2A4B47.
17B2A4B47.17B2A4B47.17B2A4B47.17B2A4B47.17B2A4B47.17B2A4B47.17B2A4B
47.17B2A4B47.17B2A4B41.3B3.17B2A4B47.17B2A4B47.17B2A4B$52.17BAB51.17B
AB51.17BAB51.17BAB51.17BAB51.17BAB51.17BAB51.17BAB51.17BAB51.17BAB51.
17BAB51.17BAB51.17BAB51.17BAB51.17BAB51.17BAB43.3B5.17BAB51.17BAB51.
17BAB$52.16B54.16B54.16B54.16B54.16B54.16B54.16B54.16B54.16B54.16B54.
16B54.16B54.16B54.16B54.16B54.16B47.B6.16B54.16B54.16B$51.14B56.14B
56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.
14B56.14B56.14B56.14B56.14B56.14B$50.14B56.14B56.14B56.14B56.14B56.
14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B56.14B
56.14B56.14B$49.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B
54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B.8B54.7B
.8B54.7B.8B54.7B.8B54.7B.8B$48.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B
.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B
52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B52.7B.10B$47.7B
.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B
50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.12B50.7B.
12B50.7B.12B50.7B.12B50.7B.12B$46.7B.3A11B48.7B.3A11B48.7B.3A11B48.7B
.3A11B48.7B.3A11B48.7B.3A11B48.7B.3A11B48.7B.3A11B48.7B.3A11B48.7B.3A
11B48.7B.3A11B48.7B.3A11B48.7B.3A11B48.7B.3A11B48.7B.3A11B48.7B.3A11B
48.7B.3A11B48.7B.3A11B48.7B.3A11B$45.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.
7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.
2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B
2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B
46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B46.7B2.2BA2B2.8B$44.
7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B
44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.
8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB
5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B44.7B3.BAB5.8B$43.7B13.
8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B
13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.
7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B42.7B13.8B$42.7B15.8B40.7B15.8B
40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.
8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B15.8B40.7B
15.8B40.7B15.8B40.7B15.8B40.7B15.8B$41.7B17.8B38.7B17.8B38.7B17.8B38.
7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B
38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.8B38.7B17.
8B38.7B17.8B38.7B17.8B$40.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B
19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.
7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B36.7B19.8B
36.7B19.8B$39.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.
8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B
21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B34.7B21.8B$38.
7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B
32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.
8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B32.7B23.8B$37.7B25.8B30.7B
25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.
7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B
30.7B25.8B30.7B25.8B30.7B25.8B30.7B25.8B$36.7B27.8B28.7B27.8B28.7B27.
8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B
27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.7B27.8B28.
7B27.8B28.7B27.8B28.7B27.8B$35.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B
26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.
8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B29.8B26.7B
29.8B26.7B29.8B$34.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.
7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B
24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.8B24.7B31.
8B$33.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B
33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.
7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B22.7B33.8B$32.7B35.8B
20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.
8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B
35.8B20.7B35.8B20.7B35.8B20.7B35.8B20.7B35.8B$31.7B37.8B18.7B37.8B18.
7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B
18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.8B18.7B37.
8B18.7B37.8B18.7B37.8B18.7B37.8B$30.7B39.8B16.7B39.8B16.7B39.8B16.7B
39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.
7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B16.7B39.8B
16.7B39.8B16.7B39.8B$29.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.
8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B
41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.7B41.8B14.
7B41.8B$28.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B
12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.
8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B12.7B43.8B$27.7B
45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.
7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B
10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B10.7B45.8B$26.7B47.2B2A4B8.7B
47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.
2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A
4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.7B47.2B2A4B8.
7B47.2B2A4B8.7B47.2B2A4B$25.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A
4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B
8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.7B49.2A4B8.
7B49.2A4B8.7B49.2A4B8.7B49.2A4B$24.7B51.BAB9.7B51.BAB9.7B51.BAB9.7B
51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB9.
7B51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB9.7B51.BAB
9.7B51.BAB9.7B51.BAB$23.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.
7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B$22.B2A4B63.B2A4B63.B
2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B
63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B63.B2A4B$20.
2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B
62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA
3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B62.2BABA3B$20.4BAB64.4BAB
64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB64.4BA
B64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB64.4BAB$18.7B63.7B63.7B63.
7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B63.7B
63.7B63.7B$18.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B64.
6B64.6B64.6B64.6B64.6B64.6B64.6B64.6B$18.5B65.5B65.5B65.5B65.5B65.5B
65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B$17.
5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B
65.5B65.5B65.5B65.5B65.5B$16.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.
5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B65.5B$15.4B66.4B66.4B
66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.4B66.
4B66.4B66.4B$15.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B
67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B$13.3B67.3B67.3B67.3B67.3B67.
3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B$
13.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.3B67.
3B67.3B67.3B67.3B67.3B67.3B2$10.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A$10.2A68.2A68.
2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A68.2A
68.2A68.2A68.2A!
This probe is for use with a skewed raster scan along a slope of 1/2. (My hope was this slope would make dealing with inside corners easier, but if I had thought about it a bit more I would have tried building the probe out of glider-spaceship collisions.)

One downside of only receiving one bit of information is that if the algorithm sees the signal glider it does not know if there are by-products of the probe to clean up and has to blindly proceed with cleanup #1-#3.

This is a very slow process for clearing ash with many setbacks. And so far I haven't implemented a way to intercept spurious gliders/spaceships/switch engines. It should be possible to do so, but it remains to be seen if I can do this and still maintain a positive rate of ash clearing. Below is a python golly script showing the clearing in action. Clearing a puffer trail is a bit of a cheat as the clean-up will scale quadratically in the width of the ash field due to the back-offs.

Code: Select all


import golly as g

# Copyright Andrew Wade
#
# Feel free to copy and modify.
#
# I don't know the correct attribution for line-puffer-superstable.

"""
Proof of concept for ash clearing in Conway's Life.

This is a golly script implementing an algorithm for clearing ash
in Conway's Game of Life using gliders.

Limitations
-----------

* The algorithm requires an ash field of finite (and known) width.

* This script deletes stray gliders rather than dealing with them
  in a realistic way. Stray switch engines will cause failure however.

How it Works
------------

The field containing the ash is probed by a skewed raster scan
(slope 1/2). The probe is carefully chosen so that:

1. When it interacts with an ash object it causes minmal disruption
   to avoid "blow-ups", and avoids leaving by-products further into
   ash field where they may cause future "blow-ups".

2. It returns a signal glider but not when a "blow-up" occurs.

In addition I tried to pick a volley that would not leave many
by-products just outside the ash field, but this aim is in tension
with the previous two. As a result each probe volley is followed
by three other volleys to clean up the most common by-products
when the probe interacts with ash.

If they signal glider is not seen, the algorithm assumes that
a "blow-up" has occurred and backs off a large number of rows.
The algorthm receives only one bit of information back from each
volley and needs to be pessimistic when to comes to how many rows
to back-off.

The back-off behavior causes the algorithm to scale quadratically
with the width of the ash field.
"""

def init():
    """Start a new universe with an ash target.

    Does initial golly setup (algo, etc.) and creates an ash
    field to cleanup.
    """
    g.new("")
    g.setalgo("HashLife")
    g.setbase(2)
    g.setstep(14)

    line_puffer_superstable="""
34b3o27b3o13b3o27b3o$33bo3bo25bo3bo11bo3bo25bo3bo$32b2o4bo11bo11bo4b2o
9b2o4bo11bo11bo4b2o$31bobob2ob2o3b4ob2ob2ob4o3b2ob2obobo7bobob2ob2o3b
4ob2ob2ob4o3b2ob2obobo$30b2obo4bob2ob4o7b4ob2obo4bob2o5b2obo4bob2ob4o
7b4ob2obo4bob2o$29bo4bo3bo4bo2b2obobob2o2bo4bo3bo4bo3bo4bo3bo4bo2b2obo
bob2o2bo4bo3bo4bo$6bo17bo16bo4bo7bo4bo27bo4bo7bo4bo25bo17bo$5b3o15b3o
3b2o7b2o6bo7bo6b2o7b2o3b2o7b2o6bo7bo6b2o7b2o12b3o15b3o$3b2ob3o13b3ob2o
100b2ob3o13b3ob2o$4bo2bob2o4bo4b2obo2bo18b2o7b2o35b2o7b2o27bo2bob2o4bo
4b2obo2bo$b2obo4bobob2ob2obobo4bob2o17bo5bo39bo5bo26b2obo4bobob2ob2obo
bo4bob2o$b2obobo2bobo7bobo2bobob2o15bo2bo3bo2bo35bo2bo3bo2bo24b2obobo
2bobo7bobo2bobob2o$bo8b3obobob3o8bo16bo2bobo2bo37bo2bobo2bo25bo8b3obob
ob3o8bo$2o7b2o9b2o7b3obo15bobo43bobo24bob3o7b2o9b2o7b2o$33b2o12bobobob
o39bobobobo21b2o$31b2obo11b2obobob2o37b2obobob2o20bob2o$34b2o9bo3bobo
3bo35bo3bobo3bo18b2o$33bo88bo$35b3o7b2ob2ob2ob2o35b2ob2ob2ob2o16b3o$7b
3o15b3o9b2o78b2o9b3o15b3o$6bo3bo13bo3bo9bo7bo3bo3bo37bo3bo3bo16bo9bo3b
o13bo3bo$5b2o4bo11bo4b2o8b2o6bo3bo3bo7b3o9b3o9b3o3bo3bo3bo4b3o8b2o8b2o
4bo11bo4b2o$4bobob2ob2o3b3o3b2ob2obobo8bo21bo3bo7bo3bo7bo3bo14bo3bo7bo
8bobob2ob2o3b3o3b2ob2obobo$3b2obo4bob2ob3ob2obo4bob2o6bobo5b2o5b2o5b2o
3b2o5b2o3b2o5b2o3b2o5b2o5b2o3b2o5bobo6b2obo4bob2ob3ob2obo4bob2o$2bo4bo
3bo4bobo4bo3bo4bo6b3o3b4o3b4o3b2obobob2o3b2obobob2o3b2obobob2o3b4o3b2o
bobob2o3b3o6bo4bo3bo4bobo4bo3bo4bo$14bo5bo20b2ob2o2b2ob2o2b2ob2ob2ob2o
b2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2b2ob2ob2ob2ob2ob2o20bo5bo$2b2o7b2o9b2o
7b2ob3o5bobo4bobo4bobo3bobo3bobo3bobo3bobo3bobo3bobo4bobo3bobo3bobo5b
3ob2o7b2o9b2o7b2o$36bo82bo$34bo6b2ob2o2b2ob2o2b2ob2ob2ob2ob2ob2ob2ob2o
b2ob2ob2ob2ob2ob2o2b2ob2ob2ob2ob2ob2o6bo$34bob2o80b2obo$39b78o$38bo78b
o!
"""

    g.putcells(g.parse(line_puffer_superstable),-78, 0)

    # block to collide with. We don't want the puffer running
    # indefinitely since that will slow down HashLife for the
    # clearing stage. For the same reason we will trim off gliders
    # later.
    g.putcells(g.parse("2o$2o!"),0, -5000)
    g.step()
    g.step()

    # Trim off the outsides of the ash (mostly gliders)
    g.select([-400, -10000, 800, 20000])
    g.clear(1)
    g.select([])

def glider(pos, direction):
    """Returns a cell list for a glider with the given pos and direction

    Parameters
    ----------

    pos:
        The (x,y) position of the glider in units of quarter cells.

    direction:
        The (dx, dy) offset in quarter cells the glider moves each tick.

    Which positions are valid depends on the direction.
    """

    corner = ((pos[0] * direction[0]) // 4, (pos[1] * direction[1]) // 4)
    mod = ((pos[0] * direction[0]) % 4, (pos[1] * direction[1]) % 4)

    if mod == (2,0):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] -2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] -1 ) * direction[1],
            ]
    elif mod == (1, 3):
        return [
            (corner[0] - 1) * direction[0], (corner[1] + 1) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1]
            ]
    elif mod == (0, 2):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1]
            ]
    elif mod == (3, 1):
        return [
            (corner[0] + 1) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1]
            ]
    else:
        raise Exception("Invalid glider location")

def write_glider(pos, direction):
    """writes a glider into the universe at the given pos and direction

    Parameters
    ----------

    pos, direction:
        As per the parameters to glider()
    """

    g.putcells(glider(pos, direction))

def read_glider_destructive(pos, direction):
    """If a glider is present, delete it and return true

    Parameters
    ----------

    pos, direction:
        As per the parameters to glider()

    Note: for slightly misaligned/mistimed gliders this function will
    behave differently than realistic life circuitry. We're not expecting
    many misaligned gliders so this shouldn't matter much.
    """
    celllist = glider(pos, direction)
    rv = g.getcell(celllist[0], celllist[1])
    g.putcells(celllist, 0, 0, 1, 0, 0, 1, "not")
    return bool(rv)


def volley(pos, delay, delay2, stepsize):
    """Fire off a probe volley and return True if the signal glider returns.

    The same volley but offset is also used to clean up possible
    by-products. There is no need to use the same volley for cleanup,
    it's just convenient.

    Parameters
    ----------

    pos:
        The (x,y) position being probed. There is actually not much
        significance to the particular cell at (x,y); each different
        ash object will have some offset from (x,y) at which an
        interaction with this probe would be the first interaction
        with the raster scan.

    delay:
        How far back before interaction to place the gliders (ticks).

    delay2:
        Additional delay the last two gliders which result in the signal
        glider.

    stepsize:
        How many generations does g.step() advance.

    Returns
    -------

    True if the signal glider is seen (blow-up probably didn't occur).

    False if the signal glider is not seen (possble blow-up).
    """

    x = pos[0] * 4
    y = pos[1] * 4
    write_glider((x -4 - delay, y +2 +8 + delay), (1,-1))
    write_glider((x + delay, y +  2 + delay), (-1, -1))
    write_glider((x + 23 + delay, y + 2 + 43 + delay), (-1, -1))
    write_glider((x + 40 - delay - delay2, y + 2 + 24 + delay + delay2), (1, -1))
    write_glider((x + 49 + delay + delay2, y + 2 + 41 + delay + delay2), (-1, -1))

    g.step()

    if not read_glider_destructive((x + 35 + stepsize - delay - delay2, y + 2 + 23 + stepsize - delay - delay2), (1, 1)):
        return False

    return True

def run_clear_algo():
    """Ash clearing algorithm.

    This algorithm is based on volley(), which only interacts with the
    life universe through write_glider(), read_glider_destructive()
    and g.step(), all of which can be implemented with life circuitry.
    (g.step() is just a fixed wait.)

    However this function also cleans up stray gliders in a non-realistic
    way.

    """
    x=0
    y=128

    for i in range(1000000000):
        x += 2
        y += 1
        if x > 256:
            # start next row in the raster scan.
            x -= 511
            y -= 256
        if not (
            volley((x, y), 4096, 100, 1<<14)
            and volley((x - 3, y - 1), 4096, 100, 1<<14)
            and volley((x - 1, y), 4096, 100, 1<<14)
            and volley((x, y), 4096 + 1, 100, 1<<14)
            ):
            # something's gone wrong. Back off in the raster scan.
            y += 100

        if i & 1023 == 0:
            # updating after evey volley slows things down
            # too much.

            # Remove stray gliders
            oldsel = g.getselrect()
            g.select([-1000, -10000, 2000, 20000])
            g.clear(1)
            g.select(oldsel)

            g.update()

init()
run_clear_algo()
-- Andrew Wade

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

Re: Clearing Ash

Post by dvgrn » September 4th, 2021, 1:50 pm

That's an impressive amount of progress! I watched the script run until about T = one billion, where I think the first toad showed up and caused a (theoretically successful) reset. It does seem as if, given another layer or two of paranoid damage-control mechanisms, a replicator pattern might actually be able to clear out enough space around itself to make two copies of itself, in a sufficiently old and settled Life universe.

The "another layer or two" might be along the lines of a scattering of blocks that can absorb any incoming stray glider from a failed explosion like the one you showed caused by the toad. The blocks could be torn down and rebuilt whenever the "don't back off" glider fails to return from the cleanup site.

I guess a more extreme version might have a protected inner region listening to signals from an outer region, and the outer region would do all the testing while periodically reassuring the inner region that everything is going okay. Whenever an outer-region signal fails to come back, the inner region would send a self-destruct message to the outer region, wait a good long time, and then do its own ash-clearing attempt for the outer-region area and rebuild the outer region.

Not sure if this would really improve the survivability of the structure, though -- quite possibly smaller and simpler will turn out to be better.

All of that said, it doesn't take very much bad luck or uncommon objects to trick the current probe. For example, a biblock can cause an out-of-control explosion without triggering a back-off message:

Code: Select all

x = 75, y = 56, rule = LifeHistory
36.2C$36.2C2$36.2E$36.2E2$50.2A$49.A.A$51.A6.2A$58.A.A$58.A7$44.2A$
45.2A$44.A18$72.2A$72.A.A$72.A2$13.A$13.2A$12.A.A$8.2A$8.2A3$6.2A$6.
2A2$3.2A$3.2A2$2A$2A!
And of course you don't have to have very much additional stuff scattered around before you could have really dangerous active things suddenly aimed back at the space-clearing mechanism, like glider-producing switch engines or even guns:

Code: Select all

x = 97, y = 107, rule = B3/S23
90bo$89bobo$90b2o4$94b2o$94b2o10$93b2o$92bobo$92b2o9$72bo21b2o$71bobo
20bobo$71bo2bo20b2o$72b2o6$67bo$66bobo$67b2o$95b2o$95b2o$34b2o$33bo2bo
52bo$34b2o42b2o8bobo$78bobo8bobo$79bobo8b2o$80bo4$36b2o$36b2o2$36b2o$
36b2o2$50b2o$49bobo$51bo6b2o$58bobo$58bo7$44b2o$45b2o$44bo18$72b2o$72b
obo$72bo2$13bo$13b2o$12bobo$8b2o$8b2o3$6b2o$6b2o2$3b2o$3b2o2$2o$2o!
I guess it's just a question of how often really unlucky ash constellations actually show up in real Life. A failure in a replicator every now and then just makes a bunch more random ash for its fellow replicators to clean up.

AGreason
Posts: 53
Joined: January 31st, 2018, 9:02 pm

Re: Clearing Ash

Post by AGreason » September 7th, 2021, 9:43 pm

I kept running the example - it fully cleared the line puffer ash after 1.18e12 ticks.

mscibing
Posts: 105
Joined: May 18th, 2010, 8:30 pm

Re: Clearing Ash

Post by mscibing » October 23rd, 2021, 9:38 pm

I've made some additional progress in ash clearing, I now have a volley that can advance the eight corners of an octogon.

The is the probe volley:

Code: Select all

x = 268, y = 179, rule = LifeHistory
214.C$164.C48.C.C48.2C$64.2C47.3C48.C48.C.C47.C2.C$64.2C98.C49.C49.2C
19$4.3A47.3A47.3A47.3A47.3A47.3A$6.A49.A49.A49.A49.A49.A$5.A49.A49.A
49.A49.A49.A3$2A48.2A48.2A48.2A48.2A48.2A$.2A48.2A48.2A48.2A48.2A48.
2A$A49.A49.A49.A49.A49.A3$15.3A47.3A47.3A47.3A47.3A47.3A$14.A2.A46.A
2.A46.A2.A46.A2.A46.A2.A46.A2.A$3.A13.A35.A13.A35.A13.A35.A13.A35.A
13.A35.A13.A$3.2A12.A35.2A12.A35.2A12.A35.2A12.A35.2A12.A35.2A12.A$2.
A.A12.A34.A.A12.A34.A.A12.A34.A.A12.A34.A.A12.A34.A.A12.A$17.A49.A49.
A49.A49.A49.A$16.A49.A49.A49.A49.A49.A32$14.C49.2C49.C47.2C$13.C.C47.
C2.C47.C.C45.C2.C47.2C50.C$13.C2.C46.C.C47.C2.C46.C.C47.C.C48.C.C$14.
2C48.C49.2C48.C49.C49.2C19$4.3A47.3A47.3A47.3A47.3A47.3A$6.A49.A49.A
49.A49.A49.A$5.A49.A49.A49.A49.A49.A3$2A48.2A48.2A48.2A48.2A48.2A$.2A
48.2A48.2A48.2A48.2A48.2A$A49.A49.A49.A49.A49.A3$15.3A47.3A47.3A47.3A
47.3A47.3A$14.A2.A46.A2.A46.A2.A46.A2.A46.A2.A46.A2.A$3.A13.A35.A13.A
35.A13.A35.A13.A35.A13.A35.A13.A$3.2A12.A35.2A12.A35.2A12.A35.2A12.A
35.2A12.A35.2A12.A$2.A.A12.A34.A.A12.A34.A.A12.A34.A.A12.A34.A.A12.A
34.A.A12.A$17.A49.A49.A49.A49.A49.A$16.A49.A49.A49.A49.A49.A32$114.2C
$14.C49.2C47.C2.C47.C48.2C50.2C$13.C.C47.C.C47.C2.C46.C.C47.C.C48.C.C
$14.2C48.C49.2C48.C49.2C48.2C19$4.3A47.3A47.3A47.3A47.3A47.3A$6.A49.A
49.A49.A49.A49.A$5.A49.A49.A49.A49.A49.A3$2A48.2A48.2A48.2A48.2A48.2A
$.2A48.2A48.2A48.2A48.2A48.2A$A49.A49.A49.A49.A49.A3$15.3A47.3A47.3A
47.3A47.3A47.3A$14.A2.A46.A2.A46.A2.A46.A2.A46.A2.A46.A2.A$3.A13.A35.
A13.A35.A13.A35.A13.A35.A13.A35.A13.A$3.2A12.A35.2A12.A35.2A12.A35.2A
12.A35.2A12.A35.2A12.A$2.A.A12.A34.A.A12.A34.A.A12.A34.A.A12.A34.A.A
12.A34.A.A12.A$17.A49.A49.A49.A49.A49.A$16.A49.A49.A49.A49.A49.A!
The probe itself doesn't return a signal glider, but the follow-up volleys to clean up the mess left by the probe do return signal gliders. I can clean up the mess left by the probe with 9 follow-up volleys, which is rather a lot, and it is necessary to send all 9 follow-up volleys for each probe since the algorithm doesn't know what the probe encountered (if anything).

Here is a golly script for clearing a corner in a cardinal direction:

Code: Select all


import golly as g

# Copyright Andrew Wade
#
# Feel free to copy and modify.

"""
Proof of concept for ash clearing in Conway's Life.

This is a golly script implementing an algorithm for clearing ash
in Conway's Game of Life using gliders.

Limitations
-----------

* This script deletes stray gliders rather than dealing with them
  in a realistic way. Stray switch engines will cause failure however.

How it Works
------------

The field containing the ash is probed by a skewed raster scan
(slope 1/2). The probe is carefully chosen so that when it interacts
with an ash object it causes minmal disruption to avoid "blow-ups",
and avoids leaving by-products further into ash field where they may
cause future "blow-ups".

Each probe is followed by 9 follow-up volleys. Each follow-up volley does
two things:

1. Deletes an object that would be left behind outside the ash field
   after the probe interacts with one of the top 8 most common ash objects.

2. Returns a signal glider. This indicates that everything is still
   (probably) going okay with the ash clearing.

If the signal glider is not seen, the algorithm assumes that
a "blow-up" has occurred and backs off a large number of rows.
The algorthm receives only one bit of information back from each
volley and needs to be pessimistic when to comes to how many rows
to back-off. As an optimization the back-off is along only a limited
frontage of the ash field.

This script demonstrates that slope -1/2 and 1/2 edges meeting at a corner
can be advanced in a cardinal direction. The corner is rounded slightly
to mitigate against the poor performance of the probe in a corner.

"""

def init():
    """Start a new universe with an ash target.

    Does initial golly setup (algo, etc.) and creates an ash
    field to cleanup.
    """
    g.new("")
    g.setalgo("HashLife")
    g.setbase(2)
    g.setstep(14)
    g.setmag(0)

    g.select([-700, -1700, 1400, 1400])
    g.randfill(30)

    g.step()
    g.step()
    g.step()
    g.step()

    # Trim off the outsides of the ash (mostly gliders)
    g.select([-5000, -10000, 10000, 10000])
    g.clear(1)
    g.select([])

def glider(pos, direction):
    """Returns a cell list for a glider with the given pos and direction

    Parameters
    ----------

    pos:
        The (x,y) position of the glider in units of quarter cells.

    direction:
        The (dx, dy) offset in quarter cells the glider moves each tick.

    Which positions are valid depends on the direction.
    """

    corner = ((pos[0] * direction[0]) // 4, (pos[1] * direction[1]) // 4)
    mod = ((pos[0] * direction[0]) % 4, (pos[1] * direction[1]) % 4)

    if mod == (2,0):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] -2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] -1 ) * direction[1],
            ]
    elif mod == (1, 3):
        return [
            (corner[0] - 1) * direction[0], (corner[1] + 1) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1]
            ]
    elif mod == (0, 2):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1]
            ]
    elif mod == (3, 1):
        return [
            (corner[0] + 1) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1]
            ]
    else:
        raise Exception("Invalid glider location")

def xwss(weight, pos, direction, phase):
    """Returns a cell list for a spaceship

    Parameters
    ----------

    weight:
        0 - lwss, 1 - mwss, 2 - hwss

    pos:
        The (x, y) position of the spaceship in units of quarter cells.

    direction:
        The (dx, dy) offset in quarter cells the glider moves each tick.

    phase:
        The phase of the spaceship.

    Which positions are valid depend on the direction and phase.
    """

    if phase % 2 == 0:
        assert pos[0] % 4 == 2 or pos[1] % 4 == 2
        cells = [(-4, 6), (-4, 10), (0, 2), (0, 6)]
        cells += [(0, 2 + 4 * y) for y in range(3, 5 + weight)]
        cells += [(4, 2 + 4 * y) for y in range(1, 5 + weight)]
        cells += [(8, 2 + 4 * y) for y in range(2, 4 + weight)]
    else:
        assert pos[0] % 4 == 0 and pos[1] % 4 == 0
        cells = [(0,4), (4, 4), (8, 8)]
        cells += [(0, 20 + 4 * weight), (8, 20 + 4 * weight)]
        cells += [(-4, 4 * y) for y in range(1, 5 + weight)]
        cells += [(12, 4 * y) for y in range(4, 4 + weight)]

    if phase % 4 > 1:
        cells = [(-x, y) for (x, y) in cells]

    if direction == (2, 0):
        assert pos[1] % 4 == 0
        cells = [((pos[0] - y) // 4, (pos[1] + x) // 4) for (x, y) in cells]
    elif direction == (0, 2):
        assert pos[0] % 4 == 0
        cells = [((pos[0] - x) // 4, (pos[1] - y) // 4) for (x, y) in cells]
    elif direction == (-2, 0):
        cells = [((pos[0] + y) // 4, (pos[1] - x) // 4) for (x, y) in cells]
    elif direction == (0, -2):
        cells = [((pos[0] + x) // 4, (pos[1] + y) // 4) for (x, y) in cells]
    else:
        raise Exception("Invalid spaceship velocity")

    return [coord for cell in cells for coord in cell]


def write_glider(pos, direction):
    """writes a glider into the universe at the given pos and direction

    Parameters
    ----------

    pos, direction:
        As per the parameters to glider()
    """

    g.putcells(glider(pos, direction))

def write_lwss(pos, direction, phase):
    g.putcells(xwss(0, pos, direction, phase))

def write_mwss(pos, direction, phase):
    g.putcells(xwss(1, pos, direction, phase))

def write_hwss(pos, direction, phase):
    g.putcells(xwss(2, pos, direction, phase))

def read_glider_destructive(pos, direction):
    """If a glider is present, delete it and return true

    Parameters
    ----------

    pos, direction:
        As per the parameters to glider()

    Note: for slightly misaligned/mistimed gliders this function will
    behave differently than realistic life circuitry. We're not expecting
    many misaligned gliders so this shouldn't matter much.
    """
    celllist = glider(pos, direction)
    rv = g.getcell(celllist[0], celllist[1])
    g.putcells(celllist, 0, 0, 1, 0, 0, 1, "not")
    return bool(rv)


def probe_volley(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Set up a probe volley.

    This function does not advance time so that the probe_volley
    can be combined with the first follow-up volley.

    Parameters
    ----------

    delay:
        How far back before interaction to place the gliders (ticks).

    x0, y0:
        The (x0,y0) position being probed.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    x = x0 * 4
    y = y0 * 4
    (dx, dy) = (8, 12 + 2 * delay)
    write_hwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (18 - delay, 24 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (1 - delay, 45 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (11 - delay, 75 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))


def followup_volley(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Fire off a followup volley and return True if the signal glider returns.

    Parameters
    ----------

    delay:
        How far back before the interaction to place the gliders (ticks).

    stepsize:
        How many generations g.step() advances.

    x0, y0:
        The (x0, y0) position being cleaned up. The position of the object
        relative to (x0, y0) will vary with the type of object.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    x = x0 * 4
    y = y0 * 4

    (dx, dy) = (-16, 20 + 2 * delay)
    write_lwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (-5 - delay, 11 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (-22 - delay, 28 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    g.step()

    (dx, dy) = (-18 + delay - stepsize, 36 - delay + stepsize)
    return read_glider_destructive((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))


def clear_cell(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Clears the cell at (x0, y0). returns True if all signal gliders return.

    delay:
        How far back before the interaction to place the gliders (ticks).

    stepsize:
        How many generations g.step() advances.

    x0, y0:
        The (x0, y0) position being cleaned up. The position of the object
        relative to (x0, y0) will vary with the type of object.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    probe_volley(delay, x0, y0, axx, axy, ayx, ayy)

    for (dx, dy, extra_delay) in [
        (5, 12, 100),
        (-1, 9, 0),
        (-6, 0, 0),
        (-1, 4, 1),
        (-3, 2, 1),
        (-4, 1, 0),
        (-2, 0, 0),
        (1, 4, 1),
        (0, 0, 0) ]:
        if not followup_volley(delay + extra_delay,
                               stepsize,
                               x0 + dx * axx + dy * axy,
                               y0 + dx * ayx + dy * ayy,
                               axx, axy, ayx, ayy):
            return False

    return True

def clear_corner_cell(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """clear_cell() except that some of the follow-up volleys are omitted.

    The omitted follow-up volleys are counter-productive in a corner.
    """

    probe_volley(delay, x0, y0, axx, axy, ayx, ayy)

    for (dx, dy, extra_delay) in [
        (5, 12, 100),
        (-1, 9, 0),
        #(-6, 0, 0),
        (-1, 4, 1),
        (-3, 2, 1),
        (-4, 1, 0),
        #(-2, 0, 0),
        (1, 4, 1),
        (0, 0, 0) ]:
        if not followup_volley(delay + extra_delay,
                               stepsize,
                               x0 + dx * axx + dy * axy,
                               y0 + dx * ayx + dy * ayy,
                               axx, axy, ayx, ayy):
            return False

    return True



def run_clear_algo():
    """Ash clearing algorithm.

    This algorithm is based on clear_cell(), which only interacts with the
    life universe through write_glider(), read_glider_destructive()
    and g.step(), all of which can be implemented with life circuitry.
    (g.step() is just a fixed wait.)

    However this function also cleans up stray gliders in a non-realistic
    way.

    """

    min_col_backoff = -10
    max_col_backoff = 10
    ash_front = 600 # line at which we should start clearing the entire ash front.
    line = 600 # current line being cleared in units of 1/2 cell.

    for i in range(1000000000):
        # Remove stray gliders (this is unrealistic.)
        oldsel = g.getselrect()
        g.select([-5000, -10000, 10000, 10000])
        g.clear(1)
        g.select(oldsel)

        g.update()

        line += 1
        # if a "blow-up" is detected then the line will be updated in the
        # middle of a pass. The back-off is always a power of two so that
        # the loops continue to function correctly after the update.

        if line >= ash_front:
            # Go back to clearing the entire width of the ash field.
            ash_front = line
            min_col = -1000 # start of frontage being cleared
            max_col = 1000 # end of frontage being cleared
            min_col_backoff = 1000 # will be updated if there is a backoff
            max_col_backoff = -1000 # will be updated if there is a backoff
        else:
            # clear a limited width of the ash field as we recover
            min_col = min_col_backoff
            max_col = max_col_backoff

        if line % 2 == 0:
            for col in (1, 0, -1, -2, -3, -4, -5):
                if not clear_corner_cell(4000, 1<<14, col, (-line + 6) // 2, -1, 0, 0, 1):
                    min_col_backoff = min(col - 100, min_col_backoff)
                    max_col_backoff = max(col + 100, max_col_backoff)
                    line -= 160
            for col in (-1, 0, 1, 2, 3, 4, 5):
                if not clear_corner_cell(4000, 1<<14, col, (-line + 6) // 2, 1, 0, 0, 1):
                    min_col_backoff = min(col - 100, min_col_backoff)
                    max_col_backoff = max(col + 100, max_col_backoff)
                    line -= 160
            col = -1000
        else:
            col = -1001

        # clear top left edge along -1/2 slope.
        while col < -7:
            col += 2
            if col < min_col:
                continue

            if not clear_cell(4000, 1<<14, col, (-line - col) // 2, -1, 0, 0, 1):
                min_col_backoff = min(col - 100, min_col_backoff)
                max_col_backoff = max(col + 100, max_col_backoff)
                line -= 160

        if line % 2 == 0:
            col = 1000
        else:
            col = 1001

        # clear top right edge along 1/2 slope
        while col > 7:
            col -= 2
            if col > max_col:
                continue

            if not clear_cell(4000, 1<<14, col, (-line + col) // 2, 1, 0, 0, 1):
                min_col_backoff = min(col - 100, min_col_backoff)
                max_col_backoff = max(col + 100, max_col_backoff)
                line -= 160


init()
run_clear_algo()
And here in a diagonal direction:

Code: Select all


import golly as g

# Copyright Andrew Wade
#
# Feel free to copy and modify.

"""
Proof of concept for ash clearing in Conway's Life.

This is a golly script implementing an algorithm for clearing ash
in Conway's Game of Life using gliders.

Limitations
-----------

* This script deletes stray gliders rather than dealing with them
  in a realistic way. Stray switch engines will cause failure however.

How it Works
------------

The field containing the ash is probed by a skewed raster scan
(slope 1/2). The probe is carefully chosen so that when it interacts
with an ash object it causes minmal disruption to avoid "blow-ups",
and avoids leaving by-products further into ash field where they may
cause future "blow-ups".

Each probe is followed by 9 follow-up volleys. Each follow-up volley does
two things:

1. Deletes an object that would be left behind outside the ash field
   after the probe interacts with one of the top 8 most common ash objects.

2. Returns a signal glider. This indicates that everything is still
   (probably) going okay with the ash clearing.

If the signal glider is not seen, the algorithm assumes that
a "blow-up" has occurred and backs off a large number of rows.
The algorthm receives only one bit of information back from each
volley and needs to be pessimistic when to comes to how many rows
to back-off. As an optimization the back-off is along only a limited
frontage of the ash field.

This script demonstrates that slope 1/2 and 2/1 edges meeting at a corner
can be advanced in a diagonal direction. The corner is rounded slightly
to mitigate against the poor performance of the probe in a corner.

"""

def init():
    """Start a new universe with an ash target.

    Does initial golly setup (algo, etc.) and creates an ash
    field to cleanup.
    """
    g.new("")
    g.setalgo("HashLife")
    g.setbase(2)
    g.setstep(14)
    g.setmag(0)

    g.select([300, -1700, 1400, 1400])
    g.randfill(30)

    g.step()
    g.step()
    g.step()
    g.step()

    # Trim off the outsides of the ash (mostly gliders)
    g.select([0, -10000, 10000, 10000])
    g.clear(1)
    g.select([])

def glider(pos, direction):
    """Returns a cell list for a glider with the given pos and direction

    Parameters
    ----------

    pos:
        The (x,y) position of the glider in units of quarter cells.

    direction:
        The (dx, dy) offset in quarter cells the glider moves each tick.

    Which positions are valid depends on the direction.
    """

    corner = ((pos[0] * direction[0]) // 4, (pos[1] * direction[1]) // 4)
    mod = ((pos[0] * direction[0]) % 4, (pos[1] * direction[1]) % 4)

    if mod == (2,0):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] -2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] -1 ) * direction[1],
            ]
    elif mod == (1, 3):
        return [
            (corner[0] - 1) * direction[0], (corner[1] + 1) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1]
            ]
    elif mod == (0, 2):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1]
            ]
    elif mod == (3, 1):
        return [
            (corner[0] + 1) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1]
            ]
    else:
        raise Exception("Invalid glider location")

def xwss(weight, pos, direction, phase):
    """Returns a cell list for a spaceship

    Parameters
    ----------

    weight:
        0 - lwss, 1 - mwss, 2 - hwss

    pos:
        The (x, y) position of the spaceship in units of quarter cells.

    direction:
        The (dx, dy) offset in quarter cells the glider moves each tick.

    phase:
        The phase of the spaceship.

    Which positions are valid depend on the direction and phase.
    """

    if phase % 2 == 0:
        assert pos[0] % 4 == 2 or pos[1] % 4 == 2
        cells = [(-4, 6), (-4, 10), (0, 2), (0, 6)]
        cells += [(0, 2 + 4 * y) for y in range(3, 5 + weight)]
        cells += [(4, 2 + 4 * y) for y in range(1, 5 + weight)]
        cells += [(8, 2 + 4 * y) for y in range(2, 4 + weight)]
    else:
        assert pos[0] % 4 == 0 and pos[1] % 4 == 0
        cells = [(0,4), (4, 4), (8, 8)]
        cells += [(0, 20 + 4 * weight), (8, 20 + 4 * weight)]
        cells += [(-4, 4 * y) for y in range(1, 5 + weight)]
        cells += [(12, 4 * y) for y in range(4, 4 + weight)]

    if phase % 4 > 1:
        cells = [(-x, y) for (x, y) in cells]

    if direction == (2, 0):
        assert pos[1] % 4 == 0
        cells = [((pos[0] - y) // 4, (pos[1] + x) // 4) for (x, y) in cells]
    elif direction == (0, 2):
        assert pos[0] % 4 == 0
        cells = [((pos[0] - x) // 4, (pos[1] - y) // 4) for (x, y) in cells]
    elif direction == (-2, 0):
        cells = [((pos[0] + y) // 4, (pos[1] - x) // 4) for (x, y) in cells]
    elif direction == (0, -2):
        cells = [((pos[0] + x) // 4, (pos[1] + y) // 4) for (x, y) in cells]
    else:
        raise Exception("Invalid spaceship velocity")

    return [coord for cell in cells for coord in cell]


def write_glider(pos, direction):
    """writes a glider into the universe at the given pos and direction

    Parameters
    ----------

    pos, direction:
        As per the parameters to glider()
    """

    g.putcells(glider(pos, direction))

def write_lwss(pos, direction, phase):
    g.putcells(xwss(0, pos, direction, phase))

def write_mwss(pos, direction, phase):
    g.putcells(xwss(1, pos, direction, phase))

def write_hwss(pos, direction, phase):
    g.putcells(xwss(2, pos, direction, phase))

def read_glider_destructive(pos, direction):
    """If a glider is present, delete it and return true

    Parameters
    ----------

    pos, direction:
        As per the parameters to glider()

    Note: for slightly misaligned/mistimed gliders this function will
    behave differently than realistic life circuitry. We're not expecting
    many misaligned gliders so this shouldn't matter much.
    """
    celllist = glider(pos, direction)
    rv = g.getcell(celllist[0], celllist[1])
    g.putcells(celllist, 0, 0, 1, 0, 0, 1, "not")
    return bool(rv)


def probe_volley(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Set up a probe volley.

    This function does not advance time so that the probe_volley
    can be combined with the first follow-up volley.

    Parameters
    ----------

    delay:
        How far back before interaction to place the gliders (ticks).

    x0, y0:
        The (x0,y0) position being probed.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    x = x0 * 4
    y = y0 * 4
    (dx, dy) = (8, 12 + 2 * delay)
    write_hwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (18 - delay, 24 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (1 - delay, 45 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (11 - delay, 75 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))


def followup_volley(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Fire off a followup volley and return True if the signal glider returns.

    Parameters
    ----------

    delay:
        How far back before the interaction to place the gliders (ticks).

    stepsize:
        How many generations g.step() advances.

    x0, y0:
        The (x0, y0) position being cleaned up. The position of the object
        relative to (x0, y0) will vary with the type of object.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    x = x0 * 4
    y = y0 * 4

    (dx, dy) = (-16, 20 + 2 * delay)
    write_lwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (-5 - delay, 11 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (-22 - delay, 28 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    g.step()

    (dx, dy) = (-18 + delay - stepsize, 36 - delay + stepsize)
    return read_glider_destructive((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))


def clear_cell(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Clears the cell at (x0, y0). returns True if all signal gliders return.

    delay:
        How far back before the interaction to place the gliders (ticks).

    stepsize:
        How many generations g.step() advances.

    x0, y0:
        The (x0, y0) position being cleaned up. The position of the object
        relative to (x0, y0) will vary with the type of object.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    probe_volley(delay, x0, y0, axx, axy, ayx, ayy)

    for (dx, dy, extra_delay) in [
        (5, 12, 100),
        (-1, 9, 0),
        (-6, 0, 0),
        (-1, 4, 1),
        (-3, 2, 1),
        (-4, 1, 0),
        (-2, 0, 0),
        (1, 4, 1),
        (0, 0, 0) ]:
        if not followup_volley(delay + extra_delay,
                               stepsize,
                               x0 + dx * axx + dy * axy,
                               y0 + dx * ayx + dy * ayy,
                               axx, axy, ayx, ayy):
            return False

    return True


def run_clear_algo():
    """Ash clearing algorithm.

    This algorithm is based on clear_cell(), which only interacts with the
    life universe through write_glider(), read_glider_destructive()
    and g.step(), all of which can be implemented with life circuitry.
    (g.step() is just a fixed wait.)

    However this function also cleans up stray gliders in a non-realistic
    way.

    """

    min_diag_backoff = -10
    max_diag_backoff = 10
    ash_front = 1000 # line at which we should start clearing the entire ash front.
    line = 1000 # current line being cleared in units of 1/3 diagonal.

    for i in range(1000000000):
        # Remove stray gliders (this is unrealistic.)
        oldsel = g.getselrect()
        g.select([0, -10000, 10000, 10000])
        g.clear(1)
        g.select(oldsel)

        g.update()

        line += 1
        # if a "blow-up" is detected then the line will be updated in the
        # middle of a pass. The back-off is always a power of three so that
        # the loops continue to function correctly after the update.

        if line >= ash_front:
            # Go back to clearing the entire width of the ash field.
            ash_front = line
            min_diag = -line // 2 # start of frontage being cleared
            max_diag = line // 2 # end of frontage being cleared
            min_diag_backoff = max_diag # will be updated if backoff occurs
            max_diag_backoff = min_diag # will be updated if backoff occurs
        else:
            # clear a limited width of the ash field as we recover
            min_diag = min_diag_backoff
            max_diag = max_diag_backoff

        if line % 3 == 0:
            diag = -3
        elif line % 3 == 1:
            diag = -2
            for (x, y) in [ ((line - 4) // 3, (-line + 1) // 3),
                            ((line - 7) // 3, (-line - 2) // 3)]:
                if not clear_cell(4000, 1<<14, x, y, 1, 0, 0, 1):
                    min_diag_backoff = min(diag - 140, min_diag_backoff)
                    max_diag_backoff = max(diag + 140, max_diag_backoff)
                    line -= 180
        else:
            diag = -1
            if not clear_cell(4000, 1<<14, (line - 5) // 3, (-line - 1) // 3, 1, 0, 0, 1):
                min_diag_backoff = min(diag - 140, min_diag_backoff)
                max_diag_backoff = max(diag + 140, max_diag_backoff)
                line -= 180

        # clear top edge along 1/2 slope.
        while diag > min_diag:
            diag -= 3
            if diag > max_diag:
                continue

            if not clear_cell(4000, 1<<14, (line + 2 * diag) // 3, (-line + diag) // 3, 1, 0, 0, 1):
                min_diag_backoff = min(diag - 140, min_diag_backoff)
                max_diag_backoff = max(diag + 140, max_diag_backoff)
                line -= 180

        if line % 3 == 0:
            diag = 3
        elif line % 3 == 1:
            diag = 2
            for (x, y) in [ ((line - 1) // 3, (-line + 4) // 3),
                            ((line + 2) // 3, (-line + 7) // 3)]:
                if not clear_cell(4000, 1<<14, x, y, 0, -1, -1, 0):
                    min_diag_backoff = min(diag - 140, min_diag_backoff)
                    max_diag_backoff = max(diag + 140, max_diag_backoff)
                    line -= 180
        else:
            diag = 1
            if not clear_cell(4000, 1<<14, (line + 1) // 3, (-line + 5) // 3, 0, -1, -1, 0):
                min_diag_backoff = min(diag - 140, min_diag_backoff)
                max_diag_backoff = max(diag + 140, max_diag_backoff)
                line -= 180

        # clear right edge along -2/1 slope.
        while diag < max_diag:
            diag += 3
            if diag < min_diag:
                continue

            if not clear_cell(4000, 1<<14, (line + diag) // 3, (-line + 2*diag) // 3, 0, -1, -1, 0):
                min_diag_backoff = min(diag - 140, min_diag_backoff)
                max_diag_backoff = max(diag + 140, max_diag_backoff)
                line -= 180

init()
run_clear_algo()

dvgrn wrote:
September 4th, 2021, 1:50 pm
The "another layer or two" might be along the lines of a scattering of blocks that can absorb any incoming stray glider from a failed explosion like the one you showed caused by the toad. The blocks could be torn down and rebuilt whenever the "don't back off" glider fails to return from the cleanup site.
I'm thinking of trying something along these lines next. Probably with just one line of blocks and handwaving that additional layers can be added.

dvgrn wrote:
September 4th, 2021, 1:50 pm
I guess it's just a question of how often really unlucky ash constellations actually show up in real Life. A failure in a replicator every now and then just makes a bunch more random ash for its fellow replicators to clean up.
Switch engines I think should be possible to deal with fairly easily with enough layers of protection. Guns though, that's far more tricky. If a replicator comes up on a gun from the back then there is no problem, but I think the glider stream would probably be kryptonite. I would expect almost all glider streams from a gun that fires long enough to end up terminated on a fishhook, so it sould at least be possible to work around to the back of guns. Something to consider is how to avoid failed replicators turning into guns since a circuit outputting a periodic signal is a gun. But large circuits are fragile so perhaps this wouldn't be a big problem.

A replicator probably wouldn't use volleys they way I'm doing here since they would be quite expensive to launch. Slow salvo techniques near the ash front would probably be more suitable. But I find the volleys easier to use for the proof of concept that clearing ash is possible at all.

A shout-out to Golly and HashLife, without which I wouldn't have been able to test the ash clearing.

Edit: On second thought a glider producing switch engine would be quite awkward to defend against due to the gliders all being in the same lane.
-- Andrew Wade

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Clearing Ash

Post by Macbi » October 31st, 2021, 11:05 am

I think this research is amazing! It's exciting because it has the potential to tell us new things about the far future of the Life universe.

In particular, it suggests that a replicator standing in a large field of ash could clear the area around itself and then build copies of itself into the cleared space. If it then builds some walls of scattered ash between itself and the copies, it will be protected in the case that any of the copies hits something it can't cope with and explodes. In this way, the replicator could spread copies of itself throughout a large area of ash.

If we imagine an infinite grid, initialised randomly to 50% density, then such replicators will occur (very sparsely spaced) in the initial pattern. A small proportion of these will even survive the initial chaos. But then, these replicators will grow to cover the entire grid. So, far from the dead field of ash you would expect from looking at the sizes of soups we can simulate on our computers, the ability to clear ash implies that the eventual future of the Life universe is teeming with life!

The main issue with regards to demonstrating this is whether we can make a cleaning method reliable enough to make space for the copies of the replicator. We don't need a 100% success rate, just enough that each replicator has on average more than one child. The size of a replicator might be comparable to the 0E0P metacell, so we might need to clear on the order of 10^10 cells.

Of course the replicators that would eventually come to dominate the Life universe might be very different from the ones we design ourselves.

User avatar
Wyirm
Posts: 307
Joined: October 29th, 2021, 6:54 pm
Location: 30.541634, 47.825445 (on the boat)

Re: Clearing Ash

Post by Wyirm » October 31st, 2021, 5:04 pm

SO there is an IceNine, Just not one that expands at C/137.

Seriously though, the implications of a replicatory-turing-complete machine that woudl be able to clear debris, synthesize itself and any other pattern necessary, and be able to recognize certain patterns and possibly even be able to recognize itself is truly mind blowing.

Code: Select all

x = 36, y = 28, rule = TripleLife
17.G$17.3G$20.G$19.2G11$9.EF$8.FG.GD$8.DGAGF$10.DGD5$2.2G$3.G30.2G$3G
25.2G5.G$G27.G.G.3G$21.2G7.G.G$21.2G7.2G!
Bow down to the Herschel

mscibing
Posts: 105
Joined: May 18th, 2010, 8:30 pm

Re: Clearing Ash

Post by mscibing » June 18th, 2022, 10:53 pm

I've added some armor to the ash clearing. And it does work fairly well, I'm down to 1-2 stray gliders per 100,000 cells cleared. But it is also horribly slow. Despite the slowness of the current approach I think the evidence is strong that clearing ash at fairly large scales is possible. What I see providing the upper limit to scaling is the appearance of natural glider guns; I have no counter-measures for those.

What I think would work better is replacing the ash not with empty space, but with a field of blocks. If the occasional lane is left clear through the field, the inital probes and follow-up probes could be assembled near to the ash using single-lane construction techniques. I'm not planning on trying anything like this though, and the same scaling limit from natural glider guns would still apply.

Anyway, here is the clearing script with armor:

Code: Select all


import golly as g

# Copyright Andrew Wade
#
# Feel free to copy and modify.

"""
Proof of concept for ash clearing in Conway's Life.

This is a golly script implementing an algorithm for clearing ash
in Conway's Game of Life using gliders and spaceships.

Limitations
-----------

* This script deletes stray gliders rather than dealing with them
  in a realistic way. Stray switch engines will cause failure however.

How it Works
------------

The field containing the ash is probed by a skewed raster scan
(slope 1/2). The probe is carefully chosen so that when it interacts
with an ash object it causes minmal disruption to avoid "blow-ups",
and avoids leaving by-products further into ash field where they may
cause future "blow-ups".

Each probe is followed by 9 follow-up volleys. Each follow-up volley does
two things:

1. Deletes an object that would be left behind outside the ash field
   after the probe interacts with one of the top 8 most common ash objects.

2. Returns a signal glider. This indicates that everything is still
   (probably) going okay with the ash clearing.

If the signal glider is not seen, the algorithm assumes that
a "blow-up" has occurred and backs off a large number of rows.
The algorthm receives only one bit of information back from each
volley and needs to be pessimistic when to comes to how many rows
to back-off. As an optimization the back-off is along only a limited
frontage of the ash field.

This script demonstrates that slope -1/2 and 1/2 edges meeting at a corner
can be advanced in a cardinal direction. The corner is rounded slightly
to mitigate agains the poor performance of the probe in a corner.

The probe and follow-up volleys can be accompanied by barriers composed
of blocks to stop stray gliders and spaceships that could otherwise damage
circuitry used for clearing. However a return lane needs to be left through
the barriers to received the signal glider through. To work around the
problem of stray gliders working their way through the barrier on the signal
glider lane the signal glider is detected with a bitboat: stray gliders on
the same lane will simply toggle the bitboat.
"""

# set to 1 to pause the script as soon as the first follow up volley is set up
DEBUG=0

# 0, 1, or 2
BARRIER=1

def step():
    global DEBUG
    if DEBUG:
        DEBUG -= 1
        if not DEBUG:
            g.update()
            DEBUG = int(g.getstring("Step by (0 is continuous)", "1"))
    g.step()


def init():
    """Start a new universe with an ash target.

    Does initial golly setup (algo, etc.) and creates an ash
    field to cleanup.
    """
    g.new("")
    g.setalgo("HashLife")
    g.setbase(2)
    g.setstep(14)
    g.setmag(0)

    g.select([-700, -1700, 1400, 1550])
    g.randfill(30)

    for i in range(5):
        g.clear(1)
        g.step()

    g.select([])

def glider(pos, direction):
    """Returns a cell list for a glider with the given pos and direction

    Parameters
    ----------

    pos:
        The (x,y) position of the glider in units of quarter cells.

    direction:
        The (dx, dy) offset in quarter cells the glider moves each tick.

    Which positions are valid depends on the direction.
    """

    corner = ((pos[0] * direction[0]) // 4, (pos[1] * direction[1]) // 4)
    mod = ((pos[0] * direction[0]) % 4, (pos[1] * direction[1]) % 4)

    if mod == (2,0):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] -2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] -1 ) * direction[1],
            ]
    elif mod == (1, 3):
        return [
            (corner[0] - 1) * direction[0], (corner[1] + 1) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1]
            ]
    elif mod == (0, 2):
        return [
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1],
            (corner[0] - 2) * direction[0], corner[1] * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1]
            ]
    elif mod == (3, 1):
        return [
            (corner[0] + 1) * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], (corner[1] - 1) * direction[1],
            corner[0] * direction[0], corner[1] * direction[1],
            (corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1],
            (corner[0] - 1) * direction[0], corner[1] * direction[1]
            ]
    else:
        raise Exception("Invalid glider location")

def set_bitboat(pos, direction):
    """Returns a cell list for a bitboat

    Returns a cell list for a set bitboat that would be about to be cleared
    by a glider in the given pos and direction.
    """

    corner = ((pos[0] * direction[0]) // 4, (pos[1] * direction[1]) // 4)
    mod = ((pos[0] * direction[0]) % 4, (pos[1] * direction[1]) % 4)

    if mod == (2,0) or mod == (3,1):
        return [
            (corner[0] + 2) * direction[0], (corner[1] + 2) * direction[1],
            (corner[0] + 3) * direction[0], (corner[1] + 1) * direction[1],
            (corner[0] + 4) * direction[0], (corner[1] + 2) * direction[1],
            (corner[0] + 3) * direction[0], (corner[1] + 3) * direction[1],
            (corner[0] + 4) * direction[0], (corner[1] + 3) * direction[1],
            (corner[0] + 3) * direction[0], (corner[1] + 5) * direction[1],
            (corner[0] + 4) * direction[0], (corner[1] + 5) * direction[1],
            (corner[0] + 4) * direction[0], (corner[1] + 6) * direction[1],
            (corner[0] + 3) * direction[0], (corner[1] + 7) * direction[1],
            (corner[0] + 3) * direction[0], (corner[1] + 8) * direction[1],
            (corner[0] + 4) * direction[0], (corner[1] + 8) * direction[1],
            ]
    elif mod == (0,2) or mod == (1,3):
        return [
            (corner[0] + 1) * direction[0], (corner[1] + 3) * direction[1],
            (corner[0] + 2) * direction[0], (corner[1] + 2) * direction[1],
            (corner[0] + 3) * direction[0], (corner[1] + 3) * direction[1],
            (corner[0] + 2) * direction[0], (corner[1] + 4) * direction[1],
            (corner[0] + 3) * direction[0], (corner[1] + 4) * direction[1],
            (corner[0] + 5) * direction[0], (corner[1] + 3) * direction[1],
            (corner[0] + 5) * direction[0], (corner[1] + 4) * direction[1],
            (corner[0] + 6) * direction[0], (corner[1] + 4) * direction[1],
            (corner[0] + 7) * direction[0], (corner[1] + 3) * direction[1],
            (corner[0] + 8) * direction[0], (corner[1] + 3) * direction[1],
            (corner[0] + 8) * direction[0], (corner[1] + 4) * direction[1],
            ]
    else:
        raise Exception("Invalid glider location")

def xwss(weight, pos, direction, phase):
    """Returns a cell list for a spaceship

    Parameters
    ----------

    weight:
        0 - lwss, 1 - mwss, 2 - hwss

    pos:
        The (x, y) position of the spaceship in units of quarter cells.

    direction:
        The (dx, dy) offset in quarter cells the glider moves each tick.

    phase:
        The phase of the spaceship.

    Which positions are valid depend on the direction and phase.
    """

    if phase % 2 == 0:
        assert pos[0] % 4 == 2 or pos[1] % 4 == 2
        cells = [(-4, 6), (-4, 10), (0, 2), (0, 6)]
        cells += [(0, 2 + 4 * y) for y in range(3, 5 + weight)]
        cells += [(4, 2 + 4 * y) for y in range(1, 5 + weight)]
        cells += [(8, 2 + 4 * y) for y in range(2, 4 + weight)]
    else:
        assert pos[0] % 4 == 0 and pos[1] % 4 == 0
        cells = [(0,4), (4, 4), (8, 8)]
        cells += [(0, 20 + 4 * weight), (8, 20 + 4 * weight)]
        cells += [(-4, 4 * y) for y in range(1, 5 + weight)]
        cells += [(12, 4 * y) for y in range(4, 4 + weight)]

    if phase % 4 > 1:
        cells = [(-x, y) for (x, y) in cells]

    if direction == (2, 0):
        assert pos[1] % 4 == 0
        cells = [((pos[0] - y) // 4, (pos[1] + x) // 4) for (x, y) in cells]
    elif direction == (0, 2):
        assert pos[0] % 4 == 0
        cells = [((pos[0] - x) // 4, (pos[1] - y) // 4) for (x, y) in cells]
    elif direction == (-2, 0):
        cells = [((pos[0] + y) // 4, (pos[1] - x) // 4) for (x, y) in cells]
    elif direction == (0, -2):
        cells = [((pos[0] + x) // 4, (pos[1] + y) // 4) for (x, y) in cells]
    else:
        raise Exception("Invalid spaceship velocity")

    return [coord for cell in cells for coord in cell]


def write_glider(pos, direction):
    """writes a glider into the universe at the given pos and direction

    Parameters
    ----------

    pos, direction:
        As per the parameters to glider()
    """

    g.putcells(glider(pos, direction))

def write_lwss(pos, direction, phase):
    g.putcells(xwss(0, pos, direction, phase))

def write_mwss(pos, direction, phase):
    g.putcells(xwss(1, pos, direction, phase))

def write_hwss(pos, direction, phase):
    g.putcells(xwss(2, pos, direction, phase))

def write_set_bitboat(pos, direction):
    g.putcells(set_bitboat(pos, direction))

def read_bitboat(pos, direction):
    celllist = set_bitboat(pos, direction)
    # first part of the celllist is the boat
    return bool(g.getcell(celllist[0], celllist[1]))

def delete_bitboat(pos, direction):
    """Delete bitboat whether set or cleared"""
    g.putcells(set_bitboat(pos, direction), 0, 0, 1, 0, 0, 1, "not")


def inject_mwss(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Set up a volley to create a perpendicularly travelling mwss.

    Parameters
    ----------

    x0, y0:
        The position of the created mwss in units of cells.
    """

    x = x0 * 4
    y = y0 * 4
    (dx, dy) = (-16, -20 + 2 * delay)
    write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (-8 - delay, -22 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (-20 - delay, -6 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (-27 - delay, 13 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))


def add_horizontal_barrier(delay, x0, y0, signal_lane, blocks, axx=1, axy=0, ayx=0, ayy=1):
    """Set up a volley to create a horizonal barrier.

    Parameters
    ----------

    x0, y0:
        The corner where the created mwss will be created in units of cells.

    signal_lane:
        How far from x0, y0 to create the beehive that will return
        a signal glider when the barrier is later destroyed. In units of cells.

    blocks:
        A list of distances from x0, y0 to create blocks for the barrier
        Must be even numbers >= 4. In units of cells.
    """

    inject_mwss(delay, x0, y0, axx, axy, ayx, ayy)

    x = x0 * 4
    y = y0 * 4
    (dx, dy) = (-3 - delay + 2*signal_lane, 37 + delay + 2*signal_lane)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

    (dx, dy) = (19 - delay + 2*signal_lane, 71 + delay + 2*signal_lane)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

    (dx, dy) = (-11 - delay + 2*signal_lane, 85 + delay + 2*signal_lane)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

    for block in blocks:
        (dx, dy) = (-12 - delay + 2*block, 30 + delay + 2*block)
        write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                     (axx - axy, ayx - ayy))

def add_vertical_barrier(delay, x0, y0, blocks, axx=1, axy=0, ayx=0, ayy=1):
    """Set up a volley to create a vertical barrier.

    This is simpler than add_horizontal_barrier as a mwss in the volley
    can be used directly rather than needing to construct a mwss.

    Parameters
    ----------

    x0, y0:
        Where tp create the beehive that will return a signal glider when the
        barrier is later destroyed. In units of cells.

    blocks:
        A list of distances from x0, y0 to create blocks for the barrier.
        Must be ven numbers. In units of cells.
    """

    x = x0 * 4
    y = y0 * 4
    write_mwss((x + 2 * delay * axy, y + 2 * delay * ayy),
               (-2 * axy, -2 *ayy), axx * ayy - axy * ayx - delay)

    (dx, dy) = (-37 - delay, 3 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

    (dx, dy) = (-71 - delay, -19 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

    (dx, dy) = (-85 - delay, 11 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

    for block in blocks:
        (dx, dy) = (-30 - delay + 2*block, 12 + delay + 2*block)
        write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                     (axx - axy, ayx - ayy))



def probe_volley(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Set up a probe volley.

    This function does not advance time so that the probe_volley
    can be combined with the first follow-up volley.

    Parameters
    ----------

    delay:
        How far back before interaction to place the gliders (ticks).

    x0, y0:
        The (x0,y0) position being probed.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    x = x0 * 4
    y = y0 * 4
    (dx, dy) = (8, 12 + 2 * delay)
    write_hwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (18 - delay, 24 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (1 - delay, 45 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (11 - delay, 75 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

def corner_probe_volley(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Set up a corner probe volley.

    This function does not advance time so that the corner probe volley
    can be combined with the first follow-up volley.

    This probe is less likely to blow up in a corner but will fail to
    clear blinkers/some still lives and will need follow up probes.

    Parameters
    ----------

    delay:
        How far back before interaction to place the gliders (ticks).

    x0, y0:
        The (x0,y0) position being probed.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    x = x0 * 4
    y = y0 * 4
    (dx, dy) = (-4, 16 + 2 * delay)
    write_lwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (9 - delay, 21 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (9 - delay, 45 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (7 - delay, 75 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))


def followup_volley(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
    """Fire off a followup volley and return True if the signal glider returns.

    Depending on the global BARRIER this function may also create barriers.
    For BARRIER=1 only one horizontal barrier will be created.
    True will be returned if and only if the barriers have also been
    successfully cleaned up.

    Parameters
    ----------

    delay:
        How far back before the interaction to place the gliders (ticks).

    stepsize:
        How many generations g.step() advances.

    x0, y0:
        The (x0, y0) position being cleaned up. The position of the object
        relative to (x0, y0) will vary with the type of object.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    x = x0 * 4
    y = y0 * 4

    if abs(x0) > 390:
        adj = 0
    elif abs(x0) > 360:
        adj = (390 - abs(x0)) // 2
    elif abs(x0) > 10:
        adj = 374 - abs(x0)
    else:
        adj = 374

    (dx, dy) = (-16, 20 + 2 * delay)
    write_lwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
               (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
    (dx, dy) = (-5 - delay, 11 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))
    (dx, dy) = (-22 - delay, 28 + delay)
    write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                 (axx - axy, ayx - ayy))

    (dx, dy) = (-18 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
    bitboat1 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))

    (dx, dy) = (2014 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
    bitboat2 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))

    (dx, dy) = (2090 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
    bitboat3 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))

    (dx, dy) = (3038 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
    bitboat4 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))

    (dx, dy) = (3114 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
    bitboat5 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))

    (dx, dy) = (-2234 + 2000 + delay - stepsize + 4 * adj, 36 - 2000 - delay + stepsize)
    bitboat6 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))

    (dx, dy) = (-2158 + 2000 + delay - stepsize + 4 * adj, 36 - 2000 - delay + stepsize)
    bitboat7 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                                   (axy - axx, ayy - ayx))


    write_set_bitboat(*bitboat1)
    if BARRIER > 0:
        write_set_bitboat(*bitboat2)
        write_set_bitboat(*bitboat3)

        (dx, dy) = (-350, 186)
        add_horizontal_barrier(delay-1025,
                    x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 680,
                    list(range(28, 168, 28)) +
                    # gap for signal glider
                    list(range(172, 648, 28)),
                    axx, axy, ayx, ayy)

        (dx, dy) = (-350, 215)
        add_horizontal_barrier(delay-1017,
                    x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 680 - 48,
                    list(range(18, 158, 28)) +
                    # gap for signal glider
                    list(range(162, 638, 28)),
                    axx, axy, ayx, ayy)

        (dx, dy) = (-350, 244)
        add_horizontal_barrier(delay-1009,
                    x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 680 - 58,
                    list(range(8, 120, 28)) +
                    # gap for signal glider
                    list(range(124, 628, 28)),
                    axx, axy, ayx, ayy)


    if BARRIER > 1:
        write_set_bitboat(*bitboat4)
        write_set_bitboat(*bitboat5)
        write_set_bitboat(*bitboat6)
        write_set_bitboat(*bitboat7)
        (dx, dy) = (-350, 274)
        add_horizontal_barrier(delay-1001,
                    x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 848,
                    list(range(24, 80, 28)) +
                    # gap for signal glider
                    list(range(84, 588, 28)) +
                    # two non-consecutive lanes will be left open here
                    # to allow signal gliders from the clean up of inner
                    # barriers to return.
                    list(range(592, 816, 28)),
                    axx, axy, ayx, ayy)


        (dx, dy) = (-350, 303)
        add_horizontal_barrier(delay-993,
                    x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 848 - 48,
                    list(range(14, 70, 28)) +
                    # gap for signal glider
                    list(range(74, 578, 28)) +
                    # two non-consecutive lanes will be left open here
                    # to allow signal gliders from the clean up of inner
                    # barriers to return.
                    list(range(582, 806, 28)),
                    axx, axy, ayx, ayy)

        (dx, dy) = (-350, 332)
        add_horizontal_barrier(delay-985,
                    x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 848 - 58,
                    list(range(4, 32, 28)) +
                    # gap for signal glider
                    list(range(36, 568, 28)) +
                    # two non-consecutive lanes will be left open here
                    # to allow signal gliders from the clean up of inner
                    # barriers to return.
                    list(range(572, 796, 28)),
                    axx, axy, ayx, ayy)

        (dx, dy) = (-376, -158 + adj)
        add_vertical_barrier(delay - 2*adj + 10,
                x0 + dx * axx + dy * axy, y0 + dx *ayx + dy * ayy,
                list(range(60, 500 - adj, 28)),
                axx, axy, ayx, ayy)

        (dx, dy) = (-405, -158 + 48 + adj)
        add_vertical_barrier(delay - 2*adj - 2*48 + 18,
                x0 + dx * axx + dy * axy, y0 + dx *ayx + dy * ayy,
                list(range(22, 500 - 48 - adj, 28)),
                axx, axy, ayx, ayy)

        (dx, dy) = (-434, -158 + 58 + adj)
        add_vertical_barrier(delay - 2*adj - 2*58 + 26,
                x0 + dx * axx + dy * axy, y0 + dx *ayx + dy * ayy,
                list(range(22, 500 - 58 - adj, 28)),
                axx, axy, ayx, ayy)


    step()

    rv = not read_bitboat(*bitboat1)

    if rv and BARRIER > 1:
        # row #9 needs to be remove first because it blocks rows #1-7
        (dx, dy) = ((-432) *4, (-157 + 58 + adj) * 4 + 2*delay)
        write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                   (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
        step()
        rv = not read_bitboat(*bitboat6)

    if rv and BARRIER > 1:
        # remove row #7
        (dx, dy) = ((-374) *4, (-157 + adj) * 4 + 2*delay)
        write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                   (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
        step()
        rv = read_bitboat(*bitboat6)

    if rv and BARRIER > 1:
        # remove row #8
        (dx, dy) = ((-403) *4, (-157 + 48 + adj) * 4 + 2*delay)
        write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
                   (-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
        step()
        rv = not read_bitboat(*bitboat7)

    if rv and BARRIER > 0:
        # row #3 needs to be removed before row #1 because the return glider is on the
        # same lane
        (dx, dy) = (-349, 242)
        inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
                    axx, axy, ayx, ayy)
        step()
        rv = not read_bitboat(*bitboat3)

    if rv and BARRIER > 0:
        # row #1
        (dx, dy) = (-349, 184)
        inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
                    axx, axy, ayx, ayy)
        step()
        rv = read_bitboat(*bitboat3)

    if rv and BARRIER > 0:
        # row #2
        (dx, dy) = (-349, 213)
        inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
                    axx, axy, ayx, ayy)
        step()
        rv = not read_bitboat(*bitboat2)

    if rv and BARRIER > 1:
        # row #6 needs to be removed before row #4 because the return glider is on the
        # same lane
        (dx, dy) = (-349, 330)
        inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
                    axx, axy, ayx, ayy)
        step()
        rv = not read_bitboat(*bitboat5)

    if rv and BARRIER > 1:
        # row #4
        (dx, dy) = (-349, 272)
        inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
                    axx, axy, ayx, ayy)
        step()
        rv = read_bitboat(*bitboat5)

    if rv and BARRIER > 1:
        # row #5
        (dx, dy) = (-349, 301)
        inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
                    axx, axy, ayx, ayy)
        step()
        rv = not read_bitboat(*bitboat4)

    delete_bitboat(*bitboat1)
    if BARRIER > 0:
        delete_bitboat(*bitboat2)
        delete_bitboat(*bitboat3)
    if BARRIER > 1:
        delete_bitboat(*bitboat4)
        delete_bitboat(*bitboat5)
        delete_bitboat(*bitboat6)
        delete_bitboat(*bitboat7)

    return rv


def clear_cell(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1, variant=None):
    """Clears the cell at (x0, y0). returns True if all signal gliders return.

    delay:
        How far back before the interaction to place the gliders (ticks).

    stepsize:
        How many generations g.step() advances.

    x0, y0:
        The (x0, y0) position being cleaned up. The position of the object
        relative to (x0, y0) will vary with the type of object.

    axx, axy, ayx, ayy:
        Same as transform() from golly.
    """

    if not variant:
        probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
        followup_volleys = [
            (5, 12, 100),
            (-1, 9, 0),
            (-6, 0, 0),
            (-1, 4, 1),
            (-3, 2, 1),
            (-4, 1, 0),
            (-2, 0, 0),
            (1, 4, 1),
            (0, 0, 0) ]
    elif variant == "corner1":
        corner_probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
        followup_volleys = [
            (-3, 17, 100),
            (-6, 9, 0),
            (2, 8, 0),
            (-2, 6, 0),
            (0, 8, 0),
            (1, 5, 0),
            (-2, 5, 0),
            (-4, 5, 0),
            (-6, 5, 0),
            (1, 5, 0),
            (4, 12, 0),
            (5, 4, 0),
            (5, 3, 0),
            (5, 3, 0),
            (-1, 4, 0),
            (2, 1, 0)
            ]

    elif variant == "corner2":
        probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
        followup_volleys = [
            (5, 12, 100),
            (-1, 9, 0),
            #(-6, 0, 0),
            (-1, 4, 1),
            (-3, 2, 1),
            (-4, 1, 0),
            #(-2, 0, 0),
            (1, 4, 1),
            (0, 0, 0) ]
    elif variant == "corner3":
        probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
        followup_volleys = [
            (5, 12, 100),
            (-1, 9, 0),
            #(-6, 0, 0),
            (-1, 4, 1),
            (-3, 2, 1),
            (-4, 1, 0),
            (-2, 0, 0),
            (1, 4, 1),
            (0, 0, 0) ]

    for (dx, dy, extra_delay) in followup_volleys:
        if not followup_volley(delay + extra_delay,
                               stepsize,
                               x0 + dx * axx + dy * axy,
                               y0 + dx * ayx + dy * ayy,
                               axx, axy, ayx, ayy):
            return False



    return True


def run_clear_algo():
    """Ash clearing algorithm.

    This algorithm is based on clear_cell(), which only interacts with the
    life universe through write_glider(), read_glider_destructive()
    and g.step(), all of which can be implemented with life circuitry.
    (g.step() is just a fixed wait.)

    However this function also cleans up stray gliders in a non-realistic
    way.

    """

    ash_front = 310 # line at which we should start clearing the entire ash front.
    line = 300 # current line being cleared in units of 1/2 cell.
    max_backoff_row = -100
    min_col_backoff = -100
    max_col_backoff = 100

    backoff = 1500

    if BARRIER > 1:
        backoff_by_rows = 350
        backoff_cols = 520
    else:
        backoff_by_rows = 280
        backoff_cols = 355

    for i in range(1000000000):

        g.update()

        line += 1
        # if a "blow-up" is detected then the line will be updated in the
        # middle of a pass. The back-off is always a power of two so that
        # the loops continue to function correctly after the update.

        if line >= ash_front:
            # Go back to clearing the entire width of the ash field.
            g.show("")
            ash_front = line
            min_col = -1000 # start of frontage being cleared
            max_col = 1000 # end of frontage being cleared
            max_row = max(max_row -1, 0)
            max_backoff_row = -1000000000
            min_col_backoff = 1000 # will be updated if there is a backoff
            max_col_backoff = -1000 # will be updated if there is a backoff
        else:
            # clear a limited width of the ash field as we recover
            max_row = max_backoff_row
            min_col = min_col_backoff
            max_col = max_col_backoff

        if line % 2 == 0 and (-line + 6) // 2 <= max_row:
            for (col, axx, variant) in [
                (0, -1, "corner1"),
                (0, -1, "corner1"),
                (-1, -1, "corner2"),
                (-2, -1, "corner2"),
                (-3, -1, "corner3"),
                (-4, -1, "corner3"),
                (-5, -1, "corner3"),
                (0, 1, "corner3"),
                (1, 1, "corner3"),
                (2, 1, "corner3"),
                (3, 1, "corner3"),
                (4, 1, "corner3"),
                (5, 1, "corner3")]:

                if not clear_cell(4000, 1<<14, col, (-line + 6) // 2, axx, 0, 0, 1, variant):
                    g.show(variant + " backoff axx=" +str(axx) + " X=" + str(col))
                    max_backoff_row = max(max_backoff_row, ((-line + 6) // 2) + backoff_by_rows)
                    min_col_backoff = min(col - backoff_cols, min_col_backoff)
                    max_col_backoff = max(col + backoff_cols, max_col_backoff)
                    line -= backoff
            col = -2000
        else:
            col = -2001

        # clear top left edge along -1/2 slope.
        while col < -7:
            col += 2
            if col < min_col or (-line - col) // 2 > max_row:
                continue

            if not clear_cell(4000, 1<<14, col, (-line - col) // 2, -1, 0, 0, 1):
                g.show("backoff X=" + str(col))
                max_backoff_row = max(max_backoff_row, ((-line - col) // 2) + backoff_by_rows)
                min_col_backoff = min(col - backoff_cols, min_col_backoff)
                max_col_backoff = max(col + backoff_cols, max_col_backoff)
                line -= backoff

        if line % 2 == 0:
            col = 2000
        else:
            col = 2001

        # clear top right edge along 1/2 slope
        while col > 7:
            col -= 2
            if col > max_col or (-line + col) // 2 > max_row:
                continue

            if not clear_cell(4000, 1<<14, col, (-line + col) // 2, 1, 0, 0, 1):
                g.show("backoff X=" + str(col))
                max_backoff_row = max(max_backoff_row, ((-line + col) // 2) + backoff_by_rows)
                min_col_backoff = min(col - backoff_cols, min_col_backoff)
                max_col_backoff = max(col + backoff_cols, max_col_backoff)
                line -= backoff


init()
run_clear_algo()

edit: BARRIER=2 enhancements.
Last edited by mscibing on June 20th, 2022, 11:11 am, edited 1 time in total.
-- Andrew Wade

Ch91
Posts: 49
Joined: April 26th, 2019, 8:05 pm

Re: Clearing Ash

Post by Ch91 » June 19th, 2022, 11:38 pm

Why blocks specifically? Wouldn't eater 1s be more reliable in stopping gliders?

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

Re: Clearing Ash

Post by dvgrn » June 20th, 2022, 7:12 am

Ch91 wrote:
June 19th, 2022, 11:38 pm
Why blocks specifically? Wouldn't eater 1s be more reliable in stopping gliders?
Blocks are pretty much unique in B3/S23 as glider stoppers. As long as they're expendable -- i.e., it's okay to use them up -- they're much more reliable than eaters.

They mutually annihilate gliders on a lot of lanes (the six adjacent lanes in the middle) and the other possible lanes get you pi explosions, honeyfarms, and (2,1) block moves -- none of which release any gliders, as long as there's enough space around the block.

An eater can cleanly eat an unlimited number of gliders on one particular lane, and it's cleanly destroyed by gliders on a few other lanes. But some of the other lanes cause so much trouble that it more than makes up for the "good" lanes.

Code: Select all

x = 12, y = 14, rule = B3/S23
11bo$9b3o$8bo$8b2o8$3o$2bo$bo!
Eater2s are actually pretty good as glider absorbers, with clean absorbtion on four adjacent lanes and mostly just a harmless collapse otherwise. But there are a couple of mildly annoying cases:

Code: Select all

x = 14, y = 17, rule = B3/S23
9bo$8bobo$8bobo$7b2ob3o$13bo$7b2ob3o$7b2obo8$3o$2bo$bo!

Code: Select all

x = 7, y = 16, rule = B3/S23
2bo$bobo$bobo$2ob3o$6bo$2ob3o$2obo7$3o$2bo$bo!
I guess they're not show-stoppers, exactly, since the output glider is pointed away from the area that's being protected. But we have to scatter these things over a wide area, and the second glider is offset way to the side and might hit other eater2s from behind.

Long story short, blocks are way way easier to build, and they absorb gliders better with no weird edge cases to worry about. There's not much reason to use anything else.

mscibing
Posts: 105
Joined: May 18th, 2010, 8:30 pm

Re: Clearing Ash

Post by mscibing » June 20th, 2022, 5:57 pm

dvgrn wrote:
June 20th, 2022, 7:12 am
They mutually annihilate gliders on a lot of lanes (the six adjacent lanes in the middle) and the other possible lanes get you pi explosions, honeyfarms, and (2,1) block moves -- none of which release any gliders, as long as there's enough space around the block.
In addition the results of pi explosions, honeyfarms, and (2,1) block moves can all be cleaned up by the generic ash clearing routine -- as well as the untouched blocks. After a blow-up it is very convenient to hand off the task of cleaning up the barrier to the generic ash clearing routine, although this admittedly also results in a very slow algorithm. I had an earlier design where the ash clearing routine could clean up an untouched barrier no problem, but cleaning up a barrier that had been hit by a glider would cause subsequent blow-ups a little too often. The ash clearing is quite marginal and it doesn't take much to push it into the red.

I'll add a couple of additional considerations. The probe and follow-up volleys use a lot of lanes and it is good to be able to throw up a barrier behind them quickly. Blocks are very easy to construct. I use this reaction:

Code: Select all

x = 80, y = 40, rule = B3/S23
.5A$A4.A$5.A$A3.A$2.A4$.2A$A.A$2.A12$15.2A$14.A.A$16.A12$29.2A$28.A.A
$30.A!
The other thing any barrier design needs to contend with is some mechanism to get the signal glider back across the barrier. With the block barrier I did this by providing one clear glider lane back.

The downsides of blocks are that pi explosions are awkwardly large, and that blocks are consumed when they block gliders. Defense in depth will help with the latter, but as soon as a glider gun shows up it is going to be game over.
-- Andrew Wade

AlbertArmStain
Posts: 1219
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Clearing Ash

Post by AlbertArmStain » September 23rd, 2022, 12:32 pm

Dusting this thread off, here's some reactions I found that might not be useful:

Code: Select all

x = 451, y = 257, rule = B3/S23
448bobo$448b2o$449bo4$431bobo$431b2o$432bo4$414bobo$414b2o$415bo4$397b
obo$397b2o$398bo4$380bobo$380b2o$381bo4$357bo$355b2o$356b2o4$340bo$338b
2o$339b2o4$323bo$321b2o$322b2o4$306bo$304b2o$305b2o4$289bo$287b2o$288b
2o4$266bo$265bo$265b3o4$249bo$248bo$248b3o4$232bo$231bo$231b3o4$215bo
$214bo$214b3o4$198bo$197bo$197b3o3$179bo$179bobo$179b2o4$162bo$162bob
o$162b2o4$145bo$145bobo$145b2o4$128bo$128bobo$128b2o4$111bo$111bobo$111b
2o4$107bo2bo$111bo$107bo3bo$108b4o2$101b4o$100bo3bo$104bo$82bo2bo14bo
2bo$86bo$82bo3bo$83b4o2$76b4o$75bo3bo$79bo$57bo2bo14bo2bo$61bo$57bo3b
o$58b4o2$51b4o$50bo3bo$54bo$32bo2bo14bo2bo$36bo$32bo3bo$33b4o2$26b4o$
25bo3bo$29bo$7bo2bo14bo2bo$11bo$7bo3bo$8b4o2$b4o$o3bo$4bo$o2bo2$36bo$
37bo$35b3o2$33bo$34bo$32b3o2$30bo$31bo$29b3o2$27bo$28bo$26b3o2$24bo$25b
o$23b3o4$24bo2bo$28bo$24bo3bo$25b4o2$18bo2bo$22bo$18bo3bo$19b4o2$12bo
2bo$16bo$12bo3bo$13b4o2$6bo2bo$10bo$6bo3bo$7b4o2$o2bo$4bo$o3bo$b4o14$
107bo15bo$106bo15bo$106b3o13b3o4$102bo14bo$101bo14bo$101b3o12b3o3$104b
2o13b2o$104b2o13b2o3$99b2o13b2o$99b2o13b2o3$94b2o13b2o$94b2o13b2o3$89b
2o13b2o$89b2o13b2o3$84b2o13b2o$84b2o13b2o3$79b2o13b2o$79b2o13b2o3$74b
2o13b2o$74b2o13b2o!

Post Reply