Robot in the Labyrinth from MTS – you can practice in any language
The qualifying round for the competition from MTS has recently ended – if you didn’t have time to participate, no problem 🙂 I managed to recreate the task about a robot in a maze – and you can practice (now – in any language!)
If you tried to participate, you may have been amazed by the confusion of the instructions, the crooked implementation of the emulator, and the unresponsive support. At the same time, the robot puzzles were easy, educational, and overall fun. They had to be resolved by sending requests to the API. I made an analogue of the “API server” for the first of the three – so that I could practice it myself later (I don’t really like my solution) – and to share with my colleagues who are fans of such exercises. Below there will be just a small instruction for use with an example of sending commands to the robot simply manually, using the command line.
I simplified the clone of the MTS problem a little in terms of coordinates and distances – now everything is simply measured in cells. The labyrite is of a simple nature – it is made of square cells, the size itself N*N – and between each pair of cells there is either a wall or not (no one-way doors, teleports, etc.)
_ _ _ _ _ _ _ _ _ _ _ _ _
|_ _ _ _ _ | | | |_ | // визуализация просто для примера
|_ _ _ _ _|_ _ _ _| |_ | | // лабиринт генерится рандомно
| |_ |_ _ _ _ _ _ _ | |
|_ _ |_ _ _| _ | | |
|_ _ _| _|_|_ _ _|
|_ _|_ | | _| _ _ |
| |_|_|_ _| |_ _ | |
|_| | |_|_ _ _ _| _ | |
|_ | |_ _ _| | _ | _| |
| |_|_ _ _ _|_ | | |
| |_ |_ _ _|_ _ |_| | |
| | _ _|_ _ _ _ _|_ |_| |
|_|_ _|_ _ _ _ _ _ _ _|_ _| The starting position of the robot is in the lower left corner. In this case, it is clear that he can only move from there in the direction “north” (or “up” in the picture).
You will be able to give commands forward And backward to move one square forward or backward, as well as left And right to rotate the robot 90 degrees (initially it is oriented north).
Technical Details
Implemented on the basis of the CodeAbbey website (my open source website with tasks – since there are other HTTP tasks there, it was easiest for me to add another one to the ready-made infrastructure). The task page is here: https://www.codeabbey.com/index/task_view/maze-mapping-api-robot (if English is difficult or clumsy, right-click and ask Google to translate – I think it works very well).
To play with the server you need to get a token – it is valid for an hour. To do this you will need to log in to the site (but registration is much simpler than with MTS – create a password and that’s it, mail is optional) – then a token will appear on the task page as input data.
Now we can start the game – from the description of the task we can figure out where the server address is – and send our first request there – for example, with a curl. We will do everything manually first – to make it easier to understand what and how to program.
Data can be sent in three different formats – text/plain, application/json and application/x-www-form-urlencoded (the latter is used by default, although the server will try to guess if it sees json, for example).
export MAZE_URL=http://codeabbey-games.atwebpages.com/maze1.php
curl -d 'token=blahblahblah' $MAZE_URLWhen the server receives the token without additional commands, it will reinitialize the maze and restart the game. Endpoint analogue restart at MTS.
If everything is fine with the token, URL and network, you will receive a response like:
x: 0
y: 6
dir: 0
front: 1
right: 0
back: 0
left: 0
steps: 0Here, first we see two coordinates and the third line is the direction where the robot is now turned (0 – north, 1 – east, 2 – south, 3 – west – in general, clockwise).
Next are four sensor values (front, right, back, left) – one means that there is a passage in this direction and you can move.
We see that there is a way forward. Let's execute the command forward (don't forget the token with each request):
curl -d 'token=blahblahblah&cmd=forward' $MAZE_URLthe answer will be similar to the previous one, but the robot has moved:
x: 0
y: 5
dir: 0
front: 1
right: 0
back: 1
left: 0
steps: 1Let's try to turn around:
curl -d 'token=blahblahblah&cmd=right' $MAZE_URLnow the coordinates remain unchanged – but the direction indicator has become 1 and the sensors are oriented differently:
x: 0
y: 5
dir: 1
front: 0
right: 1
back: 0
left: 1
steps: 2Result View
In order to win, you need to go around the entire maze and make yourself a map (preferably programmatically and not manually), and then send it with a special command guess:
export RESULT=4444444-579d555-7945555-783d3d5-5445479-557bbbc-3bbaa81
curl token=blah&cmd=guess&matrix=$RESULT $MAZE_URLLet's consider what kind of map description this is, which for clarity we have arranged in a temporary variable RESULT.
Here N lines by N characters, and they are separated (connected?) by hyphens. Each symbol represents one cell, starting from the top left corner and line by line.
The symbol is simply a hexadecimal number from 0 to F – it encodes the presence of passages in a given cell, the order of the bits corresponds to the order of directions (north, east, south, west – as above). That is, if there is a passage only to the north, this is a bitmask 0001 – write a symbol 1. If there are exits to the south and west – this is a mask 1100 – write a symbol f. In general, you probably don’t need to learn hexadecimal digits 🙂
If the map you made is incorrect, the server will answer which one it actually expected and end the game.
If the card is correct, the game will also end, but in addition, the server will issue a secret token for the answer (you can submit it on the page with the task so that it will be credited to you, if it is important/needed/interesting to you).
Conclusion
There were actually three tasks in the qualifying round tasks. The first required making a map, the second required finding the shortest path to the center. In the third, it was necessary to control a “physical” robot (that is, taking into account motors on both sides, accelerations, distances, etc.). If such exercises are of interest, I will be happy to try to implement the remaining two.
And of course, if someone shares tasks from the next round (at its end), then maybe it will be possible to implement them too.
