sriramchandrk

Branch Unspecified

10 Nov 2008

**Programming Challenge - Try this (Triangle problem)**

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1)Figure 1 shows a number triangle.

Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

- Each step can go either diagonally down to the left or diagonally down to the right.
- The number of rows in the triangle is >1 but <=100.
- The numbers in the triangle, all integers, are between 0 and 99.

**Input Data**

Data about the number of rows in the triangle are first read from the INPUT.TXT file.

In our example, INPUT.TXT appears as follows:

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

**Output Data**

The highest sum is written as an integer in the OUTPUT.TXT file. In our example:

30

Note: This is taken from an olympiads exams.

You definitely will enjoy solving this

Thanks & Regards

Sriram

Kaustubh Katdare

Electrical

10 years ago

Oh boy, this is interesting. Would love to see CEans cracking this one!

Shall move it to front page, soon.

Shall move it to front page, soon.

prakash.athani

Branch Unspecified

10 years ago

Hey Sriram,

Check this. This program does basically what you want.

Reply back & I can add support for error handling and INPUT.txt & OUTPUT.txt stuff.

Check this. This program does basically what you want.

Reply back & I can add support for error handling and INPUT.txt & OUTPUT.txt stuff.

#include <stdio.h> #include<conio.h> int main() { int a[20],size=0,rows,sum,i,j,depth,height,left,right; clrscr(); printf("Input the number of rows(>1 & <=100) :"); scanf("%d",&rows); for(i=1;i<=rows;i++) { printf("Input %d number(s) between 0 & 99 for row %d :",i,i); for(j=1;j<=i;j++) { scanf("%d",&a[size++]); } } i=0; sum=a[0]; depth=0; height=rows-1; while(depth<height) { left=a[i+depth+1]; right=a[i+depth+2]; if(left>right) { sum=sum+left; i=i+depth+1; } else { sum=sum+right; i=i+depth+2; }//end of if depth++; }//end of while loop printf("Highest sum : %d",sum); getch(); return 0; }

sriramchandrk

Branch Unspecified

10 years ago

The logic is wrong, its not working even for my data.

If there is a big number at the top level you are taking that direction what will it happen if from that route on all are small numbers!

for the data given by me it should give 30 as answer but your code gives 28.

It is taking this route 7 8 1 7 5=28

instead of 7 3 8 7 5=30 the correct route.

the list of possible paths for my given problem for reference

7 3 8 2 4=24

7 3 8 2 5=25

7 3 8 7 5=30

7 3 8 7 2=27

7 3 1 7 5=23

7 3 1 7 2=20

7 3 1 4 2=17

7 3 1 4 6=21

7 8 1 7 5=28

7 8 1 7 2=25

7 8 1 4 2=22

7 8 1 4 6=26

7 8 0 4 2=21

7 8 0 4 6=25

7 8 0 4 6=25

7 8 0 4 5=24

Big = 30

Prakash, let me know if you need any clarification regarding my comment.

Thanks & Regards

Sriram

If there is a big number at the top level you are taking that direction what will it happen if from that route on all are small numbers!

for the data given by me it should give 30 as answer but your code gives 28.

It is taking this route 7 8 1 7 5=28

instead of 7 3 8 7 5=30 the correct route.

the list of possible paths for my given problem for reference

7 3 8 2 4=24

7 3 8 2 5=25

7 3 8 7 5=30

7 3 8 7 2=27

7 3 1 7 5=23

7 3 1 7 2=20

7 3 1 4 2=17

7 3 1 4 6=21

7 8 1 7 5=28

7 8 1 7 2=25

7 8 1 4 2=22

7 8 1 4 6=26

7 8 0 4 2=21

7 8 0 4 6=25

7 8 0 4 6=25

7 8 0 4 5=24

Big = 30

Prakash, let me know if you need any clarification regarding my comment.

Thanks & Regards

Sriram

pradeep_agrawal

Branch Unspecified

10 years ago

Try the code:

Compile the file with above code and run as:

a.exe < input.txt > output.txt [on windows]

a.out < input.txt > output.txt [on linux]

Here,

a.exe or a.out are the executables generated after compilation

input.txt is the file containing input as specified in the problem statement

output.txt is the output file containing result

-Pradeep

#include "stdio.h" #define MAX_SUPPORTED_ROWS 100 int sum(int a[MAX_SUPPORTED_ROWS][MAX_SUPPORTED_ROWS], int row_count, int i, int j) { int highest_sum = 0; if(i == (row_count-1)) { highest_sum = a[i][j]; } else { int left_sum = sum(a, row_count, i + 1, j); int right_sum = sum(a, row_count, i + 1, j + 1); if(left_sum > right_sum) { highest_sum = a[i][j] + left_sum; } else { highest_sum = a[i][j] + right_sum; } } return highest_sum; } int main() { int a[MAX_SUPPORTED_ROWS][MAX_SUPPORTED_ROWS] = {0}; int row_count = 0; int i = 0, j = 0; scanf("%d", &row_count); if((row_count < 1) || (row_count > 100)) { printf("Invalid row count"); return 0; } for(i = 0; i < row_count; i++) { for(j = 0; j <= i; j++) { scanf("%d", &a[i][j]); if((a[i][j] < 0) || (a[i][j] > 99)) { printf("Invalid values"); return 0; } } } printf("Row count: %d\n", row_count); printf("Data:\n"); for(i = 0; i < row_count; i++) { for(j = 0; j <= i; j++) { printf("%d ", a[i][j]); } printf("\n"); } int highest_sum = sum(a, row_count, 0, 0); printf("Highest sum: %d\n", highest_sum); return 0; }

