12
\$\begingroup\$

Introduction

Adam (A) and Bubbler (B) are playing coin toss, where the one who wins 5 times first would win the prize of $32. If the game is aborted when the scores are A:B = 4:3, how should they distribute the prize? Assume the coin toss is fair, so the winning chance of either player is 1/2 for each game.

The answer is:

Adam should take $24 and Bubbler should take $8. Possible cases are as follows:

A wins (score 5:3, chance 1/2): A wins the prize
B wins (score 4:4) then A wins (score 5:4, chance 1/4): A wins the prize
B wins (score 4:4) then B wins (score 4:5, chance 1/4): B wins the prize

Therefore, the chance of A winning is 3/4 and that of B is 1/4.

Challenge

In order to do the fair splitting of prizes, we should compute the chance of winning the prize for each player. Given the following information,

  • X, how many times a player should win coin toss to win the prize
  • Wa, how many times player A has already won
  • Wb, how many times player B has already won

compute the chance of player A winning the prize.

Input and output

You can assume the three input numbers X, Wa, Wb satisfy the following:

  • All numbers are non-negative integers.
  • X > max(Wa, Wb), i.e. the game hasn't finished already.

You can choose to output a fraction or a floating-point number.

Scoring and winning criterion

Standard rules apply. Shortest code in bytes wins.

Test cases

X Wa Wb => Expected output
--------------------------
5  4  3 =>  3/4  = 0.75
5  3  4 =>  1/4  = 0.25
1  0  0 =>  1/2  = 0.5
4  3  1 =>  7/8  = 0.875
4  2  1 => 11/16 = 0.6875
6  4  2 => 13/16 = 0.8125
\$\endgroup\$
  • \$\begingroup\$ Can Wa and Wb be taken as a complex number Wa+j*Wb, where j is the imaginary unit? \$\endgroup\$ – Luis Mendo Dec 23 '19 at 0:44
  • \$\begingroup\$ @LuisMendo That's OK. I/O is flexible as always. \$\endgroup\$ – Bubbler Dec 23 '19 at 1:37
  • \$\begingroup\$ May i output 6/8 instead of 3/4? \$\endgroup\$ – tsh Dec 23 '19 at 2:35
  • \$\begingroup\$ @tsh Yes, it's fine. \$\endgroup\$ – Bubbler Dec 23 '19 at 3:16
  • \$\begingroup\$ @Bubbler What about binary or hex "decimals"? \$\endgroup\$ – wizzwizz4 Dec 23 '19 at 11:21

13 Answers 13

9
\$\begingroup\$

R, 36 32 bytes

function(X,A,B)pbeta(.5,X-A,X-B)

Try it online!

The closed formula from this answer suggested a natural probability distribution to use -- this is a Negative Binomial with \$X - W_b - 1\$ failures and \$X - W_a\$ successes, i.e., the probability that there are \$X - W_a\$ "successes" before there are \$X - W_b\$ "failures".

Further identities reduce the CDF of the negative binomial to the CDF of a beta distribution or in terms of the (regularized) incomplete beta function.

\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

