// Jonathan Frech, 2022-04-13, 2022-04-14, 2022-04-30
// brute-force-solving Baba Is You's level e3bd-v4z1

// the two found solutions minimal in their move length are:
// * {vv><^^>v>v^<<v>^>>vvv<<^^<^>vvv>>^<>^>>v<<v<<^><^
//    >>>v>^^v<<<<<^^>v<v>>>>v>^<<^<v<<^^>v<v>>>><<v>>}
// * {vv><^^>v>v^<<v>^>>vvv<<^^<^>vvv>>^<>^>>v<<v<<^^>>
//    >v>^^v<<<<<^^>v<v>>>>v>^<<^<v<<^^>v<v>>>><<<v>>>}

// best built by:
// $ c++ -std=c++20 -Wall -Werror -Wextra -Wpedantic -Wswitch-enum -O3
// > baba-sokoban.cpp -o binary


#include <algorithm>
#include <array>
#include <chrono>
#include <exception>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <thread>
#include <tuple>
#include <vector>

constinit int STEPS_BETWEEN_PROGRESS_UPDATES{100000};
constinit bool DO_ANIMATE{true};
constinit auto ANIMATION_DELAY{std::chrono::milliseconds(300)};


enum class Tile {
    Wall, Void, Flag
};


enum class Move {
    Right, Up, Left, Down
};

static constexpr std::array<Move, 4> MOVES{
    Move::Right, Move::Up, Move::Left, Move::Down};

std::ostream& operator<<(std::ostream& os, const Move move) {
    switch (move) {
        case Move::Right:
            return os << ">";
        case Move::Up:
            return os << "^";
        case Move::Left:
            return os << "<";
        case Move::Down:
            return os << "v";
        default:
            return os << "?";
    }
}


using History = std::vector<Move>;

std::ostream& operator<<(std::ostream& os, const History& history) {
    os << '{';
    for (const Move m : history)
        os << m;
    return os << '}';
}


struct Point {
    private:
    uint16_t yx;

    static int from_signed_eight_bits(const uint8_t bits) {
        if (bits & 0b1000'0000)
            return -from_signed_eight_bits(1+~bits);
        return static_cast<int>(bits);
    }
    static uint8_t to_signed_eight_bits(const int n) {
        if (n < -128 || n > 127)
            throw std::out_of_range{"to_signed_eight_bits"};

        if (n < 0)
            return 0b1000'0000 | static_cast<uint8_t>(-n);
        return static_cast<uint8_t>(n);
    }

    public:
    Point() : Point(0, 0) { ; }
    Point(const int y, const int x) {
        if (!(-128 <= y && y <= 127) || !(-128 <= x && x <= 127))
            throw std::out_of_range{"Point"};
        yx = to_signed_eight_bits(y) << 8 | to_signed_eight_bits(x);
    }

    Point(const std::tuple<int, int>& yx)
        : Point(std::get<0>(yx), std::get<1>(yx)) { ; }

    int y() const {
        return from_signed_eight_bits((yx >> 8) & 0xff);
    }
    int x() const {
        return from_signed_eight_bits((yx >> 0) & 0xff);
    }

    std::tuple<int, int> as_tuple() const {
        return {y(), x()};
    }

    bool operator==(const Point other) const {
        return y() == other.y() && x() == other.x();
    }

    bool operator<(const Point other) const {
        return y() == other.y() ? x() < other.x() : y() < other.y();
    }

    Point moved(const Move move) const {
        switch (move) {
        case Move::Right:
            return Point(y(), x()+1);
        case Move::Up:
            return Point(y()-1, x());
        case Move::Left:
            return Point(y(), x()-1);
        case Move::Down:
            return Point(y()+1, x());
        default:
            throw std::runtime_error{"enum betrayal"};
        }
    }
};

std::ostream& operator<<(std::ostream& os, const Point p) {
    return os << "Point(" << p.y() << ", " << p.x() << ")";
}


template<int Cap> class PointSet {
    private:
    std::array<Point, Cap> points; // invariant: `points` is always sorted
    int len;

    public:
    Point at(const int j) const {
        if (j < 0 || j >= len)
            throw std::out_of_range{"PointSet::at"};
        return points.at(j);
    }

    bool contains(const Point p) const {
        for (int j{0}; j < len; ++j)
            if (at(j) == p)
                return true;
        return false;
    }

    void insert(const Point p) {
        if (contains(p))
            return;
        if (len >= Cap)
            throw std::length_error{"PointSet::insert"};
        points[len++] = p;
        std::sort(std::begin(points), std::begin(points)+len);
    }

    void remove(const Point p) {
        for (int j{0}; j < len; ++j) {
            if (points[j] == p)
                std::swap(points[j--], points[--len]);
        }
    }

    int length() const {
        return len;
    }

    bool operator==(const PointSet other) const {
        if (len != other.len)
            return false;
        for (int j{0}; j < len; ++j)
            if (points[j] != other.points[j])
                return false;
        return true;
    }

    bool operator<(const PointSet other) const {
        for (int j{0}; j < len; ++j) {
            if (j >= other.len)
                return false;
            if (points[j] != other.points[j])
                return points[j] < other.points[j];
        }
        return len < other.len;
    }

    void foreach(const std::function<void(const Point)> f) const {
        for (int j{0}; j < len; ++j)
            f(points[j]);
    }
};


struct World {
    int h, w;
    std::vector<Tile> tiles;

