#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>

#include <cassert>
#include <cstdlib>
#include <memory.h>

using std::vector;
using std::istringstream;
using std::ifstream;

#define L( X, Y ) (((X) + 3 - (Y))%3)
#define R( X, Y ) (((X)*(Y)+2)%3)

int op_left[9] = {
	L(0, 0), L(1, 0), L(2, 0),
	L(0, 1), L(1, 1), L(2, 1),
	L(0, 2), L(1, 2), L(2, 2),
};

int op_right[9] = {
	R(0, 0), R(1, 0), R(2, 0),
	R(0, 1), R(1, 1), R(2, 1),
	R(0, 2), R(1, 2), R(2, 2),
};

void run(vector< unsigned int > const &ins, vector< int > &outs) {
	assert(ins.size() == outs.size());
	assert(ins.size() % 2 == 0);
	for (unsigned int i = 2; i + 1 < ins.size(); i += 2) {
		assert(ins[i] < outs.size());
		assert(ins[i+1] < outs.size());
		outs[i]   = op_left[outs[ins[i+1]]*3+outs[ins[i]]];
		outs[i+1] = op_right[outs[ins[i+1]]*3+outs[ins[i]]];
	}
}

void dump(vector< unsigned int > const &ins, vector< int > const &outs) {
	for (unsigned int i = 2; i + 1 < ins.size(); i += 2) {
		assert(ins[i] < outs.size());
		std::cout << i << ": ";
		if (ins[i] == 1) std::cout << "T";
		else std::cout << ins[i];
		std::cout << ' ';
		if (ins[i+1] == 1) std::cout << "T";
		else std::cout << ins[i+1];
		std::cout << '\n';
	}
	std::cout.flush();
}

void reset(vector< int > &outs) {
	for (unsigned int i = 0; i < outs.size(); ++i) {
		outs[i] = 0;
	}
}

