[Advent of Code 2021] Day 3 | Binary Diagnostic

Part 1

The submarine has been making some odd creaking noises, so you ask it to produce a diagnostic report just in case.

The diagnostic report (your puzzle input) consists of a list of binary numbers which, when decoded properly, can tell you many useful things about the conditions of the submarine. The first parameter to check is the power consumption.

You need to use the binary numbers in the diagnostic report to generate two new binary numbers (called the gamma rate and the epsilon rate). The power consumption can then be found by multiplying the gamma rate by the epsilon rate.

Each bit in the gamma rate can be determined by finding the most common bit in the corresponding position of all numbers in the diagnostic report. For example, given the following diagnostic report:

00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010

Considering only the first bit of each number, there are five 0 bits and seven 1 bits. Since the most common bit is 1, the first bit of the gamma rate is 1.

The most common second bit of the numbers in the diagnostic report is 0, so the second bit of the gamma rate is 0.

The most common value of the third, fourth, and fifth bits are 1, 1, and 0, respectively, and so the final three bits of the gamma rate are 110.

So, the gamma rate is the binary number 10110, or _22_ in decimal.

The epsilon rate is calculated in a similar way; rather than use the most common bit, the least common bit from each position is used. So, the epsilon rate is 01001, or _9_ in decimal. Multiplying the gamma rate (22) by the epsilon rate (9) produces the power consumption, _198_.

Use the binary numbers in your diagnostic report to calculate the gamma rate and epsilon rate, then multiply them together. What is the power consumption of the submarine? (Be sure to represent your answer in decimal, not binary.)

Proposed solution: iterate through each binary string while populating a map of the bit positions and their frequencies

Time complexity: O(n * m) where m is the bitstring length

Space complexity: O(m)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

bitstr_len = len(file_input[0])
gamma_map = {k: 0 for k in range(bitstr_len)}
for line in file_input:
    for i, char in enumerate(line):
        bit = int(char)
        gamma_map[bitstr_len - i - 1] += bit

gamma = 0
for pos, val in gamma_map.items():
    bit = (val * 2) // len(file_input)
    gamma += bit << pos

epsilon = ~gamma & (1 << bitstr_len) - 1
print("Power consumption: " + str(gamma * epsilon))

Let's break some of this down so it makes more sense.

bitstr_len = len(file_input[0])
gamma_map = {k: 0 for k in range(bitstr_len)}
for line in file_input:
    for i, char in enumerate(line):
        bit = int(char)
        gamma_map[bitstr_len - i - 1] += bit

We are keeping track of the sum of the bits in gamma_map which I initialize with 0 for every bit position in our input. The number of bits are the same on every line so we can use the first line for the length of the bit string. On each individual line, we inverse the index with bitstr_len - i - 1 since the most significant bits are printed first.

gamma = 0
for pos, val in gamma_map.items():
    bit = (val * 2) // len(file_input)
    gamma += bit << pos

Now that we have the frequencies, we can floor divide by the number of binary strings in our input. This works because having half of the bits in any position would effectively result in bit = (1 * 2) // 2. Anymore than half will result in a 1 bit while any less will result in 0. We take the result, bit shift it into its position, and add it to gamma. Repeat for all positions, and their respective values, and we have calculated gamma.

epsilon = ~gamma & (1 << bitstr_len) - 1

For epsilon, we can do binary negation with a mask (all of the bits are inverted in epsilon by definition). Since we only want to negate the bits up to the length of our input binary strings, we can construct a binary mask with (1 << bitstr_len) - 1. For example, if the bit string length is 5 then we 00001 will be shifted 5 times to the left 100000 and decremented by one to produce the mask 11111.

❯ python3 solution3.py input3
Power consumption: 2967914

Part 2

Next, you should verify the life support rating, which can be determined by multiplying the oxygen generator rating by the CO2 scrubber rating.

Both the oxygen generator rating and the CO2 scrubber rating are values that can be found in your diagnostic report - finding them is the tricky part. Both values are located using a similar process that involves filtering out values until only one remains. Before searching for either rating value, start with the full list of binary numbers from your diagnostic report and consider just the first bit of those numbers. Then:

• Keep only numbers selected by the bit criteria for the type of rating value for which you are searching. Discard numbers which do not match the bit criteria.
• If you only have one number left, stop; this is the rating value for which you are searching.
• Otherwise, repeat the process, considering the next bit to the right.

The bit criteria depends on which type of rating value you want to find:

