Problem 18

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 5

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:

[number triangle]

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

*WARNING: This contains the solution!*

As soon as I read "clever method" my heart jumped for joy for it knows what a challenge looks like. I immediately began seeking to discover this oh so clever method.

My initial thought was that I could possibly use some type of algorithm like A* (A-star) and find the best path using that. In order for A* to work I would need each point, every number, to know what its value is to reach the bottom - or at least this is what I was thinking. When I did look at the bottom and see if I could actually come up with this value for each number, I saw that I could get this if I started with the second to last row and considered each number. For each number I would take the largest out of the two choices that number had below it and add it to the number. Like so...

//consider the first number

63 66

04 62 98

//add 62 to 63

125 66

04 62 98

//consider the secon number

125 66

04 62 98

//add 98 to 66

63 164

04 62 98

...and so on. Move up the rows as you complete them to get the best value so we can perform the A*... wait. When we get to the top it is going to have the largest number we can get right? Isn't that we are going for?

Yes!

And this is how I stumbled upon the "clever method". It was around this point that I concluded that A* is not the algorithm you'd want to use for this type of problem. It was worth a shot though and amazing it did lead to the correct answer.

Here is my implementation of the method explained above.

#include <iostream>

#include <vector>

#include <fstream>

#include <string>

using std::string;

using std::ifstream;

using std::vector;

//changes a string to an int

int stoi(string str)

{

int val;

val = 0;

for (int i = 0; i < str.length(); ++i)

val = 10 * val + (str[i] - '0');

return val;

}

int main()

{

vector<vector<int>> triangle;

//read in the triangle from file

string line;

int lineCount = 0;

ifstream file ("triangle.txt");

if (file.is_open())

{

while (!file.eof())

{

std::getline(file, line);

triangle.push_back(vector<int>());

for (int i = 0; i * 3 + 1 < line.length(); ++i)

{

int number = stoi(line.substr(i * 3, 2));

triangle[lineCount].push_back(number);

}

++lineCount;

}

//take back the extra line

--lineCount;

}

//go through every row, starting from the second to the bottom,

//and calculate the row's optimal values based off of the row below

for (int i = lineCount - 1; i >= 0; --i)

//go through every number

for (int j = 0; j < triangle[i].size(); ++j)

//add the best possible value to the current index

triangle[i][j] += triangle[i + 1][j] > triangle[i + 1][j + 1] ? triangle[i + 1][j] : triangle[i + 1][j + 1];

//the top will house the maximum value at the end of the algorithm

std::cout << triangle[0][0] << std::endl;

}

*saved game*

## No comments:

## Post a Comment