TopCoder problem "FallingCoconuts" used in SRM 273 (Division I Level One , Division II Level Two)



Problem Statement

    You are on vacation on a tropical island, but you couldn't resist the temptation of solving a good old problem. It all started when a group of kids played a game they call "The Falling Coconuts". In this game, a number of coconuts fall to the ground, one by one, on a single axis, at the locations given in drops. If a coconut X lands on the ground, it remains where it is. If it lands on top of another coconut Y, one of the following things happens:



- If coconut Y is surrounded on both sides by coconuts (denoted by 'O'), coconut X remains where it is. 
     X
    OYO
- If there is no coconut directly to the right of coconut Y, coconut X slides down to the position directly to the right of coconut Y. 
     X
    OY   ->  OYX

     X
     Y   ->   YX
- If there is a coconut directly to the right of coconut Y, but no coconut directly to the left of coconut Y, coconut X slides down to the position directly to the left of coconut Y. 
     X
     YO  ->  XYO


Each time coconut X slides down to a different position, it will continue to slide (following the behavior outlined above) until it's in a place where it will not slide any further.



The task is to return the final coconut configuration in a String[]. Each element represents a single row in the final configuration. The first element represents the lowest row and the last element represents the highest row. Within each element, coconuts are represented by the uppercase letter 'O', and empty space is represented by '-'. The first and last characters of the first element of the String[] must both be 'O', and the rest of the elements must have exactly the same number of characters as the first. Each element included in the String[] must contain at least one 'O' character.
 

Definition

    
Class:FallingCoconuts
Method:harvest
Parameters:int[]
Returns:String[]
Method signature:String[] harvest(int[] drops)
(be sure your method is public)
    
 

Constraints

- drops will contain between 1 and 50 elements, inclusive.
-Each element in drops will be between 0 and 20, inclusive.
 

Examples

0)
    
{8, 9, 10, 11, 12, 8, 12, 10}
Returns: {"OOOOOOO", "---O---" }
The configuration after each fallen coconut is given below: 
                                                                         X
X  ->  OX  ->  OOX  ->  000X  ->  0000X  ->  X00000  ->  000000X  ->  0000000
In this diagram, 'X' denotes the last fallen coconut.
1)
    
{5, 20, 5, 20, 5, 6, 7}
Returns: {"OOOOO-----------OO" }
2)
    
{6, 8, 10, 7, 9, 8, 8, 8, 8, 8}
Returns: {"OOOOOO", "-OOO--", "--O---" }
3)
    
{0, 0, 0, 0}
Returns: {"OOO", "-O-" }
One of the coconuts will end up at a location with a negative index.
4)
    
{5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5}
Returns: 
{"OOOOOOOOOOOO",
"-OOOOOOOOOO-",
"--OOOOOOOO--",
"---OOOOOO---",
"----OOOO----",
"-----OO-----" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5895

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8070&pm=5895

Writer:

supernova

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simulation, String Manipulation