Никому неинтересная лирика, можно пропустить
"Вот и лето прошло..." как писал Тарковский-старший и как потом пела Ротару. Статья была готова практически сразу после публикации связанного материала, но лето есть лето - сначала меня отправили в бан за то, что рьяно защищал свою точку зрения (совсем не по статье про черепах), а потом просто практически потерял интерес к Хабру в первоначальном виде. А как накатили холода и осень тихо напомнила о том, что дубак не за горами (первый снег уже увидел), я решил реанимировать статью.
Писать её в полном объёме, как задумывал, я не стану, опубликую только фактическое сравнение двух реализаций в защиту моей точки зрения. Остальное вполне под силу заинтересованной публике - может быть кто-то напишет реализацию еще лучше или найдёт какие-то ошибки, совсем не сомневаюсь в компетенции уважаемого @wataru, который и был моим оппонентом в дискуссии в оригинальной статье, всё же я считаю целью не писать в стол, а хоть как-то побуждать публику к действию, ну а если я не прав в чём-то, то это повод или пересмотреть взгляды или научиться новому.
Начнём
Материал является логическим и практическим продолжением статьи про алгоритм вывода черепахи из лабиринта. Автор @demitryy сформулировал идею, но не описал практического её воплощения (не в укор сказано, но с кодом всё было бы интереснее) и в ходе оживлённой дискуссии появилось два подхода к реализации алгоритма. Один представил и воплотил на C++ пользователь @wataru, а второй, с разными видами оптимизаций, озвучил ваш покорный слуга.
Я не стал только на веру принимать мнение @wataru касательно итоговой производительности и/или эффективности обоих решений (для его реализации моего подхода он оказался не таким уж эффективным, что на мой взгляд было странным и нелогичным) и я захотел воплотить в жизнь свою задумку, но так, как я считаю правильным с теми или иными оптимизациями. Ну или всё же "получить по щам" и пересмотреть своё мнение (кстати вполне возможно что это и случится в ходе обсуждения статьи).
Задачка интересная и было забавно потратить некоторое время на проверку разных элементов реализации алгоритма. Сам код будет на C# с присущими ему особенностями. Жаль что я не стану писать первоначальный вариант, там было очень много тестов разных лабиринтов и подробностей работы, но чему не быть - тому не быть.
Процитирую саму задачу из оригинальной статьи:
Скрытый текст
Дан связный прямоугольный лабиринт NxM клеток, одна из которых обозначена как выход. В произвольной клетке появляется черепаха, и она может перемещаться в четырех направлениях (вверх, вправо, вниз, влево).
Черепаха не мыслит логически, однако имеет безупречную память. Она может запомнить и выполнить любую конечную последовательность команд. Черепаха не может перемещаться сквозь стенки лабиринта, и поэтому просто игнорирует команду, если не может ее исполнить и переходит к следующей.
Как только черепаха оказывается в клетке "выход", она тут же выходит из лабиринта и больше не исполняет никакие команды.
Расположение стенок лабиринта и клетки "выход" известны заранее, а вот начальное расположение черепахи неизвестно.
Помогите черепахе выбраться из лабиринта. Напишите конечную последовательность команд (up, right, down, left), которая гарантирует ей выход независимо от ее начального местонахождения.
Для начала хочу озвучить саму идею, которую транслирует автор оригинальной статьи: каждая итерация - это применение набора команд к гипотетической черепашке в одной из ранее нерассматриваемых свободных клеток. Данное действие всегда гарантирует выход из лабиринта одной черепашке, таким образом для лабиринта 
будет выполнено как максимум 
итераций (так сказать - лабиринт без стен), которые ограничиваются исключительно конфигурацией самого лабиринта, так как любая клетка занятая стеной уже не может быть использована черепашкой, что очевидно.
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓Ж▓ ▓...▓ ........▓ .......▓
▓.▓▓▓▓ ▓.▓.▓ .▓▓▓▓▓▓.▓ .▓▓▓▓▓.▓
▓.▓ .▓....▓....▓.▓ . ▓.▓
▓.▓▓▓▓▓▓.▓▓▓▓▓▓.▓▓.▓.▓ .▓▓▓▓▓.▓
▓....▓...▓ ▓E. ▓.▓....▓ ...▓
▓ ▓ .▓.▓▓▓ ▓▓▓▓ ▓▓.▓▓▓▓▓▓▓▓.▓ ▓
▓ ▓ ...▓ ▓ ▓▓▓..▓........▓ ▓
▓ ▓▓▓▓▓▓ ▓▓▓ .▓▓.▓▓▓▓▓▓▓▓ ▓
▓ ▓ ▓▓▓▓....▓ ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓В качестве примера возьмём такой лабиринт как я показал выше. Буквой "Е" обозначим выход, а буквой "Ж" будем обозначать черепашку, а точками обозначим маршрут.
Так как способ @wataru подразумевает простой перебор всех позиций, то на второй итерации мы получим такой лабиринт с новой базовой позицией черепашки. Это просто вторая свободная клетка по координате X.
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓Ж ▓ ▓ ▓ ▓
▓ ▓▓▓▓ ▓ ▓ ▓ ▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓
▓ ▓▓▓▓▓▓ ▓▓▓▓▓▓ ▓▓ ▓ ▓ ▓▓▓▓▓ ▓
▓ ▓ ▓ ▓E ▓ ▓ ▓ ▓
▓ ▓ ▓ ▓▓▓ ▓▓▓▓ ▓▓ ▓▓▓▓▓▓▓▓ ▓ ▓
▓ ▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓
▓ ▓▓▓▓▓▓ ▓▓▓ ▓▓ ▓▓▓▓▓▓▓▓ ▓
▓ ▓ ▓▓▓▓ ▓ ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓Применяя команды первой черепашки мы получим такой маршрут
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓о...▓..о▓ ........▓ .......▓
▓ ▓▓▓▓.▓.▓.▓ .▓▓▓▓▓▓.▓ .▓▓▓▓▓.▓
▓ ▓ ...▓....▓....▓.▓ . ▓.▓
▓ ▓▓▓▓▓▓ ▓▓▓▓▓▓.▓▓.▓.▓ .▓▓▓▓▓.▓
▓ ▓ ▓ ▓E. ▓.▓....▓ ...▓
▓ ▓ ▓ ▓▓▓ ▓▓▓▓ ▓▓.▓▓▓▓▓▓▓▓.▓ ▓
▓ ▓ ▓ ▓ ▓▓▓..▓........▓ ▓
▓ ▓▓▓▓▓▓ ▓▓▓ .▓▓.▓▓▓▓▓▓▓▓ ▓
▓ ▓ ▓▓▓▓....▓ ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓Со стороны кажется что это просто прямой путь к выходу, но буквой "о" я обозначил места, где черепашка билась о стену пытаясь выполнить набор команд из первой итерации.
С новой позиции, получившейся в ходе перемещения гипотетической черепашки, строим следующий маршрут опять до выхода. Так мы в очередной ход выводим еще одну черепашку из лабиринта. Конечно, часть черепашек могут выйти из лабиринта досрочно, это хороший бонус, но не правило.
Для каждой последующей черепашки мы сначала повторяем все команды первой, второй и т.д. черепашек, и строим новый маршрут и так - пока все свободные клетки не будут просчитаны. На выходе у нас будет список команд, который для любой позиции черепашки в лабиринте гарантирует её выход.
Мне в этом алгоритме не нравится сама суть перебора всех клеток.
Ниже код @wataru на языке C++:
Скрытый текст
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <chrono>
using namespace std;
enum Direction {
kRight = 0,
kUp = 1,
kLeft = 2,
kDown = 3
};
const char kDirToChar[4] = {'>', '^', '<', 'V'};
char ToChar(Direction d) {
return kDirToChar[d];
}
class Maze {
public:
/*
`map` - map of the labirinth. '#' indicates a wall. 'E' indicates exit.
*/
Maze(vector<string> map);
int Width() const;
int Height() const;
bool IsExit(int x, int y) const;
bool IsWall(int x, int y) const;
/*
Finds the shortest sequence of moves to get from (x, y) to exit.
`x` - 0 based column coordinate;
`y` - 0 based row coordinate;
(0, 0) is top-left.
*/
vector<Direction> GetPath(int x, int y) const;
/*
Moves turtle from position (x,y) according to `commands`.
`x` - 0 based column coordinate;
`y` - 0 based row coordinate;
returns new position in `x` and `y`.
*/
void ApplyCommands(int &x, int &y, const vector<Direction> &commands) const;
~Maze() = default;
private:
string _map;
int _height;
int _width;
int _exit;
int _offset[4];
vector<int> _prev;
void Bfs();
};
Maze::Maze(vector<string> map) : _height(map.size()), _width(map[0].size()) {
for (int i = 0; i < _width + 2; ++i)
_map += '#';
for (int i = 0; i < _height; ++i) {
_map +='#';
_map += map[i];
_map += '#';
}
for (int i = 0; i < _width + 2; ++i)
_map += '#';
_height += 2;
_width += 2;
_offset[kRight] = 1;
_offset[kUp] = -_width;
_offset[kLeft] = -1;
_offset[kDown] = _width;
for (size_t i = 0; i < _map.size(); ++i) {
if (_map[i] == 'E') {
_exit = i;
break;
}
}
Bfs();
}
void Maze::Bfs() {
_prev.resize(_map.size(), -1);
queue<int> q;
q.push(_exit);
_prev[_exit] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int npos = cur + _offset[k];
if (_map[npos] != '#' && _prev[npos] == -1) {
_prev[npos] = k^2;
q.push(npos);
}
}
}
cout << "Paths in the maze:n";
for (int i = 0; i < _height; ++i) {
for (int j = 0; j < _width; ++j) {
int cur = i*_width + j;
if (_map[cur] == '#') {
cout << '#';
} else if (_map[cur] == 'E'){
cout << 'E';
} else {
cout << ToChar(Direction(_prev[cur]));
}
}
cout << "n";
}
}
int Maze::Width() const {
return _width-2;
}
int Maze::Height() const {
return _height-2;
}
bool Maze::IsExit(int x, int y) const {
return _map[(y+1)*_width + x + 1] == 'E';
}
bool Maze::IsWall(int x, int y) const {
return _map[(y+1)*_width + x + 1] == '#';
}
vector<Direction> Maze::GetPath(int x, int y) const {
int pos = (y+1)*_width + x + 1;
vector<Direction> commands;
while (pos != _exit) {
commands.push_back(Direction(_prev[pos]));
pos += _offset[_prev[pos]];
}
return commands;
}
void Maze::ApplyCommands(int &x, int &y, const vector<Direction> &commands) const {
int pos = (y+1)*_width + x + 1;
for (auto &c : commands) {
if (pos == _exit) break;
int npos = pos + _offset[c];
if (_map[npos] != '#')
pos = npos;
}
y = pos / _width - 1;
x = pos % _width - 1;
}
vector<string> kMaze1 = {
"....",
".##.",
"..#.",
"#E#."
};
vector<string> kMaze2 = {
"....#.....",
".##...#.#.",
"..#####.#.",
"#E#...#.#.",
"###.#.....",
};
vector<string> kMaze3 = {
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"...................................................",
"E.................................................."
};
bool Check(const Maze &m, const vector<Direction> commands) {
for (int x = 0; x < m.Width(); ++x) {
for (int y = 0; y < m.Height(); ++y) {
if (m.IsWall(x, y)) continue;
int nx = x;
int ny = y;
m.ApplyCommands(nx, ny, commands);
if (!m.IsExit(nx, ny)) {
return false;
}
}
}
return true;
}
void Algo1(const Maze &m) {
vector<Direction> commands;
for (int x = 0; x < m.Width(); ++x) {
for (int y = 0; y < m.Height(); ++y) {
if (m.IsWall(x, y)) continue;
int nx = x;
int ny = y;
m.ApplyCommands(nx, ny, commands);
auto c = m.GetPath(nx, ny);
commands.insert(commands.end(), c.begin(), c.end());
}
}
if (!Check(m, commands)) {
cout << "Botva!n";
}
}
void Algo2(const Maze &m) {
vector<Direction> commands;
vector<pair<int, int>> turtles;
for (int x = 0; x < m.Width(); ++x) {
for (int y = 0; y < m.Height(); ++y) {
if (m.IsWall(x, y)) continue;
turtles.emplace_back(x, y);
}
}
vector<vector<int>> was(m.Width(), vector<int>(m.Height()));
int stage = 0;
while (!turtles.empty()) {
auto t = turtles[0];
auto c = m.GetPath(t.first, t.second);
commands.insert(commands.end(), c.begin(), c.end());
++stage;
size_t last_pos = 0;
for (size_t i = 1; i < turtles.size(); ++i) {
m.ApplyCommands(turtles[i].first, turtles[i].second, c);
if (!m.IsExit(turtles[i].first, turtles[i].second) && was[turtles[i].first][turtles[i].second] < stage) {
was[turtles[i].first][turtles[i].second] = stage;
turtles[last_pos++] = turtles[i];
}
}
turtles.resize(last_pos);
}
if (!Check(m, commands)) {
cout << "Botva!n";
}
}
int main() {
Maze m(kMaze3);
auto start = chrono::high_resolution_clock::now();
for (int i = 0; i < 1000; ++i) {
Algo2(m);
}
auto stop = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
cout << "Clever algo took " << duration.count() << "nsn";
start = chrono::high_resolution_clock::now();
for (int i = 0; i < 1000; ++i) {
Algo1(m);
}
stop = chrono::high_resolution_clock::now();
duration = chrono::duration_cast<chrono::microseconds>(stop - start);
cout << "Naive algo took " << duration.count() << "nsn";
return 0;
}Я не собирал проект @wataruи не делал тестов и наверное зря, даже статью писать не пришлось бы, хотя получается забавный результат. Это кусок статьи пишу прямо сейчас.
Загрузил проект на C++ в Visual Studio и для маленьких лабиринтов вроде бы всё работает, но когда загрузил большой 810х410 клеток, как я тестировал для C# - программа повисла на 2 часа и я её закрыл не дожидаясь завершения.
Я уменьшал лабиринт пока не добрался до 81х41 (фактически до одной секции большого лабиринта), время работы было таким:
Clever algo took 100690395ns (это реализация моих мыслей от @wataru)
Naive algo took 181084166ns (это его собственный алгоритм)Это безумно долго. Не знаю в чем конкретно проблема, возможно из-за работы со строками. Я не знаю нюансов работы C++. В любом случае мой вариант реализации на большом лабиринте оказался быстрее почти в 2 раза, хотя @wataru.в комментариях к статье писал что его реализация работает лучше, возможно это вопрос подбора самого лабиринта. Давайте увеличим лабиринт еще и посмотрим как изменится работа (я сделал лабиринт 81х410, то есть увеличил его в 10 раз):
Clever algo took 391981893ns
Naive algo took 688208407nsКак видим отставание реализации @wataruсохраняется всё еще в рамках его же кода на C++.
Лабиринт на котором я проводил тестирование кода C++
vector<string> kMaze3 = {
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################..",
"..#############################################################################..",
"#.......#...#...#...........#...........#.......#.....#...#......................",
"###.###.#.###.#.#.#.#.#.#.#.###.#####.###.###.#.#.#.###.#.#.#.#.###.###.#.#.#.#.#",
"#.....#.#.#...#.#.#...#...#...#...#...#...#.#.....#.#.....#.#...#...#...#...#.#.#",
"#.#.#.#.#.#####.#.#########.#####.#.###.###.#########.#########.#.#.###.###.#.#.#",
"#.#.#.#.#.....#.#.......#.#...#...#.#.........#.........#.........#...#...#...#.#",
"#.#######.#.###.###.#.#.#.#.#######.#########.#.###.#.#########.#.###.#.#.#.#####",
"#.........#...#.#.#.#.#...#.#.#.....#...#.........#.#.#...#.....#...#.#.#.#.#...#",
"#.#.#######.###.#.#.#.#######.#####.###.#.#.#.#####.#.#.###.#.###.#####.###.###.#",
"#.#.....#.....#.....#...#...#...#.#.#.....#.#.#.....#.#...#.#...#...#.#.#.......#",
"#.#.#.###.###.#.#.#####.#.#.#.###.#.#####.###.###.#####.###.#####.#.#.#.#.#######",
"#.#.#.#...#...#.#.....#.#.#.....#.......#.#...#.#.#.#.....#.#.#...#...#.#.....#.#",
"#.#########.#######.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#####.#.###########.#####.#",
"#.........#.....#.#...#...#...#.#.#.#.#.#.#.#.#...#.....#.....#...#...#.........#",
"#.#.#######.#.###.###.#########.#.#.###.#.###.#.#.###.#.#.#######.#.###.#.###.###",
"#.#.#.......#.#...#.....#...........#.....#...#.#.#.#.#.#...#...#.#.#.#.#.#.....#",
"###.#.###.###.###.###.###.#######.#.#####.#.#######.#.###.#.###.#.#.#.#######.#.#",
"#.#.#.#...#.....#...#...#...#...#.#.#.#.#.#...#...#.#...#.#.....#...#...#.....#.#",
"#.#.###.#.#####.#.#########.#.###.#.#.#.#######.#.#.#.#####.###.#.#.#.#.#####.#.#",
"#...#...#.#.....#...#...#...#.#...#.........#.#.#.......#...#.....#...#.....#.#.#",
"#.#########.#.###.###.###.###.#.#.###.#######.#.#####.###.###.#######.###.#####.#",
"#...#...#.#.#.#...........#...#.#.#...............#...#.#.#...#...#.#...#.#.....#",
"###.#.###.#####.#.#######.#.#########.#.###.#####.#####.#.#####.###.#####.###.#.#",
"#.....#...#.....#.#.#.......#.........#...#.#...#...#.......#.#...#.......#.#.#.#",
"#.###.#.#####.#####.#############.#######.###.#####.#.###.###.#.#.#.#####.#.#.#.#",
"#.#.#.....#.#.....#.#...#.........#.........#.#...#.#.#.......#.#.......#.#...#.#",
"#.#.#######.###.###.#.#.###.#############.#.#.#.#####.#####.###.###.#####.#####.#",
"#.........#.#...#...#.#.#...#.#.....#...#.#...#...#...#...#...#...#...#...#.#...#",
"#.#####.###.###.###.#.#####.#.#.#######.#.###.#.#########.#.#.###.###.#####.#.###",
"#.#...#.........#...............#...........#.....#.#.#.#.#.#...#.#...#...#...#.#",
"###.###.#.###############.###########.#.#.###.#####.#.#.#.#########.#.#.###.#.#.#",
"#.......#...#...#...#.....#.#.......#.#.#.#...#.......#.....#.#...#.#.......#...#",
"#.#####.#####.#####.#.#####.#.#.###.#.#.###.###.###.#.###.#.#.#.#######.###.#####",
"#.#.................#...#...#.#...#.#.#...#.....#...#.....#.#.#.#...#...#.......#",
"###.###.###.#####.#.#.###.#####.###.#.#.###########.###.###.#.#.#.#######.#####.#",
"#.#.#.#.#.....#.#.#.#.....#.#...#.....#.#.....#.#...#.....#...#.#.#.......#.....#",
"#.#.#.#.###.###.###.#####.#.###########.###.#.#.#.#.#.###.###.#.#.###.#########.#",
"#...#...#.#...#...#.....#.#.....#.#.....#...#.....#.#.#...#...#...#.#.#.#.......#",
"###.#.###.#######.#.#.###.#.#####.###.#.###.###.#####.#.###.#.#.#.#.#.#.#####.#.#",
"#...#...#...........#...#...........#.#.#.....#.#.....#...#.#...#.......#.....#..",
"..#############################################################################.E"
};Теперь о моей реализации на C#
Я знаю что это не чистый эксперимент, так как код на С++ может отработать быстрее (это строка написана до тестов на C++). Возможно @wataru, если будет желание, перепишет мою реализацию на С++ и сравнит всё там (я не думаю что смогу быстро перенести код на C++).
Тут лежит реализация, можно скачивать, проект .NET 8.0, в папке BIN можно найти сборку DEBUG и RELEASE
В своих примерах @wataruиспользует таймер с точностью до микросекунд, не знаю как в C++, но как мне кажется, независимо от ЯП делать тесты на критически малых значениях таймера - не совсем корректно (тут речь о том, что лабиринты в коде @wataru безумно маленькие, а значит и результаты таймера могут зависеть от разных причин). В C# для этого есть отдельная библиотека для бенчмарков, но я думаю, что куда практичнее просто сделать большой лабиринт и из-за масштаба накладные расходы и погрешности сведутся к минимуму, тут-то и можно сделать замеры таймером.
Для своей реализации он, в коде Algo1() , просто проходит по всем пустым ячейкам лабиринта и для каждой строит путь до выхода. Так как каждая последующая черепашка должна пройти маршрут всех предыдущих, я сделал несколько предположений еще при обсуждении оригинальной статьи, а именно:
-
список команд будет внушительным
-
его выполнение будет долгим по времени, так как по сути это наивная реализация
Для тестирования, чтобы замеры времени не сильно менялись из-за погрешностей, я взял лабиринт размерами 810х410 клеток.
Для обоих реализаций уже на C# получаем такие результаты:
По пунктам 1-2 выше получается, что по количеству команд разница не такая большая (26%), а вот по скорости видно что это аж 18.8 раз (1880%).
Описание моей реализации алгоритма
Обе реализации доступны тут
Я представляю каждую черепашку как отдельный элемент, так же я делаю и с лабиринтом, причем черепашки знают где они находятся, а каждая клетка лабиринта знает какая черепашка находится в ней.
Я не сканирую лабиринт по ячейкам чтобы понимать где у меня стены, еще на этапе формирования лабиринта я в каждой ячейке сохраняю информацию о том, какие соседние ячейки существуют, это в том числе избавляет от постоянных обращений к лабиринту, не нужно следить за выходом за пределы и т.д.
Для всех клеток лабиринта я использую BFS чтобы построить маршруты.
Основной цикл в целом не отличается от реализации @wataru, но на этапе перемещения черепашки я сдвигаю все черепашки сразу, это позволяет в определенных ситуациях некоторым черепашкам оказаться в одной клетке. Я это не допускаю и по сути уничтожаю все черепашки кроме одной, так как очевидно, что если одна черепашка может выйти из этой клетки то и все остальные это сделают, таким образом наращивать список команд не требуется.
Черепашек я реализую через двусвязный список, что позволяет не заботиться об изменении размеров такого списка или массива в памяти, так как все манипуляции идут с указателями. В реализации @wataru возможно это был один из факторов замедления. Я переделывал код @wataruна списки - прибавка в скорости ощутима, но всё равно не опережает мой подход.
Но, разумеется, требования к ОЗУ у варианта @wataru будут ниже. Ну так с этим я никогда и не спорил.
Итог
-
На данный момент у меня есть вопросы по реализации C++, кто в теме - можно ли исправить такую катастрофически медленную скорость работы?
-
Мой подход к решению задачи быстрее, все озвученные ранее проблемы наивной реализации проявились и дали плохой результат.
-
Я не делал тестов с разными вариантами лабиринтов - пустой "короб", "змейки", не менял положение выхода по простой причине - я потерял интерес к теме. Возможно позже я сделаю вторую статью где это проверю, но это не факт. У меня остались черновые наработки с визуализацией лабиринта (скриншоты вы видели в самом начале) и с его помощью можно интересно наблюдать, как исчезают черепашки в моем алгоритме. Может быть это будет позже сделано.
Буду рад если кто-то захочет разобраться с кодом C++ чтобы сделать обработку лабиринта 810х410 за сопоставимые 2.5 секунды, не обязательно так как это сделал я, может быть есть куда интереснее решение.
Всем бобра!
Автор: Zara6502
