Advent of Code - Day 8

Learning Questions & Discussions Coding Challenges
, ,
1

Note by the Moderators: This topic is to talk about Day 8 of the Advent of Code.

For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.

2

Here’s my take on day 8. Today problem was refreshingly simple.

3

I finally got around to solving this one. Part 1 was done a while ago and was pretty straightforward but then I did a lot of refactoring and tinkering to solve part 2 and now the answers to both parts are essentially solved together whilst the ‘tree’ is being build.

The overall process is fairly simple and in general terms I do this:

  1. Read in the data, split the number strings and convert the strings to integers. This list is then passed into a parse_data function and then the resultant struct’s sum or value field is used for each part’s answer.

  2. parse_data is called recursively and handles cases where we are looking at a parent node or a child node.

  3. A TreeNode struct is used to store the node data. Each one stores a list of any child nodes, a list of the metadata items, a sum (the sum of the metadata items), a value (the value calculated according to the rules of part 2, the count of children and the metadata length from the header and a scratchpad which is the list of numbers left to parse. The scratchpad is really just for convenience but seemed like a good way to keep everything together in a single struct.

My code is here.

4

Hi @sasajuric,

I’m doing the AoC, slowly, as time and my knowledge allows.
The first seven days were done with an imperative language.
Day 8 and the following are to be accomplished with Elixir.
I’m struggling with day 8, part 1, though.
I have an algorithm, probably more complex than it should that I’m having difficulties to put in functional code. Searched for some solutions in order to learn other ways to do this, and have come to yours.

As my knowledge of Elixir is still low, I’d like some explanation for the line 20:
{license_number, _remaining_numbers = []} = next_node(numbers, license_strategy)

There’s some pattern matching, the second term begins with an underscore _ and has a = []. What do these two mean?

I’d appreciate some help on this.

5

The function next_node returns the license number of the next node (including its descendants), as well as the rest of the input (remaining numbers). In line 20, we invoke this function with the entire input, and so here we expect the function to consume the entire input (i.e. there should be no remaining numbers). The purpose of this pattern match is to take the license number and also to assert that the function has indeed consumed the entire input. If any number remains, either the input is invalid, or there is some bug in the code. In both cases, we don’t want the program to proceed further.

Note that this pattern match is the same as {license_number, []} = next_node(numbers, license_strategy), i.e. without the _remaining_numbers part.
The _remaining_numbers = addition is included only to clarify the meaning of the [] element.

This works because pattern matches can be chained. You can e.g. write something like

entire_result = {license_number, remaining_numbers} = next_node(...)

In this case you take the entire result tuple in entire_result, and also take each element of the tuple into license_number and remaining_numbers respectively.

Another piece of the puzzle is that if you don’t need to use a variable, you can prefix it with underscore. So therefore the _remaining_numbers = [] is a chained match which states that the second element represents remaining numbers, and that it has to be an empty list.

2 Likes