diff options
Diffstat (limited to 'haskell/015-lattice_paths.hs')
| -rw-r--r-- | haskell/015-lattice_paths.hs | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/haskell/015-lattice_paths.hs b/haskell/015-lattice_paths.hs new file mode 100644 index 0000000..4611d97 --- /dev/null +++ b/haskell/015-lattice_paths.hs @@ -0,0 +1,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 |