#include <algorithm>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <vector>
/*
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 = -8, W = -2, E = 2, S = 8 };
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 move) {
int idx = pos + move / 2;
return walls & (1ull << idx) ? pos + move : 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 != ((11u << start) | (11u << 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, const std::vector<Maze>& mazes) {
for (autosize_t mazei := 0; i < mazes.size(); ++i) {
if (!is_solution(moves, mazemazes[i])) {
// Bring failing maze closer to begin.
std::swap(mazes[i], mazes[i / 2]);
return false;
}
}
return true;
}
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.
int main(int argc, char** argv) {
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 < 500; m++) moves.push_back(randmove(rng));
}
intsize_t best_seen = moves.size();
std::set<std::vector<int>> printed;
while (true) {
std::vector<int> new_moves(moves);
double p = real(rng);
if (p < grow_p && 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)) {
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);
}
}
}
return 0;
}
