//Gabriel Nivasch
//October 14, 2007

#include <stdio.h>
#include <assert.h>

/*
This program simulates the photon/XOR system in time O(n log n),
based on the algorithm by Tomas Rokicki.
The initial configuration is specified by the arrays
start_left and start_right, and the photon direction start_dir.
The entries in start_left and start_right are listed from next to
the photon outwards.
The constant MAXGEN specifies how many generations to run.

The algorithm involves grouping the cells into "plateaus", which are
kept at different generations <= the current generation.

For a detailed description of the algorithm see my web page on
the photon/XOR system:

http://yucs.org/~gnivasch/life/photonXOR/index.html
*/

//Possible directions for the photon:
enum dir { LEFT, RIGHT };

//Number of generations to calculate:
const int MAXGEN = 1000;

//Size of the arrays start_left and start_right:
const int start_left_n  = 2;
const int start_right_n = 3;

//Initial condition of the system:
const bool start_left [start_left_n]  = {false, true};
const bool start_right[start_right_n] = {false, true, true};
const dir start_dir = RIGHT;

//After how many symbols to print a newline in the output:
const int out_newline_n = 5;

//The boolean array C is used to run the pattern.
//The left side of the pattern is kept from index left_pos leftwards.
//The right side of the pattern is kept from index right_pos rightwards.
//
//On each step, an extra cell is inserted to one of the two sides.
//This is done by doing left_pos++ or right_pos--.
//
//The first cell and the last cell of C are set OFF, and they also
//represent the infinitely many OFF cells which are farther away.

const int C_size = start_left_n + start_right_n + MAXGEN + 2;
bool C[C_size];

int left_pos, right_pos;

dir photon_dir; //Current direction of the photon
int gen; //Current generation

//Function prototypes:
void init();
int top_index(int);
void advance_side(dir);
void do_backtracking_side(dir);

//Initialize the array C, the indices left_pos and right_pos,
//and photon_dir:
void init()
{
	int i;
	
	C[0] = false; //This cell represents the infinitely many
		//OFF cells off to the left
	
	//Copy start_left into C:
	for (i=1; i <= start_left_n; i++)
		C[i] = start_left[start_left_n - i];
	
	//Initialize left_pos:
	left_pos = start_left_n;
	
	C[C_size - 1] = false; //This cell represents the infinitely
		//many OFF cells off to the right
		
	//Copy start_right into C:
	for (i=1; i <= start_right_n; i++)
		C[C_size - 2 - i] = start_right[start_right_n - i];
	
	//Initialize right_pos:
	right_pos = C_size - 2 - start_right_n;
	
	//Initialize photon direction:
	photon_dir = start_dir;
}

//Make index not larger than C_size-1 and not smaller than 0.
//Called by advance_side() and do_backtracking_side().
//This is used to create the illusion of infinitely many OFF cells
//to the sides.
int top_index(int index)
{
	if (index >= C_size)
		index = C_size - 1;
	if (index < 0)
		index = 0;
	return index;
}

//Advance the specified side from generation gen-1 to generation gen.
//This is done using the technique of plateaus.
void advance_side(dir d)
{
	int side_start = d==LEFT ? left_pos : right_pos;
	int sign = d==LEFT ? -1 : 1;
	int step, k, m;
	int ind1, ind2, ind3;
	
	//Do triple XORs to as many plateaus as gen has trailing zeros
	//in binary:
	for (k = gen, step = 1; k%2 == 0; k /= 2, step *= 2)
		for (m=0; m<step; m++)
		{
			ind1 = top_index(side_start + sign*(  step-1+m));
			ind2 = top_index(side_start + sign*(2*step-1+m));
			ind3 = top_index(side_start + sign*(3*step-1+m));
			
			C[ind1] = C[ind1] ^ C[ind2] ^ C[ind3];
		}
	
	//Do double XORs to the next plateau:
	for (m=0; m<step; m++)
		{
			ind1 = top_index(side_start + sign*(  step-1+m));
			ind2 = top_index(side_start + sign*(2*step-1+m));
			
			C[ind1] = C[ind1] ^ C[ind2];
		}
}

//Adjust the plateau boundaries on the specified side, because of the
//new cell that will be inserted (by doing left_pos++ or right_pos--).
void do_backtracking_side(dir d)
{
	int side_start = d==LEFT ? left_pos : right_pos;
	int sign = d==LEFT ? -1 : 1;
	int step;
	int ind1, ind2;
	
	//Do double XOR whenever gen has a 1 bit in binary:
	for (step = 1; step <= gen; step *= 2)
		if (gen & step)
		{
			ind1 = top_index(side_start + sign*(2*step - 2));
			ind2 = top_index(side_start + sign*(3*step - 2));
			
			C[ind1] = C[ind1] ^ C[ind2];
		}
}

int main()
{
	FILE *f = stdout;
	dir new_photon_dir;
	int i;
	
	//Call initialization:
	init();
	
	fprintf(f, "Starting configuration:\n");
	for (i = start_left_n - 1; i >= 0; i--)
		fprintf(f, "%c", start_left[i] ? '*' : '_');
	fprintf(f, "%c", start_dir==LEFT ? 'L' : 'R');
	for (i=0; i < start_right_n; i++)
		fprintf(f, "%c", start_right[i] ? '*' : '_');
	fprintf(f, "\n\n");
	
	fprintf(f, "First %d states of the photon:\n", MAXGEN);
	
	//Main loop:
	for (gen = 1; gen <= MAXGEN; gen++)
	{
		//Print L or R:
		fprintf(f, "%c", photon_dir==LEFT ? 'L' : 'R');
		if (gen % out_newline_n == 0)
			fprintf(f, "\n");
		
		assert(left_pos >= 0);
		assert(right_pos < C_size);
		assert(left_pos < right_pos);
		
		//Calculate new direction of photon:
		if (photon_dir==LEFT)
			new_photon_dir = C[left_pos]  ? RIGHT : LEFT;
		else
			new_photon_dir = C[right_pos] ? LEFT : RIGHT;
		
		//Calculate state of extra cell at left or right side:
		if (photon_dir==LEFT)
			C[right_pos - 1] = C[right_pos];
		else
			C[left_pos + 1] = C[left_pos];
		
		//Advance the left and right sides:
		advance_side(LEFT);
		advance_side(RIGHT);
		
		//Do backtracking to correct boundaries of plateaus
		//to account for extra cell:
		if (photon_dir==LEFT)
			do_backtracking_side(RIGHT);
		else
			do_backtracking_side(LEFT);
		
		//Adjust left_pos or right_pos to insert extra cll
		if (photon_dir==LEFT)
			right_pos--;
		else
			left_pos++;
			
		//Set new photon direction:
		photon_dir = new_photon_dir;
		
	} //for gen
	
	fprintf(f, "\nDone.\n");
}