PROBLEM STATEMENT
While sitting outside and enjoying the lovely weather, Dave noticed a bunch of
one-inch caterpillars at the base of a nearby tree. The caterpillars were
racing slowly to the top of the tree where a green leafed utopia was awaiting
their immense hunger. Dave took one look at the frantic little caterpillars
and knew immediately which caterpillar would win.
What Dave noticed was that all the caterpillars moved in the same general
pattern, but each caterpillar moved in its own distinct cycle. At each second,
a caterpillar can do one of three things:
1.) The caterpillar can remain still.
2.) The caterpillar can bring its tail end halfway from the tail's current
position to its head.
3.) The caterpillar can stretch out to its original length by moving its head
forward and assuming an extended position.
A caterpillar's cycle is a list of movements the caterpillar chooses. When all
movements have been executed, the caterpillar will begin its cycle again. At
the beginning of its first cycle, the caterpillar is in the extended state.
A caterpillar may choose movement 1 at any time. From its extended position, a
caterpillar may choose movement 2 up to 8 times before choosing movement 3. A
caterpillar must not choose movement 3 if it is already in its extended
position. If movement 2 is chosen, the caterpillar must choose movement 3
somewhere in its cycle.
*The cycle "3333" is illegal because a caterpillar cannot choose move 3 from
the extended position.
*The cycles "2222" and "2222222232" are all illegal because a caterpillar may
not choose movement 2 more than eight times without choosing movement 3 (this
applies throughout the repetitions of each cycle).
Consider the example where a caterpillar's cycle is "223". At time 0 the
caterpillar moves its back end forward one half-inch. At time 1 the
caterpillar moves its back end forward 1 quarter-inch. At time 2 the
caterpillar moves its head forward 3 quarters of an inch. At time 3 the
caterpillar begins its cycle again by moving its back end forward one
half-inch. For this example, the caterpillar makes 3 quarters of an inch
progress every 3 seconds. Notice that at time 0 and 1 the caterpillar made
only potential progress and is actually no closer to the goal than it began.
Your task is to determine which caterpillar will reach the goal first given the
cycle of each caterpillar and the distance to the goal (in inches). A
caterpillar reaches the goal when its head has moved the distance of "distance"
or more.
DEFINITION
Class: LarvaRace
Method: getWinner
Parameters: String[], int
Returns: int
Method signature (be sure your method is public): int getWinner(String[]
cycles, int distance);
If two or more caterpillars tie, your method should return the lowest numbered
caterpillar of the tied caterpillars. Lowest numbered means the index of the
first element in cycles of the tied cycles. See example 4.
NOTES
*Caterpillars start with their heads at a distance of "distance" from the goal.
*Caterpillars never interfere with each other's movements.
*Caterpillars' moves are instantaneous.
The diagram below shows a single cycle of the the caterpillar's movement for
cycles = {"213"} and distance = 1
T represents the tail end of the caterpillar.
H represents the head of the caterpillar.
G represents the goal.
Time 0, no move has been chosen:
T------H G
|_______|_______|
1 inch 1 inch
Time 1, move 2 is chosen:
T--H G
|___|___|_______|
1/2 1/2 1 inch
Time 2, move 1 is chosen:
T--H G
|___|___|_______|
1/2 1/2 1 inch
Time 3, move 3 is chosen:
T------H G
|___|_______|___|
1/2 1 inch 1/2
When H and G are in the same position or H has passed G, the caterpillar has
reached the goal.
TopCoder will ensure the validity of all inputs.
Inputs are valid if all of the following criteria are met:
* distance will be between 0 and 20, inclusive
* cycles will contain between 1 and 10 elements, inclusive
* The length of each element in cycles will be between 1 and 10, inclusive
* Caterpillars will never choose move 2 more than eight times without chosing
move 3
* Caterpillars will never choose move 3 when already in the extended state.
* At least one caterpillar will be able to reach the goal
EXAMPLES
0) cycles = {"123", "223", "23", "23223", "232"}
distance = 1
returns: 2
Caterpillar 0: 123
Caterpillar 1: 223
Caterpillar 2: 23
Caterpillar 3: 23223
Caterpillar 4: 232
If the distance is 1 inch, which caterpillar will win?
Caterpillar 0 moves 1 half-inch every 3 seconds, so it will take 6 seconds to
reach the goal.
Caterpillar 1 moves 3 quarters of an inch every 3 seconds, so it will take 6
seconds to reach the goal.
Caterpillar 2 moves 1 half-inch every 2 seconds, so it will take 4 seconds to
reach the goal.
Caterpillar 3 moves 1 half-inch during the first 2 seconds of its cycle and 3
quarters of an inch during the last 3 seconds of its cycle, so it will take 5
seconds to reach the goal.
Caterpillar 4 moves 1 half-inch during the first 2 seconds of the race and 3
quarters of an inch every 3 seconds thereafter, so it will take 5 seconds to
reach the goal.
Because caterpillar 2 takes the least time to reach the goal, your method
should return 2.
1) cycles = {"231", "2232", "23"}
distance = 3
returns: 2
2) cycles = {"22223", "1123"}
distance = 1
returns: 1
3) cycles = {"22223", "1123", "1"}
distance = 2
returns: 0
4) cycles = {"2223", "23"}
distance = 0
returns: 0
5) cycles = {"232322323", "232323223"}
distance = 3
returns: 0