Add Problem 15 solution

1 files changed, 35 insertions, 0 deletions

diff --git a/15-Lattice-Paths/lattice.c b/15-Lattice-Paths/lattice.c
new file mode 100644
index 0000000..aec6821
--- /dev/null
+++ b/15-Lattice-Paths/lattice.c
@@ -0,0 +1,35 @@
+#include <stdio.h>
+#include <gmp.h>
+
+// Compile Notes: use `gcc <program>.c -lgmp`
+
+// 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?
+
+// This is another problem where pure math is the best solution
+// Taking a look at the 2x2 grid, you notice all paths need 4 steps
+// Check for a 3x3 and a 4x4, you'll notice the paths need 6 and
+// 8 steps respectively. So a 20x20 will take 2*20 or 40 steps
+
+// Another way of stating this problem: we have forty steps to take
+// and each one will be either right or down AND they must be equal. 
+// I couldn't traverse a 2 x 2 by going RRRD, 
+// it must be RRDD, RDRD, DDRR, DRDR, RDDR, DRRD
+// So of 40 steps we have to make, we have twenty choices to choose from.
+// i.e. 40 nCr 20
+// nCr = n!/r!(n-r)!
+//      = 40!/(20! * 20!)
+//      = 40*39*38*...*21 / 20*19*18...
+
+int main(){
+    mpz_t nCr;
+    mpz_init_set_ui(nCr, 1);
+    for(long i = 21; i <= 40; i++)
+        mpz_mul_ui(nCr, nCr, i);
+    for(long i = 20; i > 0; i--)
+        mpz_fdiv_q_ui(nCr, nCr, i);
+    gmp_printf("%Zd\n", nCr);
+    return 0;
+}