[Community Puzzle] Probability for Dummies

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @Westicles,validated by @pluieciel,@CeliTop and @jk_java.
If you have any issues, feel free to ping them.

I don’t know American roulette. Per the description, 0 ought to be a number. Is “00” considered as a number too?

Yes, so 38 in all.

I published the fastest C++ code I came up with (6M runs), and am curious to see faster random implementations.

I ran 100,000 iterations in Python.

How is it an easy puzzle? Cannot solve with normal formulas, as well as Bernoulli’s formula do not work for this.

No formulas required, just use brute force monkey method

2 Likes

If you don’t want to go with a Monte Carlo solution, try to recursively solve the sub-problem ‘pick exactly k different numbers’ .
The recursive relation is not hard to find and doesn’t require much knowledge.
If it’s too slow you might want to memoize it.

You can also expess the result with a double summation formula but it’s harder to find.

2 Likes

Yeah, the math is pretty interesting. It is easy to work out a recursive approach (which leads you to independently rediscovering Stirling numbers), and the real math guys would probably just crank out the simple equation with inclusion/exclusion.

But the only way it fits in easy is the brute force monkey method.

1 Like

7 1-stars now! I’m afraid our esteemed math professors on the continent are stumped by this one!

lol really? That’s nuts. It’s kinda clear what you’re being asked to do, hence the easy approach is fairly obvious.

1 Like

I like the brute-force approach.

But strictly speaking, throwing the dice a million times to know the probability of some combinations does not prove this % result is correct. At least the author has to put together a mathematical calculation to prove that the experimental results are theoretically correct.

1 Like

As you can see, there is a python implementation using inclusion/exclusion in the solution.

Do you know why almost all who solved this puzzle are from top players here? You are talking about the monkey method, but how many years you’ve been programming before you find out about this method? I thought that Easy puzzles are for newbies, like me, who just started learning about all of this. Because there is no explanation for this puzzle and no clear way for me to solve it, so 1 star

Actually, within the “easy” puzzles, you have different difficulties. Don’t hesitate to ask for something which could help training you. But every puzzle categorized as “easy” can be solved with paper and pen, that is why there are in this category.
Medium puzzles need more complex approach, and sometimes dedicated algorithms or difficult mathematical formulas to solve. As it is not the case for this one, it is in easy.

Don’t forget : being stuck on a problem is not a reason to be mad, but a way to improve your skills. Try something different, learn on the internet, and you will laugh at your difficulties in a short amount of time.

3 Likes

Thank you for the explanation. I’m not mad, just curious. Also, wanted to explain why there are so many 1 stars. I think, there would be less 1 stars if there will be some hints about the solution (links on youtube where someone digs into a theme that is related to the puzzle or some other links to have a clue about the solution)

Maybe because of flock behaviour…

1 Like

I have no idea who gives you poor ratings but it might not be who you’re thinking about.
If I remember well, the day I solved this one, there were only good ratings, included mine (and probably Nicola’s who solved it before me).

I think math oriented puzzles tend to receive mixed review, some people think that ‘CG is not project Euler’ and it probably explains part of the bad ratings.
That and the fact that some people don’t think it fits the easy category.

3 Likes

No worries, I taunted the fr with it on cheloniangall and got 4 1-stars in 10 minutes. Kind of deserved it :stuck_out_tongue:

I keep getting time out error using recursion.
Any help/guide with algorithm optimization?

I’m pretty sure I’m missing something obvious, but can’t quite get it.