Written by Chris Alfeld and Chad Barb
Yoyodyne ("riding the high seas of high technology"(tm)) is thriving, indeed. Following their concurrent success in the biological warfare and baby formula industries, they are seeking greener pastures. Suffering from sweeping government cutbacks in baby formula subsidies, Yoyodyne saw a new opportunity with recent advances in "nanotechnogy" and was ready to pounce.
Yoyodyne engineers developed a nano-robot (which it calls a "nanobot") that can be placed on the surface of a silicon wafer before it is made into an integrated circuit. The nanobot moves around on the surface, smoothing and cleaning it as it goes.
During the design, Nanotech engineers discovered that most surfaces have a few valuable molecules scattered on them, so they revised their "bot" to collect these molecules. The nanobot works as follows:
First it is placed on the surface of a wafer at some starting point, which becomes its home base. Under the control of an on-board computer, the bot moves around the wafer, smoothing the surface and picking up valuable items. Due to size restrictions, it can only carry a small number of molecules and has a restricted fuel supply, so it must periodically return to its base and drop its cargo.
Before running out of fuel, the nanobot must return to base, where it can be retrieved to be refueled and reused. Unfortunately, a bot is permanently lost if it doesn't get back to its base before running out of fuel.
One feature of the nanobot's home base is a special flash camera that scans the surrounding area. Unfortunately, this is a one-time process, so the bot's computer must store a single image when it is placed on the surface of the wafer. This surface "map" is then used by the software to plot the nanobots course. The map is simply a 2-dimensional array of "squares", each of which represents a location on the surface of the wafer. Included on the map are the drop point (base) and locations of valuable molecules.
The map also identifies certain areas that contain sensitive components that must be avoided. Your bot may not enter one of those squares.
It is your job to write the software to guide a nanobot. Your goal is to provide a sequence of commands for the bot to allow it to smooth the greatest surface possible and to collect the largest number of valuable molecules with a given amount of fuel.
Your solution should, given a map and a fuel limit, produce a series of movement and pickup commands to guide the nanobot. The commands (defined in detail below) tell the nanobot to move north, south, east, or west; pick up a molecule; stop and wait to be picked up.
The bot can only carry five (5) molecules and automatically drops them when visiting the base. The bot automatically smooths a square upon entering it.
The software must prevent the bot from entering an illegal square.
Your program will receive 1 point for each square visited for the first time, plus a certain number (1-9) per valuable molecule picked up and delivered to base.
The map includes the location of the base or start point. This square never contains a valuable molecule. Every time the bot visits its base, all the molecules it is carrying are dropped and scored. If it does not end on its base (i.e., if it runs out of fuel at some other location), you will be charged 10 points (the cost of the nanobot) and any objects it is carrying at that time will not be scored.
The borders of all maps are designated as sensitive locations, so there is no way your bot can wander off of the map if your program is working properly. Note that borders may not be rectangular!!
Moving to and cleaning a square takes one fuel unit total. Picking up a molecule consumes one fuel unit.
All input is from standard input (i.e., the keyboard).
Input consists of the width of the map, the height of the map, the amount of fuel, and then the map itself.
10 10 30 XXXXXXXXXX X 3 5 X X 4 X X7 1 X X B 8 X X X X 9 3 X X 6 3X X 4 X XXXXXXXXXX
No map will be smaller than 3x3.
" (space) indicates a normal (empty) square.
X indicates a sensitive square that the nanobot cannot enter.
1-9) indicate molecules of various worth.
B indicates the starting position.
All output is to standard output (i.e., the screen).
Output consists of one action per line with the actions being:
NORTH - Move North
SOUTH - Move South
EAST - Move East
WEST - Move West
TAKE - Pick up a Molecule
END - Stop
NORTH TAKE NORTH EAST EAST TAKE EAST SOUTH SOUTH TAKE WEST WEST WEST WEST WEST WEST NORTH TAKE SOUTH SOUTH SOUTH EAST TAKE EAST EAST NORTH NORTH END
| Input | Comment | Score | Fuel | Bin |
NORTH | Move north | 1 | 29 | |
TAKE | Pick up molecule | 1 | 28 | 1 |
NORTH | Move north | 2 | 27 | 1 |
EAST | Move east | 3 | 26 | 1 |
EAST | Move east | 4 | 25 | 1 |
TAKE | Pick up molecule | 4 | 24 | 1 4 |
EAST | Move east | 5 | 23 | 1 4 |
SOUTH | Move south | 6 | 22 | 1 4 |
SOUTH | Move south | 7 | 21 | 1 4 |
TAKE | Pick up molecule | 7 | 20 | 1 4 8 |
WEST | Move west | 8 | 19 | 1 4 8 |
WEST | Move west | 9 | 18 | 1 4 8 |
WEST | Move west (1,2) | 22 | 17 | |
WEST | Move west | 23 | 16 | |
WEST | Move west | 24 | 15 | |
WEST | Move west | 25 | 14 | |
NORTH | Move north | 26 | 13 | |
TAKE | Pick up molecule | 26 | 12 | 7 |
SOUTH | Move south (2) | 26 | 11 | 7 |
SOUTH | Move south | 27 | 10 | 7 |
SOUTH | Move south | 28 | 9 | 7 |
EAST | Move East | 29 | 8 | 7 |
TAKE | Pick up molecule | 29 | 7 | 7 9 |
EAST | Move East | 30 | 6 | 7 9 |
EAST | Move East | 31 | 5 | 7 9 |
NORTH | Move North | 32 | 4 | 7 9 |
NORTH | Move North (1,2) | 48 | 3 | |
| END | End Run | 48 | 3 |
There are several possible ways to tackle this problem. Here are a few to get you started:
We have provided C++ source code for a simulator program. This program will input a map file and a list of commands. It will figure out your score, display incorrect move commands, and potentially provide other information. This is the same program we will use to test your bots. See the README file for more information.
A number of sample maps are at the bottom of this document. We will test your rover using these and other maps. Feel free to make your own maps to help test your bots.
We have also provided a C++ version of a basic shell for your nanobot. The
shell contains a main procedure that will parse the input file as well as a
number of procedures to produce output. These procedures are:
MoveNorth(), MoveSouth(), MoveEast(), MoveWest(), TakeMolecule(), and
EndRun(). This is a good starting point but does not necessarily need
to be used.
Please submit your source code and a DOS executable via e-mail or bring a floppy disk when you come to the contest. E-mail submissions should be sent to hspc@cs.utah.edu.
Your submission will be run on a large number of maps. In order to keep testing times down and prevent brute force algorithms the following restrictions are imposed.
Your submission will be scored on a range of 0-200. Of these 200 points, 50 will be for code clarity, organization, and program efficiency (both memory and CPU cycles). The remaining 150 points will be based on test cases.
Clear code has meaningful variable names, indentation to show structure, comments where appropriate, and is generally easy to understand. With comments, quantity does not equal quality; please do not fill your code with useless comments. Organized code uses functions and procedures where appropriate, meaningful and intuitive data structures and, in larger projects, multiple source files and modules. Efficient code uses data structures that are sufficient for the task and algorithms that are as fast as the data allows. There is a tradeoff between speed and memory usage; if you lean heavily in one direction or the other for your program, please indicate so in a comment. Memory leaks and useless computations do not make efficient code.
Each test map will be assigned a weight. The solution that scores the top score on that map will receive the full number of points for that map; other solutions will receive a number points equal to the ratio of their score to the top score (example: on a 50 point map if the top score is 40 and your solution scores 20 then you will receive 20/40 = 1/2 the points, or 25). Solutions that crash will be penalized with a small negative score for that map. Solutions that run out of time will receive their current score at time out. The scores will be totaled, with the top total score receiving the full 150 points and the other scores receiving points in a similar manner to the map scores.
There will be at least one map that will test the limits of the problem description. For example, a 3x50 map is valid, as is a map with borders very close to the base.
A web page that will contain bug-fixes, updates, and answers to common questions is available at the contest web page.
Please send all questions and comments to: hspc@cs.utah.edu
10 10 30 XXXXXXXXXX X 3 5 X X 4 X X7 1 X X B 8 X X X X 9 3 X X 6 3X X 4 X XXXXXXXXXX
10 10 100 XXXXXXXXXX X4 5 6X XXXXXX XXX X9X 4 7X X X XXXX X X X 3X X X X 2X 7X X5 X X XX4XB XX3X XXXXXXXXXX
20
33
150
XXXXXXXXXX
X X
X X
XXXXXXX 3 5 XXXXX
X 2 4 X
X 4 X
X XXX 7 X
X 3 3XXXXX X
X XXX X
X1 2 X
X 3 X
X B 3 X
X 2 X
X 2 4 X
X 1 1 X
X XXXX X
X X X 3 3 X
X X6 1 X
X5 X X 2 X
X XXXX X
X 2 3 X
X 7 X
X XXXXXXXXXXX X
X 3 XXXXXXXXXXX X
X XXXXXXXXXXX X
X 2 1 X
X 5 1111 X
X XXXX 1111 X
X 1 XXXX 1 X
X 4 XXXX X
X 2 9 X
X 3 1 X
XXXXXXXXXXXXXXXXXXXX