Project Euler Problem 329 - Solved

You can find the statement of this problem here.

The solution to this problem is really an easy one. It's just straightforward dynamic programming.

The DP approach I used is top-down with memoization. The DP dictionary will be indexed by a 2-tuple of the starting cell and the string of the expected sequence. And it's initialized for all the numbers for the strings 'N' and 'P'.

The function which calculates the probability of a sequence from a determined cell first checks if it's already in the DP dictionary, if it's not there are three cases:

1. The cell is number 1: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 2.
2. The cell is number 500: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 499.
3. Rest of the cells: the probability of listening a sequence is: the probability of hearing the first letter of the string in that position multiplied by (p + q) where p stands for the probability of listening to the rest of the string from the previous cell divided by 2 (the probability of choosing the previous cell is 0.5) and q stands for the probability of listening to the rest of the string from the next cell divided by 2 (the probability of choosing the next cell is 0.5).

The result is the sum of the probability of listening to the sequence from each cell and then divided by 500. There's a probability of 1/500 to start in each cell.

The python code is available problem329.py:

from CommonFunctions import find_primes_less_than
from fractions import Fraction

d = {}

primes = set(find_primes_less_than(501))
for i in range(1, 501):
    if i in primes:
        d[(i, 'P')] = Fraction(2, 3)
        d[(i, 'N')] = Fraction(1, 3)
    else:
        d[(i, 'P')] = Fraction(1, 3)
        d[(i, 'N')] = Fraction(2, 3)

def calc_prob(i, string):
    if (i, string) in d:
        return d[(i, string)]

    if (i == 1):
        prob = d[(i, string[0])] * calc_prob(i + 1, string[1:])
    elif (i == 500):
        prob = d[(i, string[0])] * calc_prob(i - 1, string[1:])
    else:
        prob = d[(i, string[0])] * (calc_prob(i + 1, string[1:]) * Fraction(1, 2) + calc_prob(i - 1, string[1:]) * Fraction(1, 2))

    d[(i, string)] = prob
    return prob

if __name__ == '__main__':
 result = Fraction(0, 1)
 for i in range(1, 501):
  result += calc_prob(i, 'PPPPNNPPPNPPNPN')
 print("The result is:", result / 500)