Project Euler — Problem 15 Solution

Problem

Start­ing in the top left cor­ner of a 2x2 grid, there are 6 routes (with­out back­track­ing) to the bot­tom right cor­ner.

How many routes are there through a 20x20 grid?

Solution

let rec factorial(n:bigint) = if n <= 1I then 1I else n * factorial(n-1I)
let combo n k = factorial(n) / (factorial(k) * factorial(n-k))
let answer = combo 40I 20I

It took me a while to fig­ure out that this prob­lem is actu­al­ly a sim­ple com­bi­na­tion prob­lem – con­sid­er a X by Y grid, any route from the top left to the bot­tom right cor­ner with­out back­track­ing must have trav­elled Right X num­ber of times and Down Y num­ber of times. In the case of the orig­i­nal exam­ple:

RRDD, RDRD, RDDR, DRRD, DRDR, DDRR

This also means that all routes have a total of X + Y steps, and the num­ber of routes is equal to the num­ber of ways you can pick X num­ber of R moves out of X + Y, i.e.

image

where n = X + Y and k = X.