#C++, 97 95 93 91 characters
WWSESSENESENNWWSESESWSWNENENWNWESSENNESWSESWNEWNWNSSNENSWSWEEWNENWSWSSESNEEWNWSWSNNENESESNN
My strategy is fairly simple - an evolution algorithm that can grow, shrink and mutate valid sequences. It will spend most of it's time on mutating the shortest strings, then 1/5th of that on the next shortest, etc. This provides resistance against getting stuck in local minima.
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.
#include <vector>
#include <cstdint>
#include <iostream>
#include <random>
#include <algorithm>
#include <set>
/*
Positions:
2, 4, 6
10, 12, 14
18, 20, 22
Now, any position smaller than 0, divisible by 8 or larger than 22 is
illegal. 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:
3, 5, 6, 8, 10, 11, 13, 14, 16, 18, 19, 21
*/
enum { N = 0, W, E, S };
int do_move(uint32_t walls, int pos, int move) {
// Masking with all ones will always fail.
static const uint32_t masks[32] = {
~0u, ~0u, ~0u, 1<<0, ~0u, 1<<1, 1<<2, ~0u, 1<<3, ~0u, 1<<4, 1<<5, ~0u,
1<<6, 1<<7, ~0u, 1<<8, ~0u, 1<<9, 1<<10, ~0u, 1<<11, ~0u, ~0u, ~0u, ~0u,
~0u, ~0u, ~0u, ~0u, ~0u, ~0u
};
int pos_offset = 6*move - 2*(move > 1) - 8;
int idx = pos + pos_offset / 2;
return (idx < 0 || walls & masks[idx]) ? pos : pos + pos_offset;
}
struct Maze {
uint32_t walls;
int start, end;
Maze(uint32_t maze_id, int start, int end) {
static const int encoded_pos[9] = {2, 4, 6, 10, 12, 14, 18, 20, 22};
walls = (1u << 31) + maze_id ;
this->start = encoded_pos[start];
this->end = encoded_pos[end];
}
bool valid() {
if (start == end) return false;
uint32_t visited = 0;
std::vector<int> fill; fill.reserve(8); fill.push_back(start);
while (fill.size()) {
int pos = fill.back(); fill.pop_back();
if (visited & (1 << pos)) continue;
if (pos == end) return true;
visited |= 1 << pos;
for (int m = 0; m < 4; ++m) fill.push_back(do_move(walls, pos, m));
}
return false;
}
};
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.valid()) 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) result += "NWES"[move];
return result;
}
int fitness(const std::vector<int>& moves, const std::vector<Maze>& mazes) {
int fit = 0;
for (auto maze : mazes) if (!is_solution(moves, maze)) return 1000;
return moves.size();
}
bool solves_all(const std::vector<int>& moves, const std::vector<Maze>& mazes) {
for (auto maze : mazes) if (!is_solution(moves, maze)) return false;
return true;
}
constexpr double mutation_p = 0.2; // Chance to mutate.
constexpr double shrink_p = 0.8; // Chance to shrink.
constexpr double grow_p = 0.05; // Chance to grow.
template<class Gen>
int randint(int lo, int hi, Gen& gen) {
return std::uniform_int_distribution<int>(lo, hi)(gen);
}
struct SizeSorter {
template<class T>
bool operator()(const T& lhs, const T& rhs) {
return lhs.size() < rhs.size() || (lhs.size() == rhs.size() && lhs < rhs);
}
};
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(0.5);
std::vector<Maze> mazes = gen_valid_mazes();
std::set<std::vector<int>, SizeSorter> population;
while (population.size() < 10) {
std::vector<int> moves;
for (int m = 0; m < 500; m++) moves.push_back(randint(0, 3, rng));
if (solves_all(moves, mazes)) population.insert(moves);
}
while (true) {
int best_size = population.begin()->size();
int worst_seen_size = best_size;
std::vector<std::vector<int>> children;
for (auto moves : population) {
if (moves.size() > worst_seen_size) {
if (real(rng) < 0.8) break;
worst_seen_size = moves.size();
}
if (real(rng) < mutation_p) {
std::vector<int> mut_moves(moves);
int num_mut = std::min<int>(1 + exp(rng), mut_moves.size());
for (int mut = 0; mut < num_mut; ++mut) {
int idx = randint(0, mut_moves.size() - 1, rng);
mut_moves[idx] = randint(0, 3, rng);
}
if (solves_all(mut_moves, mazes)) children.push_back(mut_moves);
}
if (real(rng) < shrink_p) {
std::vector<int> mut_moves(moves);
int num_mut = std::min<int>(1 + exp(rng), mut_moves.size());
for (int mut = 0; mut < num_mut; ++mut) {
int idx = randint(0, mut_moves.size() - 1, rng);
mut_moves.erase(mut_moves.begin() + idx);
}
if (solves_all(mut_moves, mazes)) children.push_back(mut_moves);
}
if (real(rng) < grow_p) {
std::vector<int> mut_moves(moves);
int idx = randint(0, mut_moves.size() - 1, rng);
mut_moves.insert(mut_moves.begin() + idx, randint(0, 3, rng));
if (solves_all(mut_moves, mazes)) children.push_back(mut_moves);
}
}
population.insert(children.begin(), children.end());
best_size = population.begin()->size();
auto iter = population.begin();
for (; iter != population.end(); ++iter) {
if (iter->size() - best_size > 5) break;
}
population.erase(iter, population.end());
// Cool printing, shows evolution.
for (iter = population.begin(); iter != population.end(); ++iter) {
if (iter->size() != best_size) break;
}
std::vector<std::vector<int>> best_print(population.begin(), iter);
std::shuffle(best_print.begin(), best_print.end(), rng);
std::cout << moves_to_str(best_print[0]) << "\n";
std::cout << best_size << " (" << best_print.size() << "/" << population.size()
<< " individuals)\n";
}
return 0;
}