Page 1 of 1
Patterns that invert themselves in the next generation
Posted: February 11th, 2015, 5:15 pm
by gameoflifeboy
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!
Re: Patterns that invert themselves in the next generation
Posted: February 11th, 2015, 7:29 pm
by simsim314
Here is one:
Code: Select all
x = 4, y = 4, rule = LifeHistory
.2A$4A$4A$.2A!
Re: Patterns that invert themselves in the next generation
Posted: February 12th, 2015, 8:46 pm
by simsim314
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;
}
Re: Patterns that invert themselves in the next generation
Posted: February 13th, 2015, 4:21 am
by simsim314
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;
}
Re: Patterns that invert themselves in the next generation
Posted: February 13th, 2015, 9:07 am
by simsim314
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!
Re: Patterns that invert themselves in the next generation
Posted: February 15th, 2015, 8:22 am
by unname66609
x = 12, y = 12, rule = B3/S23
2o3b2o3b2o$obobo2bobobo$b2obo2bob2o$4b4o$b3o4b3o$o2bob2obo2bo$o2bob2ob
o2bo$b3o4b3o$4b4o$b2obo2bob2o$obobo2bobobo$2o3b2o3b2o!
Re: Patterns that invert themselves in the next generation
Posted: February 15th, 2015, 2:11 pm
by dvgrn
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).
Re: Patterns that invert themselves in the next generation
Posted: February 15th, 2015, 3:48 pm
by simsim314
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.
Re: Patterns that invert themselves in the next generation
Posted: February 15th, 2015, 7:45 pm
by unname66609
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!