Project Euler Problem 323 - Solved

You can find the statement of this problem here.

To solve this problem I used, as usual, dynamic programming as top-down approach with memoization.

The DP dictionary will be indexed by a tuple consisting of the number of tries left and the number of bits still in 0.

The base cases are:

• remaining tries > 0 and bits in 0 = 0: Then I already have all bits in 1 so it doesn't count, thus the probability is 0.
• remaining tries = 0 and bits in 0 > 0: I have no or operations left to do, so I couldn't complete it, thus the probability is 0.
• remaining tries = 0 and bits in 0 = 0: I have all bits in 1 and finished with the or operations, so this is a good case, probability of 1.

If what we are dealing with is not one of the base cases and it's not stored in the DP dictionary then we calculate the probability of finishing with all bits in 1 using exactly remaining tries or operations. This will calculate the probabilities by using the probabilities stored in the DP.

In order to calculate the result we use the function that retrieves the probability of fulfilling all the bits in exactly i or operations to calculate the weight of that i in the total(this is done by multiplying i to that probability), we add up the sum for i from 1 to 50, and we get the correct result.

The python code is problem323.py:

factorial = {0:1}
for i in range(1, 33):
    factorial[i] = factorial[i-1] * i

bits = 32

comb = lambda n, k: factorial[n] // (factorial[k] * factorial[n-k])

dp = {
    (0, 0) : 1
}

def get_value(*args):
    if args in dp:
        return dp[args]

    length, rem = args
    if length > 0 and rem == 0:
        return 0
    if length == 0 and rem > 0:
        return 0
    result = 0
    for i in range(bits+1):
        for overlooked in range(max(0, i-rem), min(i, bits-rem)+1):
            result += get_value(length-1, rem-i+overlooked) * ((comb(bits-rem, overlooked) * comb(rem, i-overlooked) / (2 ** bits)))

    dp[args] = result
    return result

iters = 50

if __name__ == '__main__':
    result = 0
    for i in range(1, iters+1):
        result += get_value(i, bits) * i
    print("The result is:", result)