findsolution.cpp

//  пусть 1 - красный, 2 - желтый, 0 - пустота, 3 - синий, 4 - светолосиний, 5 - зелёный, 6 - белый, 7 - розовый
//  пусть в массиве индекс идёт по часовой стрелке 0 - 12 часов, 1 - 1, 2 - 2 - 3 часа, 3 - 3, 4 - 6 часов, 5 -5, 6 - 9 часов, 7 - 7
//  тогда q - сдвиг влево на  2, e - сдвиг вправо на 2
//  switch (S) - циклический сдвиг внизу 3, 4, 5
#include <string>
#include <cstdlib>
#include <iostream>
#include <unordered_set>
#include <unordered_map>

std::string initial_state = "10020003";
std::string desired_state = "13200000";// "13200000";


std::string q(const std::string& in)
{
	std::string result = in.substr(2) + in[0] + in[1];
	return result;
}

std::string e(const std::string& in)
{
	std::string result;
	result += in[6];
	result += in[7];
	result += in.substr(0, 6);
	return result;
}

std::string s(const std::string& in)
{
	std::string result = in;
	char c3 = in[3];
	char c4 = in[4];
	char c5 = in[5];
	result[4] = c5;
	result[3] = c4;
	result[5] = c3;
	return result;
}

std::string find_solution(const std::string& current_state, const std::string& actions, const std::string& desired_state, const std::unordered_set<std::string>& previous_states, std::unordered_map<std::string, std::string>& precomputed_states)
{
	if (current_state == desired_state)
	{
		//std::cout << "Found actions: " << actions << std::endl;
		return actions;
	}
	if (precomputed_states.find(current_state) != precomputed_states.end())
	{
		if (precomputed_states[current_state].length() != 0)
		{
			if (precomputed_states[current_state][0] == 'F')
			{
				return "";
			}
			//std::cout << "Suffix for " << current_state <<  " is " << precomputed_states[current_state] << std::endl;
			return actions + precomputed_states[current_state];
		}
		else
		{
			return actions;
		}
	}
	std::unordered_set<std::string> new_states = previous_states;
	new_states.insert(current_state);
	std::string result = "";
	size_t result_length = INT_MAX;
	{
		std::string s_actions =   actions + "s";
		std::string s_state = s(current_state);
		bool can_apply_s = true;
		if (s_state == current_state)
		{
			can_apply_s = false;
		}
		else
		{
			if (new_states.find(s_state) != new_states.end())
			{
				can_apply_s = false;
			}
		}
		if (actions.length() >= 2)
		{
			if (actions.substr(actions.length() - 2) == "ss")
			{
				can_apply_s = false;
			}
		}
		if (can_apply_s)
		{
			std::string attempt_s_result = find_solution(s_state, s_actions, desired_state, new_states, precomputed_states);
			if (attempt_s_result.length() > 0)
			{
				if (result_length > attempt_s_result.length())
				{
					result = attempt_s_result;
					result_length = attempt_s_result.length();
				}
			}
		}
	}
	{
		// Do not apply q if we did three turns already - this is just full rotation
		bool can_apply_q = true;
		if (actions.length() >= 3)
		{
			if (actions.substr(actions.length() - 3) == "qqq")
			{
				can_apply_q = false;
			}
		}
		// Do not apply q if we did e - this just cancels it!
		if (actions.length() > 0)
		{
			if (actions[actions.length() - 1] == 'e')
			{
				can_apply_q = false;
			}
		}
		std::string q_state = q(current_state);
		if (can_apply_q)
		{
			if (new_states.find(q_state) != new_states.end())
			{
				can_apply_q = false;
			}
		}
		if (can_apply_q)
		{
			std::string q_actions =   actions + "q";
			std::string attempt_q_result = find_solution(q_state, q_actions, desired_state, new_states, precomputed_states);
			if (attempt_q_result.length() > 0)
			{
				if (result_length > attempt_q_result.length())
				{
					result = attempt_q_result;
					result_length = attempt_q_result.length();
				}
			}
		}
	}
	{
		// Do not apply e if we did three turns already - this is just full rotation
		bool can_apply_e = true;
		if (actions.length() >= 3)
		{
			if (actions.substr(actions.length() - 3) == "eee")
			{
				can_apply_e = false;
			}
		}
		// Do not apply e if we did q - this just cancels it!
		if (actions.length() > 0)
		{
			if (actions[actions.length() - 1] == 'q')
			{
				can_apply_e = false;
			}
		}
		std::string e_state = e(current_state);
		if (can_apply_e)
		{
			if (new_states.find(e_state) != new_states.end())
			{
				can_apply_e = false;
			}
		}
		if (can_apply_e)
		{
			std::string e_actions =   actions + "e";
			std::string attempt_e_result = find_solution(e_state, e_actions, desired_state, new_states, precomputed_states);
			if (attempt_e_result.length() > 0)
			{
				if (result_length > attempt_e_result.length())
				{
					result = attempt_e_result;
					result_length = attempt_e_result.length();
				}
			}
		}
	}
	if (result.length() > 0)
	{
		precomputed_states.insert(std::make_pair(current_state, result.substr(actions.length())));
	}
	else
	{
		precomputed_states.insert(std::make_pair(current_state, std::string("F")));
	}
	//std::cout << "Exit for " << current_state << " with " << result << " ("  << result_length << ")" << std::endl;
	return result;
}

