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

Collatz conjecture

 

Problem

  This is project euler problem 14. Really interesting and mathematically challenging one.

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1

Source: Project Euler.

The below figure will explain the problem precisely.

References

http://en.wikipedia.org/wiki/Collatz_conjecture

http://projecteuler.net/problem=14

Solution

I tried the tail recursive way first..!! But its too slow and it took hours to run.. In debug mode, stack is used even for tail recursion.. so, it went useless to do 1 million function calls every time. so, moved into a iterative way.

Just a brute force algorithm for 1 million values took around 10-15 minutes to run. But, the 1-minute rule given by project euler is not followed in this program.. :)

There are better ways to do.. But since there seems no valid applications for this series, am just leaving it here..

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    int gMax = 0;

    double gI = 0;

    for(double i=1; i<1000000; i++) {

        double val = i;

        int count = 0;

        cout<<val<<" ";

        while(val != 1) {

            ++count;

            if (fmod(val, 2.0) == 0) {

                val = val/2;

            }

            else

            { // odd

                val = 3*val + 1;

            }

        }

        count++;

        if(count > gMax) {

            gI = i;

            gMax = count;

        }

        cout<<endl;

    }

    return 0;

}

• gMax is the maximum count of the numbers in the series
• gI is the number which yields this max count

Find the maximum product in an array (in all directions)

 

Question

  Really an interesting question again on Project Euler site. Problem #11.

http://projecteuler.net/index.php?section=problems&id=11

Its a 20x20 matrix in which you need to find the maximum product of 4 numbers in all the possible directions you can traverse the array. :) But thank god, the traversal is in straight line. Not zig-zag or random.. :)

Brain storm

  I started solving the problem. Initially thought it in very complex way possible as i always do. But its really simple. It’s no optimization problem, sorting problem, anything of that sort. :)

You need to find the adjacent elements of size 4 in up, down, left, right, diagonal directions in an array which when multiplied gives you a max. Even though the question looks complex, it will look like solvable.

Just do the brute force way. You need to first check horizontal 4-by-4 elements. vertical same 4-by-4 elements and then the diagonal.

I got the horizontal and vertical somehow as we take 4 elements on hand and multiply and still move the loop from 0->20.

But for diagonal what is the pattern ?

simple.. diagonal is 2 ways

• from left top to bottom right, move a line
• from right top to bottom left, move a line

But even when you move diagonal, you need to consider 4 elements?.. How, simple..

the pattern is,

(i,j) (i+1, j+1) (i+2, j+2) (i+3,j+3)

for all i,j. Note that we end by 17 itself. :)

the above one is for right top to bottom left

for, left top to bottom right, since we need to ignore elements, we start after 3.

Code

using namespace std;

void main()

{

    char line[10];

    double arr[20][20];

    ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\algorithms\\euler-input.txt");

    for(int i =0 ; i<20; i++) {

        for(int j=0; j<20; j++) {

            myfile.getline(line, 10, ' ');

            arr[i][j] = atof(line);

            cout<<arr[i][j]<<" ";

        }

        cout<<endl;

    }

    double max=1;

    double prod;

    // rows

    for(int i=0;i<20; i++) {

        for(int j=0; j<17; j++) {

            prod = arr[i][j] * arr[i][j+1] * arr[i][j+2] * arr[i][j+3];

            if(max < prod) {

                max = prod;

            }

        }

    }

    // column

    for(int j =0; j<20;j++) {

        for(int i=0;i<17; i++) {

            prod = arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j];

            if(max < prod) {

                max = prod;

            }

        }

    }

    // diagonal right top to bottom left

    // exclude 3 from 20 as it never can make it to 4 elements

    for(int i=0; i< 17;i++) {

        for(int j=0; j<17;j++) {

            prod = arr[i][j]*arr[i+1][j+1]*arr[i+2][j+2]*arr[i+3][j+3];

            if(max < prod)

                max = prod;

        }

    }

    // diagonal left top to right bottom

    for(int i=3; i< 20;i++) {

        for(int j=0; j<17;j++) {

            prod = arr[i][j]*arr[i-1][j+1]*arr[i-2][j+2]*arr[i-3][j+3];

            if(max < prod)

                max = prod;

        }

    }

}

• You cannot end by 20. :) be careful even some runtime won’t warn about array overrun, calculation will happen with garbage, your basic type will overflow and you will wrong value. Even for horizontal & vertical we do +3, so must run loop perfectly from 0 to 16
• For math contests like this, always try to use the maximum sized type as possible. :) But do that only if memory of the program is not the winning criteria.. :P
• Thanks to http://duncan99.wordpress.com/2008/10/29/project-euler-problem-11/ for enlightening me about the diagonal flow.