Никому неинтересная лирика, можно пропустить
«Вот и лето прошло...» как писал Тарковский-старший и как потом пела Ротару. Статья была готова практически сразу после публикации связанного материала, но лето есть лето - сначала меня отправили в бан за то, что рьяно защищал свою точку зрения (совсем не по статье про черепах), а потом просто практически потерял интерес к Хабру в первоначальном виде. А как накатили холода и осень тихо напомнила о том, что дубак не за горами (первый снег уже увидел), я решил реанимировать статью.
Писать её в полном объёме, как задумывал, я не стану, опубликую только фактическое сравнение двух реализаций в защиту моей точки зрения. Остальное вполне под силу заинтересованной публике - может быть кто-то напишет реализацию еще лучше или найдёт какие-то ошибки, совсем не сомневаюсь в компетенции уважаемого @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() << "ns\n";
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() << "ns\n";
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 секунды, не обязательно так как это сделал я, может быть есть куда интереснее решение.
Всем бобра!
Комментарии (5)
checkpoint
26.09.2024 06:03Хорошо когда у людей есть много свободного времени.
Zara6502 Автор
26.09.2024 06:03Что можно ответить на такой простой, но одновременно завуалированно грубый комментарий?
В сутки вы как минимум находитесь 10 минут в туалете, где у вас руки и голова не заняты, давайте посчитаем 4*30*10=1200 минут или 20 часов в моем случае за 4 месяца. Статью я писал в общей сложности не более чем 10 часов, софт, отладку и всякое сопутствующее пусть еще столько же. Как думаете, пострадало ли моё свободное время ощутимо? Тему можно развивать бесконечно. Например от дома до работы мне 8 минут на самокате, я не стою в пробках, так как у меня нет авто, я не трачу время на то чтобы ухаживать за машиной, сколько это в сутки? 1-2-3 часа? У меня нет собаки, с которой мне бы пришлось регулярно ходить на прогулки. И т.д. и т.п. Предлагаю вам постить такие комментарии на автофорумах вроде Дрома и Авто.ру, там оценят, или на форумах собачников и кошатников.
Если вы напишете сюда свой график жизни за месяц - поверьте, я выкину как минимум 50% из всего того, на что вы тратите время, как абсолютно ненужное и бестолковое занятие. Надеюсь объяснять не нужно почему это именно так?
Я не хожу в бары, не посещаю театры и дискотеки, не хожу на спортивные мероприятия и т.п.
Как думаете, я могу те редкие минуты, что я развлекаю себя логическими задачами, потратить на себя?
Вы же читаете Хабр, а могли бы ... - тут напишете что там у вас входит в список одобряемого времяпровождения (интересно, а вы не думали как на том Хабре, где вы находитесь, появляются статьи, и что будет, если все, опасаясь вашего неодобрения, перестанут эти статьи писать?).
Zara6502 Автор
26.09.2024 06:03Программирую микроконтроллеры STM32, AVR. Правлю драйвера для Linux для сорвременных СнК на базе ARM. Балуюсь с ПЛИСами. Разрабатываю схемотехнику, трассировку печатных плат в том числе СВЧ и DDR. Разрабатываю дизайн корпусов для РЭА и управляющие программы для многокоординатных ЧПУ. В далеком прошлом — сисоп узла Fidonet и оператор узла IRC сети. Юниксоид с 1996 года. Поддерживаю проект FreeBSD и использую эту ОС на рабочем ноутбуке. Апологет движения Open Source и Open Hardware, в том числе RISC-V.
Кстати такой комментарий от такого человека это весьма странно. Как минимум 50% из перечисленного это просто развлекуха.
comradeleet
Круто, что в интернете всегда кто-то неправ. Статьи получаются интересные)
Zara6502 Автор
я люблю мелкие задачи, можете посмотреть мою статью про слова в предложении, это что-то вроде допинга для мозга, как судоку, но судоку очевидный и линейный, хоть и сложный, а в программировании еще есть элемент творчества, хитрый хак какой - сильно влияющие на скорость.