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

Large number addition method

Question

  It’s a simple and usual question. If you need to add 2 50-digit numbers, what would you do? The first thing a dummy would look into is definitely the limits of the primitive data type. But note that, a 32-bit machine with a separate floating point processor can at max process 64-bit (for double). So, it comes to max 2^64 which is 20 digits. Then how would you solve for more digits?

Say, the question is you need to add some 100’s of 50-digit numbers and you need to find the first 20 digits.

Brain storm

  I started solving the problem. Straight forward I knew that I need to write code for a simple adder system. Addition is very simple considering the operations required for doing it.

1. Take the LSD part (Least significant digit or the last digit in the number)
2.  Add all the LSD digits of the given numbers (50^th digit)
3.  Ex: if there are 100 numbers with digit max which can be 9, it can add up to max 900.
4. We need to maintain a carry which is the digits other than the last digit that we got in the sum
5. Take carry as well in addition of the next set of digits. (49-0^th digit)
6. Finally output the sum

The method I followed to find the last digit is not much optimized. That is, if you divide a number by 10, you get the carry value. If you mod the number by 10, you get the remainder which is nothing but the last digit.

This same question might get twisted for different bases. Say, you need to do the same for base 2. J Then the rules are different and our algorithm won’t work.

Code

int main()

{

    char line[55];

    short dignum[100][50];

    int count=0;

    ifstream myfile ("eulerinput.txt");

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

        myfile.getline(line, 51);

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

            dignum[i][j] = line[j]-48;

            cout<<dignum[i][j];

        }

      cout<<endl;

    }

    int carry=0; // never >999.. since 100 digits addition + carry can never exceed over 999

    //adder

    int dsum;

    for(int i=49; i>=0; i--) {

      dsum = 0;

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

                  dsum += dignum[j][i];

      }

      dsum += carry;

      carry = dsum/10;

      cout<<dsum%10<<" "; //digits in reverse

    }

    cout<<endl<<dsum;

    return 0;

}

Finding the count of factors of a number

 

Question

  This is more of a mathematical and a GMAT/CAT question rather than a programming one. But found this question very interesting and found it from Project Euler.

Before seeing the solution, please try out yourselves.

Let me reiterate the question,

“Find a number which has more than 500 factors. The number is part of a triangle series or natural series of additions”

Triangular number is given a name since it can fill every point in a triangle and will add up like this,

1+2+3+4…+n = n(n+1)/2

The above is sometimes called arithmetic series sum as well.

If you need some mathematical background about finding factors, see the below video,

Methods to find factors

Answer

   I really loved the second brute force method given in the above video since its simple and easier to visualize and program.

  I got into lots of problem since I didn’t make up the triangular number in my mind after I got that clear, zoom I got the answer. Number of trails would be at least 20 times. :)

  First tried manually using calculators. But it didn’t work out since I didn’t see that I need to calculate only for triangular number.

Do the second method of factorizing start from 1 and go up by triangular series and count the number of factors.

   The Method is,

1.  find sqrt(number)

2. If the sqrt is a perfect square, then set diff to –1

3. run a loop from 1 to sqrt(number) and count how many numbers are dividing the triangular number selected

4. count*2+diff gives the total factors.

 

Code

#include <math.h>

void main(int argc, char* argv[])

{

    int data=0; //pow(35.00,13.00);

    int next=1;

    int max = 0;

    while(1) {

    int count=0;

    int diff = 0;

    data = data+next;

    int mid = (int) floor(sqrt((double)data));

    if(mid * mid == data) 

        diff = -1;

    for(int j=1;j<=mid;j++) {

        if(data % j == 0) {

            ++count;

        }

    }

    count = count*2+diff;

    if(count > max) {

        max = count;

        cout<<data<<"="<<count<<endl;

        if(max > 499) 

            break;

    }

    next++;

    }

}

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.