Skip to content

Project Euler Problem 15

October 26, 2011

Project Euler Problem 15 is of a type that if you being tricked into brute force solution this does you no good. It would be better to think before coding.

The first consideration is that any route for a grid of size NxN consists exactly of N moves down and N moves to the right. The second consideration is that on each route these N let’s say down moves are taken from 2xN choices where you can either move down, or move right. And finally, this picking is a case of general combinatorial problem of number of ways to pick X items from the set of Y items:
ways = Y!/X!*(Y -X)!, where ! is factorial function.

Applying to our problem:

let fact n = [1I..n] |> Seq.reduce (*)

let problem015 () =
    fact 40I / ((fact 20I) * (fact 20I))
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: