blob: 4611d972a9303bc7459f59c858b6b7801d91fba6 (
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
31
32
33
|
-- 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.
--
-- image: https://projecteuler.net/project/images/p015.png
--
-- How many such routes are there through a 20×20 grid?
main = do
print (pascalTriangleEntry (20 + 20) 20)
-- counting number of routes of problem 18
-- print (sum [pascalTriangleEntry 14 k | k <- [0..14]])
-- https://stackoverflow.com/questions/15580291/how-to-efficiently-calculate-a-row-in-pascals-triangle
-- https://www.wikiwand.com/en/Pascal's_triangle#/Calculating_a_row_or_diagonal_by_itself
-- using the identity: C(n,k+1) = C(n,k) * (n-k) / (k+1)
pascalTriangleEntry :: Int -> Int -> Int
pascalTriangleEntry _ 0 = 1
pascalTriangleEntry n k = (pascalTriangleEntry n (k - 1)) * (n + 1 - k) `div` k
-- naive recursion (factorial are pretty slow)
-- pascalTriangleEntry :: Int -> Int -> Int
-- pascalTriangleEntry _ (-1) = 0
-- pascalTriangleEntry (-1) _ = 0
-- pascalTriangleEntry _ 0 = 1
-- pascalTriangleEntry 0 _ = 1
-- pascalTriangleEntry n k | k == n = 1
-- pascalTriangleEntry n k = pascalTriangleEntry (n - 1) (k - 1) + pascalTriangleEntry (n - 1) k
|
