# Build a program to analyze coin flip sequence choices

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.

• Are the sequences always the same length as each other? Jan 5 '15 at 8:43
• @UriZarfaty No, not necessarily. Jan 5 '15 at 16:39
• Though presumably the sequences have to be distinct (since the output can't specify a tie). Jan 5 '15 at 16:53
• Yes, the sequences must be distinct. Jan 5 '15 at 16:54
• More specifically, one cannot be a terminal substring of the other. Jan 5 '15 at 16:55

## Python 3 (139136134132126115 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.

• The current version doesn't work for me. For the input "HTT" and "TTT", o has the value -1 and it divides it by 0. Jan 5 '15 at 14:49
• Nice golf! I like the default argument trick. A couple of (untested) tips: you can multiply by 2**i with <<i, and the output probability can be written as 1/(1/o + 1), into which you can put the reciprocal of o directly.
– xnor
Jan 5 '15 at 14:53
• Thanks. Good spot re o/(1+o). Somewhat embarrassed to have missed <<! Jan 5 '15 at 15:32
• @Jakube Sorry, didn't spot your comment! Current version works fine for me with "HTT" and "TTT". Jan 5 '15 at 17:26
• This gives a nonzero answer for HTH and T, even though the first player cannot win. The other answer has the same problem. Jan 6 '15 at 21:28

# 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

• Joe said in comments (after this was posted) that the strings are not necessarily the same length. Still, +1 because I don't understand CJam. Jan 5 '15 at 22:47
• @mdc32 fixed, 1 byte longer now :( Jan 5 '15 at 22:56
• You already let me believe that codegolfSE now supports LaTeX... =( Jan 6 '15 at 9:23
• @flawr HAHA. Sorry about that :( . These are PNGs from online LaTeX editor. Jan 6 '15 at 9:36
• This gives a nonzero answer for HTH and T, even though the first player cannot win. The other answer has the same problem. Jan 6 '15 at 21:28

# 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;
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