Packet Decoder

Advent of Code 2021 Day 16

Solve for X where...

X = sum of each version number from all packets

Our input is...

• A long string

It represents...

• A hexadecimal string
• Each character is one of 0123456789ABCDEF

Keywords that hint at the underlying concepts inherent to this puzzle

• Bits
• Layers
• Subpackets
• Operators
• Binary
• Modes
• Lengths

Leading me to presume the algorithm will make use of...

• Integer parsing
• Recursion
• String traversal
• Conditional logic
• Forever loops with an inevitable break

Piecing together the master formula

Here's an animation I made to help myself understand the instructions for decoding a hexadecimal string:

I wrote an algorithm to decode the first example

• After some Googling and trial and error, I successfully converted each hexadecimal character into binary...padded with up to three 0s at the start so each one is exactly four characters long
• I cut off each of the 0s at the end using string splitting, reversal and slicing
• Lastly, I 'walked' the length of the literal packet to extract the decimal value of the combined binary expression: 2021

Then came the second example

• It became clear that I was cutting off trailing 0s incorrectly
• I was confused by the instructions with regards to handling the length type ID
• I felt certain that were I to continue fiddling with further iterations of my algorithm to solve each of the remaining examples, there was going to be some subtle difference in the puzzle's input string that I would fail to troubleshoot

I threw in the towel earlier than anticipated, out of fear of wasted time and increasing frustration.

I was more excited to find a solution I know must exist:

• Short (Under 20 lines?)
• Single-function
• Understandable to a beginner

In search of an eloquent solution to sink my teeth into

• A few of the JavaScript puzzlers I reference had well-labeled code, but the number of functions made me hesitant to study closer
• Several solutions posted in the adventofcode sub-reddit were concise, but in languages I've never studied
• Finally, I found one!

Another gem by Topaz!

This python program by Topaz is exactly what I was looking for!

• A single function
• Seems understandable given the magic numbers and logic inherent to the puzzle

My attempt at describing how Topaz's algorithm for Part 1 works

I re-created it in JavaScript. Here is the repl.

Parse the string as hexadecimal and convert into binary

Define sub-routine that expects an index:
  Copy and store index
  Calculate the base-2 integer of the values at positions 0-2 and store in a variable that will accumulate the total versions
  Calculate the base-2 integer of the values at positions 3-5 and store in a variable as this packet's ID
  Increment the copied index value by 6, thereby committing the action of walking right along the binary number
  If the ID was 4:
    Then do seemingly forever:
      Increment the copied index value by 5, thereby moving to the position immediately after the first group of 5 bits
      If the first value among the skipped group of 5 bits was 0
        Then break out of this otherwise infinite loop, because that means the skipped group was the last group
  Else (the ID was anything other than 4):
    If the value at the current index is 0:
      Calculate the sum of three values and store the result in a new variable representing where to end the next move-right process:
        1. The copied index's current value
        2. The integer 16
        3. The value of the binary number at positions 1-15 relative to the copied index's current value
      Increment the copied index by 16 in order to jump past the binary number calculated in the previous step
      Do the following until the copied index is at or past the end marker:
        Invoke this sub-routine again, passing as input the copied index's current value
          Store the returned values in two variables:
            1. The copied index, thereby updating it
            2. The version number, which is newly created
        Update the total version count by adding the value of the returned version number
     Else (the value at the current index is anything other than 0 - it could only by 1):
       Calculate the value of the binary number at positions 1-11 relative to the copied index's current value and store in a new variable representing the number of packets contained in this sub-packet
       Increment the copied index by 12 in order to jump past the binary number calculated in the previous step
       Do as many times as equivalent to the value stored in the recently-created variable:
         Store the returned values in two variables:
            1. The copied index, thereby updating it
            2. The version number, which is newly created
        Update the total version count by adding the value of the returned version number
  Finally, return two values:
    1. The current value of the copied index
    2. The accumulated value of all tallied version numbers

A working algorithm, but deciding not to reveal the correct answer

I ran the program on each of the sample inputs to confirm it works as expected.

Since I did not author this code - and don't feel confident re-writing it from scratch - I decided not to run this algorithm on my input and discover the correct answer.

I still haven't seen Part 2's instructions.

Although, Part 1 hints at the objective:
the specific operations deduced from operators - Type IDs other than 4 - that perform some calculation on one or more sub-packets contained within

I can further see in Topaz's code (and in others' code that I studied), that Part 2 has us evaluating each sub-packet using one of eight arithmetic operators.

Topaz's algorithm for Part 2 is equally as eloquent as Part 1. There are only a few differences:

• A list of functions
• A list of one or more values to be operated on
• Expressions that conditionally insert values into that list

What this challenge taught me

• Parsing integers as hexadecimal and binary values
• Padding numbers to be of a certain length
• Using visual diagrams (a.k.a. GIFs) to fully understand the inner workings of a complex formula
• Recognizing the core of a challenge may be as simple as tracking your spot - and store the values you've collected - as you 'walk' along a long string
• In JavaScript, array destructuring into existing variables is possible, contrary to my naive and failed prior attempts

In my record book, it remains unsolved.

At least I got what I wanted from this puzzle.