## Patterns that invert themselves in the next generation

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
gameoflifeboy
Posts: 474
Joined: January 15th, 2015, 2:08 am

### Patterns that invert themselves in the next generation

I have been trying to find patterns where every cell in the bounding box changes state in the next generation. Here is what I have found for Life so far, including an infinite family:

Code: Select all

``````x = 87, y = 47, rule = LifeHistory
A9.2A8.2A.A6.A.A7.A2.A6.A2.A6.A2.A6.A2.A6.D2.D2.D\$23.A7.A9.2A8.2A8.2A
8.2A\$20.A9.A.A8.2A8.2A8.2A8.2A\$20.A.2A16.A2.A7.2A8.2A8.2A\$50.A2.A7.2A
8.2A\$60.A2.A7.2A\$70.A2.A4\$50.A3.A5.A3.A5.A3.A\$51.3A7.3A7.3A\$51.3A7.3A
7.3A\$51.3A7.3A7.3A\$50.A3.A6.3A7.3A\$60.A3.A6.3A\$70.A3.A4\$60.A4.A4.A4.A
\$61.4A6.4A\$61.4A6.4A\$61.4A6.4A\$61.4A6.4A\$60.A4.A5.4A\$70.A4.A4\$70.A5.A
\$71.5A\$71.5A\$71.5A\$71.5A\$71.5A\$70.A5.A4\$80.D3\$83.D3\$86.D!
``````

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Patterns that invert themselves in the next generation

Here is one:

Code: Select all

``````x = 4, y = 4, rule = LifeHistory
.2A\$4A\$4A\$.2A!
``````

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Patterns that invert themselves in the next generation

I've written a small search utility to find more examples, and there weren't any. Everything brought here is actually all there is (at least for what I've checked).

Here is the c code - it could be used for other stuff as well.

Code: Select all

``````#include <stdio.h>

#define M 6
#define N 6
#define YES 1
#define NO 0

void print(int arr[])
{
printf("\n\n\n");

for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
int val = arr[M * i + j];

if(val == 0)
printf(".");
if(val == 1)
printf("*");
if(val == 2)
printf("?");
}

printf("\n");
}

printf("\n\n\n");

}

int contradict(int x, int y, int evolved, int val)
{
if(x == 0 || y == 0 || x == M - 1 || y == N - 1)
{
if(evolved == 1 || val == 1)
return YES;

return NO;
}

if(evolved == 2 || val == 2)
return NO;

if(evolved == 1 - val)
return NO;

return YES;
}

int value(int arr[], int x, int y)
{
if(x < 0 || y < 0 || x >= M || y >= N)
return 0;

return arr[x + M * y];
}

int evolved(int arr[], int x, int y)
{
int cnt0 = 0;
int cnt1 = 0;
int cnt2 = 0;

for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
if(i == 0 && j == 0)
continue;

int val = value(arr, x + i, y + j);

if(val == 0)
cnt0++;
if(val == 1)
cnt1++;
if(val == 2)
cnt2++;
}
}

int curval = value(arr, x, y);

int min = cnt1;
int max = cnt1 + cnt2;

if(min >= 4)
return 0;

if(max < 2)
return 0;

if(min <= 3 && max > 3)
return 2;

if(min == 3 && max == 3)
return 1;

if(min == 2)
{
if(max == 3)
{
if(curval == 1)
return 1;
else
return 2;
}
if(max == 2)
{
if(curval == 2)
return 2;
else
return curval;
}
}

if(max == 2 && curval == 0)
return 0;

return 2;

}

int contradict(int arr[], int x, int y, int val)
{

arr[x + M * y] = val;

for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
int ev = evolved(arr, x + i, y + j);
int val = value(arr, x + i, y + j);

if(contradict(x + i, y + j, ev, val) == YES)
return YES;
}
}

return NO;
}

int movexy(int *x, int *y)
{
if((*x) >= M - 2 && (*y) >= N - 2)
return NO;

(*x)--;
(*y)++;

if((*x) > 0 && (*y) < N - 1)
return YES;

(*x)++;

while((*y) > 1 && (*x) < M - 2)
{
(*x)++;
(*y)--;
}

return YES;
}

