2
\$\begingroup\$

The following code solves Project Euler Problem 121. I will quote the description of the problem

A bag contains one red disc and one blue disc. In a game of chance a player takes a disc at random and its colour is noted. After each turn the disc is returned to the bag, an extra red disc is added, and another disc is taken at random.

The player pays £1 to play and wins if they have taken more blue discs than red discs at the end of the game.

If the game is played for four turns, the probability of a player winning is exactly 11/120, and so the maximum prize fund the banker should allocate for winning in this game would be £10 before they would expect to incur a loss. Note that any payout will be a whole number of pounds and also includes the original £1 paid to play the game, so in the example given the player actually wins £9.

Find the maximum prize fund that should be allocated to a single game in which fifteen turns are played.

I will explain my reasoning using example provided by the Euler:

So we have 4 turns (N = 4). Problem specifies that we need to pick more blue discs than red discs. In other words, we need to pick either 3 blue discs of 4 blue discs in order to win.

If we pick 4 blue discs, calculating probability is simple: 1/2 * 1/3 * 1/4 * 1/5 = 1/120

However, with 3 blue discs, situation is slightly more complicated, because there 4 ways to pick 3 blue discs in 4 turns, i.e

  1. Blue Blue Blue Red

  2. Blue Blue Red Blue

  3. Blue Red Blue Blue

  4. Red Blue Blue Blue

And because for each turn we put an extra red disc into the bag, the probability of picking disc at attempt n will be different from picking disc at attempt n±1, hence we need to calculate probabilities for each variation separately.

After we calculated probabilities for 3 blue discs we end up with 10/120. Adding up probability of picking 4 blue discs, we have:

10/120 + 1/120 = 11/120

And to find the maximum prize fund, we divide 1 by 11/120:

1/(11/120) = 120/11 ~ 10.9

And take floor of that value:

floor(10.9) = 10. Which tallies with the Euler's answer.

The code is following:

import math
from itertools import combinations
import time
start = time.time()
def _121_(N): #N - number of turns
    TOTAL_PROBABILITY = 0
    #Calclulate min number of blue discs you need to pick in order to win the game
    if N % 2 == 1: minimum_picks = int(math.ceil(N/2))
    else: minimum_picks = int((N/2) +1)

    #Calculate probabilities for picking blue or red disc at nth attempt
    blue = [1/x for x in range(2,N+2)]
    red = [1-x for x in blue]

    #Calculate probabilities of all variations
    indeces_chain = set(range(N))
    for V in range(minimum_picks,N+1):
        blue_indeces = list(combinations(indeces_chain,V))
        for M in blue_indeces:
            cumul = 1
            for blue_prob in M:
                cumul*= blue[blue_prob]
            for red_prob in indeces_chain.difference(set(M)):
                cumul*=red[red_prob]
            TOTAL_PROBABILITY+=cumul
    return TOTAL_PROBABILITY


print(math.floor(1/(_121_(15))))
print(time.time() - start)

I suppose there are a lot of things that may be improved. Hence I'm glad to hear any suggestions/remarks. Thanks!

P.S I believe the part of the code after "#Calculate probabilities of all variations" is the most confusing. Because the post is already lengthy, I decided not to elaborate on that part. However, if you think that I must explain that too, I will edit my post to do so.

\$\endgroup\$
2
\$\begingroup\$

For a start, the code is missing several items of whitespace which PEP8 says it should have. There are automated PEP8 checkers which will tell you more.


def _121_(N): #N - number of turns

The Pythonic way to document the arguments is with a docstring.


    TOTAL_PROBABILITY = 0

This use of upper case is also not conventional.


    #Calclulate min number of blue discs you need to pick in order to win the game
    if N % 2 == 1: minimum_picks = int(math.ceil(N/2))
    else: minimum_picks = int((N/2) +1)

This can be simplified. The first line says that if \$n = 2k + 1\$ then we want \$k+1\$; the second line says that if \$n = 2k\$ then we want \$k+1\$. So

    minimum_picks = 1 + N // 2

    #Calculate probabilities of all variations
    indeces_chain = set(range(N))

The plural of index is indexes or indices, depending on the context. But spelling aside, I'm not sure what this name means. To me, chain implies ordering, and a set is unordered.


    for V in range(minimum_picks,N+1):
        blue_indeces = list(combinations(indeces_chain,V))
        for M in blue_indeces:
            cumul = 1
            for blue_prob in M:
                cumul*= blue[blue_prob]
            for red_prob in indeces_chain.difference(set(M)):
                cumul*=red[red_prob]

I think it would be simpler to turn the combination into a set and then iterate over the indexes:

blue_indexes = set(combinations(range(N), V))
cumul = 1
for index in range(N):
    cumul *= blue[index] if index in blue_indexes else red[index]

Also, although this finishes inside the minute, it's not very efficient. Specifically, the number of combinations is exponential in the input. I would encourage you as an exercise to try to find a way of solving the problem which is quadratic in the input.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your response! One question: Why is the use of the upper case when naming variables not conventional (TOTAL_PROBABILITY)? And how would you name this variable then? \$\endgroup\$ – Nelver Sep 6 at 12:17
  • 2
    \$\begingroup\$ @Nelver, see PEP8's prescriptions on naming conventions. It's a local variable, so it would be total_probability. \$\endgroup\$ – Peter Taylor Sep 6 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.