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

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

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

Клон МТС-овской задачи я немножко упростил в отношении координат и расстояний - теперь всё измеряется просто в клетках. Лабирит носит незамысловатый характер - он из квадратных клеток, сам размера 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. В общем наверное учить шестнадцатеричным цифрам не требуется :)

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

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

Заключение

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

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