void recurse(int arr[], int x, int y)
{

//print(arr);
//getchar();

int initx = x;
int inity = y;

if(contradict(arr, x, y, 1) == NO)
{
if(movexy(&x, &y) == YES)
{
recurse(arr, x, y);
}
else
print(arr);
}

x = initx;
y = inity;

if(contradict(arr, x, y, 0) == NO)
{
if(movexy(&x, &y) == YES)
{
recurse(arr, x, y);
}
else
print(arr);
}

arr[initx + M * inity] = 2;

}

int main()
{
int arr[M * N];

for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(i == 0 || j == 0 || j == M - 1 || i == N - 1)
arr[j + M * i] = 0;
else
arr[j + M * i] = 2;
}
}

recurse(arr, 1, 1);
getchar();
return 0;
}
``````

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Patterns that invert themselves in the next generation

I've modified to search in HighLife rule, and in this rule there are much more interesting results.

Code: Select all

```#C [[ AUTOSTART GPS 1 ZOOM 4 WIDTH 480 LOOP 1 THEME 1 ]] x = 12, y = 72, rule = B36/S23 o5bo\$b5o\$b2ob2o\$bo2b2o\$b5o\$b5o\$o5bo14\$obo2b2o\$2bob4o\$8o\$2b5o\$b5o\$8o\$4o bo\$b2o2bobo13\$b2o2bo2b2o\$4obob4o\$11o\$b2o2b5o\$2bob5o\$11o\$2b5obo\$b5o2b2o \$11o\$4obob4o\$b2o2bo2b2o10\$obo2b2o2bobo\$2bob4obo\$12o\$2bo2b2o2bo\$b2ob4ob 2o\$12o\$12o\$b2ob4ob2o\$2bo2b2o2bo\$12o\$2bob4obo\$obo2b2o2bobo!```

Code: Select all

``````#include <stdio.h>
#include <time.h>

#define M 10
#define N 10
#define YES 1
#define NO 0

void print(int arr[])
{
printf("\n\n\n");

for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
int val = arr[M * i + j];

if(val == 0)
printf(".");
if(val == 1)
printf("*");
if(val == 2)
printf("?");
}

printf("\n");
}

printf("\n\n\n");

}

int contradict(int x, int y, int evolved, int val)
{
if(x == 0 || y == 0 || x == M - 1 || y == N - 1)
{
if(evolved == 1 || val == 1)
return YES;

return NO;
}

if(evolved == 2 || val == 2)
return NO;

if(evolved == 1 - val)
return NO;

return YES;
}

int value(int arr[], int x, int y)
{
if(x < 0 || y < 0 || x >= M || y >= N)
return 0;

return arr[x + M * y];
}

int evolved(int arr[], int x, int y)
{
int cnt0 = 0;
int cnt1 = 0;
int cnt2 = 0;

for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
if(i == 0 && j == 0)
continue;

int val = value(arr, x + i, y + j);

if(val == 0)
cnt0++;
if(val == 1)
cnt1++;
if(val == 2)
cnt2++;
}
}

int curval = value(arr, x, y);

int min = cnt1;
int max = cnt1 + cnt2;

if(min >= 7)
return 0;

if(min == 6)
{
if(max == 6)
return 1;

return 2;
}

if(min == 5)
{
if(max == 5)
return 0;

return 2;
}

if(min == 4)
{
if(max <= 5)
return 0;

return 2;
}

if(max < 2)
return 0;

if(min <= 3 && max > 3)
return 2;

if(min == 3 && max == 3)
return 1;

if(min == 2)
{
if(max == 3)
{
if(curval == 1)
return 1;
else
return 2;
}
if(max == 2)
{
if(curval == 2)
return 2;
else
return curval;
}
}

if(max == 2 && curval == 0)
return 0;

return 2;

}

//n is the last index of the array
int contradict(int arr[], int x, int y, int val)
{

arr[x + M * y] = val;

for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
int ev = evolved(arr, x + i, y + j);
int val = value(arr, x + i, y + j);

if(contradict(x + i, y + j, ev, val) == YES)
return YES;
}
}

return NO;
}

int movexy(int *x, int *y)
{
if((*x) >= M - 2 && (*y) >= N - 2)
return NO;

(*x)--;
(*y)++;

if((*x) > 0 && (*y) < N - 1)
return YES;

(*x)++;

while((*y) > 1 && (*x) < M - 2)
{
(*x)++;
(*y)--;
}

return YES;
}

