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

Example:
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.
Input
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.
Output
Line 1: A : B, the odds ratio (in lowest terms) that k white balls are in your sample of s balls
Constraints
0 ≤ N ≤ 60
0 ≤ W ≤ N
0 ≤ s ≤ N
0 ≤ k ≤ s
0 ≤ k ≤ W

## Solution

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
end
return c
end

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

« Back to problem overview