### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Tantalizer 452: Snailspaces | |

Brian Gladman on Enigma 1061: Par is never… | |

Hugh Casement on Enigma 1061: Par is never… | |

Jim Randell on Enigma 1061: Par is never… | |

geoffrounce on Puzzle 47: Digits all wro… |

### Archives

### Categories

- article (11)
- enigma (1,175)
- misc (2)
- project euler (2)
- puzzle (44)
- site news (46)
- tantalizer (48)
- teaser (3)

### Site Stats

- 183,007 hits

Advertisements

The following Python program recursively enumerates all shortest paths. It runs in 100ms

Solution:A complete cycle takes 96 hours and 15 minutes.The On-line Encyclopedia of Integer Sequences, has a formula that lets you calculate the answer directly.

Although another way of looking at it is that a minimal path from (0, 0, 0) to (x, y, z) has

x+y+zsteps (as there arexsteps in the x-direction,ysteps in the y-direction andzsteps in the z-direction). So, considering the path as being a sequence ofx+y+zslots each to be filled with the direction of travel, we can see that for the x-direction there are C(x+y+z,x) ways of filling these out (where C(n,k) is the standard combinatorial choice function), then for the y-direction we can chooseyslots from the remainingy+z, so C(y+z,y), and then all the remaining slots are in the z-direction.Hence the number of minimal paths is:

So for paths from (0, 0, 0) to (

n,n,n) this simplifies to (3n)!/(n!)^3.By generalising the construction of Pascal’s triangle to 3 dimensions (and using memoization):

My solution was so similar to Jim’s that I wasn’t going to publish but Arthur’s use of caching reminded me of just how powerful this technique can be. To test this, here is a version of the code to enumerate the number of shortest paths in a 100 x 100 x 100 cubic lattice:

It enumerates the paths in the cube in around 1 second to give:

376523493564631064367712071965768747782444205128669798396168767743500485766630075466163294008566118208045715304490994009624725072511252178400