Grind Report 18

Alright! I am now officially above the average for the number of problems completed on Project Euler. The current average is 17.3. You can see the statistics here.

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*