Lattice paths: https://projecteuler.net/problem=15

lattice-paths.py

#!/usr/bin/python3.8


import argparse
import math


def memoize(f):
    memo = {}

    def helper(*args):
        if args not in memo:
            memo[args] = f(*args)
        return memo[args]

    return helper


@memoize
def number_of_paths(width: int, height: int):
    if width == 0 or height == 0:
        return 1
    else:
        result = 0

        x = width
        for y in range(0, height + 1):
            result += number_of_paths(x, y) * number_of_paths(width - x, height - y)

            x -= 1

            if x < 0:
                break

        return result


parser = argparse.ArgumentParser(
    description='Number of paths in a lattice from upper-left corner to lower-right corner.')
parser.add_argument('width')
parser.add_argument('height')

args = parser.parse_args()


print(number_of_paths(int(args.width), int(args.height)))
print(math.comb(int(args.width) + int(args.height), int(args.width)))