From 78fbf8dbcf39aa51cf682a8795d0d0c3be6034c6 Mon Sep 17 00:00:00 2001 From: Charles Date: Fri, 16 Aug 2019 21:58:12 +0200 Subject: haskell problem 13 -> 18, 20 --- haskell/015-lattice_paths.hs | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 haskell/015-lattice_paths.hs (limited to 'haskell/015-lattice_paths.hs') 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 -- cgit