Binomial[g=#-#2+t,k]~Sum~{k,0,t=#-#3-1}/2^g&

Try it online!

Not super short, but uses an algorithm that might lead to shorter code in other languages: the code calculates the sum of binomial coefficients formula which is the closed form for the result of the path-counting algorithms in other solutions.

\$\endgroup\$
  • \$\begingroup\$ 33 bytes \$\endgroup\$ – Giuseppe Dec 24 '19 at 4:59
  • \$\begingroup\$ Alternately, this is the CDF of a negative binomial distribution if that's at all helpful. \$\endgroup\$ – Giuseppe Dec 24 '19 at 4:59
  • \$\begingroup\$ @Giuseppe That's a great approach, you should post it as an answer! Note that you can shave off 1 more byte by making the denominator a~Beta~b. \$\endgroup\$ – Greg Martin Jan 3 at 20:54
  • \$\begingroup\$ Sure, done. \$\endgroup\$ – Giuseppe Jan 3 at 21:34
4
\$\begingroup\$

Python 2, 62 56 bytes

f=lambda n,a,b:a<n>b and(f(n,a+1,b)+f(n,a,b+1))/2.or a>b

Try it online!

Returns a float. Uses a recursive approach.

Ungolfed:

def f(n,wa,wb):
    if wa<n and wb<n:
        return (f(n, wa+1, wb) + f(n, wa, wb+1))/2.0
    elif wa==n: return 1
    else: return 0
\$\endgroup\$
3
\$\begingroup\$

MATL, 24 bytes

x"TF1GEZ^!Ys@+1G<~s]P>Ym

Try it online! Or verify all test cases.

Input is X, then [Wa Wb]. Output is a floating-point number.

How it works

This enumerates all possible paths of length 2*X that emanate from the initial conditions defined by Wa and Wb. This length is enough to ensure that someone wins (actually length 2*X-Wa-Wb-1 would suffice).

For each path, the code determines who wins as follows. It keeps a cumultive sum of score for each player, computes how long each player has had score X or more along the path, and the winner is the player who has maintained that condition for longer. This is equivalent to, but golfier than, asking who reached X earlier in that path. Note that there can be no ties.

The result is the proportion of paths in which player A wins.

x      % Implicit input: X. Delete it
"      % Implicit input: [Wa Wb]. For each
  TF   %   Push [0 1]
  1G   %   Push X
  E    %   Multiply by 2
  Z^   %   Cartesian power of [0 1] with exponent 2*X. Gives a matrix with each
       %   Cartesian tuple contained in a row. Rows are in lexicographical order
       %   Each column is a step in the path, containing 1 if the user wins or 0
       %   otherwise
  !    %   Transpose. Each tuple is now a column
  Ys   %   Cumulative sum of each column. This is the accumulated gain along each
       %   path. Note that the matrix has more than one row; otherwise the
       %   cumulative sum would work along the single row
  @    %   Push Wa (first iteration) or Wb (second iteration)
  +    %   Add. This gives the total accumulated score along each path, including
       %   the initial score
  1G   %   Push X
  <~   %   Not less than?
  s    %   Sum of each column. This indicates for how long the score X has been
       %   reached, or exceeded, in each path
]      % End
P      % Flip. This reverses the results for player B, to reflect the fact that
       % the paths of the two users are complementary: user B increases their 
       % score when user A doesn't. Reversing the vector is equivalent to
       % replacing each path by its complement, thanks to the lexicographical
       % order of the Cartesian tuples
>      % Greater than? This indicates for which paths player A wins
Ym     % Mean. Implicit display
\$\endgroup\$
  • \$\begingroup\$ Poorly golfed, but 14 bytes using the incomplete beta function, as it's the CDF of the negative binomial. \$\endgroup\$ – Giuseppe Dec 24 '19 at 4:55
  • \$\begingroup\$ (and the beta distribution too!) \$\endgroup\$ – Giuseppe Dec 24 '19 at 5:04
  • 1
    \$\begingroup\$ @Giuseppe You should definitely post that! A little shorter: tio.run/##y00syfn/X880M1M3qtZTJTL9/39TrmgTBeNYAA \$\endgroup\$ – Luis Mendo Dec 24 '19 at 10:27
  • 1
    \$\begingroup\$ Ah, Z}, that's what I was looking for. Thanks! \$\endgroup\$ – Giuseppe Dec 24 '19 at 15:14
2
\$\begingroup\$

Jelly, 12 bytes

_Ä’Żc@SH⁹¡ʋ/

Try it online!

A dyadic link taking the number to win as left argument and the coin tosses won so far by players b and a respectively as the right argument.

Based on the formula described by @GregMartin so be sure to upvote his answer too!

Explanation

_            | Subtract
 Ä           | Cumulative sum
  ’          | Decrease by 1
          ʋ/ | Reduce using the following as a dyad (left argument represents X - Wb - 1; right argument represents 2X - Wa - Wb - 1)
   Ż         | - Range from 0..left argument
    c@       | - Number of combinations for each using right argument as n
      S      | - Sum
       H⁹¡   | - Half the number of times indicated by the right argument