void recurse(int arr[], int x, int y)
{

//print(arr);
//getchar();

int initx = x;
int inity = y;

if(contradict(arr, x, y, 1) == NO)
{
if(movexy(&x, &y) == YES)
{
recurse(arr, x, y);
}
else
print(arr);
}

x = initx;
y = inity;

if(contradict(arr, x, y, 0) == NO)
{
if(movexy(&x, &y) == YES)
{
recurse(arr, x, y);
}
else
print(arr);
}

arr[initx + M * inity] = 2;

}

int main()
{
int arr[M * N];

for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(i == 0 || j == 0 || j == M - 1 || i == N - 1)
arr[j + M * i] = 0;
else
arr[j + M * i] = 2;
}
}

clock_t begin, end;
double time_spent;

begin = clock();

recurse(arr, 1, 1);

end = clock();

printf("Total time = %f", (double)(end - begin) / CLOCKS_PER_SEC);
getchar();
return 0;
}
``````

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Patterns that invert themselves in the next generation

Here is an oscillator (p2) in some totalistic rule with this property in both phases:

Code: Select all

```#C [[ AUTOSTART GPS 2 ZOOM 16 WIDTH 480 THEME 1 ]] x = 9, y = 10, rule = B345678/S bobobobo\$2ob3ob2o2\$2ob3ob2o\$bobobobo\$bobobobo\$2ob3ob2o2\$2ob3ob2o\$bobob obo!```
And it can easily be expanded in trivial ways in any direction.

EDIT Here is another infinite family:

Code: Select all

```#C [[ AUTOSTART GPS 1 ZOOM 16 WIDTH 480 THEME 1 ]] x = 15, y = 15, rule = B345678/S obobobobobobobo\$2bobobobobobo\$3obobobobob3o\$4bobobobo\$5obobob5o\$6bobo\$ 7ob7o2\$7ob7o\$6bobo\$5obobob5o\$4bobobobo\$3obobobobob3o\$2bobobobobobo\$obo bobobobobobo!```
And here are results for 6x6 of modified search for such oscilators:

Code: Select all

```#C [[ AUTOSTART GPS 1 ZOOM 3 WIDTH 480 THEME 1 ]] x = 6, y = 276, rule = B345678/S obobo\$2bob2o\$4o\$2bob2o\$2obo\$bobobo5\$obobo\$2bob2o\$4o\$3b3o\$2obo\$bobobo5\$ obobo\$2bob2o\$4o\$4b2o\$2obo\$bobobo5\$obobo\$2bob2o\$3o\$2b4o\$2obo\$bobobo5\$ob obo\$2bob2o\$3o\$2bob2o\$2obo\$bobobo5\$obobo\$2bob2o\$3o\$3b3o\$2obo\$bobobo5\$ob obo\$2bob2o\$3o\$4b2o\$2obo\$bobobo5\$obobo\$2bob2o\$2obo\$2b4o\$2obo\$bobobo5\$ob obo\$2bob2o\$2obo\$2bob2o\$2obo\$bobobo5\$obobo\$2bob2o\$2obo\$3b3o\$2obo\$bobobo 5\$obobo\$2bob2o\$2obo\$4b2o\$2obo\$bobobo5\$obobo\$2bob2o\$2o\$2b4o\$2obo\$bobobo 5\$obobo\$2bob2o\$2o\$2bob2o\$2obo\$bobobo5\$obobo\$2bob2o\$2o\$3b3o\$2obo\$bobobo 5\$bobobo\$2obo\$2b4o\$3o\$2bob2o\$obobo5\$bobobo\$2obo\$2b4o\$2obo\$2bob2o\$obobo 5\$bobobo\$2obo\$2b4o\$2o\$2bob2o\$obobo5\$bobobo\$2obo\$2bob2o\$4o\$2bob2o\$obobo 5\$bobobo\$2obo\$2bob2o\$3o\$2bob2o\$obobo5\$bobobo\$2obo\$2bob2o\$2obo\$2bob2o\$o bobo5\$bobobo\$2obo\$2bob2o\$2o\$2bob2o\$obobo5\$bobobo\$2obo\$3b3o\$4o\$2bob2o\$o bobo5\$bobobo\$2obo\$3b3o\$3o\$2bob2o\$obobo5\$bobobo\$2obo\$3b3o\$2obo\$2bob2o\$o bobo5\$bobobo\$2obo\$3b3o\$2o\$2bob2o\$obobo5\$bobobo\$2obo\$4b2o\$4o\$2bob2o\$obo bo5\$bobobo\$2obo\$4b2o\$3o\$2bob2o\$obobo5\$bobobo\$2obo\$4b2o\$2obo\$2bob2o\$obo bo!```