int main(int argc, char **argv) {
	if (argc != 2) {
		std::cout << "Please pass filename or trit string to build gates for (\"empty\" -> fuel for empty string)." << std::endl;
		return 1;
	}
	vector< int > wanted;
	{
		int key[17] = {1,1,0,2,1,2,1,0,1,1,2,1,0,1,2,2,1};
		wanted.insert(wanted.end(), key, key + 17);
	}

	if (argv[1] != std::string("empty")) {
		ifstream in(argv[1]);
		if (!in) {
			istringstream in(argv[1]);
			char c;
			while (in >> c) {
				if (c >= '0' && c <= '2') {
					wanted.push_back(c - '0');
				} else if (c == 'x') {
					std::cerr << "Clearing wanted at 'x' character in trit string." << std::endl;
					wanted.clear();
				} else {
					std::cerr << "Ignoring '" << c << "'" << std::endl;
				}
			}
		} else {
			char c;
			while (in >> c) {
				if (c >= '0' && c <= '2') {
					wanted.push_back(c - '0');
				} else if (c == 'x') {
					std::cerr << "Clearing wanted at 'x' character in trit string." << std::endl;
					wanted.clear();
				} else {
					std::cerr << "Ignoring '" << c << "'" << std::endl;
				}
			}
		}
	}



	/*
	//testing:
	wanted.resize(100);
	srand(time(0));
	for (unsigned int i = 0; i < wanted.size(); ++i) {
		wanted[i] = rand() % 3;
	}
	*/

	vector< unsigned int > ins;
	vector< int > outs;
	ins.push_back(1); //the target input always points at the [unused] out 1.
	ins.push_back(-1U); //right input of world not used
	outs.push_back(0);
	outs.push_back(0); //right output of world used for temp values when testing

	//start with a known stream (thanks, zeroer):
	// || (straight to bottom ?)
	// 0/0/0 .. 0/0/2
	outs.push_back(0);
	outs.push_back(0);
	ins.push_back(outs.size() + 8);
	ins.push_back(outs.size() + 9);

	// X
	//2/2/2 ... 0/0/1

	outs.push_back(0);
	outs.push_back(0);
	ins.push_back(outs.size() - 3);
	ins.push_back(outs.size() - 4);

	//  2/2/1 2/2/1
	//  ||

	outs.push_back(0);
	outs.push_back(0);
	ins.push_back(outs.size() - 4);
	ins.push_back(outs.size() - 3);

	// 0/0/0 0/0/0
	//  ||
	
	outs.push_back(0);
	outs.push_back(0);
	ins.push_back(outs.size() - 4);
	ins.push_back(outs.size() - 3);

	// 0/0/0 2/2/2

	//  (zero tap) ._/ |
	//  /--------------/
	//  |    .--- (entropy input)
	//  2    *

	outs.push_back(0);
	outs.push_back(0);
	ins.push_back(outs.size() - 3);
	ins.push_back(0);

	// ||
	
	// 2/1/0   2/1/0

	outs.push_back(0);
	outs.push_back(0);
	ins.push_back(outs.size() - 4);
	ins.push_back(outs.size() - 3);
	// 0/0/0 0/0/2
	//  (crossed to top)


	unsigned int target = 0; //the location of target input
	unsigned int source = outs.size() - 6; //the location of known dangling output

	for (unsigned int tick = 0; tick < wanted.size(); ++tick) {
		assert(target < ins.size());
		assert(ins[target] == 1);

		//figure out what we need to set target to at tick 0 to get proper output:
		int target_val = -1;
		//"what happens at output if we put 'x' into target?"
		// -- a lazy way to figure out the proper target value to output
		//std::cout << "Hoping for " << wanted[tick] << "..." << std::endl;
		for (unsigned int x = 0; x < 3; ++x) {
			//std::cout << x << ": ";

			reset(outs);
			run(ins, outs);
			outs[1] = x;
			//assert(ins[0] < outs.size());
			//std::cout << outs[ins[0]];

			for (unsigned int iter = 0; iter < tick; ++iter) {
				assert(ins[0] < outs.size());
				if (outs[ins[0]] != wanted[iter]) {
					std::cout << "On tick " << tick << ", got mis-match." << std::endl;
					assert(outs[ins[0]] == wanted[iter]);
				}
				run(ins, outs);
				//std::cout << outs[ins[0]];
			}
			assert(ins[0] < outs.size());
			if (outs[ins[0]] == wanted[tick]) {
				target_val = x;
				//std::cout << " <-" << std::endl;
				break;
			} else {
				//std::cout << std::endl;
			}
		}
		assert(target_val >= 0);
		assert(target_val < 3);

		//reset circuit and execute up ins the point where we start our logic.
		reset(outs);
		run(ins, outs);
		assert(source < outs.size());
		int source_val = outs[source];
		//Now we have source_val and as many zeros as we can eat to make some glom of gates that outputs a target_val on the left.
		
		unsigned int old_target = target;
		//build gates
		{
			std::cerr << source_val << " to " << target_val << " requires ";
			if (target_val == source_val) {
				std::cerr << "E" << std::endl;
				//single gate; source into the left input.
				outs.push_back(0);
				outs.push_back(0);
				ins.push_back(source);
				ins.push_back(1);

				ins[target] = outs.size() - 2;

				//new target is right input; new source is right output.
				target = ins.size() - 1;
				source = outs.size() - 1;
			} else if (target_val == (3 - source_val) % 3) {
				std::cerr << "N" << std::endl;
				//single gate; source into right input.
				outs.push_back(0);
				outs.push_back(0);
				ins.push_back(1);
				ins.push_back(source);

				ins[target] = outs.size() - 2;

				//new target is left input; new source is right output.
				target = ins.size() - 2;
				source = outs.size() - 1;
			} else if (target_val == 0) {
				std::cerr << "0" << std::endl;
				//single gate; right output zero into right.
				outs.push_back(0);
				outs.push_back(0);
				ins.push_back(1);
				ins.push_back(outs.size() - 1);

				ins[target] = outs.size() - 2;

				//new target is left input; new source is old source.
				target = ins.size() - 2;
				source = source;
			} else if (target_val == 1) {
				std::cerr << "1" << std::endl;
				assert(source_val == 0); //if == 1 or 2 should have got caught above.
				//stack of gates; top makes 2, bottom gets -2 == 1.

				//top gate. left loops back. right from source (== 0 right now)
				outs.push_back(0);
				outs.push_back(0);
				ins.push_back(outs.size() - 2);
				ins.push_back(source);

				//bottom gate. right is from top gate.
				outs.push_back(0);
				outs.push_back(0);
				ins.push_back(1);
				ins.push_back(outs.size() - 3);

				ins[target] = outs.size() - 2;

				//new target is left input; new source is right output.
				target = ins.size() - 2;
				source = outs.size() - 1;
			} else if (target_val == 2) {
				std::cerr << "2" << std::endl;
				assert(source_val == 0);

				//stack of gates; top makes 2, bottom gets 2, adds control tap.

				//top gate. left loops back. right from source (== 0 right now)
				outs.push_back(0);
				outs.push_back(0);
				ins.push_back(outs.size() - 2);
				ins.push_back(source);

				//bottom gate. left is from top gate.
				outs.push_back(0);
				outs.push_back(0);
				ins.push_back(outs.size() - 3);
				ins.push_back(1);

				ins[target] = outs.size() - 2;

				//new target is right input; new source is right output.
				target = ins.size() - 1;
				source = outs.size() - 1;
			} else {
				std::cerr << "What weird case are we at now -- source_val: " << source_val << ", target_val: " << target_val << std::endl;
				assert(0);
				return -1;
			}
		}

		assert(target < ins.size());
		assert(ins[target] = 1);
		assert(source < outs.size());

		//Check solution:
		{
			reset(outs);
			run(ins,outs);
			assert(old_target < ins.size());
			assert(ins[old_target] < outs.size());
			assert(ins[old_target] != 1); //need ins have moved the target.
			if (outs[ins[old_target]] != target_val) {
				std::cerr << "Gate config is wrong; currently:" << std::endl;
				dump(ins, outs);
				return -1;
			}
			assert(outs[ins[old_target]] == target_val);
		}

	}
	//Wire final connection:
	assert(target < outs.size());
	assert(source < outs.size());

	//Note that we can't wire final target to a source that is _before_ it,
	//as this screws up the "target gets zero" idea; so we might have
	//to introduce an extra gate.
	if (target > source) {
		//extra gate ins provide a zero & delay:
		outs.push_back(0);
		outs.push_back(0);
		ins.push_back(source);
		ins.push_back(outs.size()-1);
		ins[target] = outs.size()-2;
	} else {
		ins[target] = source;
	}

	/*
	//Run a final check:
	reset(outs);
	for (unsigned int t = 0; t < wanted.size(); ++t) {
		outs[0] = rand() % 3;
		run(ins, outs);
		assert(ins[0] < outs.size());
		std::cout << outs[ins[0]];
		if (outs[ins[0]] != wanted[t]) {
			std::cout << "!!! We deviate from wanted here (wanted[" << t << "] == " << wanted[t] << ")." << std::endl;
			return -1;
		}
	}
	std::cout << std::endl;
	*/

	vector< unsigned int > to(outs.size(), -1U);
	for (unsigned int i = 0; i < ins.size(); ++i) {
		if (ins[i] < ins.size()) {
			//std::cout << ins[i] << " -> " << i << std::endl;
			assert(to[ins[i]] == -1U);
			to[ins[i]] = i;
			assert(i != 1 && ins[i] != 1);
		} else {
			//std::cout << " -- " << std::endl;
			assert(i == 1);
		}
	}

	char lr[2] = {'L', 'R'};
	
	if (to[0] < 2) {
		std::cout << 'X';
	} else {
		assert(to[0] < to.size());
		std::cout << (to[0] - 2) / 2 << lr[to[0]%2];
	}
	std::cout << ":\n";
	for (unsigned int i = 2; i + 1 < ins.size(); i += 2) {
		assert(to[i] < to.size());
		if (ins[i] < 2) {
			std::cout << 'X';
		} else {
			std::cout << (ins[i] - 2) / 2 << lr[ins[i]%2];
		}
		if (ins[i+1] < 2) {
			std::cout << 'X';
		} else {
			std::cout << (ins[i+1] - 2) / 2 << lr[ins[i+1]%2];
		}

		std::cout << "0#";

		if (to[i] < 2) {
			std::cout << 'X';
		} else {
			std::cout << (to[i] - 2) / 2 << lr[to[i]%2];
		}
		if (to[i+1] < 2) {
			std::cout << 'X';
		} else {
			std::cout << (to[i+1] - 2) / 2 << lr[to[i+1]%2];
		}

		if (i + 2 < ins.size()) {
			std::cout << ',';
		} else {
			std::cout << ':';
		}
		std::cout << '\n';
	}
	if (ins[0] < 2) {
		std::cout << 'X';
	} else {
		assert(ins[0] < ins.size());
		std::cout << (ins[0] - 2) / 2 << lr[ins[0]%2];
	}
	std::cout << '\n';
	std::cout.flush();


	//dump(ins, outs);

	return 0;
	
}