Jelly, 16 bytes

MḢ’¹2Ṭ+Çɗ€ÆmƊ}Ị?

Try it online!

An alternative Jelly answer that uses a recursive approach. A full program that takes as its argument a list of Wb, Wa, n and returns the answer as a float.

Explanation

M                | Indices of maximum
 Ḣ               | Head
  ’              | Subtract 1
              Ị? | If absolute of this less than or equal to one:
   ¹             | Then: Return this value
            Ɗ}   | Else following as a monad applied to the original argument to this link:
    2            | - Literal 2
        ɗ€       | - Apply the following to the implicit range 1..2 with the original argument as the right argument
     Ṭ           |   - Convert to logical list with 1 at the relevant index
      +          |   - Add to the original argument (effectively increments Wa for 1 and Wb for 2)
       Ç         |   - Call this link with the updated argument
          Æm     | - Arithmetic mean
\$\endgroup\$
2
\$\begingroup\$

MATL, 11 bytes

.5ii-Z}3$Yg

Try it online!

This is a port of my R answer. Thanks to Luis Mendo for helping golf it down.

.5     # push .5
ii     # push both inputs, X, and [Wa, Wb]
-      # subtract, so stack is [.5, [X - Wa, X - Wb]]
Z}     # split array onto stack
       # so stack is [.5, X - Wa, X - Wb]
3$Yg   # (regularized) incomplete beta function with 3 arguments
       # implicitly output the probability

Also a nice short Octave solution:

Octave, 27 bytes

@(X,A,B)betainc(.5,X-A,X-B)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly,  17 16  14 bytes

-2 thanks to Kevin Cruijssen

_µS’2*ḶB§‘>ḢÆm

A dyadic Link accepting the end-goal, X, on the left and the current state [Wa,Wb] on the right which yields a float of A's chances.

Try it online!

How?

Forms all binary strings of \$X-Wa+X-Wb-1\$ bits, treating 1s as a win for A and 0s as a win for B. Identifies those with at least \$X-Wa\$ 1s and takes the mean (i.e. winCount / total).

_µS’2*ḶB§‘>ḢÆm - Link: X, [Wa, Wb]
_              - subtract (vectorises)   -> V=[X-Wa, X-Wb]
 µ             - start a new monadic chain, f(V)
  S            - sum                          X-Wa+X-Wb
   ’           - decrement                    X-Wa+X-Wb-1
    2*         - two raised to that power     2^(X-Wa+X-Wb-1)
      Ḷ        - lowered range                [0,1,2,3,4,...,2^(X-Wa+X-Wb-1)-1]
       B       - to binary (vectorises)       [[0],[1],[1,0],[1,1],[1,0,0],...,[1,1,...,1]]
        §      - sums                         [0,1,1,2,1,...,X-Wa+X-Wb-1]
         ‘     - increment (vectorises)       [1,2,2,3,2,...,X-Wa+X-Wb]
           Ḣ   - head (V)                     X-Wa
          >    - greater than? (vectorises) A=[0>=X-Wa,1>=X-Wa, ...]
            Æm - mean                         A's win probability
\$\endgroup\$
  • \$\begingroup\$ I'm not too familiar with Jelly, but isn't µS÷L just Æm? \$\endgroup\$ – Kevin Cruijssen Jan 3 at 10:43
  • \$\begingroup\$ Indeed sum/length is mean - thanks! \$\endgroup\$ – Jonathan Allan Jan 3 at 11:26
2
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

