Function andys_morning_stroll::enumerate_every_walk

pub fn enumerate_every_walk()

A new approach to part 2. Enumerating every possible walk.

Our montecarlo approach doesn’t seem to be converging on the correct answer fast enough for us to believe in the 7 decimal places we need to get this right. However, we are only looking for the number of terminating walks of less than 20 steps. We have a choice of three directions at each step, so perhaps we can just enumerate every one of the $2^{30}$ = c. 3.5 billion possible paths and get a precise answer.

Running this function (it’s only single threaded so takes a few minutes - it could be made faster by splitting the enumerable range across a few CPUs, as we have done elsewhere) we get:

$$ P(\text{random walk is longer than 20 steps}) = 0.4480326 \text{ (7 s.f.)} $$

This figure closely matches the answer we were getting stochastically, so presume we have got everything right.