pe018.cpp

#include "pe.h"

#include <iostream>

/*
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

*/
int triangle_1[] = {
       3,
      7, 4,
     2, 4, 6,
    8, 5, 9, 3
};
/*

That is, 3+7+4+9=23

with index path 0->1->4->8
   0
  1 2 
 3 4 5
6 7 8 9


Find the maximum total from top to bottom of the triangle below:

*/
int triangle_2[] = {
                  75,
                 95, 64,
                17, 47, 82,
               18, 35, 87, 10,
              20, 4, 82, 47, 65,
             19, 1, 23, 75, 3, 34,
            88, 2, 77, 73, 7, 63, 67,
           99, 65, 4, 28, 6, 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, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,
    4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 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! ;o)
*/

int get_triangle_level_from_index(int index) {
    int level = 0;
    while (index > 0) {
        level++;
        index -= level;
    }
    return level;
}

int maximum_sum_recursive(int* triangle, int index, int level, int max_level) {
    // Base case: reached the bottom level
    if (level == max_level) {
        return triangle[index];
    }
    
    // Recursive case: choose the maximum path from the current level to the next level
    int left_sum = maximum_sum_recursive(triangle, index + level, level + 1, max_level);
    int right_sum = maximum_sum_recursive(triangle, index + level + 1, level + 1, max_level);
    
    // Return the maximum sum of the current level plus the maximum path from the next level
    return triangle[index] + std::max(left_sum, right_sum);
}

template<size_t N>
int maximim_sum_triangle_path(int (&triangle)[N]) {
    int max_level = get_triangle_level_from_index(N);
    return maximum_sum_recursive(triangle, 0, 1, max_level);
}


class pe018 : public pe_base {
    void run_test() {
        // check("018", 23, maximim_sum_triangle_path(triangle_1));
        check("018", 1074, maximim_sum_triangle_path(triangle_2));
    }
};

int main(int argc, char** argv) {
    pe018 test;
    test.go();
    std::cout << test.get_message() << std::endl; 
    return test.exit_code();
}