## Enumerating Still Lifes (in C)

For scripts to aid with computation or simulation in cellular automata.
Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Nathaniel wrote:- The first cell no longer goes across the first half of the first row, but only goes across the first ceil((n+1)/4) cells in the first row. This bound definitely can't be lowered, and I'm quite sure that you don't miss any still lifes this way (though if someone is uncomfortable with this, I'm always up for a discussion).

Code: Select all

``````..O.....
.O......
O...O...
.O.O....
..O.....
........
........
``````
7 cells, 12/-. And I don't see how you could make the first cell fit in the first two spaces.

[edit:] incidentally, you could also trivially reduce bounding box if you have B2, as that also stops lines from being drawn easily.
Vi veri veniversum vivus vici.

Nathaniel
Posts: 614
Joined: December 10th, 2008, 3:48 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Elithrion wrote:
Nathaniel wrote:- The first cell no longer goes across the first half of the first row, but only goes across the first ceil((n+1)/4) cells in the first row. This bound definitely can't be lowered, and I'm quite sure that you don't miss any still lifes this way (though if someone is uncomfortable with this, I'm always up for a discussion).

Code: Select all

``````..O.....
.O......
O...O...
.O.O....
..O.....
........
........
``````
7 cells, 12/-. And I don't see how you could make the first cell fit in the first two spaces.
Hrm, you'd think I'd have noticed something like that. Alright, how about ceil((n+2)/3) if 1 is in the survival list, and ceil((n+1)/4) otherwise?

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Nathaniel wrote:Hrm, you'd think I'd have noticed something like that. Alright, how about ceil((n+2)/3) if 1 is in the survival list, and ceil((n+1)/4) otherwise?
I don't think so. I'm pretty sure /4 is not tenable while we have S2. I'm too lazy to draw it out, but make the same shape with 19 cells: first a south-west diagonal of 6 cells, south-east 5 cells, north-east 5 cells. That's 16 used up, add another two to the ends, thus needing S23, and throw the last cell anywhere you want.

Also, is the +2 really necessary? I'd guess ceil(n/3) will always be enough.
Vi veri veniversum vivus vici.

Nathaniel
Posts: 614
Joined: December 10th, 2008, 3:48 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Elithrion wrote:
Nathaniel wrote:Hrm, you'd think I'd have noticed something like that. Alright, how about ceil((n+2)/3) if 1 is in the survival list, and ceil((n+1)/4) otherwise?
I don't think so. I'm pretty sure /4 is not tenable while we have S2. I'm too lazy to draw it out, but make the same shape with 19 cells: first a south-west diagonal of 6 cells, south-east 5 cells, north-east 5 cells. That's 16 used up, add another two to the ends, thus needing S23, and throw the last cell anywhere you want.

Also, is the +2 really necessary? I'd guess ceil(n/3) will always be enough.
Again you're quite right. And as for why I put +2 there: I forgot I had the ceiling function around it I'll update the script now to use n/3 instead of (n+1)/4.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Hmm... to be fair, I think your last statement would only fail for 15, and then maybe for 18-19, and then 21+ (not anything lower anyway), and then only under some specific conditions and in a limited way. From a practical point of view, since the program only goes up to 16, something like that might be better. Hmm... 1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6 vs 1,1,1,2,2,2,2,3,3,3,3,4,4,4,"4",5. So it makes 7,10,11,13,14, and 16 cells better off.

[edit:] also, to be perfectly honest, what we're really interested in is 9 and 10, right? I expect if we explicitly focus on that, some stronger conditional statements can be made.
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Okay, a few things.

1. Please find attached a list of the first 10000 nine-cell still lifes in 2x2. It might actually be comprehensive as the last one appears to have the first cell in position 4, something that we agreed would produce a duplicate and which really should not happen:

Code: Select all

``````...O..
OO..O.
O.....
..O...
...O..
......
.....O
....O.
``````
Took a little under 4h, by the way.

1.b. The 000100 -> 001000 = reject rule should ideally be applied to the actual width of a pattern, as the above one is clearly a mirror of

Code: Select all

``````..O...
.O..OO
.....O
...O..
..O...
......
O.....
.O....
``````

2. The single biggest improvement in speed for me might just be a full usage of my processor's second core. Right now it seems one stays at a steady 95-100% usage throughout the search, while the other idles at 10-30%.

3. That nice giant list needs automatic island killing. Here's the algorithm I have in mind in pseudo-pseudo-code:

Code: Select all

