In a puzzle in an old book of mine, a game is defined in which two players choose sequences of coin flips that they believe will appear first when a coin is repeatedly flipped. (It was actually odd and even dice rolls, but this little detail doesn't matter in terms of problem equivalence.)
It is noted that if player 1 chooses TTT
and player 2 chooses HTT
, that player 2 has a 7/8 chance of winning the game, since the only way TTT
can come before HTT
is if the first three flips are all tails.
Your job is to create a program or function that will deduce the probability that one of two chosen sequences will comes first. Your program will take two lines of input (or two strings as arguments), each representing a sequence of length 10 or less:
HTT
TTT
And output the probability that the first player will win, in either fraction or decimal form:
7/8
0.875
The shortest code to do this in any language wins.