RandomRide | Topcoder Archive

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

```
"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.
```
"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.
```
"HTH"
```
```
Returns: 13
```

"HHHTHHHHHHTTTHHHHHHHHHTTHHT"

Returns: 328

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)2024, Topcoder, Inc. All rights reserved.