20 Dec 21

Binary Diagnostic - Advent of Code 2021 Day 3


Day 3 of the Advent of Code problem calls for counting and comparing bits at various positions in a binary number. 
This problem can be solved by treating the binary number as a string and then using indices to compare and count the bit at each position. This can also be solved using bitwise operation. I have solved a few coding problems in the past that deal with bitwise operators, and have observed some common patterns that can prove useful as building blocks for a solution -


Testing if the right most bit is equal to 1 (or 0)

The number 1 when converted to binary has leading zeroes. When a number is AND-ed with 1, it will only produce 1 if the right most bit of the number is equal to 1. By itself, this information if not very useful as it only operates on position 0 of a binary number. It is however possible to "traverse" a binary number as seen in the next section

Extending the above - when a number is AND-ed with another "test" number, which has only one bit set, it will produce the test number. This can be use to infer whether a bit at a particular position of number is either set to 1 or 0.

Traversing the digits in a binary number

The shift operator moves a binary number's bits to the right or the left. This effectively halves or doubles a number. 

The right shift operator moves the 2nd bit into the 1st bit position allowing us to inspect it if needed. The left shift operator moves the 1st bit into the 2nd bit position allowing us to insert a new value into the newly created "empty" position

Setting the right most bit to 1

And finally, we can set the right most bit using OR and the number 1


Solving the probem

Both parts of the problem require determining how many One or Zero bits are present in each position. The function below accepts a list of binary numbers -

  • Tests the right most bit of the numbers, and increments a counter stored in an array. 
  • The counter array is indexed by the positions of the bit in the numbers.
  • Each bit in the number is traversed by shifting right. 
  • The position is incremented to reflect the current position.

def getPositionsOfAboveAverageOneBits(binaryLines, lineLen):

    counter = [ 0 for i in range(lineLen) ]

    for num in binaryLines:
        pos = 0
        while num != 0:        
            counter[pos] += num & 1
            num >>= 1
            pos += 1

    print(counter)
    return [ True if i >= len(binaryLines)/2 else False for i in counter ]

Part A

In order to determine the gamma and epsilon values, we need to rebuild a binary number based on the number of occurrences of the 1 and 0 bits in the various positions. 

  • We can start from the left most counter
    • If there are above average one bits, the right most bit of gamma is set to one
    • If there are above average zero bits, the right most bit of epsilon is set to one
    • In either case, both gamma and epsilon are shifted left so that we can move on to the next left most position
  • At the end of the iteration we have both gamma and epsilon values

def getGammaAndEpsilonFromOneBitCounter(positionsOfAboveAverageOneBits):

    gamma = 0
    epsilon = 0

    for i,aboveAverageOneBits in enumerate(reversed(positionsOfAboveAverageOneBits)):
        if aboveAverageOneBits: # common 1 bit
            gamma |= 1    
        else:
            epsilon |= 1

        # don't want to shift if this is the last one
        if i < len(positionsOfAboveAverageOneBits)-1:
            epsilon <<= 1
            gamma <<= 1

    return gamma,epsilon

Part B

For the second part, we need to determine the O2 and CO2 values. Each of these values requires reducing the numbers until we are left with only one number. 

For the O2 value we need to filter the numbers based on the which numbers have the most common bit in the current position being iterated. The CO2 value is the exact inverse and we need to filter based on the least common bit in the current position. 

Both reductions operate on the filtered values and NOT the original set of values.
  • The common counter function defined earlier is useful here as it can be called to determine the counts of 1 or 0 bits in the current position of the filtered values
  • The AND operator is used to tests each bit position. Unlike part 1 however, we create a test value 
  • The XOR operator serves to toggle whether we are searching for 1 or 0 in a particular position
  • The XOR operator is also used to toggle whether we are looking for the O2 or C02 values

def getO2CO2Numbers(candidates, lineLen ,o2Toggle=True):

    position = lineLen - 1 # start with the left most bit

    # keep filtering the candidates until we have only one number
    while len(candidates) != 1:

        oneBitToggle = getPositionsOfAboveAverageOneBits(candidates,lineLen)[position]

        test = 1
        test <<= position 

        candidates = [ c for c in candidates \
            if ((c & test == test) ^ (not oneBitToggle)) ^ (not o2Toggle)  ] 
        
        position -= 1 # move right to the next bit
            
    return candidates[0]

The full source code can be found here -



 

show some love