#include <algorithm>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <random>
#include <thread>
#include <set>
#include <vector>
#include <mutex>

/*
    Positions:

        8, 10, 12
        16, 18, 20
        24, 26, 28

    By defining as enum respectively N, W, E, S as 0, 1, 2, 3 we get:

        N: -8, E: 2, S: 8, W: -2
        0: -8, 1: -2, 2: 2, 3: 8

    To get the indices for the walls, average the numbers of the positions it
    would be blocking. This gives the following indices:

        9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27

    We'll construct a wall mask with a 1 bit for every position that does not
    have a wall. Then if a 1 shifted by the average of the positions AND'd with
    the wall mask is zero, we have hit a wall.
*/

enum { N = -4, W = -1, E = 1, S = 4 };
static const int encoded_pos[] = { 8, 10, 12, 16, 18, 20, 24, 26, 28 };
static const int wall_idx[] = { 9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27 };
static const int move_offsets[] = { N, W, E, S };

int do_move(uint32_t walls, int pos, int halfmove) {
    int idx = pos + halfmove;
    return walls & (1ull << idx) ? pos + halfmove + halfmove : pos;
}

struct Maze {
    uint32_t walls;
    int start, end;

    Maze(uint32_t maze_id, int start, int end) {
        walls = 0;
        for (int i = 0; i < 12; ++i) {
            if (maze_id & (1 << i)) walls |= 1 << wall_idx[i];
        }
        this->start = encoded_pos[start];
        this->end = encoded_pos[end];
    }

    uint32_t reachable() {
        if (start == end) return false;

        uint32_t reached = 0;
        std::vector<int> fill; fill.reserve(8); fill.push_back(start);
        while (fill.size()) {
            int pos = fill.back(); fill.pop_back();
            if (reached & (1 << pos)) continue;
            reached |= 1 << pos;
            for (int m : move_offsets) fill.push_back(do_move(walls, pos, m));
        }

        return reached;
    }

    bool interesting() {
        uint32_t reached = reachable();
        if (!(reached & (1 << end))) return false;
        if (std::bitset<32>(reached).count() <= 4) return false;

        int max_deg = 0;
        uint32_t ends = 0;
        for (int p = 0; p < 9; ++p) {
            int pos = encoded_pos[p];
            if (reached & (1 << pos)) {
                int deg = 0;
                for (int m : move_offsets) {
                    if (pos != do_move(walls, pos, m)) ++deg;
                }
                if (deg == 1) ends |= 1 << pos;
                max_deg = std::max(deg, max_deg);
            }
        }

        if (max_deg <= 2 && ends != ((1u << start) | (1u << end))) return false;

        return true;
    }
};

std::vector<Maze> gen_valid_mazes() {
    std::vector<Maze> mazes;
    for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
        for (int points = 0; points < 9 * 9; ++points) {
            Maze maze(maze_id, points % 9, points / 9);
            if (!maze.interesting()) continue;
            mazes.push_back(maze);
        }
    }

    return mazes;
}

bool is_solution(const std::vector<int>& moves, Maze maze) {
    int pos = maze.start;
    for (auto move : moves) {
        pos = do_move(maze.walls, pos, move);
        if (pos == maze.end) return true;
    }

    return false;
}

std::vector<int> str_to_moves(std::string str) {
    std::vector<int> moves;
    for (auto c : str) {
        switch (c) {
        case 'N': moves.push_back(N); break;
        case 'E': moves.push_back(E); break;
        case 'S': moves.push_back(S); break;
        case 'W': moves.push_back(W); break;
        }
    }

    return moves;
}

std::string moves_to_str(const std::vector<int>& moves) {
    std::string result;
    for (auto move : moves) {
        if (move == N) result += "N";
        else if (move == E) result += "E";
        else if (move == S) result += "S";
        else if (move == W) result += "W";
    }
    return result;
}

bool solves_all(const std::vector<int>& moves, std::vector<Maze>& mazes) {
    for (size_t i = 0; i < mazes.size(); ++i) {
        if (!is_solution(moves, mazes[i])) {
            // Bring failing maze closer to begin.
            std::swap(mazes[i], mazes[i / 2]);
            return false;
        }
    }
    return true;
}

int solves_n(const std::vector<int>& moves, std::vector<Maze>& mazes) {
    int n = 0;
    for(auto&& maze : mazes)
    {
        n += is_solution(moves, maze);
    }
    return n;
}

template<class Gen>
int randint(int lo, int hi, Gen& gen) {
    return std::uniform_int_distribution<int>(lo, hi)(gen);
}

template<class Gen>
int randmove(Gen& gen) { return move_offsets[randint(0, 3, gen)]; }

constexpr double mutation_p = 0.35; // Chance to mutate.
constexpr double grow_p = 0.1; // Chance to grow.
constexpr double swap_p = 0.2; // Chance to swap.
constexpr int num_threads = 4;
constexpr int initial_length = 500;

void work()
{
    static std::mutex mutex;
    static size_t best_seen = initial_length;
    static std::set<std::vector<int>> printed;

    std::random_device rnd;
    std::mt19937 rng(rnd());
    std::uniform_real_distribution<double> real;
    std::exponential_distribution<double> exp_big(0.5);
    std::exponential_distribution<double> exp_small(2);

    std::vector<Maze> mazes = gen_valid_mazes();

    std::vector<int> moves;
    while (!solves_all(moves, mazes)) {
        moves.clear();
        for (int m = 0; m < initial_length; m++) moves.push_back(randmove(rng));
    }
    while (true) {
        std::vector<int> new_moves;
        {
            std::unique_lock lock(mutex);
            new_moves = moves;
        }
        double p = real(rng);

        if (p < grow_p && new_moves.size() < best_seen + 10) {
            int idx = randint(0, new_moves.size() - 1, rng);
            new_moves.insert(new_moves.begin() + idx, randmove(rng));
        }
        else if (p < swap_p) {
            int num_swap = std::min<int>(1 + exp_big(rng), new_moves.size() / 2);
            for (int i = 0; i < num_swap; ++i) {
                int a = randint(0, new_moves.size() - 1, rng);
                int b = randint(0, new_moves.size() - 1, rng);
                std::swap(new_moves[a], new_moves[b]);
            }
        }
        else if (p < mutation_p) {
            int num_mut = std::min<int>(1 + exp_big(rng), new_moves.size());
            for (int i = 0; i < num_mut; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves[idx] = randmove(rng);
            }
        }
        else {
            int num_shrink = std::min<int>(1 + exp_small(rng), new_moves.size());
            for (int i = 0; i < num_shrink; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves.erase(new_moves.begin() + idx);
            }
        }

        if (solves_all(new_moves, mazes)) {
            std::unique_lock lock(mutex);

            moves = new_moves;

            if (moves.size() <= best_seen && !printed.count(moves)) {
                std::cout << moves.size() << " " << moves_to_str(moves) << "\n";
                if (moves.size() < best_seen) {
                    printed.clear(); best_seen = moves.size();
                }
                printed.insert(moves);
            }
        }
    }
}

int main(int argc, char** argv) {

    std::vector<std::thread> threads;
    for (int i = 0; i < num_threads; ++i)
    {
        threads.emplace_back(work);
    }

    for (auto&& th : threads)
    {
        th.join();
    }

    return 0;
}