General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 18 – Maximum Path Sum 1
My workflow and macro:
Workflow:
Macro:
Answer: 1074
Announcement:
Advent of code is a mere 4 days away. Despite the shortened calendar, I’m sure it will, as always, prove to be an immense challenge! Euleryx was indeed inspired by the Advent of Code challenges and was designed to help replicate some of the inspirationally nerdy discussions by attempting to fill the AoC shaped hole found within the 11 inferior months of the year. To give everyone (myself included) a chance to compete in the AoC, Euleryx will indeed be taking a break for a few weeks.
Fear not, as Euleryx will make a return on the 18th December. Until that time, I hope you enjoy this weeks problem, and I look forward to seeing you in the Advent of Code forums shortly.
Last Week's Favourite Solution:
Although the monster formula tool was indeed impressive, last weeks favourite solution goes to @Qiu. There were several submissions which used the clever idea of a master lookup table, containing all 29 values together. This helped filter out some of the teens initially and made the joining process more efficient. However, after a quick run through each one, @Qiu 's solution ran the quickest and is hence awarded this weeks favourite solution! Please find their solutions on page one of last week's post or click here.
Mathematical Theory:
With this being the last project for a few weeks, we have made sure it’s a good one! As the question suggests, this problem could be solved in a bruit force approach, however, implementing a more streamlined algorithm would allow the solution to work for both Problem 18 and Problem 67. The solution below is indeed sufficient for both problems, so feel free to plug in the data from either one.
We will begin with the bottom of the pyramid. This may sounds strange but as the aim is to find the greatest path total, meaning mathematically, it doesn’t matter which end we start with as the numbers get summed either way. The idea is to move up the levels, one by one, each time finding the greatest path length for each record on the “current level”. Lets take a look at an example to help walk through the steps, here is the first 4 levels from problem 18 (note the numbers in red denote the position within each level):
Like with walking, when talking about paths, its often best to take one step at a time. If we are starting on the bottom, and take just one step, that would take us to level 3. So lets focus on those two levels:
Now, what we want to do is update level three with the greatest possible path total, to get to that point. For each number, there are two potential starting spots, one to the bottom left and the other to the bottom right. These are the only two number we need to consider per record. As we want the greatest path total possible, we simply take the maximum of the two values. i.e:
- For the value 17, on level 3, we can either start from the 18, or 35 on the line below.
- As 35 is the larger of the two, we will take this value.
- Use the selected value, 35, to update the original value on level 3 to be 17 + 35 = 52. Applying this idea to the whole level we end up with the following:
Now we know the maximum possible value, to get to each of the positions on level 3 (starting from the bottom). With this in mind we can effectively ignore the bottom row, meaning the table looks like this:
Because we know the values on level three are the largest values possible, we don’t need to consider the different routes on level 4, as they will be smaller. Now we just repeat the above process!
- Select the bottom two rows.
- Update the values on Level 2 by adding the maximum of the two below numbers.
- Drop the bottom row to get:
Repeating this process for the final time we end up with:
And that gives us our answer!
Method:
1) To start with, input the data and label the different levels.
2) Next we need to parse the values into their own separate cells, and ID them. As we already have the Level ID, we can group the Position ID by the level.
3) Now its time to implement the algorithm we discussed above.
3a) We need to figure out the Level ID for the bottom two levels. This will always be the maximum Level ID and one less than the maximum Level ID.
3b) Use the join tool to filter to the records on the penultimate level.
3c) For each of these records, we need to have access to the two values below, so we can take the maximum and add it onto the current level. This is where the Position ID comes in. You may have spotted earlier that the positions we need to consider on the level below, are those with the same, or “same + 1” position ID, when compared with the current level.
i.e the above represents a section from level 3 & 4 where you can see the 52 has position ID 1, and the two values we need to look at in the line below have position IDs 1 & 2. We need to create a column representing these position IDs, so we can later perform a join.
3d) We also need to filter to the records on the bottom level
3e) Now we have the bottom two levels isolated, and we have created the column to join on, we can actually perform the joins. Here you can see the current “Values” on Level 14, along side the two candidates from the level below.
3f) Add the greater of the two records from the level below, onto the current value in the “Values” column.
3g) Join the updated level back to the other levels that were filterd out earlier.
3h) Check to see if the records can exit the loop, or need to continue for another iteration
4) Now we have the iterative macro created, all that’s left to do is hit run:
5) Submit your answer to the Project Euler Website!
Summary:
Often we consider “looking at the bigger picture”, to be the best way to arrive at an optimal solution, however this problem requires quite the opposite approach. Whilst this problem sounds complex at first, when we take it back to the basics and focus on the next step only each time, it significantly simplifies the problem!
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
My solution!
At the Project 18, I calculated all pattern. But it woked well. But about Project 67, it didn't work.
Macro :
So, I remade the workflow for project 67.
macro
The difficult part was that the data was laid out in a triangle rather than a regular grid, so getting the data into a form that could be processed was the most difficult part.
