// Solution to Project Euler problem 15
// Author: David J. Oftedal.
package main
import fmt "fmt"
import big "math/big"
// Compute the factorial of a number.
func factorial(n *big.Int) *big.Int {
one := big.NewInt(1)
res := big.NewInt(1)
i := big.NewInt(0)
for i.Set(n); i.Cmp(one)>0; i.Sub(i, one) {
res.Mul(res, i)
}
return res
}
func main() {
// Compute the number of combinations of ways one can move 20 squares
// downward and 20 squares to the right in a 20x20 grid.
// First compute the number of possible routes that are combinations
// of 40 unique moves, rather than 40 moves of two different types.
// This yields 40 * 39 * ... * 2 * 1 moves - The factorial of 40.
forty := big.NewInt(40)
moves := factorial(forty)
// Then calculate all the different ways each of the 20 unique downward
// moves and the 20 unique rightward moves could have been ordered.
twenty := big.NewInt(20)
permutations := factorial(twenty)
// Finally, divide by those numbers, since moves in the same direction
// are not unique, and all of the permutations should be considered to
// be identical.
moves.Div(moves, permutations)
moves.Div(moves, permutations)
fmt.Printf("There are %d routes through the grid.\n", moves)
}