Problem 15: Lattice Paths

Problem

• Link to the problem

Starting in the top left corner of a $2\times 2$ grid, and only being able to move to the right and down, there are exactly $6$ routes to the bottom right corner.

How many such routes are there through a $20\times 20$ grid?

Notes

For an $n\times n$ grid, you must make $n$ moves right and $n$ moves down in any order. The total number of ways to arrange these moves is:

$$\begin{array}{rlr}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)& =\frac{(2n)!}{(n!{)}^2}& \\ & =\frac{2n\times (2n-1)\times \cdots \times (n\times (n-1)\times \cdots \times 1)}{(n\times (n-1)\times \cdots \times 1)(n\times (n-1)\times \cdots \times 1)}& =\frac{2n\times (2n-1)\times \cdots \times (n+1)}{n\times (n-1)\times \cdots \times 1}\\ & =\frac{2n}{n}\times \frac{2n-1}{n-1}\times \cdots \times \frac{n+1}{1}& \\ & =\prod _{k=1}^n\frac{n+k}{k}& \end{array}$$

Solution

See it on GitHub.

//* Problem 15: Lattice Paths
//* Starting in the top left corner of a 2 × 2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
//* How many such routes are there through a 20 × 20 grid?

//! time complexity: O(N)
// see the book for implementation details
// https://euler.newty.dev/problems/15.html#notes
use euler::prelude::*;

const N: usize = 20;

fn solve() -> Solution {
    let mut result = 1usize;
    for i in 1..=N {
        // can't do result *= (N + i) / i due to loss of precision
        result = result * (N + i) / i;
    }
    solution!(result)
}

problem!(
    15,
    solve,
    "7b8f812ca89e311e1b16b903de76fa7b0800a939b3028d9dc4d35f6fa4050281"
);