Complement speedy solution for Pearls in the Box by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Complement solution in Speedy category for Pearls in the Box by veky

checkio=lambda m,s,c=lambda x:1-x:c(c(2/len(m)*m.count("w"))/c(2/len(m))**c(s))/2

Feb. 5, 2014

Comments:

nickie on Feb. 6, 2014, 8:41 p.m.
Once more, well done! It was obvious that an O(N) dynamic programming solution was possible, but it turns out that a closed formula is not too much to ask... I'll try to explain how this works; as the markdown syntax does not seem to allow inline images for mathematics (unless I upload them externally, or unless I just couldn't figure out how), I'm attaching a PDF file that could be much more readable than the rest of this comment. Assume that, in the beginning (i.e., in round 1), there are P pearls numbered from 1 to P and that C out of these P pearls are white. Also assume that, for each round, a number i between 1 and P is picked and the pearl numbered by i is replaced by a pearl of the opposite colour. Finally assume that in the N-th round the pearl numbered by k is picked. In the beginning, this pearl was white with probability C/P and black with probability 1-C/P. We want to find the probability r that the pearl numbered by k is white in the N-th round. This can happen in two ways: <ol> <li>Either this pearl was white in the beginning and during the following N-1 rounds it was replaced an even number of times, so it remained white;</li> <li>Or this pearl was black in the beginning and during the following N-1 rounds it was replaced an odd number of times, so in the end it became white.</li> </ol> Suppose that the probability that this pearl was replaced an even number of times during the N-1 rounds is x. Obviously, the probability that it was replaced an odd number of times during these rounds is 1-x. To calculate x, we can observe that the probability of this pearl being replaced in each single round is p = 1/P, independently of other rounds. It is <a href="http://math.stackexchange.com/questions/79484/expressing-probability-that-successes-is-an-even-number-mathematically">not so hard to find</a> that the probability of obtaining an even number of successes after n trials, when the probability of success for each trial is p, is equal to: <pre class='brush: python'>P(n) = 1/2 * ( 1 + (1 - 2*p)**n ) </pre> Therefore, the probabilities x and 1-x of obtaining respectively an even or an odd number of "successes" (i.e., replacements of the pearl numbered k) when p = 1/P and n = N-1 are: <pre class='brush: python'>x = 1/2 * ( 1 + (1 - 2/P)**(N-1) ) 1-x = 1/2 * ( 1 - (1 - 2/P)**(N-1) ) </pre> Going back to where we started: <pre class='brush: python'>r = C/P * x + (1-C/P) * (1-x) </pre> and after a lot of simplifications: <pre class='brush: python'>r = 1/2 * ( 1 - (1-2*C/P) * (1-2/P)**(N-1) ) </pre> This is precisely what Veky's formula returns. His solution can be decrypted as: <pre class='brush: python'>def checkio(pearls, N): def c(x): return 1-x P = len(pearls) C = pearls.count("w") return c(c(2/P*C)/c(2/P)**c(N))/2 </pre> I'm also publishing this solution in the way I would write it.

veky on Feb. 7, 2014, 2:45 p.m.
LOL. The shorter I write the code, the longer the explanations in the comments are. :-D Good work. :-)

ArturoRamirez on Jan. 23, 2017, 3:43 a.m.
Awesome, only one line solution!

veky on Jan. 23, 2017, 7:20 a.m.
If you're admiring something here, admire the closed formula, not the number of lines. :-) I can write <a href="https://py.checkio.org/forum/post/1485/vekyization-challenge/">everything</a> in one line, but I cannot write everything as a closed formula. ;-)

Ice Base

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!