problem 15 16 18 in julia

1 files changed, 30 insertions, 0 deletions

diff --git a/julia/015-lattice_paths.jl b/julia/015-lattice_paths.jl
new file mode 100644
index 0000000..c155da6
--- /dev/null
+++ b/julia/015-lattice_paths.jl
@@ -0,0 +1,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)