Go to the Problem

It’s easy since I spent only 2+ hours. So try it before read my thought and you’ll have some fun.

I study Ping-Cheng Yeh’s probability course on Coursera recently and want to try some puzzle on project euler, so I pick up this one.

  • Try to compute the probability from the first to the last croak is difficult since there are many overlapped sub-trees.
  • So try to solve it from the last croak. It turns out can be solved with dynamic programming.
  • CROAKS[-1] is ‘N’, we known the chance the frog would croak a ‘N’ in every square.
  • CROAKS[-2] is ‘P’, we known the probability to get CROAKS[-2:] in position X is P(CROAKS[−2] in X)⋅0.5⋅(P(CROAKS[−1] in X - 1)+P(CROAKS[−1] in X + 1))P(CROAKS[−2] in X)⋅0.5⋅(P(CROAKS[−1] in X - 1)+P(CROAKS[−1] in X + 1))
  • Keep solving the last problems to get final ones.
  • Sum the final probabilities give the answer.
from sympy import isprime

def chance(primes, croak, i) :
  if primes[i] :
    return 2 if croak == 'P' else 1
  else :
    return 2 if croak == 'N' else 1

PRIMES = [isprime(x + 1) for x in range(500)]

CROAKS = 'PPPPNNPPPNPPNPN'[::-1]

dp_0 = [0 for _ in range(500)]
dp_1 = [0 for _ in range(500)]

for i in range(500) :
  dp_0[i] = chance(PRIMES, CROAKS[0], i)

for i in range(1, len(CROAKS)) :
  c = CROAKS[i]

  dp_0, dp_1 = dp_1, dp_0

  dp_0[  0] = 2 * chance(PRIMES, c,   0) * dp_1[  1]
  dp_0[499] = 2 * chance(PRIMES, c, 499) * dp_1[498]

  for j in range(1, 499) :
    dp_0[j] = chance(PRIMES, c, j) * (dp_1[j-1] + dp_1[j+1])

p = sum(dp_0)
q = 500 * (2 ** (len(CROAKS) - 1)) * (3 ** len(CROAKS))

def gcd(a, b) :
  if a > b :
    return gcd(b, a)

  if b % a == 0 :
    return a
  else :
    return gcd(a, b % a)

g = gcd(p, q)

print(str(p // g) + '/' + str(q // g))