Beta[.5,a=#-#2,b=#-#3]/a~Beta~b&

Try it online!

Yet another port of the negative binomial CDF approach suggested by this answer.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 36 bytes

Nθ≔E⁻θN⁰ηFE⁻θN¹FLη«≔⊘⁺ι§ηκι§≔ηκι»I⊟η

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input the desired number of coin tosses.

E⁻θN⁰η

Calculate the number of remaining tosses player A needs, and create an array of that length of zeros. The (1-indexed) nth entry represents that the probability of A winning given that he still has n tosses remaining and B initially has no tosses remaining.

FE⁻θN¹

Loop over the number of remaining tosses player B needs. Start with the probability of A winning given that he still has 0 tosses remaining and B has m tosses remaining as 1.

FLη«

Loop over the probabilities.

≔⊘⁺ι§ηκι

Average the current probability (representing the case where A wins this toss) with the probability from the array (representing the case where B wins this toss).

§≔ηκι

Save this new probability in the array.

»I⊟η

Output the last probability calculated, which is for n=X-Wa,m=X-Wb.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 44 bytes

a=>g=(b,c)=>a==b||a>c&&(g(b+1,c)+g(b,c+1))/2

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 45 bytes

{m:g/\-//$_}o{[X+] .[1],|(^2 xx+^.sum)}o&[X-]

Try it online!

Takes arguments as f((a, b), x). Counts 2x-a-b-1-bit numbers with popcount less than x-b.

Explanation

                                        &[X-]  # Compute a-x, b-x
             {                        }o  # Feed into block
                          ^2            # Range 0..1
                             xx         # repeated
                               +^.sum   # ~(a-x+b-x) = 2x-a-b-1 times
                        |(           )  # flattened
                   .[1]   # b-x
              [X+]     ,  # Cartesian product with addition,
                          # computes popcount(i)-(x-b) for all i
{          }o  # Feed into block
 m:g/\-/  # Regex match '-' chars in string representation,
          # counting negative values
        /$_  # Divide by number of values
\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 77 bytes

double f(int x,int a,int b){return(a<x&b<x?f(x,a+1,b)+f(x,a,b+1):a>b?2:0)/2;}

Try it online!

Credits

Iterative version, 89 bytes

(x,a,b)->{int r=0,i=1<<x*2>>a-~b,n=i;for(;i-->0;)r+=x.bitCount(i)<x-a?0:1;return 1.*r/n;}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 14 bytes

-¤sO<oL<2вO›ÅA

Inputs in the format and order [Wa, Wb], X.

Port of @JonathanAllan's Jelly answer.

Try it online or verify all test cases.

A port of @GregMartin's formula would be 16 bytes:

-¤sO<UFXNc}OXoz*

Try it online or verify all test cases.

Explanation:

-               # Subtract each value of the first (implicit) input-pair from the second
                # (implicit) input: [X-Wa,X-Wb]
 ¤              # Push its last value (without popping the list itself): X-Wb
  s             # Swap to get the list again
   O            # Sum them together: 2X-Wa-Wb
    <           # Decrease it by 1: 2X-Wa-Wb-1
     o          # Take 2 to the power this: 2^(2X-Wa-Wb-1)
      L         # Pop and push a list in the range [1,2^(2X-Wa-Wb-1)]
       <        # Decrease each value by 1 to make it [1,2^(2X-Wa-Wb-1))
        2в      # Convert each to a binary-list
          O     # Sum each inner list of bits
           ›    # Check for each if it's larger than the X-Wb: [X-Wb>1,X-Wb>2,...]
            ÅA  # Take the arithmetic mean of that list
                # (which is output implicitly as result)

-¤sO<           # The same as above
     U          # Pop and store this 2X-Wa-Wb-1 in variable `X`
      F         # Loop `N` in the range [0,X-Wb):
         c      #  Take the binomial coefficient (a.k.a. number of combinations) of:
       X        #   The 2X-Wa-Wb-1 of variable `X`
        N       #   And the loop-index `N`
      }O        # After the loop: sum all values on the stack
        X       # Push 2X-Wa-Wb-1 from variable `X` again
         o      # Take 2 to the power this: 2^(2X-Wa-Wb-1)
          z     # Take the invert of this: 1/(2^(2X-Wa-Wb-1))
           *    # And multiply it with the sum
                # (after which this is output implicitly as result)
\$\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.