This article is part of a series where I'll be diving head first into the Project Euler puzzles. I want to document the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that I mean I can't look up any other implementations online. After the implementation, I will validate the answer by using this document or a similar sheet.

In this article I'll be solving: Project Euler #15.

**Introduction**
This puzzle is called “Lattice paths” (no, not lettuce paths). The puzzle talks about a grid of 2x2 and how there are only 6 distinct ways of moving from the top left to the bottom right. How many ways are there for a 20x20 grid?

To draw out the example a bit more:

```
A 2x2 grid has 9 grid points:
A B C
D E F
G H I
All 6 possible routes to go from A -> I:
A B C F I
A B E F I
A B E H I
A D E F I
A D E H I
A D G H I
```

What if we took an even simpler example like a 1x1 grid?

```
A 1x1 grid which has 4 grid points:
A B
C D
You can go from A -> D in these routes:
A C D
A B D
```

I don’t see it quite yet… Let me take a bit more complex example with a 3x3 grid:

```
A 3x3 grid which has 16 grid points:
A B C D
E F G H
I J K L
M N O P
You can go from A -> P in these routes:
?
```

Now I’m not going to actually list them all quite yet, since that would be a little too much work, but I do already see a pattern emerge by doing this. For each grid length we see that there are (n + 1) ^ 2 grid points. So for 20 we’ll have (20 + 1) ^ 2 = 441 grid points.

Let’s go back to the example of a 2x2 by grid. In which other way can we visualize the routes, knowing we can only go down and to the right?

```
A B C
D E F
G H I
As a tree of all the routes:
C
/ \
B F
/ \ / \
A E I
\ / \ /
D H
\ /
G
```

That’s interesting, so it looks like a diamond. I’m not sure what that even means, and I’m sure there are some math geniuses out there that will immediately see the answer, however I don’t see it quite yet. Is it as easy as: from the root node A, it can only pick two routes B and D which themselves only have two routes, so 3 x 2 = 6?

Let’s check how many routes there are for the 3x3 grid using a tree:``` A 3x3 plane which has 16 grid points:

A B C D E F G H I J K L M N O P

You can go from A -> P in these routes:

```
D
/ \
C H / \ / \ B G L / \ / \ / \ A F K P \ / \ / \ / E J O \ / \ /
I N
\ /
M
```

A B C D H L P A B C G H L P A B C G K L P A B C G K O P A B F G K L P A B F G K O P A B F G H L P A B F J N O P A B F J K O P A B F J K L P etc.

```
There are 10 routes x 2 = 20 routes for a grid that's 3x3.
Some data for the various grid sizes:
```

Size: | Routes | Amount of grid lines ——-|——–|——————— 1 | 2 | 4 2 | 6 | 12 3 | 20 | 24 20 | ? | ?

```
If I divide the amount of grid lines, by the size of the grid, this is what I get:
```

4 / 1 = 4 2*2
12 / 2 = 6 2*3
24 / 3 = 8 2*4

```
There's a pretty clear pattern here, namely `((size + 1) * 2) * size` gives me the amount of gridlines to a grid. Simplified, this becomes: `2 * size + 2 * size^2`. If we give an example for the number 20, that's:
```

2 * 20 + 2 * 20^2 40 + 2 * 400 40 + 800 840

```
Now, another pattern that emerges here is that the previous amount of gridlines + (`2*4`) happens to result in 20. Is it really that easy? Let's find out.
**Rabbit hole number #1**
I start with a while loop that counts back from the given grid size `n` to a minimum of 2. Using the TDD approach my code looks like this:
```rust
fn problem_15(mut n: i32) -> i32 {
while n >= 2 {
println!("{}", n);
n -= 1
}
0
}#[test]
fn test_problem_15() {
assert_eq!(problem_15(2), 6);
assert_eq!(problem_15(3), 20);
assert_eq!(problem_15(20), 20);
}
```

To make the first 2 cases succeed I’ll apply my new found logic:

```
fn problem_15(mut n: i32) -> i32 {
let mut c = (n + 1) * 2;
while n > 2 {
c += n * 4;
n -= 1
}
c
}#[test]
fn test_problem_15() {
assert_eq!(problem_15(2), 6);
assert_eq!(problem_15(3), 20);
assert_eq!(problem_15(20), 870);
}
```

After executing the code, the answer is right there. There are 870 possible routes for a 20x20 matrix. To validate if that’s correct I’ll check the answer with the sheet and it seems that this is super incorrect. I’m off by quite a lot actually. The actual correct answer seems to be 137846528820.

**Rabbit hole number #2**
Judging by the number I’m assuming factorials come into play one way or the other but I can’t really see it yet. Knowing the answer to the problem, I can at least update my test:

```
fn problem_15(mut n: u64) -> u64 {
let mut c = 0;
c
}#[test]
fn test_problem_15() {
assert_eq!(problem_15(2), 6);
assert_eq!(problem_15(3), 20);
assert_eq!(problem_15(20), 137846528820);
}
```

To get a proper understanding of the problem, I feel like I have to actually read up on Lattice paths to get an idea of what they are [1]. Reading through the Wikipedia article, it pretty much just gives us the answer to our problem: use the binomial coefficient. Turns out I wasn’t that far off with my factorials. I’m not much of a mathematician, so I have to look up what the binomial coefficient is exactly. For the math noobs among us, me included, the method looks like this:

```
n! / r!(n - r)!
```

For a Lattice path, according to the Wikipedia article, you calculate it by taking a coordinate (x + y) over (x). To be clear about it: `n = (x + y)`

and `r = x`

. Because we’re on a square grid and we’ll always be moving from the top-left corner to the bottom-right corner, our `n`

equals to `x * 2`

. The code now looks like this:

```
fn fact(mut n: u64) -> u64 {
match n {
0 => 1,
1 => 1,
_ => fact(n - 1) * n
}
}
fn problem_15(k: u64) -> u64 {
let n = k * 2;
fact(n) / (fact(k) * fact(n - k))
}#[test]
fn test_problem_15() {
assert_eq!(problem_15(2), 6);
assert_eq!(problem_15(3), 20);
assert_eq!(problem_15(20), 137846528820)
}
#[test]
fn test_factorial() {
assert_eq!(fact(2), 2);
assert_eq!(fact(3), 6);
assert_eq!(fact(4), 24);
}
```

This code however doesn’t work because it will overflow. Most likely having to do with the fact that we have a `fact(40)`

to calculate, which simply doesn’t fit in a 64-bit integer in rust. So let’s try to get rid of it and simplify the `problem_15`

method:

First I’m squashing down the `let n`

into the method:

```
fn problem_15(k: u64) -> u64 {
fact(k * 2) / (fact(k) * fact((k * 2) - k))
}
```

With my minor math skills I can see that “(something * 2) - something” is the same as “one of something” so:

```
fn problem_15(k: u64) -> u64 {
fact(k * 2) / (fact(k) * fact(k))
}
```

After applying this I’m a bit stuck because I don’t know how to simplify factorials. After some searching I found a link on how to simplify factorials [2] however it is not quite what I’m looking for. I need something a bit simpler, so according to the dummies article [3] I can do the following:

```
Let's write the function problem_15 down like this:
(n * 2)!
---------
(n! * n!)
Let's imagine n = 3:
(3 * 2)!
---------
(3! * 3!)
That becomes:
6!
---------
(3! * 3!)
Writing that out it becomes:
6 * 5 * 4 * 3 * 2 * 1
---------------------
3 * 2 * 1 * 3 * 2 * 1
Simplified:
6 * 5 * 4
---------
3 * 2 * 1
I can drop one n! if I only calculate the factorial of 6
up till three numbers.
```

Knowing that this is true, this will make my code a lot simpler. Taking the grid size as `k`

I have to multiply that number by 2 and create two “factorials” for lack of a better term (which we’ll call `o`

and `p`

) from `k`

and `n`

. If I then divide the result `o`

by `p`

I should get the correct answer:

```
fn problem_15(mut k: u64) -> u64 {
let mut n = k * 2;
let mut o = 1;
let mut p = 1;
while k > 0 {
o *= n;
p *= k;
n -= 1;
k -= 1
}
o / p
}
#[test]
fn test_problem_15() {
assert_eq!(problem_15(2), 6);
assert_eq!(problem_15(3), 20);
assert_eq!(problem_15(20), 137846528820)
}
```

Fortunately this cleans up my code, but unfortunately rust still ‘overflows’ and tells me that there isn’t enough space on a `u64`

integer to run this calculation. However, I figured out recently that there is such a thing as a `u128`

in rust, which fortunately does fit, giving me the *actual* right answer this time:

```
fn problem_15(mut k: u128) -> u128 {
let mut n = k * 2;
let mut o = 1;
let mut p = 1;
while k > 0 {
o *= n;
p *= k;
n -= 1;
k -= 1
}
o / p
}
#[test]
fn test_problem_15() {
assert_eq!(problem_15(2), 6);
assert_eq!(problem_15(3), 20);
assert_eq!(problem_15(20), 137846528820)
}
```

**Conclusion**
I really started off the wrong foot, and I should’ve just started by reading the Wikipedia article about Lattice paths. That would’ve probably saved me a lot of time on actually trying to figure this out in my head. I did learn some new things though, and I’m glad that rust actually does have a 128-bit integer which will probably become useful in future Euler exercises or any other coding challenges.

**Small improvement on my answer**

For a grid where size equals 3, the way to calculate the number of routes is done like this:

```
6 * 5 * 4
---------
3 * 2 * 1
```

I just noticed that it’s the same as this:

```
5 * 4
----- * 2
2 * 1
```

All I noticed is that the first fracture will always result in 2 no matter which number.

This way I can improve my answer a tiny bit saving a single loop cycle:

```
fn problem_15(mut k: u128) -> u128 {
let mut n = (k * 2) - 1;
let mut o = 1;
let mut p = 1;
while k > 0 {
o *= n;
p *= k;
n -= 1;
k -= 1
}
(o / p) * 2
}
#[test]
fn test_problem_15() {
assert_eq!(problem_15(2), 6);
assert_eq!(problem_15(3), 20);
assert_eq!(problem_15(20), 137846528820)
}
```

It still won’t fit on a 64-bit integer, but it’s a tiny bit faster.

**Sources**

[2] Chilimath/simplifying factorials

[3] Dummies/how to simplify factorial expressions

**
The full solution is available on
GitHub.
**