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

int random(int n)
{
	return rand() % n;
}

#define SIZE 100

int maze[SIZE][3];
int L[SIZE*3];
int R[SIZE*3];
bool end[SIZE*3];

#define UNDEFINED -1

void generate_maze(int n)
{
	for (int i = 0; i < n; i++)
	{
		maze[i][0] = UNDEFINED;
		maze[i][1] = UNDEFINED;
		maze[i][2] = UNDEFINED;
	}
	
	// make first connection
	{
		maze[0][0] = 0;
		
		int k = random(n);
		if (k == 0)
			maze[0][1] = 1;
		else
			maze[1][0] = 1;
	}
	
	int l = 1;
	for (int empty_places = n * 3 - 2; empty_places > 0;)
	{
		// find a node with a free place
		int i1, j1;
		for (i1 = 0; i1 < n; i1++)
			if (maze[i1][0] != UNDEFINED && maze[i1][2] == UNDEFINED)
				break;
		if (maze[i1][1] == UNDEFINED)
			j1 = 1;
		else
			j1 = 2;
		maze[i1][j1] = 2*l;
		//printf("maze[%d][%d] = %d ", i1, j1, l);
			
		// find another node with
		int i2, j2;
		do
		{
			i2 = random(n);
			//printf(" i2 = %d ", i2);
		} while (maze[i2][2] != UNDEFINED);
		while (maze[i2][0] == UNDEFINED && maze[i2-1][0] == UNDEFINED)
			i2--;
		
		if (maze[i2][0] == UNDEFINED)
			j2 = 0;
		else if (maze[i2][1] == UNDEFINED)
			j2 = 1;
		else
			j2 = 2;
		maze[i2][j2] = 2*l + 1;
		//printf(" maze[%d][%d] = %d ", i2, j2, l);
		
		//printf("e = %d ", empty_places);
		if (empty_places == 2)
			break;
			
		bool can_go_next = false;
		for (int i = 0; i < n; i++)
			if (maze[i][0] != UNDEFINED && maze[i][2] == UNDEFINED)
			{
				can_go_next = true;
				break;
			}
		
		if (!can_go_next)
		{
			//printf(" go back\n");
			maze[i1][j1] = UNDEFINED;
			maze[i2][j2] = UNDEFINED;
		}
		else
		{
			//printf(" okay\n");
			empty_places -= 2;
			l++;
		}
	}
	
	for (int i = 1; i < n; i++)
	{
		if (random(2) == 1)
		{
			int h = maze[i][1];
			maze[i][1] = maze[i][2];
			maze[i][2] = h;
		}
	}
}

void print_maze(int n)
{
	for (int i = 0; i < n; i++)
		printf("%2d %2d %2d\n", maze[i][0]/2, maze[i][1]/2, maze[i][2]/2);
	printf("\n");
}

int reverse(int i)
{
	return (i & ~1) | (~i & 1);
}

void fill_LR(int n)
{
	for (int i = 0; i < n; i++)
	{
		int v0 = maze[i][0];
		int v1 = maze[i][1];
		int v2 = maze[i][2];
		int w0 = reverse(v0);
		int w1 = reverse(v1);
		int w2 = reverse(v2);
	
		L[v0] = w1;
		L[v1] = w2;
		L[v2] = w0;
		
		R[v0] = w2;
		R[v1] = w0;
		R[v2] = w1;
	}

	for (int i = 0; i < n*3; i++)
		end[i] = false;
	end[maze[0][0]] = true;		
	end[maze[0][1]] = true;		
	end[maze[0][2]] = true;		
}

void check_LR(int n)
{
	for (int i = 0; i < n; i++)
	{
		if (   reverse(L[reverse(R[i])]) != i
		    || reverse(R[reverse(L[i])]) != i
		    || reverse(L[reverse(L[reverse(L[i])])]) != i
		    || reverse(R[reverse(R[reverse(R[i])])]) != i)
		    printf("error %d\n", i);
	}
}

void print_LR(int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%2d: %2d %2d %s\n", i, L[i], R[i], end[i] ? "end" : "");
	}
	printf("\n");
}

int min[SIZE*3];

void print_LR_min(int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%2d (%2d): %2d (%d)  %2d (%d)\n", i, min[i], L[i], min[L[i]], R[i], min[R[i]]);
	}
	printf("\n");
}

void calculate_min(int n)
{
	for (int i = 0; i < n; i++)
		min[i] = end[i] ? 0 : n;

	for (bool modified = true; modified;)		
	{
		print_LR_min(n);
		printf("--\n");
		modified = false;
		for (int j = 0; j < n; j++)
		{
			int m = min[L[j]] + 1;
			if (m < min[j])
			{
				min[j] = m;
				modified = true;
			}
			m = min[R[j]] + 1;
			if (m < min[j])
			{
				min[j] = m;
				modified = true;
			}
		}
	}
}


void solve_straight(int n)
{
	int pos[3*SIZE];
	
	for (int i = 0; i < n; i++)
		pos[i] = i;
		
	for (;;)
	{
		// Count number at end position
		int at_end = 0;
		for (int i = 0; i < n; i++)
			if (end[pos[i]])
				at_end++;
		if (at_end == n)
			break; // -- we are done

		// Evaluate left and right
		int min_L = n;
		int nr_at_min_L = 0;
		int left_L = 0;
		int min_R = n;
		int nr_at_min_R = 0;
		int left_R = 0;
		for (int i = 0; i < n; i++)
			if (!end[pos[i]])
			{
				int m = min[L[pos[i]]];
				if (m < min_L)
				{
					min_L = m;
					nr_at_min_L = 1;
				}
				else if (m == min_L)
					nr_at_min_L++;
				left_L += m;
				m = min[R[pos[i]]];
				if (m < min_R)
				{
					min_R = m;
					nr_at_min_R = 1;
				}
				else if (m == min_R)
					nr_at_min_R++;
				left_R += m;
			}

		// make selection
//		if (   min_L < min_R
//		    || (min_L == min_R && random(2) == 0))
//		if (   min_L < min_R
//		    || (min_L == min_R && left_L < left_R)
//		    || (min_L == min_R && left_L == left_R && random(2) == 0))
		if (   min_L < min_R
		    || (min_L == min_R && nr_at_min_L > nr_at_min_R)
		    || (min_L == min_R && nr_at_min_L == nr_at_min_R && random(2) == 0))
		{
			printf("L");
			for (int i = 0; i < n; i++)
			{
				if (!end[pos[i]])
					pos[i] = L[pos[i]];
				//printf(" %2d", pos[i]);
			}
		}	
		else
		{
			printf("R");
			for (int i = 0; i < n; i++)
			{
				if (!end[pos[i]])
					pos[i] = R[pos[i]];
				//printf(" %2d", pos[i]);
			}
		}
		//printf("\n");
	}
	printf("\n");
}

int main(int argc, char *argv[])
{
	srand(time(0));
	int n = 100;
	generate_maze(n);
	print_maze(n);
	fill_LR(n);
	n = n * 3;
	check_LR(n);
	print_LR(n);
	calculate_min(n);
	print_LR_min(n);
	for (int x = 0; x < 50; x++)
		solve_straight(n);
	return 0;
}