• To find oxygen generator rating, determine the most common value (0 or 1) in the current bit position, and keep only numbers with that bit in that position. If 0 and 1 are equally common, keep values with a _1_ in the position being considered.
• To find CO2 scrubber rating, determine the least common value (0 or 1) in the current bit position, and keep only numbers with that bit in that position. If 0 and 1 are equally common, keep values with a _0_ in the position being considered.

For example, to determine the oxygen generator rating value using the same example diagnostic report from above:

• Start with all 12 numbers and consider only the first bit of each number. There are more 1 bits (7) than 0 bits (5), so keep only the 7 numbers with a 1 in the first position: 11110, 10110, 10111, 10101, 11100, 10000, and 11001.
• Then, consider the second bit of the 7 remaining numbers: there are more 0 bits (4) than 1 bits (3), so keep only the 4 numbers with a 0 in the second position: 10110, 10111, 10101, and 10000.
• In the third position, three of the four numbers have a 1, so keep those three: 10110, 10111, and 10101.
• In the fourth position, two of the three numbers have a 1, so keep those two: 10110 and 10111.
• In the fifth position, there are an equal number of 0 bits and 1 bits (one each). So, to find the oxygen generator rating, keep the number with a 1 in that position: 10111.
• As there is only one number left, stop; the oxygen generator rating is 10111, or _23_ in decimal.

Then, to determine the CO2 scrubber rating value from the same example above:

• Start again with all 12 numbers and consider only the first bit of each number. There are fewer 0 bits (5) than 1 bits (7), so keep only the 5 numbers with a 0 in the first position: 00100, 01111, 00111, 00010, and 01010.
• Then, consider the second bit of the 5 remaining numbers: there are fewer 1 bits (2) than 0 bits (3), so keep only the 2 numbers with a 1 in the second position: 01111 and 01010.
• In the third position, there are an equal number of 0 bits and 1 bits (one each). So, to find the CO2 scrubber rating, keep the number with a 0 in that position: 01010.
• As there is only one number left, stop; the CO2 scrubber rating is 01010, or _10_ in decimal.

Finally, to find the life support rating, multiply the oxygen generator rating (23) by the CO2 scrubber rating (10) to get _230_.

Use the binary numbers in your diagnostic report to calculate the oxygen generator rating and CO2 scrubber rating, then multiply them together. What is the life support rating of the submarine? (Be sure to represent your answer in decimal, not binary.)

Proposed solution: iterate through each position in the length of the bit strings keeping track of the bit strings that have the most/least common bits and discarding the rest

Time complexity: O(n log(n))

Space complexity: O(n * m)

I have appended this solution to the end of the solution to the first part.

pos, common_list, uncommon_list = 0, file_input, file_input
while pos < bitstr_len:
    if len(common_list) == 1 and len(uncommon_list) == 1:
        break
    if len(common_list) > 1:
        common_map = {k: [] for k in [0,1]}
        for line in common_list:
            bit = int(line[pos])
            common_map[bit].append(line)
        if len(common_map[0]) > len(common_map[1]):
            common_list = common_map[0]
        else:
            common_list = common_map[1]
    if len(uncommon_list) > 1:
        uncommon_map = {k: [] for k in [0,1]}
        for line in uncommon_list:
            bit = int(line[pos])
            uncommon_map[bit].append(line)
        if len(uncommon_map[1]) < len(uncommon_map[0]):
            uncommon_list = uncommon_map[1]
        else:
            uncommon_list = uncommon_map[0]
    pos += 1

oxygen_generator_rating = int(common_list[0], 2)
co2_scrubber_rating = int(uncommon_list[0], 2)
print("Oxygen generator rating = " + str(oxygen_generator_rating))
print("CO2 scrubber rating = " + str(co2_scrubber_rating))
print("Life support rating = " + str(oxygen_generator_rating * co2_scrubber_rating))

Here, we are iterating each bit position and we have lists for the common and the uncommon bit strings. While we have more than 1 element in each corresponding list, we check the next bit position and eliminate the unwanted bitstrings – the less common for the common list and the most common for the uncommon list.

If we assume that 1's and 0's are equally probable at any position within any of the bit strings, then this solution is O(n log(n)) since we are eliminating approximately half of the list after checking a single bit position.

❯ python3 solution3.py input3
Power consumption: 2967914
Oxygen generator rating = 1927
CO2 scrubber rating = 3654
Life support rating = 7041258