/*
 * Lights Out game using a shift-register
 * Test of principle.
 *
 * Code donated to the public domain
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

//#define SIMULATE	100000
//#define PRINTWHOLESHIFTREG

#define N		8
#define NELEM(x)	(sizeof(x)/sizeof((x)[0]))
#define val_at(r,c)	shiftreg[(((r)+(N-1))%N)*N+(((c)+(N-1))%N)]
#define is_set(r,c)	(val_at(r,c) & 1)

static int shiftreg[N*N];
static const int maskreg[2*N+1] = { 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1 };


static inline char set_char(int r, int c)
{
	if(r < 1 || r > 5 || c < 1 || c > 5)
		return is_set(r, c) ? 's' : 'u';
	else
		return is_set(r, c) ? '1' : '0';
}

static void print_reg(void)
{
	int i, j;
#ifdef PRINTWHOLESHIFTREG
	printf("  0 a b c d e 6 7\n");
	for(i = 0; i < N; i++) {
		printf("%d ", i);
		for(j = 0; j < N; j++) {
			printf("%c ", set_char(i, j));
		}
		printf("\n");
	}
#else
	printf("  a b c d e\n");
	for(i = 1; i < 6; i++) {
		printf("%d ", i);
		for(j = 1; j < 6; j++) {
			printf("%d ", is_set(i, j));
		}
		printf("\n");
	}
#endif
	printf("\n");
}

/* Perform one shift and put the last bit into the first */
static void shift(int n)
{
	int i;
	for(i = 0; i < n; i++) {
		int tmp = shiftreg[(N-1)*N+N-1];
		memmove(&shiftreg[1], &shiftreg[0], (N*N-1) * sizeof(shiftreg[0]));
		shiftreg[0] = tmp;
	}
}

/* Button push at (r,c) */
static void button(int r, int c)
{
	int i, n;
	shift(n = (N*N - (r*N+c)));
	for(i = 0; i < NELEM(maskreg); i++) {
		int tmp = shiftreg[(N-1)*N+N-1];
		memmove(&shiftreg[1], &shiftreg[0], (N*N-1) * sizeof(shiftreg[0]));
		shiftreg[0] = tmp + maskreg[i];
		n++;
	}
	shift(2*N*N - n);
}

/* Return true is board is cleared */
static int check_clear(void)
{
	int i, j;
	for(i = 1; i < 6; i++) {
		for(j = 1; j < 6; j++) {
			if(is_set(i, j))
				return 0;
		}
	}
	return 1;
}

/* Quiet pattern 1 */
static inline int q1(void)
{
	return	is_set(1, 1) + is_set(1, 2) + is_set(1, 4) + is_set(1, 5) +
		is_set(3, 1) + is_set(3, 2) + is_set(3, 4) + is_set(3, 5) +
		is_set(5, 1) + is_set(5, 2) + is_set(5, 4) + is_set(5, 5);
}

/* Quiet pattern 2 */
static inline int q2(void)
{
	return	is_set(1, 1) + is_set(2, 1) + is_set(4, 1) + is_set(5, 1) +
		is_set(1, 3) + is_set(2, 3) + is_set(4, 3) + is_set(5, 3) +
		is_set(1, 5) + is_set(2, 5) + is_set(4, 5) + is_set(5, 5);
}

/* Quiet pattern 3 (combi of 1 and 2) */
static inline int q3(void)
{
	return	is_set(1, 2) + is_set(1, 3) + is_set(1, 4) + is_set(2, 3) +
		is_set(2, 1) + is_set(3, 1) + is_set(4, 1) + is_set(3, 2) +
		is_set(2, 5) + is_set(3, 5) + is_set(4, 5) + is_set(3, 4) +
		is_set(5, 2) + is_set(5, 3) + is_set(5, 4) + is_set(4, 3);
}

/* Setup a random board */
static void fill_game(void)
{
	int i;
	memset(shiftreg, 0, sizeof(shiftreg));
	for(i = 0; i < 100; i++) {
		shiftreg[rand() % (N*N)]++;
	}
}

/* Board can be solved if both quiet patterns are even */
static inline int is_solvable(void)
{
	return !(q1() & 1) && !(q2() & 1);
}

#ifdef SIMULATE
/* Chase the lights to have the rest at the bottom */
static void chase(void)
{
	int i, j;
	for(i = 2; i < 6; i++) {
		for(j = 1; j < 6; j++) {
			if(is_set(i-1, j))
				button(i, j);
		}
	}
}

/* Set the solution lights at the top */
static void set_result(void)
{
	if(is_set(5, 1)) {
		button(1, 4);
		button(1, 5);
	}
	if(is_set(5, 2)) {
		button(1, 2);
		button(1, 5);
	}
	if(is_set(5, 3)) {
		button(1, 4);
	}
}

/* Simulate a lot of boards */
static void simulate(void)
{
	int n;
	int solved = 0;
	int tested = 0;
	int k1o = 0;
	int k2o = 0;
	int k3o = 0;
	int k1ou = 0;
	int k2ou = 0;
	int k3ou = 0;
	int cpshiftreg[N*N];
	for(n = 0; n < SIMULATE; n++) {
		int k1, k2, k3;
		fill_game();
		k1 = q1();
		k2 = q2();
		k3 = q3();
		if(k1 & 1) k1ou++;
		if(k2 & 1) k2ou++;
		if(k3 & 1) k3ou++;
		if(!is_solvable())
			continue;
		memcpy(cpshiftreg, shiftreg, sizeof(shiftreg));
		tested++;
		chase();
		set_result();
		chase();
		if(!check_clear()) {
			memcpy(shiftreg, cpshiftreg, sizeof(shiftreg));
			printf("%d Q{1,2,3}: %d %d %d\n", n, k1, k2, k3);
			print_reg();
			return;
		} else {
			solved++;
			if(k1 & 1) k1o++;
			if(k2 & 1) k2o++;
			if(k3 & 1) k3o++;
		}
	}
	printf("Solved: %d (%d), %d (%d), %d (%d), %d (%d)\n", solved, tested, k1o, k1ou, k2o, k2ou, k3o, k3ou);
}

#else

/* Play an interactive game */
static void playgame(void)
{
	int i;
	fill_game();
	printf("Game is%s playable\n", is_solvable() ? "" : " not");
/*
	print_reg();
	chase();
	print_reg();
	set_result();
	chase();
*/
	print_reg();
	for(i = 0; i < 100; i++) {
	int r, c;
		printf("Row Column: ");
		fflush(stdout);
		fscanf(stdin, "%d %d", &r, &c);
		button(r, c);
		print_reg();
		if(check_clear())
			break;
	}
}
#endif

int main(void)
{
	srand(time(NULL));

#ifdef SIMULATE
	simulate();
#else
	playgame();
#endif
	return 0;
}