//JAMES EVANS CSC 447 HW2

#include <set>
#include <iostream>
#include <string>

using namespace std;

bool* actors;
int bestpass = INT_MAX;
string besttransitions = "";

string generateState(bool* list);
bool stateUsed(set<string> states, string currentstate);
int runProblem(int pass, string transitions, set<string> states, bool* array);
bool isLegalState(bool* list);

void main() {
	actors = new bool[4]; //actor[0] = farmer, actor[1] = fox, actor[2] = goose, actor[3] = grain.
	actors[0] = false;
	actors[1] = false;
	actors[2] = false;
	actors[3] = false;
	set<string> states;

	runProblem(0, "", states, actors);
	cout << besttransitions << endl;
	system("pause");
}

int runProblem(int pass,string transitions, set<string> states,bool* array) {
	//initial state = FFFF, goal state TTTT
	if (isLegalState(array) == false) { return 0; }
	string currentstate = generateState(array);

	if (currentstate == "TTTT") {
		if (pass < bestpass) { besttransitions = transitions; return 0; }
	}


	if (stateUsed(states, currentstate) == true) {
		return 0;
	}
	else { states.insert(currentstate); }


	if (array[0] == array[1]) {

		string newtransitions = transitions;
		bool* newarray = new bool[4];
		newarray[0] = array[0];
		newarray[1] = array[1];
		newarray[2] = array[2];
		newarray[3] = array[3];
		set<string> newstates;
		for (set<string>::iterator it = states.begin(); it != states.end(); ++it) {
			newstates.insert(*it);

		}
		newarray[0] = !newarray[0];
		newarray[1] = !newarray[1];

		if (newarray[0] == false) { newtransitions += "Farmer + Fox -->\n"; }
		else { newtransitions += "Farmer + Fox  <--\n"; }

		runProblem(pass++, newtransitions, newstates, newarray);



	}
	if (array[0] == array[2]) {

		string newtransitions = transitions;
		bool* newarray = new bool[4];
		newarray[0] = array[0];
		newarray[1] = array[1];
		newarray[2] = array[2];
		newarray[3] = array[3];
		set<string> newstates;
		for (set<string>::iterator it = states.begin(); it != states.end(); ++it) {
			newstates.insert(*it);

		}
		newarray[0] = !newarray[0];
		newarray[2] = !newarray[2];

		if (newarray[0] == false) { newtransitions += "Farmer + Goose -->\n"; }
		else { newtransitions += "Farmer + Goose  <--\n"; }

		runProblem(pass++, newtransitions, newstates, newarray);


	}
	if (array[0] == array[3]) {

		string newtransitions = transitions;
		bool* newarray = new bool[4];
		newarray[0] = array[0];
		newarray[1] = array[1];
		newarray[2] = array[2];
		newarray[3] = array[3];
		set<string> newstates;
		for (set<string>::iterator it = states.begin(); it != states.end(); ++it) {
			newstates.insert(*it);

		}
		newarray[0] = !newarray[0];
		newarray[3] = !newarray[3];

		if (newarray[0] == false) { newtransitions += "Farmer + Grain -->\n"; }
		else { newtransitions += "Farmer + Grain  <--\n"; }

		runProblem(pass++, newtransitions, newstates, newarray);



	}

	{

		string newtransitions = transitions;
			bool* newarray = new bool[4];
			newarray[0] = array[0];
			newarray[1] = array[1];
			newarray[2] = array[2];
			newarray[3] = array[3];
			set<string> newstates;
			for (set<string>::iterator it = states.begin(); it != states.end(); ++it) {
				newstates.insert(*it);

			}
			newarray[0] = !newarray[0];

			if (newarray[0] == false) { newtransitions += "Farmer -->\n"; }
			else{ newtransitions += "Farmer <--"; }

			runProblem(pass++, newtransitions, newstates, newarray);



		}




}

bool isLegalState(bool* list) {
	if (list[0] != list[2] && (list[2] == list[3] || list[2] == list[1])) {
		return false;
	}
	return true;

}

string generateState(bool* list) {
	string state = "";
	if (list[0] == true) state += "T";
	else { state += "F"; }
	if (list[1] == true) state += "T";
	else { state += "F"; }
	if (list[2] == true) state += "T";
	else { state += "F"; }
	if (list[3] == true) state += "T";
	else { state += "F"; }

	return state;
}

bool stateUsed(set<string> states, string currentstate) {

	for (set<string>::iterator it = states.begin(); it != states.end(); ++it) {
		if (it == states.find(currentstate)) { return true; }

	}
	return false;

}