# C++, <strike>97</strike> <strike>95</strike> <strike>93</strike> <strike>91</strike> <strike>86</strike> <strike>83</strike> <strike>82</strike> <strike>81</strike> 79 characters
>!NNWSWNNSENESESWSSWNSEENWWNWSSEWWNENWEENWSWNWSSENENWNWNESENESESWNWSESEWWNENWNEES
My strategy is fairly simple - an evolution algorithm that can grow, shrink, swap elements of and mutate valid sequences. My evolution logic is now nearly the same as @Sp3000's, as his was an improvement over mine.
However, my implementation of the maze logic is rather nifty. This allows me to check if strings are valid at blistering speed. Try to figure it out by looking at the comment, `do_move` and the `Maze` constructor.
<!-- language: lang-cpp -->
#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 != ((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;
}
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));
}
size_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;
}