Code: Select all

``````#include <stdio.h>
#include <time.h>

#define M 8
#define N 8
#define YES 1
#define NO 0

void print(int arr[])
{
printf("\n");

for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
int val = arr[M * i + j];

if(val == 0)
printf(".");
if(val == 1)
printf("*");
if(val == 2)
printf("?");
}

printf("\n");
}

printf("\n");

}

int contradict(int x, int y, int evolved, int val)
{
if(x == 0 || y == 0 || x == M - 1 || y == N - 1)
{
if(evolved == 1 || val == 1)
return YES;

return NO;
}

if(evolved == 2 || val == 2)
return NO;

if(evolved == 1 - val)
return NO;

return YES;
}

int value(int arr[], int x, int y)
{
if(x < 0 || y < 0 || x >= M || y >= N)
return 0;

return arr[x + M * y];
}

int evolved(int arr[], int x, int y)
{
int cnt0 = 0;
int cnt1 = 0;
int cnt2 = 0;

for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
if(i == 0 && j == 0)
continue;

int val = value(arr, x + i, y + j);

if(val == 0)
cnt0++;
if(val == 1)
cnt1++;
if(val == 2)
cnt2++;
}
}

int curval = value(arr, x, y);

if(curval == 2)
return 2;

if(curval == 1)
return 0;

int min = cnt1;
int max = cnt1 + cnt2;

if(min >= 3)
return 1;

if(max < 3)
return 0;

return 2;

}

//n is the last index of the array
int contradict(int arr[], int x, int y, int val)
{

arr[x + M * y] = val;

for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
int ev = evolved(arr, x + i, y + j);
int val = value(arr, x + i, y + j);

if(contradict(x + i, y + j, ev, val) == YES)
return YES;
}
}

return NO;
}

int movexy(int *x, int *y)
{
if((*x) >= M - 2 && (*y) >= N - 2)
return NO;

(*x)--;
(*y)++;

if((*x) > 0 && (*y) < N - 1)
return YES;

(*x)++;

while((*y) > 1 && (*x) < M - 2)
{
(*x)++;
(*y)--;
}

return YES;
}

int oscp2(int arr[])
{
int arr1[M * N];

for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(i == 0 || j == 0 || j == M - 1 || i == N - 1)
arr1[j + M * i] = 0;
else
arr1[j + M * i] = evolved(arr, i, j);
}
}

for(int i = 1; i < N - 1; i++)
{
for(int j = 1; j < M - 1; j++)
{
if(evolved(arr1, i, j) != arr[j + M * i])
return NO;
}
}

return YES;
}

void recurse(int arr[], int x, int y)
{

//print(arr);
//getchar();

int initx = x;
int inity = y;

if(contradict(arr, x, y, 1) == NO)
{
if(movexy(&x, &y) == YES)
{
recurse(arr, x, y);
}
else
{
if(oscp2(arr))
{
print(arr);
//getchar();
}
}
}

x = initx;
y = inity;

if(contradict(arr, x, y, 0) == NO)
{
if(movexy(&x, &y) == YES)
{
recurse(arr, x, y);
}
else
{
if(oscp2(arr))
{
print(arr);
//getchar();
}
}
}

arr[initx + M * inity] = 2;

}

int main()
{
int arr[M * N];

for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(i == 0 || j == 0 || j == M - 1 || i == N - 1)
arr[j + M * i] = 0;
else
arr[j + M * i] = 2;
}
}

clock_t begin, end;
double time_spent;

begin = clock();

recurse(arr, 1, 1);

end = clock();

printf("Total time = %f", (double)(end - begin) / CLOCKS_PER_SEC);
getchar();
return 0;
}

``````
EDIT2 Chess board stabilized:

Code: Select all

```#C [[ AUTOSTART GPS 1 ZOOM 16 WIDTH 480 THEME 1 ]] x = 13, y = 13, rule = B345678/S obobobobobobo\$2bo3bo3bo\$13o\$2bobobobobo\$ob2obobob2obo\$2bobobobobo\$4obo bob4o\$2bobobobobo\$ob2obobob2obo\$2bobobobobo\$13o\$2bo3bo3bo\$obobobobobob o!```

