Project Euler – Problem 15 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

Problem

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 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 figure out that this problem is actually a simple combination problem – consider a X by Y grid, any route from the top left to the bottom right corner without backtracking must have travelled Right X number of times and Down Y number of times. In the case of the original example:

RRDD, RDRD, RDDR, DRRD, DRDR, DDRR

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

image

where n = X + Y and k = X.


 

Whenever you’re ready, here are 4 ways I can help you:

  1. If you want a one-stop shop to help you quickly level up your serverless skills, you should check out my Production-Ready Serverless workshop. Over 20 AWS Heroes & Community Builders have passed through this workshop, plus 1000+ students from the likes of AWS, LEGO, Booking, HBO and Siemens.
  2. If you want to learn how to test serverless applications without all the pain and hassle, you should check out my latest course, Testing Serverless Architectures.
  3. If you’re a manager or founder and want to help your team move faster and build better software, then check out my consulting services.
  4. If you just want to hang out, talk serverless, or ask for help, then you should join my FREE Community.

 


1 thought on “Project Euler – Problem 15 Solution”

  1. let p15 =
    let factorial n = [1I..n] |> List.fold (*) 1I
    factorial(2I*20I)/(factorial(20I) ** 2)

Leave a Comment

Your email address will not be published. Required fields are marked *