/*
	Cellular automata academic problem solution
	Garden of Eden problem
	by Miguel Revilla 2000-08-21
	
	this solution by Douglas Toltzman

	Inputs:
		system_rules - decimal # that specifies outputs (0/1) for each of 8 possible inputs
		# of cells - integer from 4 through 16 that specifies the number of cells in array
		CA_state - a string of zeros and ones that represents state of CA that must be resolved
		(CA_state must contain exactly n digits, where n equals the # of cells)
	Output:
		"Garden of eden" if state is unreachable from any input using system_rules
		"Reachable" if state can be reached
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

inline int select_rule( unsigned long input, int i, int n_cells )
{
	int which_rule;
	// input bits must occupy least significant n_cells bits of input
	// i (index) must be in range of 0 to n_cells-1, inclusive
	if (i == 0)
		which_rule = ((input & 1) << 2) + (input >> (n_cells-2));		//take LSB and multiply by 4 and add 2 top bits
	else if (i == n_cells - 1)	// center point is last node in array
		which_rule = ((input << 1) & 0x6) + (input >> (n_cells-1));	//shift 2 least sig. up 1 and add top bit
	else
		which_rule = (input >> (n_cells-2-i)) & 0x7;	// just shift bits so the 3 we want are LSB and mask
	return which_rule;
}

inline int output_of_rule( unsigned int rules, int which_rule )
{
	unsigned int r_select = 1 << which_rule;
	return (rules & r_select) ? 1:0;
}

static void show_bits( unsigned int input, int n_bits )
{
	while (n_bits--) putchar(((input >> n_bits) & 0x1) ? '1':'0');
	return;
}

static void show_rules( unsigned int rules )
{
	int i;
	printf("Cellular Automaton rules:\n");
	for (i=0; i <= 0x7; i++)
	{
		putchar('\t');	// insert a tab
		show_bits(i,3);	// show input bits
		printf(" -> %d\n", output_of_rule(rules,i));	//show result bit
	}
	putchar('\n');
	return;
}

int main( int argc, char **argv )
{
	int success=0;
	if (argc != 4)
		printf("Arguments: <rules> <number_of_cells> <state>\n");
	else {
		unsigned int rules = atoi(argv[1]);
		int n_cells = atoi(argv[2]);

		if (n_cells >= 4 && n_cells <= (sizeof(unsigned long)*8))	//allow as many cells as we have bits in an unsigned long
		{
			if (strlen(argv[3]) == n_cells)
			{
				unsigned long result, input, max_input;
				const char *arg3ptr;
				int i;

				for (i=0, arg3ptr=argv[3],result=0; i < n_cells; i++) if (*arg3ptr++ == '1') result |= (1 << (n_cells-i-1));
				printf("searching for result=%lX -> ",result);
				show_bits(result,n_cells); putchar('\n');
				show_rules(rules);

				// brute force test of all possible inputs, looking for output that matches result
				max_input = (1 << n_cells) - 1;	// maximum input is 2^n - 1 (for 8 cells 2^8-1=255)
				for (input=0; input <= max_input; input++)
				{
					unsigned long this_result=0;
					for (i=0; i < n_cells; i++)
					{
						int rule_index = select_rule(input, i, n_cells);
						if (output_of_rule(rules,rule_index))	// output of rule will be zero or one
						{
							// if output is one, insert a 1 into the correct cell in this_result
							this_result |= (1 << (n_cells-i-1));
						}
					}
					// this_result now contains the next generation of the CA, using the rules we've been given
					// and starting with input.
					if (this_result == result) {
						// just for giggles, show the input that gave us the result we were seeking
						show_bits(input,n_cells); putchar('-'); putchar('>'); show_bits(this_result,n_cells); putchar('\n');
						success=1; break;
					}
				}
				printf("%s\n", (success) ? "Reachable":"Garden of Eden");
			}
			else
				printf("arg 3 (state) must contain exactly %d digits (specified by number of cells)\n",n_cells);
		}
		else
			printf("arg 2 (number of cells) must be in range of 4-16\n");
	}
	return success;
}