#include "cube/include/cube_step.hh"
#include "cube/include/cube.hh"
#include "cube/include/cube_movements.hh"

#include <iostream>
#include <queue>
#include <string>
#include <functional>
#include <unordered_set>

struct CubeMove
{
  std::string sourceConfiguration;
  cube::Step stepTaken;
};

struct MovementFunction
{
  std::function<cube::Cube(cube::Cube const &)> movementFunction;
  cube::Step step;
};

std::vector<cube::Step> solveCube(cube::Cube const &sourceCube)
{
  static std::string const solvedEncoded = "RRRRRRRRRGGGGGGGGGOOOOOOOOOBBBBBBBBBWWWWWWWWWYYYYYYYYY";
  static std::vector<MovementFunction> moveAndFuncPairs = {
      {.movementFunction = cube::movements::movedRightLayer, .step = cube::Step::R},
      {.movementFunction = cube::movements::movedRightPrimeLayer, .step = cube::Step::R_},
      {.movementFunction = cube::movements::movedLeftLayer, .step = cube::Step::L},
      {.movementFunction = cube::movements::movedLeftPrimeLayer, .step = cube::Step::L_},
      {.movementFunction = cube::movements::movedLeftLayer, .step = cube::Step::U},
      {.movementFunction = cube::movements::movedLeftPrimeLayer, .step = cube::Step::U_},
      {.movementFunction = cube::movements::movedDownLayer, .step = cube::Step::D},
      {.movementFunction = cube::movements::movedDownPrimeLayer, .step = cube::Step::D_},
      {.movementFunction = cube::movements::movedFrontLayer, .step = cube::Step::F},
      {.movementFunction = cube::movements::movedFrontPrimeLayer, .step = cube::Step::F_},
      {.movementFunction = cube::movements::movedBackLayer, .step = cube::Step::B},
      {.movementFunction = cube::movements::movedBackPrimeLayer, .step = cube::Step::B_}};
  std::unordered_set<std::string> exploredConfigurations;
  std::unordered_map<std::string, CubeMove> encConfToParentCubeMove;
  std::queue<std::string> encodedCubes;
  std::string const sourceCubeEncoded = sourceCube.encode();
  exploredConfigurations.insert(sourceCubeEncoded);
  encodedCubes.push(sourceCubeEncoded);
  while (true)
  {
    std::string currentCubeEncodedConfiguration = encodedCubes.front();
    if (currentCubeEncodedConfiguration == solvedEncoded)
    {
      break;
    }
    cube::Cube currentCubeEncoded = cube::Cube::decode(currentCubeEncodedConfiguration);
    encodedCubes.pop();
    for (auto const &[movementFunction, step] : moveAndFuncPairs)
    {
      cube::Cube const movedCube = movementFunction(currentCubeEncoded);
      std::string movedCubeEncoded = movedCube.encode();
      if (not exploredConfigurations.contains(movedCubeEncoded))
      {
        encodedCubes.push(movedCubeEncoded); // add encoded cube to the queue
        exploredConfigurations.insert(movedCubeEncoded);
        encConfToParentCubeMove[movedCubeEncoded] = CubeMove{
            .sourceConfiguration = currentCubeEncoded,
            .stepTaken = step};
      }
    }
  }
  std::vector<cube::Step> solvingSteps;
  std::string currentEncoded = solvedEncoded;
  while (currentEncoded != sourceCubeEncoded)
  {
    auto const &[parentEncoded, stepTaken] = encConfToParentCubeMove[currentEncoded];
    currentEncoded = parentEncoded;
    solvingSteps.push_back(stepTaken);
  }
  std::reverse(solvingSteps.begin(), solvingSteps.end());
  return solvingSteps;
}

int main()
{

  // std::string cubeEncoded = "GYRBRORRGYGRYGOORWWGYWOBOYYORROBYOWBBRGGWBWWWBWGBYOYGB";
  std::string cubeEncoded = "RRORRORROYGGYGGYGGROOROOROOWBBWBBWBBYGGYWWBWWBBWYYWYYG";
  cube::Cube cube(cubeEncoded);
  auto steps = solveCube(cube);
  if (steps.empty())
  {
    std::cout << "the cube is already solved\n";
  }
  else
  {
    for (cube::Step const step : steps)
    {
      std::cout << step << std::endl;
    }
  }
  return 0;
}