#include "find_shortest_sequences_from_to.h"

#include <algorithm>
#include <iostream>
#include <queue>

namespace {
struct NumericSearchState {
  std::string sequence;
  int depth = 0;
  char state = 'A';
};
}

std::vector<std::string> FindShortestSequencesFromTo(
    char from, char to,
    std::function<std::optional<char>(char, char)> apply_cmd) {

  std::vector<std::string> sequences;
  std::queue<NumericSearchState> states;

  states.emplace(NumericSearchState{
      .sequence = "",
      .depth = 0,
      .state = from,
  });

  int max_depth = 100;

  while (!states.empty()) {
    NumericSearchState state = std::move(states.front());
    states.pop();

    if (state.depth > max_depth) {
      continue;
    }

    if (state.state == to) {
      if (max_depth > state.sequence.size()) {
        max_depth = state.sequence.size();
      }
      state.sequence.push_back('A');
      sequences.emplace_back(std::move(state.sequence));
      continue;
    }

    for (auto c : {'<', '>', '^', 'v'}) {
      std::optional<char> maybe_next_state = apply_cmd(c, state.state);
      if (maybe_next_state) {
        NumericSearchState move_state = state;
        move_state.sequence.push_back(c);
        move_state.state = *maybe_next_state;
        ++move_state.depth;
        states.emplace(std::move(move_state));
      }
    }
  }

  std::vector<std::string> min_sequences;
  for (auto &s : sequences) {
    if (s.size() > max_depth + 1) {
      continue;
    }
    min_sequences.emplace_back(std::move(s));
  }

  return min_sequences;
}