This content originally appeared on DEV Community and was authored by Robert Mion
Advent of Code 2018 Day 8
Task: Solve for X where...
Part 1
X = the sum of all metadata entries
Example input
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2
It represents:
- A list of numbers
- The navigation system's license file
- A data structure which, when processed, produces some kind of tree that can be used to calculate the license number
Part 1
- Another one of these puzzles, eh?
- A gauntlet of intimidating computer science skills
- Studying the example illustration to inspire algorithmic thinking
- Identifying a possible strategy
- Writing a recursive algorithm that I hope works
- An epiphany after trying to troubleshoot
- Throwing in the towel, again
Another one of these puzzles, eh?
You know...the ones that require the solver to parse some graph- or tree-like data structure:
- 2021 Day 18: Snailfish
- 2020 Day 19: Monster Messages
- 2020 Day 18: Operation Order
- 2019 Day 14: Space Stoichiometry
- And now, today's puzzle: 2018 Day 8: Memory Maneuver
I didn't solve any of them.
Because I haven't learned enough about building or traversing those types of data structures.
I sense I won't be able to solve this one either.
But I've got to try!
A gauntlet of intimidating computer science skills
I get the sense that this puzzle involves three primary algorithms:
- Recursion - to create the tree from the list of numbers
- Tree - must traverse to acquire all metadata entries
- Reduce - to calculate the sum of all metadata entries
- Reducing doesn't scare me anymore, thankfully
- Recursion is still intimidating
- I'm still unfamiliar with creating tree data structures
Initial impression? I'm not confident I'll even solve Part 1.
I hope I'm able to shock and amaze myself.
Studying the example illustration to inspire algorithmic thinking
The example input offered is:
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2
Alongside it is a helpful depiction of the tree and its nodes:
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2
A----------------------------------
B----------- C-----------
D-----
To better help me understand this figure, I chose to animate the creation of the tree and the subsequent sum of all metadata entries:
Identifying a possible strategy
My animation and the bulleted explanations in the instructions pertaining to the example seem to reveal a strategy:
If the first header number is 0
The metadata are the N integers immediately after the second header number in the current sub-list
Else, if the first header number is greater than 0
The metadata are the N integers at the end of the current sub-list
For example:
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2
>0 N
1 1 2
0 3 10 11 12 1 1 0 1 99 2
=0 N
10 11 12
1 1 0 1 99 2
>0 N
2
0 1 99
=0 N
99
Since all I need for Part 1 is the sum of the metadata entries, perhaps it is as easy as:
Set sum as 0
*For each smaller and smaller sub-list
Add to sum either the correct N integers at the end of the sub-list or immediately after the second header number
Chop off the beginning or ending numbers
Go to * with the smaller sub-list
Could this actually work? Let's see!
Writing a recursive algorithm that I hope works
My first algorithm that worked on the example input:
*For each smaller and smaller sub-list
Set sum as 0
If the list is empty
Return 0
Else
If the first integer is equal to 0
Add to sum the sum of the N integers immediately after the second header number, where N is the second header number
Return the sum of sum and calling this function using a subset of the list with the first few integers removed
Else, if the first integer is greater than 0
Add to sum the sum of the N integers at the end of the sub-list, where N is the second header number
Return the sum of sum and calling this function using a subset of the list with the first few two integers removed and the last several integers removed
Return sum
Then I ran it on my puzzle input.
It generated a number.
Too high.
I then printed the first two numbers and the values to be removed at each step.
The last logged output caught my attention:
[6, undefined], [6]
If everything is working correctly, the last array - before an empty one - should look like this:
0 >0 ? ? ?
- No child nodes
- One or more metadata entries
Seeing undefined alerted me that my algorithm is doing something wrong.
After some more logging, I noticed this occurrence:
7 0 ? ? ?
The instructions state:
- The header's second number is the quantity of metadata entries
- One or more metadata entries
So, if I'm seeing 0 as the number of metadata entries, then my algorithm must be mis-calculating where to slice the list.
The first occurrence of a 0 as the second header number is the third 0 in my puzzle input, roughly 40 integers into the string.
I could troubleshoot this manually, albeit tediously.
An epiphany after trying to troubleshoot
- I tried troubleshooting
- According to how I thought the solution should work, I kept seeing a
0as the second header number - But that is clearly breaking this puzzle's rules
- So I must be missing something
Alas, I discovered what I was missing!
Let's assume the example input was rearranged.
Instead of:
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2
It was:
2 3 1 1 0 1 99 0 3 10 11 12 2 1 1 2
And my algorithm would have wrongly worked like this:
2 3 1 1 0 1 99 0 3 10 11 12 2 1 1 2
1 1 2
1 1 0 1 99 0 3 10 11 12 2
2
0 1 99 0 3 10 11 12
99
0 3 10 11 12
10 11 12
11 12
?
In other words:
- I was wrongly always slicing each sub-array's first two values and last few values
- But the nature of the input isn't that convenient
- Instead, I have to create a tree seemingly depth-first
Using the first few integers of my puzzle input as further illustration:
8 11 7 2 4 5 3 6 1 6 0 8 1 7 6 3 1 3 1 1 1...
- The root node has 8 children
- It's impossible at this point to know anything about the children other than the first one has seven children
- That child has four children
- And that child has three children
- And that child has one child
- And that child has no children
Only after parsing the metadata for that child-less node can I go back up a level, to the one-child node.
At that point, since I've account for its only child, I can parse its metadata...then proceed to the next of the three children at its level.
And on and on.
I hope this animation better demonstrates the data structure I'm describing:
Throwing in the towel, again
It seems like if I wrote this algorithm, I'd have to track a ton of variables:
- How many children are left to traverse?
- How many metadata entries did each child have?
- Which level of the tree am I at currently?
I foresee hours of writing and troubleshooting.
And likely no reward, because I'll still probably overlook something.
So, add this puzzle to the stack of ones I'd love to return to one day when I become more skilled at building and using graphs and tree data structures.
Celebrating my accomplishments
- I made a couple of GIFs that demonstrated a before-and-after of my understanding of this puzzle
- After my two failed attempts at guessing the correct answer, I now know the upper and lower boundaries for my correct answer...in case I want to try again some other time
- I was diligent in diagnosing my algorithm, and had an epiphany about why my algorithm failed to generate the correct answer
- I completed a few challenges on FreeCodeCamp that are getting me closer to practicing using Tree data structures
Bummers:
- I didn't solve either part
- I didn't make any simulators...even though had I solved either part, this didn't seem like a very visual puzzle
- My list of unsolved puzzles along this theme continues to grow
If I want to beat my lowest star score of 34, I'll have to solve both parts of each upcoming puzzle in this year.
My forecast: my new lowest star score will be 31 by end of this year.
That's ok, but would be another bummer.
Off I go!
This content originally appeared on DEV Community and was authored by Robert Mion
Robert Mion | Sciencx (2022-07-02T16:38:21+00:00) Memory Maneuver. Retrieved from https://www.scien.cx/2022/07/02/memory-maneuver/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.