Build a program to analyze coin flip sequence choices

Question

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.

Answer 1

Python 3 (139 136 134 132 126 115 143)

Uses Conway's Algorithm as described at here. Handles all sequence pairs as long as the first is not a terminating subsequence of the second (as per instructions).

def f(a,b):c=lambda x,y=a:sum((x[~i:]==y[:i+1])<<i for i in range(len(x)));return 0 if b in a else(1/(1+(c(a)-c(a,b))/(c(b,b)-c(b))),1)[a in b]

Thanks xnor for shaving 6 bytes off. Thanks Zgarb for spotting a bug with subsequences.

Answer 2

CJam, 44 38 36 bytes

Using the same Conway's Algorithm as in here.

ll]_m*{~1$,,@f>\f{\#!}2b}/\-:X--Xd\/

Input is the two distinct sequences in two lines. The output is the probability of first winning over second. The inputs need not be of same lengths

I am using the formula for winning odds (p) for first player A as

Then the probability is defined as

which, after simplifying becomes

and after some simplification, becomes

---

Example input:

HTT
TTT

Output:

0.875

Try it online here

Answer 3

Lua 211 190 184

Also using Conway's Algorithm. Still new to Lua so this can be golfed more for sure.

z=io.read;e=function(s,t)r='';for d in s:gmatch"."do r=r..(d==t:sub(1,1)and 1 or 0);end;return tonumber(r,2);end;a=z();b=z();print((e(a,a)-e(a,b))/(e(b,b)-e(b,a))/(1/((1/2)^b:len())));

Ungolfed

z=io.read;
e=function(s,t)
r='';
    for d in s:gmatch"."do 
        r=r..(d==t:sub(1,1)and 1 or 0);
    end;
    return tonumber(r,2);
end;
a=z();
b=z();
print((e(a,a)-e(a,b))/(e(b,b)-e(b,a))/(1/((1/2)^b:len())));

First version

z=io.read;
e=function(s,t) 
    r=0;
    for d in s:gmatch"."do 
        r=r*10;
        if d==t:sub(1,1)then r=r+1 end;
    end
    return tonumber(r,2);
end;
f=function(n,o)
    return ((e(n,n)-e(n,o))/(e(o,o)-e(o,n)))/(1/((1/2)^3));
end;
print(f(z(),z()));