``````int changed = 1
char list1[appropriate dimensions], list2[appropriate dimensions], list3[list1's dimensions]
read file with questionable still lifes into list1 (make sure to have a shell of empty cells around the living ones)
list3 = list1
read file with smaller still lifes into list2 (make sure to have a shell of empty cells around the living ones)
create rotations/reflections of all still lifes in list2 and add them to list2
for (i = 1;i<=size(list1);++i) {
changed = 1
while (changed = 1) {
for (j=1;j<=size(list2);++j) {
if (list2[j] matches list3[i]) { /* that is, if there is an island that is exactly equal to some still life - just a simple cell for cell match */
list3[i] = list3[i] - list2[j] /* kill the island */
and then fix up list3[i] so that there's again 1 dead cell between live cells and outer edges
break;                               }
else if (j = size(list2)) {changed = 0}
}
if (list3[i] = blank) {list1[i] = blank}
}
}
print list1 to file
``````
Yeah! Well, I hope that makes sense anyway - seems simple enough to do.

4. I've been thinking about an alternative search algorithm. I call it the stability-seeking algorithm. First some quick definitions. "The cells being considered" are all the cells that might change state (so living + a shell of dead). The cells around cell i are i(0), i(1), ..., i(7), similar for cells ii, iii, iv, etc. Those numerals will denote the living cells and I'll just call the considered dead ones d1, d2, etc. n(i) is the number of living neighbours of i. For the example the rule is ab/cd and we have x cells. Oh, and I deliberately avoid obvious speed-ups to make the sketch of the idea clearer.
So, then, take cell i, place it in the middle of your array. Now if n(i)<a, place a cell in i(0). If n(i) is still less than a, place cell in i(1). Repeat until n(i) = a. Now, go to ii (if it's placed obviously). If n(ii)<a, place cell in ii(0) (or lowest empty number), but never in i(0), i(1), etc (in fact we're never placing a cell in a previously considered cell's neighbourhood; if you absolutely must do it, you have failed - move on). Once that's done, proceed to iii. If n(iii)<a, do the same as above. If n(iii) = a or n(iii) = b, move on to iv. If n(iii) > b, you have failed, go back to ii, find the last cell you've placed for it and move it over by one, then retry iii. So, let's say you've successfully made all the living cells stable like that. If you used up all x cells, check all the considered dead cells. If none want to come to life, success! Record it and move on (moving on to be explained shortly). If some want to come to life, you have failed - move on. If you did not use up all x cells, also check all the considered dead cells. However, now if you have no dead cells that want to come to life, you have failed (need I say "move on"?). If some do want to come to life (let's say d4 does), and if n(d4) <= d (if not, you failed), stick a cell in d4(0) (or first permitted number). From here repeat the process as before until success or failure. Once you do achieve one or the other, go back to the last cell placed and move it over to the next legal position. If you've exhausted all the legal positions that help meet rule a (or c), add an extra cell or two (when you have one to add obviously) to try to meet b (or d). Repeat until all possibilities are exhausted.

I hope that's clear. It's sort of a random-walk-inspired approach Anyway, I'm not so sure you're in the mood for coding a complicated algorithm, but if you are, it should be orders of magnitude faster. Something like O(7^n) at worst for stability-seeking instead of O((n^2)! / ((n^2 - n)! n!)) for brute force? (again a total guess) Advantages phrased in words include: front-loading the S/B checks for most of the efficiency gains; absolutely no problems with pseudo still lifes; a bare minimum of problems with reflections/rotations and none with displacements (most are eliminated by restricting cell ii to two positions). So, yeah, if it works, it's pretty good!
Attachments
2x2-9c.rar
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Hmm... okay, so the above list is presumably not complete, but here's one for nine-cell maze (18196 figures).
Attachments
maze-9c.rar
Vi veri veniversum vivus vici.

Nathaniel
Posts: 614
Joined: December 10th, 2008, 3:48 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Elithrion wrote:1. Please find attached a list of the first 10000 nine-cell still lifes in 2x2. It might actually be comprehensive as the last one appears to have the first cell in position 4, something that we agreed would produce a duplicate and which really should not happen:
Whoops. Sorry, throughout this thread, I've been saying that it goes across the first row when I should have been saying it goes down the first column. It does it column-wise, not row-wise. Thus, the provided example is really about 1/3 of the way done (since the first cell is in row 2, it must have enumerated all the ones with a corner cell).

This also answers the "000100 -> 001000" rejection thing of 1.b. The rejection/reflection is done to the first column, not the first row.
Elithrion wrote:2. The single biggest improvement in speed for me might just be a full usage of my processor's second core. Right now it seems one stays at a steady 95-100% usage throughout the search, while the other idles at 10-30%.
I'd thought of this, but I unfortunately have no idea how to make C use a second core, if it's possible, or anything at all like that.
Elithrion wrote:3. That nice giant list needs automatic island killing. Here's the algorithm I have in mind in pseudo-pseudo-code:

Code: Select all

``````int changed = 1
char list1[appropriate dimensions], list2[appropriate dimensions], list3[list1's dimensions]
read file with questionable still lifes into list1 (make sure to have a shell of empty cells around the living ones)
list3 = list1
read file with smaller still lifes into list2 (make sure to have a shell of empty cells around the living ones)
create rotations/reflections of all still lifes in list2 and add them to list2
for (i = 1;i<=size(list1);++i) {
changed = 1
while (changed = 1) {
for (j=1;j<=size(list2);++j) {
if (list2[j] matches list3[i]) { /* that is, if there is an island that is exactly equal to some still life - just a simple cell for cell match */
list3[i] = list3[i] - list2[j] /* kill the island */
and then fix up list3[i] so that there's again 1 dead cell between live cells and outer edges
break;                               }
else if (j = size(list2)) {changed = 0}
}
if (list3[i] = blank) {list1[i] = blank}
}
}
print list1 to file
``````
Yeah! Well, I hope that makes sense anyway - seems simple enough to do.
The problem with that code, unless I'm reading the code wrong, is exactly why the current program misses some pseudo still lifes, actually. I'll illustrate the "tricky" part of determining whether or not still lifes are pseudo with some examples:

Code: Select all

``````OO.O
O..O
..O
...O

OO.
O..
..O
...O
.....O
....OO
``````
Yes, the first one listed is a pseudo-still life, but the second one is not. You can't just see if one of the contained islands is a still life, nor can you just check that *all* of the contained islands are still lifes.

I think the easiest way to do it is simply to make a list of all the islands (like it currently does) and then partition it into all possible (n choose 2) ways of splitting the still life into two sets of islands. If in any of those partitions, both sets are still lifes, then the overall pattern is pseudo.

Fortunately, it won't be *too* hard to modify the existing code to take care of this.
Elithrion wrote:4. I've been thinking about an alternative search algorithm. I call it the stability-seeking algorithm. First some quick definitions. "The cells being considered" are all the cells that might change state (so living + a shell of dead). The cells around cell i are i(0), i(1), ..., i(7), similar for cells ii, iii, iv, etc. Those numerals will denote the living cells and I'll just call the considered dead ones d1, d2, etc. n(i) is the number of living neighbours of i. For the example the rule is ab/cd and we have x cells. Oh, and I deliberately avoid obvious speed-ups to make the sketch of the idea clearer.
So, then, take cell i, place it in the middle of your array. Now if n(i)<a, place a cell in i(0). If n(i) is still less than a, place cell in i(1). Repeat until n(i) = a. Now, go to ii (if it's placed obviously). If n(ii)<a, place cell in ii(0) (or lowest empty number), but never in i(0), i(1), etc (in fact we're never placing a cell in a previously considered cell's neighbourhood; if you absolutely must do it, you have failed - move on). Once that's done, proceed to iii. If n(iii)<a, do the same as above. If n(iii) = a or n(iii) = b, move on to iv. If n(iii) > b, you have failed, go back to ii, find the last cell you've placed for it and move it over by one, then retry iii. So, let's say you've successfully made all the living cells stable like that. If you used up all x cells, check all the considered dead cells. If none want to come to life, success! Record it and move on (moving on to be explained shortly). If some want to come to life, you have failed - move on. If you did not use up all x cells, also check all the considered dead cells. However, now if you have no dead cells that want to come to life, you have failed (need I say "move on"?). If some do want to come to life (let's say d4 does), and if n(d4) <= d (if not, you failed), stick a cell in d4(0) (or first permitted number). From here repeat the process as before until success or failure. Once you do achieve one or the other, go back to the last cell placed and move it over to the next legal position. If you've exhausted all the legal positions that help meet rule a (or c), add an extra cell or two (when you have one to add obviously) to try to meet b (or d). Repeat until all possibilities are exhausted.
Upon first glance this looks quite promising, though not without some issues that would take some thinking (but that are almost surely overcomable). I haven't looked in too depth yet because I'm not going to have time to do the coding until at least next weekend anyways.

Also, just FYI, I'm running the count for 10 cells for the Move rule, and it should finish up sometime during the night tonight, so don't bother doing that one. It looks like the final count will just be 3.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Nathaniel wrote:The problem with that code, unless I'm reading the code wrong, is exactly why the current program misses some pseudo still lifes, actually. I'll illustrate the "tricky" part of determining whether or not still lifes are pseudo with some examples:

Code: Select all

``````OO.O..
O..O..
..O...
...O..

OO....
O.....
..O...
...O..
.....O
....OO
``````
Yes, the first one listed is a pseudo-still life, but the second one is not. You can't just see if one of the contained islands is a still life, nor can you just check that *all* of the contained islands are still lifes.

I think the easiest way to do it is simply to make a list of all the islands (like it currently does) and then partition it into all possible (n choose 2) ways of splitting the still life into two sets of islands. If in any of those partitions, both sets are still lifes, then the overall pattern is pseudo.

Fortunately, it won't be *too* hard to modify the existing code to take care of this.
Could you clarify a bit? What rule is that for? (the first one doesn't even seem to be still under any common rule) I still think my plan would work okay. In plain language, for a still life being tested, it would kill off any independently stable islands, as well as groups of islands (since those would also be included in the list of smaller still lifes) in the test list, and then iff the whole pattern was killed in the test list, it would kill it in the final list. That's basically exactly what pseudo still lifes are, right? Still lifes that can be split into smaller still lifes.

Your plan would occasionally fail, however (at least at high cell counts) For exactly the reasons you mention here - they can't always be split in two. Although that reference you cite there might be worth checking out (.ps can be opened with acrobat pro ).
[edit:] okay, I started reading that and apparently that page needs to be edited (I'll maybe do that some time [and the wikipedia page needs editing as well]). The paper says that you can have O(n^2) iff you only consider that "a pseudo still life is any stable pattern whose islands can be partitioned into exactly two nonempty sets each of which is stable on its own", however if you allow any number of sets (which seems to be the more modern definition), the problem is NP-complete. Not sure if it suggests a good algorithm for that either.

[edit:] I guess I'll also run 9-cell 2x2 with a bigger array for now. I'd do 10-cell 2x2 or maze, but I'm kinda scared that they'll give >500k results, which is problematic on so many levels.
Vi veri veniversum vivus vici.

Nathaniel
Posts: 614
Joined: December 10th, 2008, 3:48 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Elithrion wrote:Could you clarify a bit? What rule is that for? (the first one doesn't even seem to be still under any common rule) I still think my plan would work okay.
Sorry, the first one should have been this:

Code: Select all

``````OO..O.
O...O.
..O...
...O..
``````
I missed a couple periods. And I suppose that algorithm would work then for weeding out pseudo still lifes (I was forgetting that multi-island still lifes would be in your list as well, so as long as you first do the checks with the largest already-known still lifes and work your way down, it should be fine).
Elithrion wrote:Your plan would occasionally fail, however (at least at high cell counts) For exactly the reasons you mention here - they can't always be split in two. Although that reference you cite there might be worth checking out (.ps can be opened with acrobat pro ).

Yeah, I was aware of that but I've basically just been using the definition that it's a pseudo if it can be split into two islands. I figured we'd never get a program fast enough to calculate still lifes where it would really be an issue

Elithrion wrote:[edit:] I guess I'll also run 9-cell 2x2 with a bigger array for now. I'd do 10-cell 2x2 or maze, but I'm kinda scared that they'll give >500k results, which is problematic on so many levels.

Don't bother with 10x10 maze. The only reason 10x10 move is doable is because 1 isn't in its survival list (and it's still about 2.5 days worth of computation). 10-cell 2x2 would take over a month, I'm sure. And it's certainly not worth doing it before I implement better pseudo-still-life checking.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Nathaniel wrote:Yeah, I was aware of that but I've basically just been using the definition that it's a pseudo if it can be split into two islands. I figured we'd never get a program fast enough to calculate still lifes where it would really be an issue
Well, my proposed algorithm might be fast enough! But it also shouldn't generate pseudo still lifes (unless you want it to), so I guess that's kind of moot...

Also, it strikes me that since the full multi-part pseudo still life problem is NP-complete, the algorithm I'm pushing is probably the fastest possible, since it should be polynomial time. Well, the fastest possible if you have the list of all the smaller still lifes on hand, which is a pretty huge precondition...
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Okay, 9-cell 2x2 finished, with a final count of 15519 candidate still lifes. I'll maybe run Day & Night a bit next (no particular reason for it - just picked something that doesn't have S1).

[edit:] actually, Day and Night's only still lifes seems to be strings of blocks, so maybe that wasn't a good choice. "Strings of blocks" =

Code: Select all

``````OO
OO

OO..
OO..
..OO
..OO

etc
``````
Attachments
2x2-9c.rar
Vi veri veniversum vivus vici.

Lewis
Posts: 325
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

### Re: Enumerating Still Lifes (in C)

Elithrion wrote:actually, Day and Night's only still lifes seems to be strings of blocks, so maybe that wasn't a good choice.
Day & Night has other still lifes, but they tend to be much bigger that still lifes in other rules, eg: these three:

x = 22, y = 7, rule = 34678/3678
18bo\$2bo7b2o4b5o\$5o3b4o4b5o\$5o3b5o2b7o\$2bo6b4o3b5o\$9b2o5b5o\$18b
o!

Nathaniel
Posts: 614
Joined: December 10th, 2008, 3:48 pm
Contact:

### Re: Enumerating Still Lifes (in C)

OK, I've uploaded a new version of the script that automatically weeds out pseudo still lifes as it calculates using the method I described earlier (ie. it uses the "two stables subgroups = pseudo still life" definition). I'm currently re-running the 8-cell maze count to double check the number that I calculated earlier there (and to make sure that the code is working properly, though it seems to be working based on the 7-cell counts).

Edit: Yup, got 197 for maze. Looks good.

Edit again: 669 for the 9-cell maze still lifes. I'll update the wiki later today.

Edit yet again: Got the 9-cell 2x2 count now as well. Once I get my new computer (the RAM arrived today!) I'll see about calculating the 10-cell values on it.

Lewis
Posts: 325
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

### Re: Enumerating Still Lifes (in C)

Could the script be altered to enumerate small oscillators in various rules?

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Lewis wrote:Could the script be altered to enumerate small oscillators in various rules?
Nope, I'm afraid it could not. An oscillator script might use some of the same elements (maybe), but it would have to be fundamentally different. The script as-is basically goes through and checks the stability of every cell, but to check for oscillators you need to actually advance generations and such, which is a whole different procedure.
Vi veri veniversum vivus vici.

Nathaniel
Posts: 614
Joined: December 10th, 2008, 3:48 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Elithrion wrote:
Lewis wrote:Could the script be altered to enumerate small oscillators in various rules?
Nope, I'm afraid it could not. An oscillator script might use some of the same elements (maybe), but it would have to be fundamentally different. The script as-is basically goes through and checks the stability of every cell, but to check for oscillators you need to actually advance generations and such, which is a whole different procedure.
Well, your proposed algorithm (which I have yet to code, sorry) wouldn't really work for that purpose, but I don't see why the brute-force one wouldn't work. Simply change the function that determines if a pattern is stable to one that evolves the pattern under the rules of the game (which, for small patterns like this, takes little time to compute even for relatively high periods). If the pattern under n iterations of the rules is equal to the original pattern, then it's a period-n oscillator.

The downside is that both the period (or at least an upper-bound for the period) AND the number of cells must be specified by the user, and it will still take painfully long to compute, and for most common rules (such as Life), you'll get extremely low counts. There almost surely is a better method for computing these things. :S

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Nathaniel wrote:Well, your proposed algorithm (which I have yet to code, sorry)
Entirely understandable, and I honestly did not expect it to be done at all quickly anyway (especially what with me not doing it myself and thus having no one to blame). So, don't worry about it.
Nathaniel wrote:the brute-force one wouldn't work. Simply change the function that determines if a pattern is stable to one that evolves the pattern under the rules of the game (which, for small patterns like this, takes little time to compute even for relatively high periods). If the pattern under n iterations of the rules is equal to the original pattern, then it's a period-n oscillator.

The downside is that both the period (or at least an upper-bound for the period) AND the number of cells must be specified by the user, and it will still take painfully long to compute, and for most common rules (such as Life), you'll get extremely low counts. There almost surely is a better method for computing these things. :S
Well, mostly I meant that it would be completely different. Island checking would go out the window, so would stability checking (well, okay, it would actually be remade into cell changes). You would still have the basic pattern of cell placement left and rotation checks left, I suppose (which is what I meant by "some elements") but you'd need to make the advancing-through-generations action, as well as the checking-across-generations one. And yeah, as you mentioned the result would be pretty questionable, speed-wise.

If we're talking about better ways the most basic improvement would be to do all cell counts at once, if you will. The idea being that you keep track of all states ever examined (which could maybe actually be an awful idea just because of the memory needs and checking such huge lists), and eliminate them from consideration as you go along. So, let's say you have a random 4 cell pattern and you see it explode a little, you'd write down what it explodes into and then not consider that later on.

An alternative plan might be to do "all oscillators with an mxn bounding box" if you will. Create all plausible states (i.e. all possible states that don't trivially die out/explode), and then map them from one to the next to create cycles where possible. The oscillators will be the (period >1) cycles you make. This of course suffers from needing in the rawest forms 2^(m*n) combinations for consideration, but might be more decent in some refined forms. Some group theory stuff might prove convenient with this approach too.

Honestly, the best plan is to try to find out what people who did it for Life did, as I assume they've already thought long and hard about it from multiple angles, and no elegant solution like the still life algorithm is coming to me.
Vi veri veniversum vivus vici.

Nathaniel
Posts: 614
Joined: December 10th, 2008, 3:48 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Well I got my new computer built yesterday, so now it's running the 10-cell counts for both 2x2 and maze. My semester finishes up later this week so I'll hopefully have more time for coding in the near future.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

On a vaguely related note, it strikes me that the algorithm I'm proposing for still lifes (point 4 over here) can possibly be (rather unintuitively) extended to oscillators of a chosen period. It would certainly be interesting. Basically, an oscillator is just a bunch of generations in cycle. So, when you place a cell in generation 1, you need to place enough cells in generation n-1 (where n is the period of the oscillator) to cause it to be born (assuming the first cell we place is one of the ones that oscillate at the full period). From here, we need to place cells in n-2, so that the original cell remains empty in n-1 and the other cells either continue existing into that generation or are born. It might be a computational nightmare, but it seems like it could be made to work (possibly very very slowly, of course) by continuing this process back through the generations, until we get back to generation 0. Once there, if everything can still be made to work together, then good. If not, go back to generation 1 and tweak cell positions to the second alternative and try again. Once you've exhausted all alternatives there and failed to build anything, go back to generation 2 and try those alternatives, and so on.

No guarantees about speed, but it could a) perform an exhaustive search of small-period oscillators with some parameters with some level of effectiveness, or b) find the missing prime-period oscillators, possibly unbelievably slowly (or prove they don't exist by exhausting all possibilities if anyone believes that).

Just a thought, anyway.
Vi veri veniversum vivus vici.

hkoenig
Posts: 132
Joined: June 20th, 2009, 11:40 am

### Re: Enumerating Still Lifes (in C)

Years ago Mark Niemiec pointed out that oscillator searches were really no different from stable object searches. You add a third dimension with a thickness of the number of generations you are interested in. Then, instead of calculating the dependencies within the layer, you place cells such that there is consistency based on the dependency on the previous generation. (For spaceships, you apply a translation of the proper speed before you tie the first and last generations together.)

For example, if in generation 0 there is a birth cell, that cell must be alive in generation 1 or you will never get a valid oscillator. The same goes for death cells. Stable objects are simply a sort of degenerate volume with the layer pointing to itself.

My current search program uses such an algorithm, but is pretty slow. I gave up trying any Period 4 searches, but it could theoretically work. I did run the P2H1V0 spaceship search for a while, but again, it was going to be a long time before it actually found anything, as the smallest has a bounding box of 21 or 22.

Currently it's grinding through 10x10 for Period 1 and Period 2, and 9x9 for Period 3. (It went faster when my employers would donate CPU time on evenings and weekends...) Here's what I've found so far

Period 1
2x2 1
3x3 3
4x4 8
5x5 19
6x6 173
7x7 6703
8x8 108582
9x9 11545196
10x10 108 million (in progress)

Period 2
4x4 3
5x5 1
6x6 2
7x7 69
8x8 813
9x9 100574
10x10 57215 (in progress)

Period 3
7x7 2
8x8 111
9x9 549 (in progress)

Working on a new algorithm which should be faster but has the unfortunate side effect of generating megabytes of intermediate files daily, consuming them at only about 10% of the production rate. But I figure a 2TByte RAID should be good for a few years...

(As of March, there were 116 different P2 rotors found. Give me a few days and I should be able to put together some RLE files showing the unique rotor/casings for these oscillators. Curious to see if anything new/different has been found since then...)

Here, for example, are the smallest objects illustrating the 41 different rotor casings for the Beacon 2-bit rotor (some of these were found by hand or by others.) A rotor casing consists of all cells that lie in the casing neighborhood of any rotor cell, the rotor casing being the 5x5 patch centered on the rotor, excluding the 4 corners. In effect, these are all the cells close enough to have an influence on the birth/death of the rotor cells. (I believe a Period 3 rotor should be a based on a 7x7 patch with the corners trimmed, but haven't investigated to determine which cells need trimming, 1 or 3, or if a 5x5 patch might still work.)

Code: Select all

``````x=145, y=70
2o13b2o15b2o11b2o2bo10b2o15b2o11b2obo12b2o12b2obo11b2o2b2o\$o15bo14bobo11b
o2bobo9bobo15bo11bob2o12b2o12bob2o11bo2bo2bob2o\$3bo12bob2o10bo5bo9bobo2bo10b
o12bo2bob2obo10b2o28b2o10b3o2bob2o\$2b2o13bo2bo9bob5o10bo4bo8bob2o2b2o6b3o2b
ob2o7b2o3bo9b4o11b2o3bo14bo\$20bo10bo16b3obo8bo3bo2bo22bo3b2o8bo4bob2o7bo3b
o12b2obo\$19bo14bo16bo10bo2bobo9b2o13b2o11b2o3bob2o8bobo12bo2bo\$20b3o10b2o15b
o12bo2bo10bo16b2obo12bo9bobobobo10b2o\$22bo27b2o12b2o12bo15bob2o10bobo9b2o3b
2o\$77b2o29b2o7\$2o2bo10b2o2b2o9b2o2bo3bo6b2o14bo3bo9b2obo11b2o2b2o9b2o2b2o9b
2o2b2o9b2o3bo\$o2bobo9bo3bobo8bo2bobobobo6bo2b2o9bobobobo8bob2o11bobo2bo9b
o2bo2bob2o5bo2bo2bob2o5bobobobo\$2b2obo2bo8bobo2bo8b2o2bob2o7bobo2bobo7b2ob
o2bo11b2o11b2obob2o7b3o2bob2o6b3o2bobo8bobo2bo\$6b3o7b2o2b2o14bo10bo2bob2o11b
2o9b2o3bo9bo3bo2bo12bo14bobo7bo3b3o\$2b2o11bo15b2obobo13bo10b2o13bo3bobo8b
o4bo11b2obo11b2obob2o6b2o\$2bo2b2o9bobob2o8bobob2o9b4obo9bo2bob2o10b2o2bo10b
4o10bo2bob2o10bo2bo12b2o\$3b2o2bo9b2obobo8bo13bo3bo11bobobobo11b2o25b2o17b
2o9b3o2bo\$6b2o13bo26bo13bo3bo8b4o13b2o42bo3b2o\$48b2o25bo2bo13b2o7\$2o3bo9b
2o14bo3bo10bo3bo9b2ob2o2b2o6b2ob2o10b2o3b2o8b2o3bo10b2o13b2o\$obobobo9bo5b
2o6bobobobo8bobobobo9bobo2bobo7bobo12bo4bo8bobobobo9bobob2o9bo2b2o\$2bobo2b
o8bob2obo2bo6b2obobo9b2obo2bo8bo2bobo8bo3bo11bob3o11bobobo11bobo2bo8b2o2b
o\$bo3b3o7b2o2bob3o11bo14b2o10bobo2bo8b3obo11bo13bo3bo11bo2bob2o12bo\$b2o14b
o13b2o13b2o15bo4bo11bo14b3o8b2o14bo2bobo9b2o2bob2o\$4b2o11bo2b2o9bo2b4o8bo2b
3o12b3obo7b2o2bob2o6b5o2bo11b4o7bobobo2bo7bo2b3o2bo\$b2obo13b2o2bo9b2o3bo9b
2o3bo14bo7bo2bo2bobo6bo5bo9b3o3bo7b2o2bobo8b2o6bo\$bo2bo16b2o11b3o12b3o14b
o8b2o2b2o12b3o10bo2bo14b2o14b3o\$2b2o30bo14bo16b2o25bo13b2o31bo7\$2ob2o10b2ob
o2b2o7b2o3bo3b2o6b2o3bo7b2obo2b2o8bo15b2o11b2o6b2o6b2ob2o9b2o2b2o\$2obobo9b
ob2o3bo8bo2bobo2bo7bobobobo6bob2o3bo8b3o13bo2b2o9bo2b2o2bo8bobobo8bo2bobo\$3b
o2bo12b3o9bobobobobo5b2o2bobobo10b3o12bo13b2o2bo8bobo2bobo7bo2bo2bo9b2obob
2o\$2o2bobo9b2o12b2obo3b2o7bobo2bob2o6b2o13b3obob2obo4b3o2bo2bo6b2obo2b2o8b
2o2bobo12bobo\$o3bob2o8bo3b2o10bo3bo8bo2bo2bo9bo3b2o8bo4bobob2o4bo2bo2b3o9b
o16bob2o6b3o2bo2bo\$b2obobo10bobo2bo9bobobo9b2o3bo10b2o2bo8bobo2bo10bobo14b
ob3o8b3obobo7bo2bo2b3o\$3bo2bo8bobobobo11bobo12b3o13b2o10bobo2bo8b2obob2o12b
o3bo6bo3bo2bo8bo2b2o\$3bobo9b2o3bo13bo13bo11b4o14bob2o11bo2bo10bobo2b2o6b2o2b
obo10b2o2bo\$4bo55bo2bo14bo14b2o12b2o16bo14b2o\$77b2o6\$4bo\$2b5o\$bo5bo\$bo2b3ob
o\$2obo4bo\$3bo4bob2o\$3bob3o2bo\$4bo5bo\$5b5o\$7bo!
``````
I've only found three different casings for the other 2 bit rotor, the one in the Spark Coil and Test Tube:

Code: Select all

``````x=31, y=10
2o4b2o5b2ob2o8b2obo\$obo2bobo5bo3bo8bob2o\$2bo2bo8b3o\$2bo2bo21b3o\$3b2o21bo3b
o\$14b3o9bo3bo\$13bo3bo9b3o\$13b2ob2o\$26bob2o\$26b2obo!
``````
There's only one 3 bit Period 2 rotor.

hkoenig
Posts: 132
Joined: June 20th, 2009, 11:40 am

### Re: Enumerating Still Lifes (in C)

Code: Select all

``````#C 4 different P3 rotors found so far in 9x9 search
x=45, y=9
2o10b2o10b2o10b2o\$o2bo2b2o5bo2bo2bo4bo2b2o2b2o4bo4b2o\$2b2o2bo5bo3b4o9bo2b
o3bo4bo\$8bo4b3o9bobobobo4b2o6bo\$2b7o7bob2o5bo3b2o6bo2bo3bo\$bo11b2obo2bo6b
3o8bobobo2bo\$b2o3bo6bo3b2o9bo7b2obo2bo\$5b2o7b3o23b2o\$16bo!
``````

Code: Select all

``````#C 157 different P2 rotors found so far in 10x10 search
x=148, y=206
bo12bo12bo11b2o12bo12bo12bo12bo12bo12bo\$obo4bo5bobo10bobob2o7bobob2ob2o4b
obob2o7bobo2b2o6bobo3b2o5bobo4bo6b3o9bobob2o\$bobo2bobo5bobo10bo3bo9b2obob
2o5bo3bo8bo2bo2bo6bobo2bo7bobo2bobo8bob2o6b2obobo\$3bo2bobo6bobo3b2o5b2obob
2o5bo3bo9b3o10b2ob2o9b3o2bo7bo2b2o8b2obo9bo2bo\$3bo2bob2o7bo4bo6bobo2bo5b2ob
5o7bo12bo11bo2b4o6bob2o10bo2bo2bo6b2ob2o\$4b2o11bobo8bo2bo14bobo6bo12b2o10b
2o12b2ob2o6bob2o2b3o4b2obo\$16b2ob2o7b2obo2bo5b2o2bo3bo5b3o3b2o4b2obob2o11b
o14bo4bobobo10bo\$31bob2o5bo2bob3o5bo4bo2bo4bo2bo2bo7b2obobo8b2o2bo6bo2bob
2o7bobob2o\$31bo10b2obo7bobo2b2o8bobo8bobobobo8bo2bo10bo2bo8b2obobo\$30b2o22b
2o13bo10bo3bo10b2o12b2o13bo4\$2o11b2o12bo12bobo10bobo10bo12bo12bo11b2obo9b
2obo\$bo2b2o2b2o4bo3b2ob2o3bobo3b2o6b2obob2o6b2obob2o6b3o10b3o3b2o5b3o3b2o5b
ob3ob2o5bob3ob2o\$o4bo2bo4bo4bo3bo4bo4bo10bobo10bob2o9bo3bo8bobo2bo7bobo2b
o3bo5b2o5bo5b2o\$b4o4bo4b3obob2o6b3obo2bo7bo4bo7bo3b2o4b3obobobo6b2ob3o7b2ob
3o4b5o4bo3b5o4bo\$2bo5b2o5bobo2bo9b2ob3o3bob3o3b2o3bob3o3b2o3bo4bob2o6bo12b
o14b6o7b6o\$2bob3o8bobobo2bo9bo6b2o11b2o11bob3obo8b2ob2o9bob2o6b2o11b2o\$b3o3b
3o4b3o2bob2o9b2o8b2o3b2o6b2o3b2o4bo3bob2o4b2obobo7bo2bobo7b2o4b2o5bo5b2o\$
o5bo2bo3bo6bo12bo9bo4bo7bo4bo7bobo2bo3b2obo4bo4b2obo4bo6b2o2bo9bo2bo\$obob
obo7b3obobo9bo12bobo10bobo9b2obobo7bo3b2o7bo3b2o6b2o5bo5b2o5bo\$b2ob2o10bob
2o10b2o10b2ob2o8b2ob2o12bo8b2o11b2o16b2o11b2o4\$2o11b2o12bo12bo11b2o11b2o11b
2o11b2obo10b2o10b2o\$obo3b2o5b2o5b2o4bobob2o7bobob2o7b2o4bobo4b2o3b2ob2o3b
o4b2ob2o3bob4ob2o5b2o5b2o4bo3b2o\$2bo2bobo7b2obo2bo5b2ob2o8b2obo3b2o5b2obob
2o6b2o2bob2o6bo2bob2o9b2o8b2obo2bo3bo4b2o\$b2obobo8b2ob2o12b2o9bo4bo5b2obo9b
2obo9b2obo8b4o4bo6b2ob3o4bobo4b2o\$bo2bob2o10bo8b6obo5b2obobo12b3o9b2ob2o8b
2ob2o3bobo2b5o3bo13b7obo\$2b2o2bobo6b2obo8bo6bo5bo2bob2o7b2o5bo5b2o5bo5b2o5b
o3bo2b2o8b4ob2o15bo\$7bobo5bo2bob2o8b2obo9bo9bo2bob3o6bo3b3o6bo3b3o5b2obob
2o8bobo10b2ob3o\$2b2obobobo8bobo10bob2o7bo2b2o7bobobo9bobo10bobo9bobobo8bo5b
o8bobo\$bo2b2ob2o8bo2bo7bo14b2obo8bo10bobobob2o5bobobob2o6bobo4bo4bo5b2o5b
o\$b2o15b2o8b2o36b2o3bobo5b2o3bobo7b2o3b2o4b2o11b2o4\$2o11b2o11b2o11b2o12bo12b
o12bobo10bo11b2o12bo\$2o4b2obo3b2o4b2o5b2o3b2ob2o3bo4b2ob2o3bobo10bobo2bo8b
2obob2o6b3o10bo4b2obo4b3o\$2b2obo2b2o5b2obo2bo6b2o2bobo7bo2bob2o4bobob2o7b
o2bobo10bob2o9bo8bo4bo2b2o7bo\$2b2ob2o8b2ob4o6b2obo3bo5b2obo10bobobo7b3obo10b
o3b2o6bobo7b2o3b2o9b2o\$6bob2o21b4o9b5o6bo14bob2o5b2obo3b2o6bo2bo9b2obob2o6b
ob2ob2o\$2b3obo2bo5b2ob2o8b2o11b2o5bo5b2o3bobo5b4o3bo3bobobo9b2o4bo5b2ob2ob
o2bo3b2obob2obo\$bo2bobo9bobo8bobob2o7bobob2o8bo5b2o5bo2bo2bo5bo3b5o3bo4b2o7b
o4bo6bo2bo4bo\$2b2o3bo8bo4bo5bobobo8bobobo10bo13bo2bo14bo4bo2bo9bob2o2bo8b
ob3o\$4b3o7bobo3b2o6bo5bo6bo5bo6b2o14b2o11b2o8bobo10b2ob2o8bo2bo\$4bo9b2o17b
2o11b2o35b2o9bo25b2o4\$bo12bobo10bobo10bobo9b2o11b2o12bo12bo12bo12bo\$b3o10b
2obob2o6b2obob2o6b2obob2o6bo4b2o6bo4b2o5bobo3b2o5bobob2o7bobob2o8b3o\$4bo12b
ob2o9bobo10bobo6bo5b2o5bo5b2o6bo4bobo5b2obobo7bo3bo11bo3b2o\$3bo13bo3b2o7b
o4bo4b3o5bo3b4o4b2o3b2o2b2o9b3obo9bo3bo7b3o11b2o2bobo\$3bo2bob2o5b3o3b2o5b
3o3b2o3bo7b2o6bo4b2o4bo2b2o11bobob2o6b2o3bo18bo5bo\$2obob2obo5bo12bo11bob2o9b
2obobo7bo7bo10bo7b2obobobo12b2o3bob4o2bo\$o2bo4bo5bob2o9bob2o9bo2bob4o3bo2b
ob5o3b9o10b2o6bo4b2o7b3o4bo3bo4b3obo\$3bob3o5b2obo9b2obo13bobo2bo6bo5bo31b
o2bo8bo2b3o7bo2bo2bobo\$2bo2bo13bo12bo9bo2bo8bo2b2o8bo3bo22bobo8bobo2b2o7b
obo3bo\$3b2o13b2o11b2o10b2o10b2obo8b2ob2o23bo10b2o12bo4\$bo11b2o12bo11b2o11b
2o11b2o11b2o11b2o11b2o12bo\$obob2o8bo2bo3bo4bobo3b2o6bo2b2o2b2o3bobo2bob2o5b
o6b2o4bo2b2ob2o4bobobo2b2o4bobo3b2obo4b3o\$b2obobo7bobobobobo4bo4bo2bo4bob
obo3bo5bo2b2obo4bo4b2o2bo4bobo2b2obo5b2obo2bo10bob2o7bob2o\$3bo3bo7b2obob2o6b
3obob2o3b2obobobo6bob2o8bobobob3o4b2obo4b2o4bo3b3o7bobobo9b2obo2bo\$3b2o3b
o8b2o12b2o8b2o2b3o6b2ob3o6b2ob2o11bo3bo6b3o11b2ob4o5bo2bo2b2o\$b2obob2obo7b
o13bo9bo6bo11bo10b3o4b4o5bo7bob2o14bo3bo2bob3o\$bo2bo3bo7b2ob2o7b4ob2o5b2ob
4obo5b2o2bobo5b2o2bobo5bo5bo2bo9bo9b2ob3o4b2obo2bob2o\$3bob3o9bobo2bo4bo4b
o2bo3bo2bo4bo5bo2bobob2o3bo2bobo3bo4bo3bob2o7bobo3bo7bobo8bo6bo\$2b2obo8bo6b
2o4b2o2bo2bo5bobobo9b2o2bo2bo4b2o2bo2b2o3b2o3bo9bo5b2o4bo13bobobobo\$14b2o16b
2o7b2ob2o12b2o10b2o10b2o9b2o10b2o13b2ob2o4\$bo12bo11b2o11b2o11b2o11b2o12bo12b
o12bo12bo\$obob2o8b3o10bo2b2ob2o5bo2b2ob2o4bobob2o2b2o3bobob2o2b2o3bobo3b2o5b
obo3b2o5bobo3b2o5bobo3b2o\$b2obobo10bo3b2o3bo3bob2o5bo3bob2o6b2obo2bobo4b2ob
o4bo4bo4bo2bo4bo4bobo5bo4bo7bo4bo\$5bobo6b3o3bobo4b3o5bo4b3o5bo7bo12bobobo6b
3obob2o5b2o4bo6b3obobo6b3obo\$b2ob3obo4bo15bob5o6bob5o4b2ob2obo6b2ob2o12b2o9b
ob3o10b2o2bo8bob2o\$bo3bob2o4b2o3bobo10bo10bobo9bo5bo6bo5bo9bo10b2o13bo3bo8b
o3bo\$2bo11bo2bo10bobo3b2o11b2o5bob5o6bob5o6b5ob2o5b2o2b2o7b4ob2o6b5o2bo\$3b
obob2o4bo3b2o8bo7bo4bobo5bo6bo12bo10bo4bobo5bo5bo6bo4bo7bo4bobo\$4b2obobo4b
3o10b2o3bo7b2o3bo12bo12bo8b3obobo6b5o8b3obo8b3obo\$8bo7bo15b2o11b2o10b2o11b
2o10bob2o9bo12b2o11bob2o4\$bobo9b2o11b2o12bo12bo12bo12bo12bobo10bobo10bobo\$b
2obob2o5b2o4b2o5b2o4bo6bobo2b2o6bobo2b2o7b3o10b3o10b2obob2o6b2obob2o6b2ob
ob2o\$4bobo8b2obo2bo6b2o2b3o5bo2bo2bo6bo2bo2bo9bo12bo12bobo10bobo10bobo\$b3o2b
ob2o5b2obob2o6b2o5bo5b2o2bo8b2o2bobo7b2o11b2o9b3o2bob2o7bo4bo7bo4bo\$o5bo11b
2o11b4o10bob2o9bo8bo12bo10bo5bo9b2o3b2o6b2o3b2o\$o4b2obo10bo8b2obo9b3obo8b
3obob2o4bob2o11b2o8bob5obo5bo12bo\$b3o3bo8b2ob2o7bo2b4o5bo3b2obo5bo3b2o9bo3b
2o4b2obo3b2o5bo5bo5bob5o6bob5o\$4b3o7bo2bobo11bo2bo6b2o3bo7b2o3bo5b2obo4bo7b
o4bo8bobo7bo4bo7bo4bo\$3bo10b2o6bo7bo2bo9b3o10b3o9bobo8bobobo10b2ob2o8bobo9b
obo\$3b2o16b2o8b2o10bo12bo10b2ob2o8b2ob2o22bo13bo4\$bo11b3o10b2o11b2o12bo11b
2o11b2o11b2o11b2o11b2o\$obob2o11bo3b2o4bo2b2ob2o4bobo3b2obo3bobob2o8bo4bo7b
o4bo6bobo2b2ob2o3bobo2b2ob2o3bo2b2ob3o\$b2obo9bobobobobo4bobob2o2bo9bob2o4b
2obo3bo4bo5bobo5bobob2o8bo3bobo6bo3bobo6b2o\$4bo8bo4bob2o4b2ob2o4bo5bobobo10b
obo2bo3b2o2bo4bo5bob3o2bo4b2obobobo5b2obobobo9bobo\$b2o3bobo4b2o2b2o7bo3bo3b
o7b2obob2o4b2obobo2bo4bo2b6o9b4o6b2o2bo8b2o2bo7b3o3bo\$bobo3b2o9bo8bobo4b2o9b
ob2o4bo2bo2bo5bo12b4o12bo12bo10bo5b2o\$5bo10bo9b2obo2b2obo4b3o2b2o8b2o8b10o3b
o3bob2o7b2ob5o5b2ob5o4bo\$5bob2o7b2o12b2ob2o5bo2bo2bo27bo5bobobo7bo2bo4bo4b
o2bo4bo5b3o\$4b2obobo33bobo21bo3bo7b2obobo7b2o2bobo6b2o3bobo9bo\$8bo35bo22b
2ob2o11bo14bo11bo10b2o4\$3o11bo12bo11b2o12bo12bo11b2o11b2o11b2o11b2o\$4bo3b
2o3bobo11b3o3bo5bobob2ob2o5b3o10b3o9bobo3b2obo3bobo3b2obo4bo3b2ob2o3bobo2b
2ob2o\$bobobobobo4bobo13bo2bo10bob2o8bo12bo14bob2o9bob2o3bo3bo4bo7bobobo\$o4b
ob2o6b2o4b2o6bobo2bo6bo2bo10b2o11b2o10bobobo8bobobo6bobo4b2o6bo5bo\$2o2b2o11b
2obobo6bo12bobo9bo12bo13b2ob4o6b2ob4o4b5obo10bo2b2o\$7b2o8bo12bobobo8bo3b2o4b
ob2o3b2o4bob2o3b2o12bo12bo9b2o6bobo2bobo\$5o3bo9bo2bo5b3o5bo4b2obobo2bo6bo5b
o6bo3bobo4b6o7b6o9b2o2b2o5b2o2b2o2bo\$o4bobo12bo5bo7b2o7bob2o5b2obo2bobo4b
2obo10bo4bo7bo4bo9bo5bo10bobo\$3bobobobo6bobobo6b3o11bobo11bobo10bobobo7bob
o11bobo11b5o11b2o\$3b2o3b2o6b2o11bo12b2o10b2ob2o8b2ob2o10bo11bo15bo5\$3o10b
3o10b2o11b3o11bo12bo12bo11b2o11b2o11b3o\$4bo2b2o8bo2b2o5bo2b2ob3o7bo3bo4bob
o10bobob2o7bobob2o8bo5b2o4bobobo3bo8bo2b2o\$bobobo2bo5bobobo2bo4bo3bo9bobob
obobo4b2o4b2o5b2obo9b2obo3bo5bob2o3bo7b2o2bobo4bobobo2bo\$o4bobo5bo4bobo6b
3o2bobo4bo4bob2o7b2obobo8bo2b3o7bobo2bo3b2obobobo10b3obo3bo4bobo\$2o2b2ob2o4b
2o2b2ob2o8b2o3bo3b2o2b2o10bo10b2obob3o5b2obobo2bo3bo2bo10b5o2bo4b2o2b2ob2o\$7b
o12bo6b2obo3b2o8bob2o8bo3bo5bo2bo9bo2bo2bo7b2obo2bo5bo5bo12bo\$4b2obo5b6ob
o6bo2bo13bo2bo13bo7bo12bo12bobo2bo7bo2bobo9b2o\$5bob2o4bo5bo10bob4o3bob2ob
o11bobob2o6bo12bo13bobo2bo6b2o3b2o6b2obob2o\$2bo13bo12bo2bo2bo3b2obo2bo9bo13b
3o10b3o7b2obo3bo7b2o10bobobo2bo\$2b2o12b2o12b2o11b2o10b2o14bo12bo7b2ob2o10b
o12bo3b2o4\$3o10b2o12bo11b2o12bo12bo12bo12bo12bo12bo\$4bo2b2o4bo2b2ob3o4bob
o10bobob2o2b2o4b3o9bobo3b2o5bobo3b2o6b3o10b3o10b3o\$bobobo2bo6b2o10b2o12bob
obo2bo7bob2o6bobo2bobo5bobo2bobo8bo12bo12bob2o\$o4bobo10bobo8b2o3b2o4b2obob
obo5b2obobobo6bobobo8bobobo9b2o11b2o11b2obobo\$2o2b2ob2o6b3o11bobobobo5b3ob
2o5bo2bo2bo9bo2bob2o6bo2bob2o5bo2b2o8bo2b2o8bo3bo\$5bo8bo5bobo19bo9b2o4bob
2o9bo12bo7bobobo8bobobobo8b2obob2o\$5b2o7bo6b2o8bo2bo5bo3b5o5b5o7b5obo6b5ob
o8bobob2o7bobo7b2obo2bo\$3b2obob2o5b3o15bo6b2obo4bo5bo4bo6bo4bo7bo4bo6b2ob
obo7b2obobob2o7bobobo\$2bobobo2bo8bo10bobobo10bobo9bobo8bobo11bobo10bobobo8b
obo8bobo2bo\$3bo3b2o8b2o10b2o15bo9bo12bo11bo11b2ob2o8b2ob2o8b2o4\$bo12bo12b
o11b3o10b3o11bo11b2o11b2o12b2o10b2o\$b3o9bobo10bobob2o11bo2b2o8bo2b2o4bobo5b
o5bo2b2obo6bo3bo2b2o6bob2ob2o3bobob2ob2o\$4bob2o6b2o5b2o4b2obobob2o4bobobo2b
o5bobobo2bo5b2o5bo4bo3bo3b2o3bo4bobobo3bo5bobo9bob2o\$3b2obobo7b2o2bobo7bob
2obo3bo4bobo5bo4bobo8b2obo2bo3b2o3bo7b2o3bo7bob4o2bo5bo2bo\$2bo3bo9bobo8b2o10b
2o2b2ob2o4b2o2b2ob2o7bo11bo4bo7bo4bo6b2o2bobo11b3o21bo\$bob2obob2o10bo6bob
o2b3o10bo12bo10bo2b2o6bo2bo9bo2bo8b2o3bo7b2o5bo\$3bo2bo10bo16bo4b5obo6b5ob
o20b2obo3b2o4b2obo3b2o5bo15b3o\$2obobobo11bobo7bo3bo5bo4bo7bo4bo11bobo7bo2b
2obo6bo2b2obo21bo\$3bo2bo8bobo2b2o6bo12bobo9bobo13b2o10bo12bo26bob2o\$2b2o11b
2o11b2ob3o7bo13bo24b2o11b2o25b2ob2o4\$2o12bo11b2o11b2o11b2o11b2o12bo11b2o11b
2o12bo\$obob2obo5bobo5bo4bobob2o2b2o3bobob2obo5bobob2obo6bo3bo2b2o3bobo5bo5b
o2bo8bobob2o2b2o4b2o\$2bobo3b2o4b2o5bo5b2obo2bobo5bobo3b2o5bobo3b2o3bo4bob
obo4bobo4bo5bobo2bo7b2obo2bobo4b2o\$2bo2bo10b2obo2bo7bo10bo2bo9bo2bo7b2o3b
o9bobobo2bo3b2obo2bo10bo10bo\$b2o4bo8bo10b3ob2o2bo4b2o4bo6b2o4bo12bo9b2o7b
o2bo2bob2o4b3ob2o2bo6b2o\$5bo11bo2b2o5bo2bo3bo10bo11bo7b4o3bo8bo3bobo4bo6b
2o4bo2bo3bo9b2o\$8b2o20bo3bo12bo11bo5bo2bo5bo6bo4b2o3b2ob4o10bo3bo5bo2b4o\$3b
obobo9bobo8bo14bobobo7bobobo8bobobobo8bo8bob3o9bo10bobobo\$3b2o11bo11bobob
o10b2o2bo7b2o2bo6bobob2o2bo4b2o3bo7bo12bo3b2o7bo2bo\$16b2o10bo2b2o33b2o13b
ob2o6b2o12b2obo12b2o4\$2o12bo11b2o11b2o11b2o11b3o10b2o11b2o11b2o11b2o\$obob
2ob2o4bobob2o7bobob2obo5bobob2obo5bobob2obo10b2ob2o3bobob2obo5bobob2obo5b
obob2obo5bobob2obo\$5bob2o5b2obobobo6bobo3b2o5bobo3b2o5bobo3b2o4b2obobobo6b
obo3b2o5bobo3b2o5bobo3b2o5bobo3b2o\$bo2bo12bo3bo6bo2bo9bo2bo9bo2bo15bo6bo2b
o9bo2bo9bo2bo9bo2bo\$6b3o5b2o5bo5b2o4bo6b2o4bo6b2o4bo7bobo3b2o4b2o4bo6b2o4b
o6b2o4bo6b2o4bo\$b2o5bo5bobo15bo13bo12bo23bo12bo12bo12bo\$7bo11b2o13bo9bo16b
o7bobo14b2o10bo10bo12bo\$3bo11bo2bo11bobobo12b2o8bobobo10bo8bobobo8bobobo8b
o12bo\$2bo2bobo8bo12bo4bo7bobobo9bo4bo9b2o7bo12bo4bo7bo3b2o8bobobo\$2b2o2b2o8b
o12b2o11b2o12b2o22b2o11b2o11b2obo10bo2b2o4\$2o11b3o10b2o11b2o11b2o14bo11bo\$
obo4b2o9b2ob2o3bobo4b2o4bobob2ob2o4bobo3b2o8bobob2o6bobobo\$6bobo5b2obobob
o10bobo9bob2o8bo2bo6bo6bo6bobo\$2bobo16bo6bobo9bo2bo10bo17bo12b2o\$6bo8bobo3b
2o9bo12b3o7b2obo6b2o13bo3bo\$3bo25bo10b2o5bo7b2o16b2o3bobo4bo\$2bo2bobo9bob
o11bobo12bo6b2o2bobo7bo11bo3bo\$2b2o23bobo12bobo8b2o11bo6bo5bobo\$7bobo9bob
o5b2o4bobo8bobobo10bobo4b2obobo9bo2b2o\$8b2o10b2o12b2o11b2o11b2o9bo11bo!
``````
These aren't the smallest objects with a particular rotor, just the first example that showed up. There are a lot of trivial combinations of two non-interacting rotors, and smaller oscillators with added tails or inductors, too.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

### Re: Enumerating Still Lifes (in C)

Huh, interesting, and some of those oscillators are really very neat (the last row of 10x10 P2's especially). Also, I must say I'm rather curious what algorithms you're using, if you don't mind sharing.
Vi veri veniversum vivus vici.

knightlife
Posts: 566
Joined: May 31st, 2009, 12:08 am

### Re: Enumerating Still Lifes (in C)

Elithrion wrote:

the last row of 10x10 P2's especially
I noticed the next to last oscillator looked very close to a phoenix oscillator, extended slightly. I wondered if it could be extended more and found the answer is yes. Going further I noticed commonality among all the oscillators and created "p2 oscillator tracks" that can be combined in many ways. I was surprised that the phoenix type loops can be connected to the other types to create giant p2 oscillators. The key element for this connectivity is the pre-block that can be extended to connect to other p2 oscillators. There are two types of barberpole intersections as shown with the "X" patterns:

Code: Select all

``````#C P2 OSCILLATOR TRACKS
x = 89, y = 169, rule = B3/S23
60bo\$60bobo\$58bo\$63b2o\$57b2o\$64bo\$56bo9bobo\$66bo\$15bo39b2o12b2o\$15bobo
b2o47bo\$13bo6bo33bo14bo\$19bo47bo\$12b2o39b2o10bo\$19bobob2o40bo2b2o\$11bo
7b2o3bo27bo10bo3bo\$23bo\$10b2o39b2o9b2o\$23bobob2o\$12bo10b2o3bo21bo13bob
o\$11bo3b2o10bo38bo\$11b2obobo32b2o17bobo\$27bobob2o37bo\$16bo10b2o3bo15bo
23bobo\$15bo3b2o10bo42bo\$15b2obobo26b2o27bobo\$32b2o44bo\$20bo28bo30bobo\$
19bo3b2o7bo15bo3b2o28bobo\$19b2obobo23b2obobo30bo\$30b2o51bobo\$24bo28bo
29bo\$23bo6bo21bo3b2o\$23b2obobo23b2obobo23bobo\$28bo50bobobo\$57bo19bo5bo
\$56bo3b2o13bobo\$56b2obobo11bo\$71bobo\$61bo7bo\$60bo6bobo\$60b2obobo\$65bo
4\$15b2o\$3b2o9bobo\$3bo\$4bobo5bobo2\$6bobobobo2\$8bo3bo2\$8bobobobo2\$6bobo
5bobo46bo\$17bo45bobo\$4bobo9b2o43bo\$4b2o60b2o\$60b2o\$67bo\$59bo9bobo\$69bo
\$58b2o12b2o\$71bo\$14b2o41bo14bo\$6b2o5bobo54bo\$6bo49b2o10bo\$7bobobobo54b
o2b2o\$55bo10bo3bo\$9bo3bo\$54b2o9b2o\$9bobobobo\$16bo36bo13bobo\$7bobo5b2o
52bo\$7b2o43b2o17bobo\$73bo\$51bo23bobo\$77bo\$50b2o27bobo\$81bo\$52bo30bobo\$
51bo3b2o28bobo\$51b2obobo30bo\$13b2o71bobo\$7b2o5bo41bo29bo\$7bobobobo41bo
3b2o\$55b2obobo23bobo\$9bo3bo68bobobo\$60bo19bo5bo\$9bobobobo47b2o13bobo\$
8bo5b2o42bobobobo11bo\$8b2o64bobo\$56bobo5bo7bo\$63bo6bobo\$43b2o9bobo6b2o
bobo\$43bo24bo\$44bobo5bobo2\$46bobobobo\$29b2o\$26bobobo17bo3bo\$26bo\$25bo
2bo19bobobobo2\$24bobobobo15bobo5bobo\$24b2o\$30bobo11bobo9bobo\$44b2o\$32b
obo23bobobo\$63b2o\$34bobo23bo\$62bo\$36bobo21bo\$63b2o\$38bobo17bobobo2\$40b
obo13bobo2\$42bobo9bobo2\$44bobo5bobo2\$46bobobobo2\$48bo2bo\$50bo\$46bobobo
2\$44bobo2\$37b2o3bobo\$37bo\$38bobobo2\$36bobobo\$34bobobo\$3b2o2b2o23bobobo
\$3bobo2bo\$7bo17b2o3bobobo\$4bo20bo9bo\$3bo2bobo17bobobo3b2o\$3b2o\$8bobo
13bobobo\$22bobobo\$10bobo7bobobo2\$12bobo3bobobo2\$14bobobo3bobo\$47b2o4b
2o\$12bobobo7bobo20bo4bobo\$10bobobo23b2o8bobo\$8bobobo13bobo10bo12bo\$36b
obo10bo\$b2o3bobobo17bobo20bobo\$bo9bo22bobo10bobo4bo\$2bobobo3b2o18bobo
14b2o4b2o\$34bo\$obobo26bo\$obo30bobo\$o28bobo\$35bobo10b2o2b2o\$27bobo18bob
o2bo\$26bo10bobo12bo\$26b2o10b2o9bo\$48bo2bobo\$48b2o2b2o!
``````

hkoenig
Posts: 132
Joined: June 20th, 2009, 11:40 am

### Re: Enumerating Still Lifes (in C)

A while back I played around with coming up with a sort of grammar for P2 oscillators. Turns out it's a lot harder and complicated that I expected, as there are lots of different ways to put various parts together. What I've got is not in any shape for any sort of publication, but here's a sample of some of the ways various parts can be combined. It appears you've found a couple of new ways (like the 1-2-3-2-1 diamond in the lower left) that don't appear here, too.

And I just did an update to my object database files...

Code: Select all

``````x=273, y=279, rule=B3/S23
39bo\$37bobo\$41bo\$36b6o\$34bo\$32bobo3b2o\$30bo9bo15bo\$28bobo6bo16bobo\$38b2o13b
o4bo58bo\$26b2o25b5o16b2o39bobo\$25bo32bo14bobo43bo\$55b2o18bob3o7bo26b6o16b
o\$23b2o30bobo14b2obo2b3o4bobo24bo23bobo\$22bo52bo13bo22bo3b2o16bo4bo\$20bo34b
o18bo9b6o21bo6bo16b5o\$20bo33bo21bo5bo26bo5bo17bo\$19bo34bo22bo4bo3b2o21bo6b
2o8b2o3b2o4bo\$17bo34bo24bo3bo6bo19bo17bobo7b2o26bo\$17bo33bo20b2o5bo5bo44b
o5b2o26bobo\$5bo10bo34bo22bo5bo5b2o11bo6b2o18bo2bo6bo25bo4bo\$4b2o8bo34bo21b
o6bo3bo15b2o5bo21bo3bo15b2o14b5o\$4b2o6bobo32b2o23b2o3bo4bo15b2o27bo4b2o13b
obo9bobo\$4bo5bo66bo5bo14bo4b2o54bo5bo\$8bobo35bo23b6o9bo16bo31bo14bobo3bob
o6b2o37b2o\$2b5o37b2o24bo13bo11b5o29bo3bobo18bo8b2o38bo2bo\$2bo4bo64bobo4b3o2b
ob2o8bo4bo27bo2bobo16bobo10bo20bo15b2obobobo\$3bobo37bo28bo7b3obo12bobo29b
o2bobob2o45bobo18bo2bo\$5bo38bo39bobo12bo31bo2bo16bo35bo14bobo\$42b3o39b2o48b
2o46b6o15bo\$150b2o28bo\$41b6o131bobo3b2o15b2o\$46bo102bo26bo9bo\$42bobo129bob
o6bo17bo\$44bo103b2o22bo11b2o17b2o\$171bobo27bo2bo\$117bo29bo23bo32bob2o\$116b
obo53b2o27b2obob2o\$117bo28b2o27bo28bo65bo\$175bobo24b3o4b2o48b2o8bobo\$115b
5o28bo30bo29b2o48b2o9bo\$68b2o28b2o14bo4bo59bobo19b2o14bo4bo4bo4bo9bo9bo\$68b
2o28b2o12bo2bobo30b2o33bo23b6o3bobo2bobo2bobo2bobo7bobo7bobo3b6o5b5o\$79bo9b
o20bobo4bo65bobo16bo4bo4bo4bo4bo4bo4bo9bo9bo4bo4bo4bo4bo\$66b6o5b2o8bobo6b
6o6bo41bo36bo16bo5bobobo5bobobo5bobobobobobobobobobobobobo5bobobobo2bobo\$66b
o4bo7b2o7bobo5bo4bo4bobo78bobob2o11bobobobo3bobobobo3bobobobo3bo5bo3bo5bo3b
obobobo3bo4bo\$64bobobo5bo3bo5bo3bo5bobobo5bo45b2o40bo44bo9bo\$62bobo3bobob
obo7bobo7bobo3bobobobo86bo44bobo7bobo\$50bo3bobobobo15b5o5b5o61bo84bo9bo\$48b
obobobo5bo20bo9bo59bo38bobo\$16bo3bobobobo3bobobobo3bobobobo5bo4bo19bobo7b
obo61b2obobo31bo2b2o\$3bo10bobobobo5bobobo5bobobo5bo5b6o21bo7bo2bo65bo29bob
o\$2b2o8bo5bo4bo4bo4bo4bo4bo44b2o68bobo7bo7bo7bo\$2b2o6bobo5b6o4b6o4b6o10b2o104b
o5bobo5bobo5bobo\$2bo5bo45b2o106bobo5bobo5bobo\$6bobo11b2o8b2o8b2o122bo7bo7b
o\$5o15b2o8b2o8b2o\$o4bo\$bobo\$3bo4\$149bo\$149bobo\$140bo6bo4bo\$140bobo5b5o\$138b
o5bobo74bobo\$144bo5bo68bo2bo2bo\$137b2o10b2o66bo2bobobo2bo\$149b2o67bobobob
obo2bo\$71b2o15bo50bo9bo66b3obobobobobo2bo\$6b2o62bobo13bobobo128bo2bobobob
obo\$5bobo64bob3o7bobobo43bo6b2o41bo32b4o3bobobobob3o\$7bob3o57b2obo2b3o4bo2b
2obob2o40bobo45bobo16bobo21bo3b2o\$4b2obo2b3o59bo9bo5bo41bo5bobo45bo15bo2b
o10b5o10b5o\$7bo14b2o47bo9bo6b2o46bo42b6o12b2obobo16bo9bo\$6bo12bo2bo50bo5b
o39bo9b2o46bo22bob3o10b5o10b5o\$8bo8bo2bobob2o48bo4bo39bobo53bobo3b2o15bob
o19b2o3bo\$17bo2bobo51bo3bo38bo13bo41bo9bo15bob5o10b3obobobobo3b4o\$8b2o8bo3b
obo44b2o5bo40b6o48bobo6bo19bo17bobobobobo2bo\$22bo48bo5bo46bo6b2o36bo11b2o18b
6o10bo2bobobobobob3o\$10bo57bo6bo3bo39b2o3bobo37b2obobo49bo2bobobobobo\$20b
2o47b2o3bo4bo38bo9bobo33bo36b5o15bo2bobobo2bo\$10b2o62bo5bo40bo6bo36bo34bo22b
o2bo2bo\$20bo46b6o46b2o79b5o20bobo\$12bo29b2o10b2o11bo13b2o65bo15bobo10bo\$18b
2o22bo10bobo13bobo11bo62bobo15b2o2bo8b2o19b6o\$12b2o29bobo23bo75bo4bo17bob
o6b2o18bo\$18bo32bobo30b2o58bob4o22bo5bo18b6o\$14bo30bobo95bobo4bo21bobo\$16b
obo30bobo33bo57bobob2o27b5o18b3o\$12bobo32bo92b2obobobobo25bo4bo18bo\$18bob
o30bo34b2o51bobobobobo29bobo22bo\$10bobo32b2o89bo2bobobobo31bo20bo3bobo\$9b
o10bobo28b2o34bo47bobobobobo53bo2bobobobo\$9b2o10b2o22bo43bo42bo2bobobobo55b
o2bobobobobo\$50bo37bo39b2obobobobobo59bo2bobobobobo\$43b2o38b3o2bob2o35bob
obobobobo64b2o2bobobobo\$49b2o33b3obo35bo2bobobobobo70bobobobobo\$44bo43bob
o31bo2bobobobobo73bo2bobobobo\$48bo39b2o32bo2bobobobo78bobobobobo\$44bobo2b
o73bo3bobo81b2obobobobo\$48b2o15bo61bo86bobob2o\$42bobo20bobo146bobo4bo\$63b
o61b2o88bob4o\$40bobo20b6o147bo4bo\$40b2o83bo91bobo\$65b3o151bo\$65bo57b2o\$66b
o\$123bo\$64b2o\$63bo57b2o42bo\$163bobobo\$61b2o58bo39bobobobobo\$57b2obo98bobob
obobobobo\$57bo61b2o36bobobo2bo2bobobobo\$58bo99b2obo5b2o2bobobo\$119bo36bo3b
o10bob2o\$53b2obobo58bo39b3o12bo3bo25b2o5b2o\$53bo3b2o56bo2bo36bo17b3o28bo4b
obo\$54bo58bo2bobo2b3o32b2o19bo23bo4b2obobo\$111bo2bobobob3o31bo3bo16b2o25b
2o3bobobob2o\$49b2obobo54bo2bobobobo36b3o16bo3bo28bobobobobo\$49bo3b2o52bo2b
obobobobo34bo21b3o22b6o3bobobobo2b2o\$50bo54bo2bobobobob2o36b2o23bo20bo10b
obobobobo2bo\$103bo2bobobo2bo38bo3bo20b2o22b4o8bobobobobo2bo\$45b2obobo50bo2b
obobobo42b3o20bo3bo34bobobobo2bo\$45bo3b2o48bo2bobobo2bo41bo24b4o19b5o13bob
o3bo\$46bo50bo2bobobobo45b4o24bo17bo20bo\$98bobobob2o45bo3bo20b3o19b5o19bo\$45b
obob2o13bo19bo11b3obobo50b2o20bo3bo40b3o\$45b2o3bo11bobo19bobo13bobo49bo23b
2o18b6o\$49bo16bo15bo12b5obo52b3o21bo16bo23b6o\$61b6o15b6o12bo52bo3bo16b3o18b
6o23bo\$45b2obobo45bobo56b2o16bo3bo40b6o\$45bo3b2o11b3o19b3o11bo55bo19b2o21b
3o\$46bo17bo19bo71b3o17bo20bo19b5o\$63bo21bo69bo3bo12b3o25bo20bo\$45bobob2o60b
o45b2obo10bo3bo20bo3bobo13b5o\$45b2o3bo12bobob2o11b2obobo25bobo42bobobo2b2o5b
ob2o21bo2bobobobo\$49bo13b2o3bo5bo5bo3b2o23bo4bo43bobobobo2bo2bobobo20bo2b
obobobobo8b4o\$67bo5bobo5bo28b5o45bobobobobobobo24bo2bobobobobo10bo\$45b2ob
obo22bobo33bo52bobobobobo29b2o2bobobobo3b6o\$45bo3b2o16bobob2obob2obobo29b
2o34bo16bobobo35bobobobobo\$46bo20b2o3bobobo3b2o28bobo32bobo18bo38b2obobob
o3b2o\$71bo2bo2bo66bo4bo58bobob2o4bo\$45bobob2o22bobo36bo31b5o59bobo4bo\$45b
2o3bo60bo3b2o32bo59b2o5b2o\$49bo61b2obobo29b2o\$146bobo\$45b2obobo65bo6bo\$45b
o3b2o64bo3b2obobo21bo\$46bo68b2obobobobo2bo14b2o3bo\$120bobobobobo13bobob2o\$44b
2o76bobobobo2bo39bobo\$43bo80bobobobobo9bo29bo2bo70bo\$34b2o90bobobobo2b2ob
2o3bo25b2obobo3b2o\$33bobo5b2o85bobobobobobobob2o28bob2obobo\$35bob2obo45bo43b
obobobobo31bobo\$32b2obobo48bobo43bobobo34b2o6bo\$35bo2bo32b2o13bobobo43bo43b
o3b2o\$34bobo33bobo105b2obobo\$88bobobo\$68bobo112bo\$87bobo2bobo55bo31bo\$66b
obo79bobo31b3o51bo\$86bobo5bobo55bo81bobobo\$64bobo80b6o29b4o46bobobo\$60bo24b
obo8bobo82bo48bo2b2obob2o\$60bobobo32b2o49b3o31b5o43bo5bo\$60bo19b2o2bobo35b
o27bo78bo6b2o\$62bo17bo41bobo24bo32b4o41bo\$60bo2bo17bobobo34bo60bo45bo\$61b
2obo56b5o23bobob2o27b3o41bo\$60bo2bo19bobobo24b2o3bobo7bo21b2o3bo69bo\$62bo22b
obo24bo4bo5bo3bobob2ob2o17bo26b4o40bo\$61bo25bo25bobo5b2o9bob2o25bo17bo43b
o\$123b2o5bobo20bobob2obobo17b3o38bo\$56b2obobo50b3obobo3bo5bo2b2o20b2o3bob
obo2bo55bo\$56bo3b2o56bo7bobo28bo2bobobobo11b4o37bo3bo\$57bo62b5o34bo2bobob
o2bo7bo40bob3o\$46bo78bo35bo2bobobobo5bob3o38bo3bo\$46bo2b2ob2obobo63bobo39b
o2bobobo2bo2bobo42bo\$45bo2bobobo3b2o63bo2bo40bo2bobobobobo2bo41bo\$50bo2bo68b
2o43bo2bobobo2bo45bo\$45bobobobo117bo2bo2bo48bo\$45b2o124bobo25bob2o21bo\$197b
2o3bo23bo\$201bo25bo\$199bo27bo\$199bo29bo\$197bo32bo\$198b3o29bo13bo\$177bo18b
o35bo9bobobo\$177bobo17b5o31bo6bobobo\$175bo19bo37bo4bobobobob2o\$175b6o15b7o32b
2obobobobo\$194bo43bobobob2o\$177b3o15b9o32bobobobo\$43b2o132bo16bo43bobobob
2o3b2o\$44bo133bo17b9o35bobobobobo2bo\$41bobo151bo46bobobobobo\$123bo52b2o19b
2ob6o38bobobobob2o\$39b2ob3o76bobo51bo19bo2bobo45bobobo\$125bobo68b2o3b4o43b
obobo\$37b2o80b2o6bo45b2o19bo55bo\$69b2o58bo39b2obo22b3o3b3o\$10bo24b2o33bo49b
o48bo23bo4bobo\$8bobo56bobo59b2o39bo23b5ob3o\$7bo4bo20b2o63b2o21b2o70bo\$7b5o53b
2ob3o27bobob2ob2o21bo36b2obobo24b7o\$13bobo15b2o70bob2o15bo42bo3b2o23bo\$9b
o5bo47b2o35bo2bo20bobobobo35bo29b5o\$9b2o6bobo9b2o67bo3b2o20bo70bo\$9b2o8bo41b
2o30b2o3bo31bobo3bo24b2obobo30b3o\$10bo10bobo3b2o64bobobo38bobo22bo34bo\$23b
o35b2o71bobo5bo21bo3bobo29bo\$25b2o68bo44bobo55bo\$57b2o35bo2bo34bo24b2obob
o5bobo29bo\$24bo69b4o45b2o12bo3b2o33b2o3bo\$45bo9b2o74b2o25bo11bobo25bob2o\$23b
2o18bobo48b2o48bo\$11b2o34bobo3b2o39b2o37bo22bobo13bobob2ob2o\$13bo6bobo18b
2o6bo95b2o10b2o18bob2o\$10bo9bo30b2o80b2o20bo18bo2bo\$11b2o3bobo23bo102bo10b
5o11bo3b2o\$16bo33bo84bobo17bo4bo11bo\$9b6o28b2o92bo5bobo11bobo11bo\$9bo39b2o88b
obo15bo11bo\$11bobo30bo96bo3bobo21bo\$11bo34bobo119bo\$46bo100bobo16bo\$166bo\$149b
obo13bo\$163bo\$151bobo9bo\$72b2o88bo\$72bobob2ob2o72bobo4bo\$77bob2o79bo\$74bo2b
o77bobobo\$72bo3b2o\$72bo84bo\$71bo84bo2bo\$69bo86b4o\$69bo\$68bo15b2o70b2o\$83b
obo2bo67b2o\$63b2obobo16bobobo\$63bo3b2o13b2obo2bo\$64bo20bo\$84bo\$62bobo18bo\$60b
o2b2o\$55b2o3bo21b2o14b2o\$55bobobo37bobo\$81bo\$57bo35bobob2o\$56bo2bo20b2o11b
o\$56b4o29bobo7b2o\$79bo9bo\$56b2o16b2o9bobo13b2o\$56b2o16bobob2o5bo\$81bobo19b
2o\$76bo4bo\$75bo2bo26b2o\$75b4o24bo4bo\$103b2o3bo\$75b2o32bo\$75b2o34bo\$111bo3b
2o\$112bobobo2\$114bo\$112bo2bo\$112b4o2\$114b2o\$114b2o!
``````