Project Euler Problem 15

Yay I solved another. Well, I refer to another blog that said something about Pascal's Triangle. It said something about scribble on paper, so I tried it on paper. Took about 30 minutes for me to finally see what does he mean. If you read the blog, you can just skip my explanation. Though, I didn't optimize my program as he did. I only brute-strength the solution.

First, we should look at the question.

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

Then, let's scribble. I suggest you take out a pen/pencil and a paper, and make a grid. Perhaps just 5x5 grid/array/boxes/whatever_you_want_to_call_it. Start with looking at this. If, we set the first point at the left, as (0,0), how many ways to go to (0,0) in a 0x0 grid? There is only 1 way, that is don't move at all. Then, how about from (0,0) to (0,1),(1,1) and (1,0) in a 1x1 grid? In 2x2 grid? Write it on the paper.

For 1x1, you will have something like
1 1
1 2

See, the maximum routes without backtracking in 1x1 grid is 2.


For 2x2, you will have something like
1 1 1
1 2 3
1 3 6

See, the maximum routes without backtracking in 2x2 grid is 6.

If  you look at it from another view, you can put it like this and saw something familiar.
      1
    1  1
  1  2  3
 1  3  3  1
1 4  6  4  1

Pascal Triangle. It is a triangle where all sides are 1, and the rows are build by adding/sum up the neighbors on previous row.

For 5x5, you will have something like
1 1   1   1     1     1
1 2   3   4     5     6
1 3   6 10   15   21
1 4 10 20   35   56
1 5 15 35   70 126
1 6 21 56 126 252

See, the maximum routes without backtracking in 5x5 grid is 252.

Did you see it now? For nxn grid, the answer will be at PascalTriangle2DArray[n+1][n+1]. That long name is kinda ridiculous. Haha. So I decided to go for it. Without reading the blog this time.

Lets have a test on manual add, or tracing, and see if we can see a pattern. Assume all row 0 and column 0 have been initialized to 1. Image, or just look at it from scribbles how to add it.

[1][1] = [1] [0] + [0][1]
[1][2] = [1] [1] + [0][2]
[3][2] = [3] [1] + [2][2]
From this, we can see the pattern of following:
[i][j] = [i][j-1] + [i-1][j]


Therefore, the Pseudocode at basic:
For all column 0, value = 1
For all row 0, value = 1
For all other cells, [i][j] = [i][j-1] + [i-1][j]



...