| | You are a lumberjack, and it is your job to inspect the forest before harvesting, to mark any trees that have been infected with a wood rotting disease. You only have a limited amount of daylight left, and therefore must work as efficiently as possible to mark off as many such trees as possible, while still having time to return to your starting point. (Otherwise, you would risk becoming hopelessly lost in the forest under the dark of night.) The trees are all arranged in a rectangular grid, so when standing in the middle of four surrounding trees, it is possible to look in any of the four cardinal directions, and attempt to determine visually if any of the trees are infected. Unfortunately, as trees are further away from you, it becomes more difficult to accurately determine whether or not they are infected.
You start at (0,0), the Northwest corner of the forest. At any given moment, you can move in a series of steps East/West/North/South, or look in any of the same four directions. Moving takes one unit of time per step. Looking in any of the four directions also takes one unit of time. Unfortunately, company policy forbids you from looking while moving, as you might trip as a result of not watching where you are going.
Your code must implement a method examineForest. You are given ints height and width describing the size of the forest, an int time indicating the maximum amount of time available before you run out of daylight, and a double density describing how thick the forest is. Your method should make use of the two available library functions, look and move, in order to move throughout the forest in search of infected trees. Your method should return 0 after you have returned to the point of origin.
Library Methods
look: This method should be called with a single String parameter ("E", "W", "S" or "N") indicating the direction you want to look. The method will return a String[] containing exactly two elements. The first element represents your assessment of the row of trees to your left, and the second element your assessment of the row of trees to your right (where left and right are relative to the direction you are looking, and the row extends away from you). Each character of each element represents your assessment of a single tree, and is either 'Y' or 'N', indicating that the tree does or does not appear to be infected. The first character is the tree directly in front of you, the next character is the tree behind it (relative to the direction you are looking), etc. The two trees directly in front of you are always assessed correctly, and are immediately marked when applicable. The probability of assessing a tree in the distance as being infected is described by: baseline * (1 - (1 - density)distance) + (1 - density)distance * I, where I is 0 for uninfected trees and 1 for infected trees, baseline is the proportion of infected trees throughout the whole forest, and distance is 0 for the trees directly in front of you, 1 for the next pair, and so on. If there are no trees in one of the rows (for example, if looking east from (0,0)) that element of the return will be the empty string.
move: This method should be called to move through the forest. The single String parameter should indicate the direction(s) you wish to move (in order), where each character is 'E', 'W', 'N' or 'S'. The return will be a int[], indicating your coordinates after moving. (ret[0] = x, ret[1] = y)
Scoring
Your raw score for each test case will simply be the number of infected trees you mark during your travel through the forest, presuming you make it back out within the given time. Any invalid parameters passed to the library methods will result in scoring a 0 for that test case. Any calls to the move method that would cause you to go outside the region from (0,0) to (width,height) will result in a 0 for that test case. If your method makes too many calls, such that your lumberjack is still in the forest after nightfall, you will score a 0 for that test case.
Your total score will be calculated by adding up your relative score for each test case. The relative score for a test case is given by the formula:
(my score for this test case) / (max score by anyone for this test case)
Test Case Generation
width, height, time, and density will be chosen uniformly at random.
We then select, all uniformly at random, M between 40 and 60, P between 10 and 15, q0 between 0.30 and 0.34, and q between 0.45 and 0.49.
We start with a width * height grid of trees.
K = (width * height / 200) of them are chosen at random.
Those K are the seeds. Each of those K start spreading disease at a
random time -t, where t in [0..M - 1]. When spreading, each tree that is infected has an incubation period of P, after which it starts spreading the disease.
That is to say, if a tree is infected at time t, then at time t + P
it will infect other trees. A tree that has incubated immediately spreads disease to all
other (not yet infected) trees, with probability q0 * q^dist (where dist is the Manhattan distance between the two trees). The disease spreading continues until time 0, when you enter the forest. At this point, the disease spreading process stops, (imagine that the disease spreading timescale is much longer than the timescale used for walking around). In pseudocode:
for K seeds
(x,y) = a random, uninfected tree
t = -Random[0...M - 1]
Mark(x, y) as infected
Add (x, y) to incubation list at time t
While incubation list has trees
currentTree = take earliest incubated tree from list
for each tree in forest
if tree is not already infected and Random < q0 * q^(man dist) then
set tree as infected
if (t + P <= 0) then
add this tree to incubation list for time t + P
Visualizer
A visualizer is provided to help you develop your solution. The seeds for the examples are 1-10. |