    Tile at(const Point p) const {
        return at(p.y(), p.x());
    }

    Tile at(const int y, const int x) const {
        if (y < 0 || y >= h || x < 0 || x >= w)
            return Tile::Wall;
        return tiles.at(y *w+ x);
    }
};


template<int Cap> struct State {
    Point baba;
    PointSet<Cap> crates;

    bool operator==(const State other) const {
        return baba == other.baba && crates == other.crates;
    }
    bool operator<(const State other) const {
        return baba == other.baba ? crates < other.crates : baba < other.baba;
    }

    bool go(const World& world, const Move move) {
        const Point once{baba.moved(move)};
        const Point twice{once.moved(move)};

        if (world.at(once) == Tile::Wall)
            return false;

        if (!crates.contains(once)) {
            baba = once;
            return true;
        }

        if (world.at(twice) == Tile::Wall || crates.contains(twice))
            return false;

        crates.remove(once);
        crates.insert(twice);
        baba = Point(once);
        return true;
    }

    bool won(const World& world) const {
        bool did_win{true};
        crates.foreach([&world, &did_win](const Point p) {
            did_win &= world.at(p) == Tile::Flag;
        });
        return did_win;
    }

    std::ostream& print(std::ostream& os, const World& world) const {
        for (int y{-1}; y < world.h+1; ++y) {
            for (int x{-1}; x < world.w+1; ++x) {
                const Point p(y, x);

                if (baba == p) {
                    if (won(world))
                        os << "\33[1m\33[47m\33[30m:|\33[m";
                    else
                        os << "\33[1m\33[47m\33[30m|:\33[m";
                    continue;
                }

                if (crates.contains(p)) {
                    if (world.at(p) == Tile::Flag)
                        os << "\33[1m\33[93m[]\33[m";
                    else
                        os << "[]";
                    continue;
                }

                switch (world.at(p)) {
                case Tile::Void:
                    os << "  ";
                    break;
                case Tile::Wall:
                    os << "\33[90m##\33[m";
                    break;
                case Tile::Flag:
                    os << "\33[1m\33[93m**\33[m";
                    break;
                default:
                    os << "\33[1m\33[91m??\33[m";
                    break;
                }
            }
            os << '\n';
        }
        return os;
    }

    void animate(const World& world, const std::vector<Move>& moves) {
        for (const Move move : moves) {
            print(std::cout, world) << std::endl;

            go(world, move);
            std::this_thread::sleep_for(ANIMATION_DELAY);

            std::cout << "\33[G\33[" << (world.h + 3) << "A";
            std::flush(std::cout);
        }
        print(std::cout, world) << std::endl;
    }
};


template<int Cap> auto parse_string_representation(
    const int h, const int w, const std::string& string_representation
) {
    if (h <= 0 || w <= 0)
        throw std::domain_error{"non-positive dimensions"};

    std::vector<Tile> tiles(h*w);
    if (string_representation.size() != tiles.size())
        throw std::domain_error{"size mismatch: string representation"};

    int baba_y{-1}, baba_x{-1};
    PointSet<Cap> crates{};
    int n_flags{0};

    for (int y{0}; y < h; ++y) {
        for (int x{0}; x < w; ++x) {
            Tile& tile = tiles[y *w+ x];
            switch (string_representation[y *w+ x]) {
            case 'B':
                if (baba_y != -1 || baba_x != -1)
                    throw std::logic_error{"multiple babas"};
                baba_y = y;
                baba_x = x;
                tile = Tile::Void;
                break;
            case '-':
                tile = Tile::Void;
                break;
            case '#':
                tile = Tile::Wall;
                break;
            case 'F':
                tile = Tile::Flag;
                ++n_flags;
                break;
            case 'C':
                crates.insert(Point(y, x));
                tile = Tile::Void;
                break;
            default:
                throw std::logic_error{"unknown representation character"};
                break;
            }
        }
    }
    if (baba_y == -1 || baba_x == -1)
        throw std::logic_error{"no baba"};
    if (n_flags != crates.length())
        throw std::logic_error{"mismatch: crates and flags"};

    return std::tuple<World, PointSet<Cap>, Point>{
        World(h, w, tiles), crates, Point(baba_y, baba_x)};
}


template<int Cap>
std::tuple<World, State<Cap>, std::set<History>> solve_sokoban(
    const int h, const int w, const std::string& string_representation
) {
    const auto [world, crates, baba]{
        parse_string_representation<Cap>(h, w, string_representation)};
    const State<Cap> state0(baba, crates);

    std::map<State<Cap>, History> reached{};
    std::map<History, std::set<History>> variants{};

    using Unch = std::tuple<State<Cap>, History>;
    std::vector<Unch> uncharted{};
    uncharted.push_back({state0, {}});

    std::vector<std::tuple<State<Cap>, History>> winning{};

    for (int steps{0}; !uncharted.empty(); ++steps) {
        if (steps % STEPS_BETWEEN_PROGRESS_UPDATES == 0) {
            const char wheel{"/-\\|"[(steps / STEPS_BETWEEN_PROGRESS_UPDATES) % 4]};
            std::clog << "\33[G\33[K" << "[" << wheel << "]"
                << " reached " << reached.size()
                << ", winning " << winning.size()
                << ", uncharted " << uncharted.size();
        }

        const auto [state, history]{uncharted.back()};
        uncharted.pop_back();

        if (reached.contains(state) && reached[state].size() <= history.size()) {
            if (reached[state].size() == history.size())
                variants[reached[state]].insert(history);
            continue;
        }
        reached[state] = history;

        if (state.won(world)) {
            winning.push_back({state, history});
            continue;
        }

        for (const Move m : MOVES) {
            State s(state);
            if (!s.go(world, m))
                continue;

            History h(history);
            h.push_back(m);

            uncharted.push_back(Unch{s, h});
        }
    }

    std::clog << "\33[G\33[Ktotal number of states reached: " << reached.size() << std::endl;
    std::clog << "total number of winning states: " << winning.size() << std::endl;

    std::sort(std::begin(winning), std::end(winning),
        [](const Unch& u, const Unch& v) -> bool {
            return std::get<1>(u).size() < std::get<1>(v).size(); });

    int number_of_unexpanded_minimal_move_solutions{0};
    for (const Unch& u : winning) {
        if (std::get<1>(u).size() > std::get<1>(winning.front()).size())
            break;
        ++number_of_unexpanded_minimal_move_solutions;
    }

    std::clog << "number of unexpanded minimal move solutions: "
        << number_of_unexpanded_minimal_move_solutions << std::endl;
    winning.resize(number_of_unexpanded_minimal_move_solutions);
    std::set<History> solutions{};
    for (const auto& [state, history] : winning) {
        std::set<History> equivalents{};
        std::function<void(const History)> search{[&](const History history) {
            if (equivalents.contains(history))
                throw std::logic_error{"equivalents loop"};
            equivalents.insert(history);

            History prefix(history);
            for (int prefix_length{static_cast<int>(history.size())}; prefix_length > 0; --prefix_length) {
                prefix.resize(prefix_length);
                for (const History prefix_variant : variants[prefix]) {
                    if (prefix_variant.size() != prefix.size())
                        throw std::logic_error{"length ought to be invariant under variants"};
                    History h(history);
                    for (int i{0}; i < static_cast<int>(prefix_variant.size()); ++i)
                        h[i] = prefix_variant[i];
                    search(h);
                }
            }
        }};

        search(history);
        for (const History& equiv : equivalents)
            solutions.insert(equiv);
    }

    return {world, state0, solutions};
}


int main() {
    constexpr int Cap = 4;
    const auto [world, state0, solutions]{
        solve_sokoban<Cap>(5, 6, "B-###F-C--#F-C---F#C--CF#---##")};

    std::cout << std::endl << "all solutions found"
        << " (" << solutions.size() << "):" << std::endl;
    for (const History& h : solutions)
        std::cout << h << std::endl;

    if (DO_ANIMATE) {
        std::cout << std::endl << "animation of the first solution:" << std::endl;
        for (const History& solution : solutions) {
            State(state0).animate(world, solution);
            break;
        }
    }
}