Connection Status:
Competition Arena > RandomRide

RandomRide

TCCC07 Finals · 2007-07-30 · by dgoodman

TCCC07 Finals · 2007-07-30 · by dgoodman · Simulation
Class Name: RandomRide
Return Type: int
Method Name: flipCount
Arg Types: (string)
Problem Statement

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.

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)
"TH"
Returns: 37
3)
"HT"
Returns: 57
4)
"HTH"
Returns: 13

Submissions are judged against all 18 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RandomRide with a public method int flipCount(string flips) · 18 test cases · 2 s / 256 MB per case

Submitting as anonymous