TopCoder problem "RandomRide" used in TCCC07 Finals (Division I Level One)



Problem Statement

    I go on random bike rides. I go down my driveway, and then at each choice point I flip a coin: Heads means to choose the leftmost road, Tails means to choose the rightmost. If there are 3 choices at the intersection, I flip twice: Heads Heads means to take the leftmost, Heads Tails means to choose the middle road, Tails Heads means choose the rightmost, and Tails Tails is a "do-over" -- repeat the whole process until a choice is made.

The ride continues until the random ride leads me back up my driveway to my house. Here is a map of my neighborhood. All of the intersections where a choice can be made are shown with a capital letter and my home is marked "Home".

                                                   
                                                     
                          +-----M-----N----------+ 
                          |     |     |          | 
                          I-----J-----K----------L 
                          |     |     |          |
                    +-----G-----H     |          |
                    |     |     |     |          |
              +-----B-----C-----D-----E---+      |
              |                           |      |
Home ---------A                           +------F
              |                                  |
              |                                  | 
              +----------------------------------+
Instead of actually flipping a coin while riding my bike, I record the results of a sequence of flips to use during the ride. If during my ride I use them all then I start back at the begining of the sequence. Given flips return the number of flips needed to get me back home. If I never will get back home, return -1.
 

Definition

    
Class:RandomRide
Method:flipCount
Parameters:String
Returns:int
Method signature:int flipCount(String flips)
(be sure your method is public)
    
 

Constraints

-flips will contain between 1 and 50 characters, inclusive.
-Each character in flips will be 'H' or 'T'.
 

Examples

0)
    
"H"
Returns: 10
Every choice will be left. My first flip is at A where my driveway hits the road. Then I go left around the curve and flip at B. My path continues going clockwise around the perimeter of my neighborhood, visiting intersections A, B, G, I, M, N, L, F, and A at which point my flip sends me home. Only at intersection G is there a 3-way choice, thus requiring 2 flips. So I used H H HH H H H H H H using a total of 10 flips at the 9 visited intersections.
1)
    
"HHTTTTTHTHTHHHTT"
Returns: 11
At A I turn left, go around the curve to B and go left there to G. This is an intersection where there are 3 choices. I flip TT (do-over), TT (another do-over), then TH so I turn right and go to C. At C the flip causes me to go right to B where I go "left" (it's really straight, but it is more to the left than the other choice) to A. Now I flip tails so I turn right and am home. The whole trip is A:H, B:H, G:TT TT TH, C:T, B:H, A:T for a total of 11 flips.
2)
    
"HTH"
Returns: 13
3)
    
"HHHTHHHHHHTTTHHHHHHHHHTTHHT"
Returns: 328

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10980&pm=8277

Writer:

dgoodman

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Simulation