JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: 2007 TopCoder Collegiate Challenge Marathon Online Round 2
Problem: DeepMining

Problem Statement

    You work for a mining company as a boring machine operator, and you are to quarry minerals of maximal cost during your working day. Unfortunately, boring work is not to your taste, so you decide to automate operating the machine.

Area map

Before each move you are given an accurate map of a certain area around you. It will be represented with String[] map. map will contain exactly 7 elements, and each element of map will contain exactly 9 charactres. Each character of the map will be one of the following: '.' for gob, ' ' for empty space (a cavern in the ground or space above the ground surface), an uppercase letter ('A'-'Z') for valuable mineral or '*' for your machine. Elements of map represent rows of cells of same depth level, element 0 representing the highest visible row.

Your machine will always be positioned in the central cell of the map.

Moving

You have three ways of moving:
  • driving. You can drive one cell left or right if your target cell is empty, and cells under your current cell and your target cell are not empty.
  • flying. You can fly one cell in any direction if your target cell is empty, and the cell under current or target cell is empty too.
  • digging. You can dig one cell left, right or down if the cell under your current cell is not empty, and your target cell is not empty. Here the state of the cell under the target position doesn't matter. Once you have dug through a cell, it becomes empty.
Driving takes 1 unit of fuel per move, while flying and digging take 2 units of fuel per move.

Quarrying minerals

You quarry mineral when you dig through a cell which contains it. If your cargo bay is not full yet, 1 unit of this mineral is added to your cargo. If your cargo bay is already full, but the mineral in question is more valuable than the least valuable mineral in the bay, 1 unit of the mineral in question replaces 1 unit of the least valuable mineral in the bay. You can quarry only 1 unit of mineral from a cell.

Scoring

Your raw score for a test case will be the overall value of the minerals you delivered to the ground surface. 1 unit of mineral denoted with letter x is valued in costFactor(x-'A') points. Thus, 1 unit of mineral A is valued at 1 point, 1 unit of mineral B is valued in costFactor points, and 1 unit of mineral Z is valued in costFactor25 points.

Each time your machine returns to the ground surface, you empty your cargo bay, and the velues of minerals from it add to your score. Note that if you fail to return to the ground surface (you run out of fuel or crash when moving), the minerals from your cargo bay will not be counted in your score.

Your total score will be the sum of raw scores for each test case divided by the highest raw score received by any competitor on this test case, excluding any cases for which all competitors received a raw zero.

Implementation

Your code should implement two methods, as described below:
  • init (fuelTank, cargoBay, maxMineral, costFactor). This method is called once per test case to give you its parameters.
    • fuelTank gives you the quantity of fuel at the beginning of work.
    • cargoBay gives you the cargo bay capacity.
    • maxMineral gives you the most valuable mineral which can be found on this map.
    • costFactor defines the growth of the minerals cost.
    Initially the machine stands somewhere on the ground surface, with full fuel tank and empty cargo bay.
  • move (map). This method is called each time you must make a move. It gives you a map of area around you. You must return the direction of your move - 'U', 'D', 'L' or 'R' for up, down, left or right, respectively. You don't need to specify the kind of moving you'll use, since it is determined by the area around you. Note that if your return will represent an invalid move, your machine crashs. You can also return 'X' if you want to stop moving.


Test case generation

All test cases are generated as follows:
  1. fuelTank, cargoBay, maxMineral and costFactor are chosen uniformly at random.
  2. Probabilities of finding gob and cavern in the cell are chosen uniformly at random between 0.2 and 0.4 and 0.05 and 0.15, correspondingly, and are the same for all depths.
  3. For each possible mineral, a seam depth is chosen randomly, so that the cheaper a mineral is, the smaller its seam depth is. More specifically, mean interval between depths is chosen as (fuelTank/4+3)/(maxMineral-'A'+1). After that, the real intervals between seam depth for alphabetically adjacent minerals are chosen uniformly at random between 0 and 2*interval, and the distance from surface to seam depth for mineral A is chosen uniformly at random between interval and 3*interval.
  4. For each depth, the probabilities of finding a certain mineral in a cell are chosen, so that the further the cell depth is from the mineral's seam depth, the smaller are the chances to find the mineral in the cell. More specifically, for a cell at depth d for all minerals j numbers exp(-(d-seam_depth[j])2/(interval)2) are calculated, divided by their sum and multiplied by (1 - gob_probability - cavern_probability) to represent the probabilities of finding mineral j in a cell at depth d.

Visualizer

A visualization tool is available to aid you in development.
 

Definition

    
Class:DeepMining
Method:init
Parameters:int, int, char, double
Returns:int
Method signature:int init(int fuelTank, int cargoBay, char maxMineral, double costFactor)
 
Method:move
Parameters:String[]
Returns:char
Method signature:char move(String[] map)
(be sure your methods are public)
    
 

Notes

-You may return any integer from init method - it will be ignored.
-If you return a character other than 'U', 'D', 'L', 'R' or 'X', from move method, the simulation will end, and your score for a test case will be 0.
-The area you can explore is infinite in all directions.
-If you dig so deep that you will run out of fuel before you reach the ground surface, the simulation will end immediately in a crash, but the minerals you delivered to the surface before the crash will be counted in your score.
-The memory limit is 64 MB and the time limit is 20 seconds (which includes only time spent in your code).
-There are 6 example test cases and 100 full submission test cases.
 

Constraints

-fuelTank will be between 200 and 10000, inclusive.
-cargoBay will be between 50 and 200, inclusive.
-maxMineral will be an uppercase letter ('A'-'Z').
-costFactor will be between 1.01 and 1.2, inclusive.
-map will contain exactly 7 elements.
-Each element of map will contain exactly 9 characters.
-Each character in map will be '.', ' ', '*' or an uppercase letter from 'A' to maxMineral, inclusive.
-There will be exactly one '*' character in map, and it will be map[3][4].
 

Examples

0)
    
seed = 9
fuelTank = 507
cargoBay = 200
maxMineral = 'V'
costFactor = 1.154
gob probability = 0.207
cavern probability = 0.137
1)
    
seed = 14
fuelTank = 4268
cargoBay = 192
maxMineral = 'Z'
costFactor = 1.143
gob probability = 0.317
cavern probability = 0.108
2)
    
seed = 20
fuelTank = 7890
cargoBay = 53
maxMineral = 'L'
costFactor = 1.2
gob probability = 0.295
cavern probability = 0.11
3)
    
seed = 28
fuelTank = 9460
cargoBay = 52
maxMineral = 'C'
costFactor = 1.178
gob probability = 0.275
cavern probability = 0.054
4)
    
seed = 31
fuelTank = 8532
cargoBay = 197
maxMineral = 'V'
costFactor = 1.03
gob probability = 0.393
cavern probability = 0.105
5)
    
seed = 7
fuelTank = 2447
cargoBay = 179
maxMineral = 'X'
costFactor = 1.101
gob probability = 0.291
cavern probability = 0.068

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.