Codingame Solution: Bag of Balls

Original Problem

Imagine you have a bag, which is filled with N balls. Each ball can have the color black or white. You know that W balls in the bag are white.

If you extract a ball from the bag, the probability changes of the remaining balls.

Your job is it to output the ratio of the odds that you extracted kwhite balls after extracting s balls from the bag.
Balls are never put back into the bag!

You have 3 balls in the bag, 2 of which are white.
What is the probability of having 2 white balls by extracting 2 balls?
2/3 * 1/2 = 1/3

When A is the event of getting 2 white balls:
P(A) = Probability of getting 2 white balls = 2/3 * 1/2 = 1/3
P(!A) = Probability of not getting 2 white balls = 1-1/3 = 2/3

So the ratio P(A) : P(!A) is 1:2 (read 1 to 2).

The ratio 2:4 would be the same ratio, but both numbers are divisible by 2, so you need to reduce the ratio.
Line 1: An Integer N for the number of balls in your bag.
Line 2: An Integer W for the number of white balls in your bag.
Line 3: An Integer s for the size of your sample.
Line 4: An Integer k for the desired number of white balls in your sample.
Line 1: A : B, the odds ratio (in lowest terms) that k white balls are in your sample of s balls
0 ≤ N ≤ 60
0 ≤ W ≤ N
0 ≤ s ≤ N
0 ≤ k ≤ s
0 ≤ k ≤ W


We calculate the Laplace-Probability by first determining the underlying set of \(s\) balls out of \(n\) balls without repetition, which are \({n\choose s}\). We then treat the draw of black and white balls separately. We first draw \(k\) white balls, which gives \(w\choose k\) possibilities and \(s-k\) black balls, which gives \(n-w\choose s-k\) possibilities and therefore

\[ P(X) = \frac{{w\choose k}\cdot{n-w\choose s-k}}{n\choose s} \]

When we take the probability as a rational number \(q=P(X)\), the odds are \(\frac{q}{1-q}\). Implemented in Ruby, the whole solution then looks as

n = gets.to_i
w = gets.to_i
s = gets.to_i
k = gets.to_i

def binom(n, k)
  n = n - k
  c = 1
  for i in 1..k do
    c = c * (n + i) / i
  return c

q = Rational(binom(w, k) * binom(n - w, s - k), binom(n, s))
if 1 == q then
  puts "1:0"
  puts (q / (1 - q)).to_s.sub("/", ":")

« Back to problem overview