Binary Diagnostic

Advent of Code 2021 Day 3

The task at hand: Solve for X where

X = the product of two decimals derived from methodically-generated - then parsed - binary numbers

Input is

• A multi-line string
• Each string is composed of 0s and 1s

It represents

• A diagnostic report about the submarine...
• ...that represents the 'power consumption' when parsed one way
• ...and the 'life support rating' when parsed another way

Part 1 solved three ways

• I wrote a successful algorithm on the day this puzzle was released
• I wrote another one as part of writing this article
• I found one that made me smack my face because I failed to spot the condition it used to make solving so much simpler

Part 1: Round 1 - several variables and loops

Split the input at each new line character into an array of strings
Create an array to store tallies of counts for each 0 and 1 in each location within the strings
For each character in the first string
  Add an object to the tallies array, initializing counts for 0 and 1 to 0
For each string in the parsed input array
  For each character in the string
    Increment the value stored in the appropriate key - 0 or 1 - in the object within tallies at the index matching with the index of the current character
For each object in tallies
  Accumulate a string - that starts as empty - according to the following condition
    If the count of 0s is greater than that of 1s
      Concatenate the string with a 0
    Else
      Concatenate the string with a 1
  Return the concatenated string after processing each object in tallies to a new variable called gamma
Create a copy of gamma where each character is replaced with the result of subtracting the value from 1 - thereby swapping all 0s with 1s and vice versa
  Store the copy in a new variable called epsilon
Return the result of parsing both binary strings as base-2 integers and multiplying them together

Part 1: Round 2 - one long chain of array methods

Here's the JavaScript version of my algorithms for Part 1 and 2

Split the input at each new line character into an array of strings
For i times from 0 to the length of the first string
  Accumulate an array containing two strings - starting as empty - whose values will grow with each iteration, according to the following steps:
    Continually mutate the contents of a copy of the parsed input array as follows:
      From a string to only the character at index i within the string
      Reduce the array of strings to an array of two numbers, each reflecting the counts of 0s and 1s in the unreduced array
      Replace the counts with boolean values representing whether the current item is greater than the other
  Coerce the boolean values to numbers
  Coerce the numbers to strings
  Concatenate the appropriate string within the accumulating array with the string value found in the respective index of the coerced-value array
Return the result of parsing both accumulated binary strings as base-2 integers and multiplying them together

Part 1: the smarter, more eloquent way

Algorithm by JavaScript solver NullDev

Split the input at each new line character into an array of strings
Create a variable and initialize it as an empty string
For i times from 0 to the length of the first string
  Concatenate the initially-empty string with the result of the following operation
    Tally all of the 1s at index i in each of the input array's strings
    If the tally is less than the number representing half the length of the input array of strings - thereby meaning 0 is the most common value
      Return a 0
    Else - if the tally is greater, thereby meaning 1 is the most common value - return a 1
Return the result of multiplying the concatenated binary string parsed as a base-2 integer by a parsed copy of that string where each character is replaced with it's binary opposite

Here's a visualization of how NullDev's algorithm works

The secrets of Part 1's puzzle

• There's no avoiding checking each character in each string at least once
• But only one character in each string should be checked at a time
• There's no need to generate both gamma and epsilon by way of checking each character in each string - just generate one and use it to generate the other
• Take full advantage of how 0 and 1 are equivalent to false and true
• There's no need to coerce from strings to numbers to booleans - just count the 1s, check if that count represents less or more than half of the total, and use the correct result depending on the outcome

Part 2: the same, but more of it, and a bit more nuanced

• This time, there's no avoiding two loops through the input array, as the eventual binary strings are derived from filtered lists of strings, not just opposite characters at each index
• In addition, there's a chance that there could be equal counts of 0s and 1s - not always one greater than the other
• Similar to Part 1, my second algorithm leveraged the use of (1 - index) to get at 0 or 1
• My first algorithm used recursion to 'walk along' each string, returning a string of length one to its caller to build up both final strings
• My second algorithm used a reducer to build up both final strings

Here's a visualization of how algorithms solving Part 2 generally work

Wait, no simulator tool?

-Unlike other simulators - which added insight and interactivity to text or animated descriptions of an algorithm - I couldn't think of a good enough reason to build such a tool to expand upon what I cover in this article

The gifs contained herein are descriptive enough as to how I did - or you could - attempt to solve this puzzle.

More great practice

• I'm proud that in my second attempts, I used method chaining and a handful of higher-order array functions to write an algorithm that is in essence one single operation
• I'm proud that I recognized how to leverage array indexes, 0s and 1s, true and false - all to avoid overly complex conditional statements
• I'm shocked - ashamed? - that I didn't think of the 'shortcut' to count only the 1s and compare to the length of half the input array

Just goes to show: there's always something to learn from other solvers' code, even when you're impressed with your own.