Probability For an N x N square:
There exist 5^x different paths can be taken:
A walk consists of of a word of up's (1), down's (-1), left's (-i), rights (i) and waits (0) such that that the sum of the elements in the word = 0 and the word is of length X, (has x elements)
Note that a walk can be broken into two parts: an actionable part and wait part. Actionable parts must have even length, as every decision to take a non-waiting move must eventually be undone at a later stage. The wait part is all the instances when waiting did occurred.
We consider the first case where X is odd:
We can have actionable parts of length 0, 2, 4, 6 ... X -1 respectively:
Each of these actionable parts has a total of 2 * rC2 * 2 * (r-2)C2 * 2 * (r - 4)C2 ... different arrangements which creates r! ways to arrange an actionable part of length r.
Therefore we know there exist 0! 2! 4! 6! ... (x - 1)! actionable parts correspondingly.
This can also be derived as: for an even integer I have r spots for the first move, r - 1 for the next unmove, etc...
Now for each of these actionable parts we must compute the number of ways to take its elements and then place on the x possible locations. That of course can be accomplished in x!/(x-r)! ways for each of the r! possible walks therefore we have:
x!0!/(x-0)! + x!2!/(x-2)! + x!4!/(x-4)! ...+ x!(x-1)!/1! possible ways to arrange actionable parts. The factorial function + while loop + a factorial function can quickly calculate this. For the probability we will denote the above sum as S(x). Simply compute S(x)/5^x to be done.
In the case of X being even, actionable parts can be computed as being either:
0, 2, 4 ... X moves and therefore there exist:
x!0!/(x-2)! + x!2!(x-2)! ... x!x!/0! possible ways to arrange the actionable parts.
Make a Factorial Method, we'll call it fact(x)
if x is odd then x = x - 1:
else x = x
start a while loop with index at 0
while index <= x - 1:
sum = sum + x!i!/(x-i)!
finally print sum/5^x.
I'm sure this can be optimized. I don't know how atm.