15
\$\begingroup\$

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.

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

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.

\$\endgroup\$
13
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jakube
    Jan 5 '15 at 14:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Jan 5 '15 at 14:53
  • \$\begingroup\$ Thanks. Good spot re o/(1+o). Somewhat embarrassed to have missed <<! \$\endgroup\$
    – Uri Granta
    Jan 5 '15 at 15:32
  • \$\begingroup\$ @Jakube Sorry, didn't spot your comment! Current version works fine for me with "HTT" and "TTT". \$\endgroup\$
    – Uri Granta
    Jan 5 '15 at 17:26
  • 1
    \$\begingroup\$ This gives a nonzero answer for HTH and T, even though the first player cannot win. The other answer has the same problem. \$\endgroup\$
    – Zgarb
    Jan 6 '15 at 21:28
3
\$\begingroup\$

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

enter image description here

Then the probability is defined as

enter image description here

which, after simplifying becomes

enter image description here

and after some simplification, becomes

enter image description here


Example input:

HTT
TTT

Output:

0.875

Try it online here

\$\endgroup\$
8
  • \$\begingroup\$ 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. \$\endgroup\$
    – mdc32
    Jan 5 '15 at 22:47
  • \$\begingroup\$ @mdc32 fixed, 1 byte longer now :( \$\endgroup\$
    – Optimizer
    Jan 5 '15 at 22:56
  • \$\begingroup\$ You already let me believe that codegolfSE now supports LaTeX... =( \$\endgroup\$
    – flawr
    Jan 6 '15 at 9:23
  • \$\begingroup\$ @flawr HAHA. Sorry about that :( . These are PNGs from online LaTeX editor. \$\endgroup\$
    – Optimizer
    Jan 6 '15 at 9:36
  • \$\begingroup\$ This gives a nonzero answer for HTH and T, even though the first player cannot win. The other answer has the same problem. \$\endgroup\$
    – Zgarb
    Jan 6 '15 at 21:28
0
\$\begingroup\$

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()));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.