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.