015 - paths across grid

See Problem 15.

This is easier than it looks. Studying the 2*2 grid, note that the path is always 4 steps long and always consists of 2 steps across and 2 steps down. The problem then is actually a question of how many different and unique ways four objects AADD can be arranged. The number of permutations for n objects is n! (factorial n). Where some of these objects are indistinguishable from each, this number is divided by the number of permutations for those objects. So 4 objects can be arranged 4! ways (24). If 2 of those objects are indistinguishable from each other, the answer is 4!/2!. If the other two are also indistinguishable from each other, the answer is $!/2!/2!. We can generalise this solution as follows:

def fact(x): return (1L if x==0 else x * fact(x-1))

board_size = 20
num_moves = fact (2 * board_size) / (2 * fact (board_size))

print num_moves

The answer is 167,683,548,393,178,540,705,382,400,000. Time calculating is negligible. The nifty one-line factorial function is taken from Patrick Thomson.