Problem 15: Pascal's Triangle - Project Euler

After a long-long time wanted to restart this blog and planning keep it updated with more problems/math and algorithms.

Problem

            Find the number of routes from the top-left corner to the bottom right corner without backtracking in a 20x20 array. The example give is a 2x2 square. In this square, you can have around 6 routes from start point to end point.

How would you start thinking about this problem? Start counting? You can never reach the conclusion.

Analysis

            As we have a useful condition that we cannot backtrack, once we move forward in any direction we can never come back. So, if we move in that angle, we get more routes passing through points in forward direction. The first thing came to my mind is the points!!

  If you count the points and tell that is the total route, then you are wrong as a single point might lead to multiple routes both vertical/horizontal. We started doing manual steps for 3x3. But at second thought, what got into my mind is a graph!! If u have a unidirectional graph all starting from one point and ending at the bottom right corner, can we then calculate for 4x4, 5x5 etc. First I tried for a 3x3 the approach we got in mind,

For each point, how many route that is possible? I remembered my entire graph logic learned to come up with this but was not sure whether this is right on 3x3 having total 20 routes. Moreover, writing in algorithm to implement this for 20x20 is impossible!!

  When I wanted to find the actual easiest way to solve this, then came the forgotten mathematics concept: combinations.

Solution

            As we know the routes are from top-left corner to bottom-right corner, we can only move two ways, right or down. For a 2x2, the various combinations possible are 6, RDDR, RRDD, RDRD, DRDR, DDRR, DRRD. All this means that, we need to find how many possible ways 2 rights can be placed in total 4 sided route.

            This can be done using combination with 4 C 2 = 4! / 2! (2!) = 6. So for NxN, we always have this generic formula, 2N C N = 2N! / N! (2N-N)!.

Simply said, with the above formula, you can easily get all the combinations. Then the analysis we did? What is that? Can the problem be solved in that way? Yes. The approach we got is nothing but Pascal’s triangle using acyclic graph method. It would have taken years to complete it. J

Refer: http://blog.functionalfun.net/2008/07/project-euler-problem-15-city-grids-and.html