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
0
s and1
s
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
and1
are equivalent tofalse
andtrue
- 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
0
s and1
s - not always one greater than the other - Similar to Part 1, my second algorithm leveraged the use of (1 - index) to get at
0
or1
- 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.
Top comments (0)