Project Euler 329 - Prime Frog

Official link:

Thought Process

I really struggled on this problem a while ago, however after re-approaching it with some increase in my recursion and dynamic programming ability was able to solve it!

Let's say we start on a number x, and probability of hearing the given sequence PPPPNNPPPNPPNPN = num/den, we know that den = 2^14 * 3^15 because for each number we have an equal chance of going to x - 1 or x + 1 and we croak 15 times.
It is important to note that even if we are on say square 1, we continue with this logic, the numerator will just be accordingly increased.

Before I calculate the numerator I define a function prob(square, croak) which outputs the numerator of probability we hear the correct croak in the sequence given we are on square.

For example:

Now to calculate the numerator given that we start on square x, all we need to do is:

prob(x, 0)*(prob(x - 1, 1)*(prob(x - 2, 2)*(...) + prob(x, 2)*(...)) + prob(x + 1, 1)*(prob(x, 2)*(...) + prob(x + 2, 2)*(...))) and we continue this recursion until we reach croak 14 (because we start at index 0)

Now all we need to do is do this for all 500 starting positions, the overall denominator is then 500 * 2^14 * 3^15. Make sure you respect the border cases!

Interactive Code

Input 2 integers separated by a space (a, b)

Code will output (p, q) in reduced form given that the frog can start on any square from [1, a] and needs to hear the first b croaks from the original sequence PPPPNNPPPNPPNPN