blob: c155da616fe2109b86db173a71eed061afdcc1b3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
###
# Lattice paths
# Problem 15
#
# 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?
###
# memoization is not enough for going deeper in the triangle,
# there is a formula to get the nth row without computing the previous ones
cache = Dict()
function pascal_triangle(n, k)
key = (n, k)
if haskey(cache, key)
return cache[key]
end
if n == 0 || k == 0 || n == k
return 1
end
cache[key] = pascal_triangle(n - 1, k - 1) + pascal_triangle(n - 1, k)
return cache[key]
end
const LATTICE_LENGTH = 20
result = pascal_triangle(2LATTICE_LENGTH, LATTICE_LENGTH)
println(result)
|
