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....
which should already have occurred.
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!
For exactly the reasons you mention 