Project Euler Solution 18
Problem Statement#
Find the maximum sum travelling from the top of the triangle to the base.
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
    3
   7 4
  2 4 6
 8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
                75
               95 64
              17 47 82
             18 35 87 10
            20 04 82 47 65
           19 01 23 75 03 34
          88 02 77 73 07 63 67
         99 65 04 28 06 16 70 92
        41 41 26 56 83 40 80 70 33
       41 48 72 33 47 32 37 16 94 29
      53 71 44 65 25 43 91 52 97 51 14
     70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
   63 66 04 68 89 53 67 30 73 16 69 87 40 31
  04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method!
Solution#
My first version of solution to this problem worked only for the above two input but not for one in problem 67.
    3
   7 4
  2 4 6
 8 5 9 3
We start with the root node 3. Root 3 has two children 7 and 4. Again there are two children for left child 7, namely 2 and 4. Among 2 and 4, 4 is larger so I added 4 to 7 to get 11. For the right child 4, 6 is larger among 6 and 4, so I added 6 with 4 to get 10. Now among 10 and 11, 11 is greater. So I considered the route along 7. The same above steps are followed with 7 as the root node.
The following program implements what I have explained above. But is not the correct algorithm that works for problem 67.
Implementation#
#include <stdio.h>#include <stdlib.h>
int No_Rows = 15;int main(){ int number[6000] = { -1 }; int index = 0, root, num, sum, level = 1; int r_left, r_right; int left_max_sum, right_max_sum; FILE * f_read; f_read = fopen("inputpe018.txt", "rt"); while (fscanf(f_read, "%d", &num) == 1) { number[index] = num; index++; } sum = number[0]; root = 0; while (level <= No_Rows) { r_left = root + level; r_right = root + level + 1; if (level == No_Rows) { if (number[r_left] > number[r_right]) { sum = sum + number[r_left]; printf("%d", sum); return 0; } else { sum = sum + number[r_right]; printf("%d", sum); return 0; } } if ((number[r_left] + number[r_left + level + 1]) > (number[r_left] + number[r_left + level + 2])) { left_max_sum = number[r_left] + number[r_left + level + 1]; } else left_max_sum = number[r_left] + number[r_left + level + 2]; if ((number[r_right] + number[r_right + level + 1]) > (number[r_right] + number[r_right + level + 2])) { right_max_sum = number[r_right] + number[r_right + level + 1]; } else right_max_sum = number[r_right] + number[r_right + level + 2]; if (left_max_sum > right_max_sum) { sum = sum + number[r_left]; root = r_left; } else if (right_max_sum > left_max_sum) { sum = sum + number[r_right]; root = r_right; } else if (number[r_left] > number[r_right]) { sum = sum + number[r_left]; root = r_left; } else { sum = sum + number[r_right]; root = r_right; } level++; }}Sample Output#
Go to problem 67 for the correct algorithm.