Робот в Лабиринте от МТС — можно практиковаться на любом языке

На днях завершился отборочный тур на соревнование от МТС — если вы не успели поучаствовать — не беда 🙂 мне удалось воссоздать задачу про робота в лабиринте — и вы сможете попрактиковаться (теперь — на любом языке!)

Если вы попытались участвовать то возможно были поражены запутанностью инструкций, кривоватой реализацией эмулятора и безответным суппортом. В то же время задачки про роботов были несложными, поучительными и в целом забавными. Их нужно было решать отсылая запросы к АПИ. Я сделал аналог «АПИ-сервера» для первой из трёх — чтобы позже поупражняться самому (мне не очень нравится моё решение) — и чтобы поделиться с соратниками — любителями подобных упражнений. Ниже будет просто небольшая инструкция по использованию с примером отправки команд для робота просто вручную, курлом из командной строки.

Клон МТС-овской задачи я немножко упростил в отношении координат и расстояний — теперь всё измеряется просто в клетках. Лабирит носит незамысловатый характер — он из квадратных клеток, сам размера N*N — и между каждой парой клеток стенка либо есть либо нет (никаких однонаправленных дверей, телепортов и пр.)

 _ _ _ _ _ _ _ _ _ _ _ _ _ |_ _ _ _   _  | |   | |_  |     // визуализация просто для примера |_ _ _ _ _|_ _ _ _| |_  | |     // лабиринт генерится рандомно | |_  |_ _ _   _ _ _ _  | | |_ _  |_ _   _|    _  | | | |_   _     _|  _|_|_ _   _| |_ _|_  | |  _|    _ _    | |       |_|_|_ _| |_ _  | | |_| | |_|_   _ _ _|  _  | | |_  | |_ _ _| |  _  |  _| | |   |_|_ _   _ _|_  | |   | | |_  |_ _ _|_ _    |_| | | | |  _ _|_ _ _ _ _|_  |_| | |_|_ _|_ _ _ _ _ _ _ _|_ _| 

Стартовое положение робота — в левом нижнем углу. В данном случае видно что двигаться он может оттуда только в направлении «север» (или «вверх» по картинке).

Вы сможете давать команды forward и backward чтобы сдвинуться на одну клетку вперед или назад, а также left и right чтобы повернуть робота на 90 градусов (изначально он ориентирован на север).

Технические Подробности

Реализовано на базе сайта CodeAbbey (мой опенсорсный сайт с задачами — т.к. там есть другие задачи на HTTP, мне было проще всего добавить ещё одну к готовой инфраструктуре). Страница задачи здесь: https://www.codeabbey.com/index/task_view/maze-mapping-api-robot (если английский сложен или коряв, щёлкните правой кнопкой и попросите гугл перевести — по-моему это работает очень хорошо).

Чтобы играть с сервером нужно получить токен — он действует в течение часа. Для этого понадобится залогиниться на сайт (но регистрация намного проще чем у МТС — придумайте пароль и всё, почта опционально) — тогда на странице задачи в качестве входных данных появится токен.

Теперь можно начать игру — по описанию задачи можно разобраться где адрес сервера — и отправить туда наш первый запрос — например курлом. Мы всё проделаем для начала ручками — чтобы было легче понять что и как запрограммировать.

Данные можно присылать в трёх разных форматах — text/plain, application/json и application/x-www-form-urlencoded (последний используется по умолчанию хотя сервер попытается угадать если увидит например json).

export MAZE_URL=http://codeabbey-games.atwebpages.com/maze1.php  curl -d 'token=blahblahblah' $MAZE_URL

Когда сервер получает токен без дополнительных команд он реинициализирует лабиринт и рестартит игру. Аналог эндпойнта restart у МТС.

Если с токеном, урлом и сетью всё нормально, вы получите ответ в духе:

x: 0 y: 6 dir: 0 front: 1 right: 0 back: 0 left: 0 steps: 0

Здесь сначала мы видим две координаты и третьей строчкой идёт направление куда сейчас повернут робот (0 — север, 1 — восток, 2 — юг, 3 — запад — в общем, по часовой стрелке).

Далее идут четыре значения датчиков (front, right, back, left) — единица означает что в данном направлении есть проход, можно двигаться.

Мы видим что есть проход вперед. Выполним команду forward (не забываем токен с каждым запросом):

curl -d 'token=blahblahblah&cmd=forward' $MAZE_URL

ответ будет похож на предыдущий, но робот сдвинулся:

x: 0 y: 5 dir: 0 front: 1 right: 0 back: 1 left: 0 steps: 1

попробуем повернуться:

curl -d 'token=blahblahblah&cmd=right' $MAZE_URL

теперь координаты остались неизменными — но указатель направления стал 1 и датчики ориентированы по-другому:

x: 0 y: 5 dir: 1 front: 0 right: 1 back: 0 left: 1 steps: 2

Представление Результата

Для того чтобы выиграть, нужно обойти весь лабиринт и составить себе карту (лучше программно а не вручную) после чего отправить её специальной командой guess:

export RESULT=4444444-579d555-7945555-783d3d5-5445479-557bbbc-3bbaa81 curl token=blah&cmd=guess&matrix=$RESULT $MAZE_URL

Рассмотрим что это за описание карты, которое для наглядности мы устроили во временной переменной RESULT.

Здесь N строк по N символов, и они разделены (соединены?) дефисами. Каждый символ означает одну клетку, начиная с верхнего левого угла и построчно.

Символ — просто 16-ричное число от 0 до F — им закодировано наличие проходов в данной клетке, порядок бит соответствует порядку направлений (север, восток, юг, запад — как и выше). То есть если есть проход только на север, это битовая маска 0001 — пишем символ 1. Если есть выходы на юг и на запад — это маска 1100 — пишем символ f. В общем наверное учить шестнадцатеричным цифрам не требуется 🙂

Если карта, которую вы составили, неправильна — сервер ответит какую он на самом деле ждал и завершит игру.

Если карта верна — игра тоже завершится, но кроме этого сервер выдаст секретный токен для ответа (его можно засубмитить на странице с задачей чтобы она была вам зачтена, если вам это важно/нужно/интересно).

Заключение

В заданиях отборочного тура задач было на самом деле три. В первой требовалось составить карту, во второй — отыскать наиболее короткий путь до центра. В третьей нужно было управлять «физическим» роботом (т.е. с учетом моторов с двух сторон, ускорений, расстояний и т.п.). Если подобные упражнения вызывают интерес — я с удовольствием попробую реализовать и оставшиеся две.

Ну и конечно если кто-то поделится заданиями со следующего тура (по его окончании) — то быть может удастся имплементировать и их.