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, 2015 at 8:43
  • 1
    \$\begingroup\$ @UriZarfaty No, not necessarily. \$\endgroup\$
    – Joe Z.
    Jan 5, 2015 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, 2015 at 16:53
  • \$\begingroup\$ Yes, the sequences must be distinct. \$\endgroup\$
    – Joe Z.
    Jan 5, 2015 at 16:54
  • \$\begingroup\$ More specifically, one cannot be a terminal substring of the other. \$\endgroup\$
    – Joe Z.
    Jan 5, 2015 at 16:55

3 Answers 3

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, 2015 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, 2015 at 14:53
  • \$\begingroup\$ Thanks. Good spot re o/(1+o). Somewhat embarrassed to have missed <<! \$\endgroup\$
    – Uri Granta
    Jan 5, 2015 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, 2015 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, 2015 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, 2015 at 22:47
  • \$\begingroup\$ @mdc32 fixed, 1 byte longer now :( \$\endgroup\$
    – Optimizer
    Jan 5, 2015 at 22:56
  • \$\begingroup\$ You already let me believe that codegolfSE now supports LaTeX... =( \$\endgroup\$
    – flawr
    Jan 6, 2015 at 9:23
  • \$\begingroup\$ @flawr HAHA. Sorry about that :( . These are PNGs from online LaTeX editor. \$\endgroup\$
    – Optimizer
    Jan 6, 2015 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, 2015 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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