std::string apply_solution(const std::string& current_state, const std::string& actions)
{
	std::string result = current_state;
	for (char c : actions)
	{
		if (c == 'q')
		{
			result = q(result);
		}
		if (c == 'e')
		{
			result = e(result);
		}
		if (c == 's')
		{
			result = s(result);
		}
	}
	return result;
}

int main(int argc, char* argv[])
{
	if (argc  < 3)
	{
		std::cout << "Usage: [exe-name]  <initial_state> <desired_state>" << std::endl;
		std::cout << "The slots in puzzle initial state and desired's state are written clockwise, the first number is 12 o'clock, 3rd - 3 a.m., 5th - 6.a.m., 7th - 9.a.m." << std::endl;
		std::cout << "Colors are written as numbers: 0 - empty, 1 - red, 2 - yellow, 3 - blue, 4 - light-blue, 5 - green, 6 - white, 7 - pink" << std::endl;
		std::cout << "Example: 10203000 looks as following"  << std::endl;
		std::cout << "       1" << std::endl;
		std::cout << "    0       0 " << std::endl;
		std::cout << std::endl;
		std::cout << "0                 2" << std::endl;
		std::cout << "    0       0 " << std::endl;
		std::cout << std::endl;
		std::cout << "       3" << std::endl;
		std::cout << "Hint for solution: q - is rotate left, e - rotate right, s - switch " << std::endl;
		return 1;
	}
	initial_state = argv[1];
	desired_state = argv[2];
	if (initial_state.length() != 8)
	{
		std::cout << "Initial state must be 8 numbers long";
		return 2;
	}
	if (desired_state.length() != 8)
	{
		std::cout << "Desired state must be 8 numbers long";
		return 3;
	}	
	std::unordered_map<std::string, std::string> precomputed_states;
	std::string result ;
	std::cout << "Initial state: " << initial_state << std::endl;
	if (initial_state == desired_state )
	{
		result = "";
	}
	else
	{
		result = find_solution(initial_state, "", desired_state, std::unordered_set<std::string>(), precomputed_states);
	}
	std::string final_state = apply_solution(initial_state, result);
	if (result.length() > 0)
	{
		std::cout << "Found sequence of actions: " << result << std::endl;
		std::cout << "Final state: " << final_state << std::endl;
	}
	else
	{
		std::cout << "No solution!" << std::endl;
	}
	return 0;
}