Algorithm notes on the back of used envelopes bound in a ring binder

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?

問 15 「格子経路」

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

では, 20×20 のマス目ではいくつのルートがあるか.

struct Permutation {
    numerator: u8,
    denominator: u8,
}

impl Permutation {
    fn num(&self) -> u128 {
        let mut acc = 1u128;
        for i in self.denominator + 1..=self.numerator {
            acc *= i as u128;
        }
        acc
    }
}

struct Grid {
    width: u8,
    height: u8,
}

fn factorial(n: u8) -> u128 {
    match n {
        0 | 1 => 1,
        _ => factorial(n - 1) * n as u128,
    }
}

impl Grid {
    fn routes(&self) -> u64 {
        let a = Permutation {
            numerator: self.width + self.height,
            denominator: self.width,
        }
        .num();
        let b = factorial(self.height);
        (a / b) as u64
    }
}

fn main() {
    let r = Grid {
        width: 20,
        height: 20,
    }
    .routes();

    println!("{}", r);
    assert_eq!(r, 137846528820);
}

fn main() {
    let mut lattice = [[0u64; 22]; 22];
    lattice[1][1] = 1;
    for y in 1..lattice.len() {
        for x in 1..lattice.len() {
            lattice[y][x] += lattice[y - 1][x] + lattice[y][x - 1];
        }
    }
    let r = lattice[21][21];

    println!("{}", r);
    assert_eq!(r, 137846528820);
}

struct Combination {
    n: f64,
    k: f64,
}

impl Combination {
    fn _num(&self, n: f64, k: f64) -> f64 {
        if k == 1f64 {
            return n;
        }
        if k == 0f64 {
            return 1f64;
        }
        let prev = self._num(n, k - 1f64);
        prev * (n - k + 1f64) / k
    }
    fn num(&self) -> f64 {
        self._num(self.n, self.k)
    }
}

struct Grid {
    width: u8,
    height: u8,
}

impl Grid {
    fn routes(&self) -> u64 {
        Combination{
            n: (self.width + self.height) as f64,
            k: self.width as f64,
        }
        .num().ceil() as u64
    }
}

fn main() {
    let r = Grid {
        width: 20,
        height: 20,
    }
    .routes();

    println!("{}", r);
    assert_eq!(r, 137846528820);
}

struct Combination {
    n: f64,
    k: f64,
}

impl Combination {
    fn num(&self) -> f64 {
        assert!(self.n == 2f64 * self.k);
        (1..=self.k as usize)
            .map(|x| x as f64)
            .map(|x| (self.k + x) / x)
            .product::<f64>()
    }
}

struct Grid {
    width: u8,
    height: u8,
}

impl Grid {
    fn routes(&self) -> u64 {
        Combination{
            n: (self.width + self.height) as f64,
            k: self.width as f64,
        }
        .num().ceil() as u64
    }
}

fn main() {
    let r = Grid {
        width: 20,
        height: 20,
    }
    .routes();

    println!("{}", r);
    assert_eq!(r, 137846528820);
}

fn main() {
    let mut b = 1u64;
    for i in 1..=20 {
        b *= i;
    }
    let mut ab = 1f64 / b as f64;
    for i in 21..=40 {
        ab *= i as f64;
    }
    println!("{}", ab);
    assert_eq!(ab.ceil() as u64, 137846528820);
}

fn main() {
    let b = 1f64 / (1..=20).product::<u64>() as f64;
    let ab = (21..=40).fold(b, |p, i| p * i as f64);
    println!("{}", ab);
    assert_eq!(ab.ceil() as u64, 137846528820);
}