Compile the file with above code and run as:

a.exe < input.txt > output.txt [on windows]

a.out < input.txt > output.txt [on linux]

Here,

a.exe or a.out are the executables generated after compilation

input.txt is the file containing input as specified in the problem statement

output.txt is the output file containing result

-Pradeep

Kaustubh Katdare

Electrical

10 years ago

Guys, do enclose your code in

, [ / code ] tags (remove the spaces)

sriramchandrk

Branch Unspecified

10 years ago

Beautiful program Pradeep.

You rock! my vote for you for Special CEan!

Prakash, is also on the way.

Thanks & Regards

Sriram

You rock! my vote for you for Special CEan!

Prakash, is also on the way.

Thanks & Regards

Sriram

pradeep_agrawal

Branch Unspecified

10 years ago

Thank you Sriram.

I would now like to take the problem to next level.

Modify the sample program given above (or write your one code) that not only print the highest sum but also print the exact number with their positions that sums to highest value, e.g., for the sample input data given in the problem statement, output should be:

Highest sum: 30

Data:

[1,1]: 7

[2,1]: 3

[3,1]: 8

[4,2]: 7

[5,2]: 5

-Pradeep

I would now like to take the problem to next level.

Modify the sample program given above (or write your one code) that not only print the highest sum but also print the exact number with their positions that sums to highest value, e.g., for the sample input data given in the problem statement, output should be:

Highest sum: 30

Data:

[1,1]: 7

[2,1]: 3

[3,1]: 8

[4,2]: 7

[5,2]: 5

-Pradeep

sriramchandrk

Branch Unspecified

10 years ago

Yes, that will be bit tricky as yours is recursive.

Go ahead, meanwhile let me think for some other Challenge.

Thanks & Regards

Sriram

Go ahead, meanwhile let me think for some other Challenge.

Thanks & Regards

Sriram

pradeep_agrawal

Branch Unspecified

10 years ago

No taker for the second part of the problem 😔

Ok, here is my solution.

Ok, here is my solution.

#include "stdio.h" #define MAX_SUPPORTED_ROWS 100 int sum(int a[MAX_SUPPORTED_ROWS][MAX_SUPPORTED_ROWS], int pos[MAX_SUPPORTED_ROWS], int row_count, int i, int j) { int highest_sum = 0; int pos_left[MAX_SUPPORTED_ROWS] = { 0 }; int pos_right[MAX_SUPPORTED_ROWS] = { 0 }; int x = 0; pos[i] = j; if(i == (row_count-1)) { highest_sum = a[i][j]; } else { int left_sum = sum(a, pos_left, row_count, i + 1, j); int right_sum = sum(a, pos_right, row_count, i + 1, j + 1); if(left_sum > right_sum) { highest_sum = a[i][j] + left_sum; for(x = (i+1); x < row_count; x++) { pos[x] = pos_left[x]; } } else { highest_sum = a[i][j] + right_sum; for(x = (i+1); x < row_count; x++) { pos[x] = pos_right[x]; } } } return highest_sum; } int main() { int a[MAX_SUPPORTED_ROWS][MAX_SUPPORTED_ROWS] = {0}; int pos[MAX_SUPPORTED_ROWS] = {0}; int row_count = 0; int i = 0, j = 0; scanf("%d", &row_count); if((row_count < 1) || (row_count > 100)) { printf("Invalid row count"); return 0; } for(i = 0; i < row_count; i++) { for(j = 0; j <= i; j++) { scanf("%d", &a[i][j]); if((a[i][j] < 0) || (a[i][j] > 99)) { printf("Invalid values"); return 0; } } } printf("Row count: %d\n", row_count); printf("Data:\n"); for(i = 0; i < row_count; i++) { for(j = 0; j <= i; j++) { printf("%d ", a[i][j]); } printf("\n"); } int highest_sum = sum(a, pos, row_count, 0, 0); printf("\nHighest sum: %d\n", highest_sum); printf("Data:\n"); for(i = 0; i < row_count; i++) { printf("[%d,%d]: %d\n", i + 1, pos[i] + 1, a[i][pos[i]]); } return 0; }-Pradeep

pradeep_agrawal

Branch Unspecified

10 years ago

The code posted in the thread determines the path in the triangle that sums to maximum count in the triangle and prints the count (this is as per requirement stated in problem statement).sreelu_abut code given calculates the maximum count for a particular row but that may not leed to maximum count for the complete triangle

Please run the second code posted by me with sample data posted in the problem or your own seed data. Let me know if it does not work for any data (also post the seed data in that case).

-Pradeep

Only logged in users can reply.