CodeDump : LongestPath

CodeDump :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register

Longest Path in a triangle


up

Given a triangle filled with digits e.g.

 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 
15 16 17 18 19


Find an algorithm that effeciently finds the longest path. Meaning that from location (i,j) you can only go to (i,j+1) or (i+1,j+1). The trivial solution would be to brute force all possible paths. This can be doable for small triangles but certainly not for large one. An efficient solution (which is O(n), n being the number of digits). Goes as follows:

- start from the lowest line - 1, and iterate to the top
-- for all elements on this line
--- current value (i,j)  = current value max ( (i,j+1), (i+1,j+1))


Or an implementation of this bottom up approach in C

#include <stdio.h>
#include <stdlib.h>

#define SIZE 200
int array[SIZE][SIZE];

int readArray()
{
    int i=0;
    int j=0;
    printf("wtf \n");
    while(scanf("%d",&array[i][j])==1)
    {
        printf("%d %d %d\n", array[i][j],i,j);
        i++;
        if(i>j)
        {
            i=0;
            j++;
        }
        if(j==SIZE)
        {
            break;
        }
    }
    return (j-1);
}


int main(int argc, char **argv)
{
    int bottomLine = readArray();
    printf("%d\n",bottomLine);
    int i=0;
    bottomLine--;
    while(bottomLine >=0)
    {
        for(i=0;i<=bottomLine;i++)
        {
            array[i][bottomLine] += array[i][bottomLine+1]>array[i+1][bottomLine+1]?array[i][bottomLine+1]:array[i+1][bottomLine+1];
        }
        bottomLine--;
    }
    printf("%d\n",array[0][0]);
}



up
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.0
Page was generated in 0.1139 seconds