Log in

"Pearl Box"

  • 2
  • 22 Jul '15

I'm trying to solve it using Monte Carlo method and it doesn't pass all the time (sometimes it passes). Trials = 10000

jasonioJason
  • 22 Jul '15

I worked this one out mathematically.

SPOILER
Given:
w = number of white marbles
b = number of black marbles
Pw = Probability of taking a white marble
Pb = Probability of taking a black marble

Pw = w / (w+b)
Pb = 1-w

wNext= w - 2Pw + 1
bNext= b + 2Pw - 1

Then I just calculated wNext and bNext over the number of steps and returned the final result
SPOILER

  • 24 Aug '15

I don't think that formula is correct. Using 'bbw' as an example, you're saying wNext is 1-2(1/3)+1 = 1.33 which can't be.

Anyway, I came up with a nice solution iterating possible outcomes that worked until they started doing 20 iterations on huge sets, which explodes quickly. Happy with what I did helping me learn Python, and not interested in what's clearly not an 'introductory' probability problem, I hard-coded the last few tests to pass.

  • 8
  • 5 Sep '15

I'm not into calculus so I instead made a program that traverses binary tree of possible outcomes. It turns out "True" answer is significantly different form mathematically derived answer.

Consider starting scenario of "bbw". Its binary possibilities tree looks like this:
. . . . bbw . . . . | . . . . 6/12. . . .
. . . ./. .\. . . . | . . . ./. .\. . . .
. . bww . . bbb . . | . . 4/6 . . 2/6 . .
. ./. .\. . . .\. . | . ./. .\. . . .\. .
www . . bbw . . bbw | 3/3 . . 1/3 . . 1/3
On the left there's "literal" pearls. On the right, there's odds of pulling the pearl at that specific point. Notice the "bbb" leaf - it has 100% chance to spawn "bbw" outcome, effectively it has two identical "bbw" children leafs. That means that 3rd step possible scenarios are "www", "bbw", "bbw", "bbw" - 6 white and 6 black, making your odds to pull out white pearl at 3rd step exactly 50%. Same with "bww" because it spawns identical sequence except B's and W's are swapped. Notably, "bbb" sequence produces exactly 1/3 chance, and "www" - exactly 2/3:
. . . . bbb . . . . | . . . . 4/12. . . .
. . . ./. . . . . . | . . . ./. . . . . .
. . bbw . . . . . . | . . 2/6 . . . . . .
. ./. .\. . . . . . | . ./. .\. . . . . .
bww . . bbb . . . . | 2/3 . . 0/3 . . . .

The idea of computing "true" odds is to traverse the tree bottom to top. Starting at the bottom, you compute the chance that this particular leaf will result in pulling a white pearl. For bottom leafs it's directly a percentage of white pearls among others. For higher leafs, it's a mean of odds of its children - in the illustration above, children odds are multiplied by 1/2 (odds of that child leaf to be a possibility) and added together, or in case of single child leaf, just directly adopted. This is how I computed the "true" odds in my puzzle solution code, only to find out that puzzle won't accept that for an answer.

The answers to the puzzle are invalid and so it's impossible to solve unless by using same flawed method that produces same invalid answers. Please fix that. Also, not every starting scenario will converge to 50% odds as the number of step increases - for some, odds would be jump around 50% mark following a pattern.

The code that I used to empirically confirm this: http://pastebin.com/vVmpxxvL

  • 5 Sep '15

Their probabilities are correct. You're forgetting that while you have a 100% chance of spawning bbw from bbb, you only have a 1/3 chance of spawning bbb from bbw, so your third row of odds are wrong.

  • 1
  • 5 Sep '15

Huh, indeed. I've managed to overlook the odds of the odds happening, and just stapled it as 50% (it can pull either white or black, eh?). That fix makes it produce correct answers.

  • 17 Sep '15

My suggestion, to the devs, would be to swap the "Pearl Box" and "Striped Words" puzzles. Currently, "Pearl Box" is next to last in the Speed Boost series and "Striped Words" is last but I'd say "Pearl Box" was the harder of the two for new programmers.

  • 29 Nov '15

Okay I have to admit this challenge stopped me for a little!

Tip (SPOILER!!):
You can write a naive algorithm traversing tree of possible choices in depth and calculating result.
Then you will be stopped on last example with len(word)=20 and step=20.
Then you add cache of type (|white_marbles|, |black_marbles|, step) without touching your solution.
Profit :)

  • 16 Apr

Hi all,

I hope necroposting is OK here.

I saw an auto-test on https://github.com/Empire-of-Code-Puzzles/checkio-empire-pearl-box/blob/master/verification/src/tests.py and it seems to be wrong:

{"input": ('www', 3),
"answer": 0.556,
"explanation": 0.56},

I'm very weak in theory of probability, but my intuitive answer is 1, because what else the robots get on third draw from the box with three white balls, if not a white ball?

  • 1
  • 16 Apr

egilewski,
You're misunderstanding the puzzle. The box may not have only white balls by the time you reach the third iteration.

Reply