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!