unname66609
Posts: 87
Joined: December 20th, 2014, 8:30 am

### Re: Patterns that invert themselves in the next generation

x = 12, y = 12, rule = B3/S23
2o3b2o3b2o\$obobo2bobobo\$b2obo2bob2o\$4b4o\$b3o4b3o\$o2bob2obo2bo\$o2bob2ob
o2bo\$b3o4b3o\$4b4o\$b2obo2bob2o\$obobo2bobobo\$2o3b2o3b2o!

dvgrn
Moderator
Posts: 7842
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Patterns that invert themselves in the next generation

unname66609 wrote:x = 12, y = 12, rule = B3/S23
2o3b2o3b2o\$obobo2bobobo\$b2obo2bob2o\$4b4o\$b3o4b3o\$o2bob2obo2bo\$o2bob2ob
o2bo\$b3o4b3o\$4b4o\$b2obo2bob2o\$obobo2bobobo\$2o3b2o3b2o!
In B3/S23 this is a stable pattern. All the other patterns on this thread are rectangles where every cell turns OFF in generation 1 if it's ON in generation 0, and vice versa.

It's common practice around here to use code blocks around pattern RLE. Just select your pattern and click the "Code" button.

Just thought of a possible generalization of these self-inverting patterns. Are there any shapes other than a bounding rectangle that might contain interesting patterns? Would have to exclude silly complex shapes, or else any instant-death pattern would count... It's easy to come up with a convex Conway's Life pattern that inverts --

Code: Select all

``````x = 20, y = 9, rule = LifeHistory
15.B\$3.B9.B3AB\$.B3AB6.B5AB\$.5A6.7A\$B5AB4.B7AB\$.5A6.7A\$.B3AB6.B5AB\$3.B
9.B3AB\$15.B!``````
-- but I don't think diamond shapes are any good (for example).

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Patterns that invert themselves in the next generation

Regarding the inversion (or twice inverting p2) I can prove the following theorems:

1. In any B1* or B2* rules there are no such p2s.
2. Any such p2 oscillator must be B3*
3. If some pattern inverts in some totalistic rule it also inverts in B345678/S.
4. Trivially from #3: any such p2 in any totalistic rule is also p2 in B345678/S.

I actually didn't took the effort to deduce all rules that support such p2 from all the found 6x6 p2s in B345678/S. But I can say there is no such p2 in Life or any B3/S* rule.

---

This is fun small problem that interestingly enough can be reduced to single rule search.

EDIT @dvgrn regarding the shape question - if we will be looking into 100% volatility p2 without "empty internal islands" inside the "trace", I think it's the best "expanded" question in order to remove bounding box constrain. Anyway inversion and S* is actually not that interesting as the S is actually additional constrain that only limits the options of such oscillators.

I mean regarding this specific problem - GOL is just not such interesting rule to explore in.

unname66609
Posts: 87
Joined: December 20th, 2014, 8:30 am

### Re: Patterns that invert themselves in the next generation

simsim314 wrote:Regarding the inversion (or twice inverting p2) I can prove the following theorems:

1. In any B1* or B2* rules there are no such p2s.
2. Any such p2 oscillator must be B3*
3. If some pattern inverts in some totalistic rule it also inverts in B345678/S.
4. Trivially from #3: any such p2 in any totalistic rule is also p2 in B345678/S.

I actually didn't took the effort to deduce all rules that support such p2 from all the found 6x6 p2s in B345678/S. But I can say there is no such p2 in Life or any B3/S* rule.

---

This is fun small problem that interestingly enough can be reduced to single rule search.

EDIT @dvgrn regarding the shape question - if we will be looking into 100% volatility p2 without "empty internal islands" inside the "trace", I think it's the best "expanded" question in order to remove bounding box constrain. Anyway inversion and S* is actually not that interesting as the S is actually additional constrain that only limits the options of such oscillators.

I mean regarding this specific problem - GOL is just not such interesting rule to explore in.

Code: Select all

``````x = 8, y = 8, rule = LifeHistory
3.AB\$2.BABA\$.A4.B\$2B4.2A\$2A4.2B\$.B4.A\$2.ABAB\$3.BA!
``````