The challenge of the competition ICFPC-2012: the robot and 位
Just a few hours ago, the ICFPC-2012 competition began, which will last the whole weekend . I decided to transfer the task for this contest in the hope that someone from the interested people will have time to take part.
The task is quite understandable, so go ahead.
The task was amended: water , teleports , beard and super stones .
')
Lambda mines found in Scotland! Your task is to read the map of the mine to create a program for the robot.
Link to a beautiful simulator: icfp.stbuehler.de/icfp2012
The map is a grid of m 脳 n cells, the coordinate (1.1) is located at the bottom and on the left.
Each cell contains one of the following characters:
Nothing can penetrate the wall. Nothing can go beyond the m 脳 n field. A robot can dig the ground, collect 位 and move stones. Stones fall. Stones can kill the robot.
An example of the initial state:
If the coordinates of the robot (x, y):
You can move into a cage with an open exit, in an empty, in a cage with earth and a cell with 位. You can still move (only left and right) in a cell with a stone, if there is an empty space behind the stone. After leaving the cage, the robot always leaves a void in the cage.
After the movement of the robot passes the simulation step. During this stage, the old state is always read and written in the new. In the following order of coordinates: (1, 1), (2, 1), ..., (n, 1), (1, 2) ... (n, m).
Rules are checked in order, from top to bottom. If one worked, then the following will no longer work.
If there is no more 位 on the card, all closed exits open.
If a robot stood under the stone that had just fallen - the robot breaks, this is a defeat.
In one step of the simulation, the stones fall 1 cell down.
Sometimes stones from different sides can fall into one cell. In this case, there is now 1 stone in this cell.
Input from stdin, output to stdout
If some lines are shorter than the maximum line length, then they are considered to be padded spaces to the right.
At the beginning of each map there are no open exits. There are exactly 1 robot and exactly 1 closed exit.
The card can be 1000 脳 1000 and more.
For each step -1
For collected 位 +25
For the collected 位 at the time of the command A +25
For the collected 位 at the time of reaching +50
Script to test your test card passing options: validator
The program should work on 32bit Debian-linux with 1 Gb of RAM.
After 150 seconds, the program receives SIGINT, after which it has 10 seconds to output a response.
After these 10 seconds, SIGKILL and 0 points.
During the competition there will be from 1 to 4 rule changes.
Details in English: icfpcontest2012.wordpress.com
Some mines are beginning to flood!
Now, after the description of the map, there can be an empty line and then 3 parameters (1 per line):
Water 0
Flooding 0
Waterproof 10
(0, 0, 10) - default values.
Water indicates the initial value of the water level (remember that we count the coordinates from 1, and the water level may be 0).
Flooding - the rate of stay of water. If 0 - water does not come at all. If N> 0, then exactly after the N steps the water level increases by 1.
Waterproof - the level of protection of the robot, how many steps without diving it can pass under water. As soon as it has emerged, the step counter is reset and you can dive again.
A robot is considered to be under water if its y coordinate is <= water level.
If the robot holds under water more than the Waterproof steps, it breaks.
Teleports have been added to the game (in the dock they are called springboards). The teleport input is denoted by the letters A..I, the teleport output is the number 1..9.
After entering the teleport, the entrance of the teleport and its exit disappears.
Which input leads to which output is described after the card with phrases:
Trampoline A targets 1
Trampoline B targets 1
Trampoline C targets 2
Added beard - W and razor - ! . At the end of the map, it now says how many razors the robot has and how fast the beard grows:
Grow 15
Razors 2
The height value (g) by default is 25, the number of razors is 0.
Each g of steps a beard fills 8 adjacent cells if they are empty (that is, including the diagonal).
Razor - the only means of combating a beard. After the S command is executed, the razor (if the robot has one) applies and clears 8 neighboring cells from the beard.
Added @ - higher order stones, inside which 位 are hidden. When falling from any height, the stone breaks and in its place 位 appears.
Note that the task is very similar to the complicated Boulder Dash, the passage of which, in the general case, as proved, is an NP-complete problem.
The proof is quite simple: I have such labyrinths, the solution of which is equivalent to finding a Hamiltonian cycle in a graph, and this is a well-known problem: wiki Hamiltonian cycle
The task is quite understandable, so go ahead.
The task was amended: water , teleports , beard and super stones .
')
Lambda mines found in Scotland! Your task is to read the map of the mine to create a program for the robot.
Link to a beautiful simulator: icfp.stbuehler.de/icfp2012
Fundamental rules
- The robot skips any symbols unknown to it (and only L, R, U, D, W, A. are known to it
- If the Robot cannot execute the command, it simply does nothing this move.
- After the robot moves, the map is updated according to the rules described below.
- After updating the map, the completion conditions are checked.
Map Description
The map is a grid of m 脳 n cells, the coordinate (1.1) is located at the bottom and on the left.
Each cell contains one of the following characters:
- R - robot
- * - stone
- L - closed exit
- . - land
- # - wall
- \ - 位
- O - open output
- " "- space, empty cell
Nothing can penetrate the wall. Nothing can go beyond the m 脳 n field. A robot can dig the ground, collect 位 and move stones. Stones fall. Stones can kill the robot.
An example of the initial state:
####### #..***# #..\\\# # ..**# #.*.*\# LR....# ####### Robot commands
If the coordinates of the robot (x, y):
- L - to the left, at (x-1, y)
- R - right, at (x + 1, y)
- U - up, at (x, y + 1)
- D - down, at (x, y-1)
- W - wait, do nothing
- A - interrupt mine exploration
You can move into a cage with an open exit, in an empty, in a cage with earth and a cell with 位. You can still move (only left and right) in a cell with a stone, if there is an empty space behind the stone. After leaving the cage, the robot always leaves a void in the cage.
Map update (simulation)
After the movement of the robot passes the simulation step. During this stage, the old state is always read and written in the new. In the following order of coordinates: (1, 1), (2, 1), ..., (n, 1), (1, 2) ... (n, m).
Rules are checked in order, from top to bottom. If one worked, then the following will no longer work.
- There is emptiness under the stone - the stone drops 1 square down.
- Under the stone there is a stone, on the right it is empty and on the bottom right it is empty - the stone falls diagonally to the right.
- Under the stone there is a stone, the left is empty and the bottom left is empty - the stone falls diagonally to the left.
- Under the stone - 位, the right is empty and the bottom right is empty - the stone falls diagonally to the right.
- The remaining cells do not touch.
If there is no more 位 on the card, all closed exits open.
If a robot stood under the stone that had just fallen - the robot breaks, this is a defeat.
In one step of the simulation, the stones fall 1 cell down.
Sometimes stones from different sides can fall into one cell. In this case, there is now 1 stone in this cell.
Termination conditions
- The robot entered the open elevator - WIN
- The robot has executed the command A - WIN
- Robot crushed by a stone - LOSE
Input Output
Input from stdin, output to stdout
If some lines are shorter than the maximum line length, then they are considered to be padded spaces to the right.
At the beginning of each map there are no open exits. There are exactly 1 robot and exactly 1 closed exit.
The card can be 1000 脳 1000 and more.
Scoring
For each step -1
For collected 位 +25
For the collected 位 at the time of the command A +25
For the collected 位 at the time of reaching +50
Script to test your test card passing options: validator
Limits
The program should work on 32bit Debian-linux with 1 Gb of RAM.
After 150 seconds, the program receives SIGINT, after which it has 10 seconds to output a response.
After these 10 seconds, SIGKILL and 0 points.
During the competition there will be from 1 to 4 rule changes.
Details in English: icfpcontest2012.wordpress.com
The first rule change: water
Some mines are beginning to flood!
Now, after the description of the map, there can be an empty line and then 3 parameters (1 per line):
Water 0
Flooding 0
Waterproof 10
(0, 0, 10) - default values.
Water indicates the initial value of the water level (remember that we count the coordinates from 1, and the water level may be 0).
Flooding - the rate of stay of water. If 0 - water does not come at all. If N> 0, then exactly after the N steps the water level increases by 1.
Waterproof - the level of protection of the robot, how many steps without diving it can pass under water. As soon as it has emerged, the step counter is reset and you can dive again.
A robot is considered to be under water if its y coordinate is <= water level.
If the robot holds under water more than the Waterproof steps, it breaks.
Second rule change: teleports
Teleports have been added to the game (in the dock they are called springboards). The teleport input is denoted by the letters A..I, the teleport output is the number 1..9.
After entering the teleport, the entrance of the teleport and its exit disappears.
Which input leads to which output is described after the card with phrases:
Trampoline A targets 1
Trampoline B targets 1
Trampoline C targets 2
Third rule change: biomass and razors
Added beard - W and razor - ! . At the end of the map, it now says how many razors the robot has and how fast the beard grows:
Grow 15
Razors 2
The height value (g) by default is 25, the number of razors is 0.
Each g of steps a beard fills 8 adjacent cells if they are empty (that is, including the diagonal).
Razor - the only means of combating a beard. After the S command is executed, the razor (if the robot has one) applies and clears 8 neighboring cells from the beard.
Last rule change: higher order stones
Added @ - higher order stones, inside which 位 are hidden. When falling from any height, the stone breaks and in its place 位 appears.
About complexity assessment
Note that the task is very similar to the complicated Boulder Dash, the passage of which, in the general case, as proved, is an NP-complete problem.
The proof is quite simple: I have such labyrinths, the solution of which is equivalent to finding a Hamiltonian cycle in a graph, and this is a well-known problem: wiki Hamiltonian cycle
Source: https://habr.com/ru/post/147789/
All Articles