Advent of Code: Day 3

I gotta tell you, Day 3 is something else. The difficulty sharply jumped higher after the two easy previous day. Who would have thought?

The Puzzle

Day 3 deals with binary, which makes it hard. Usually every year the hard puzzles showed up quite later in the game, like Day 10 or 11. Basically, Part 1 gives you a list of binary numbers, and your goal is to construct a new binary number built from the most common bit at each position. Then do the same to construct a binary number but take from the least common bit instead. Multiply the decimal values of these two binaries to get the answer.

My solution is thus:

file = open('input.txt')
binaries = file.read().splitlines()

n = len(binaries[0])  # length of each binary

# Calculate 1's and 0's
ones = [0] * n
zeroes = [0] * n

for i in range(n):
    for binary in binaries:
        if binary[i] == '1':
            ones[i] += 1
        else:
            zeroes[i] += 1

# Build most and least common binaries
most_common = [''] * n
least_common = [''] * n

for i in range(n):
    if ones[i] > zeroes[i]:
        most_common[i] = '1'
        least_common[i] = '0'
    else:
        most_common[i] = '0'
        least_common[i] = '1'

print(int(''.join(most_common), 2) * int(''.join(least_common), 2))

Part 2 of the puzzle upped the ante: Iterating each bit from left to right, you're to keep the binaries that have the same most common bit at each position, then discard the rest in the input. Rinse and repeat until you have one binary left. Do the same but with the least commot bit instead, then produce a second binary. Again, multiply their decimal values to get the answer.

The trick is to reuse the calculation of most and least common binaries from Part 1.

Here's my code for Part 2:

def calculate_commons(binaries):
    n = len(binaries[0])  # length of each binary

    # Calculate 1's and 0's
    ones = [0] * n
    zeroes = [0] * n

    for i in range(n):
        for binary in binaries:
            if binary[i] == '1':
                ones[i] += 1
            else:
                zeroes[i] += 1

    # Build most and least common binaries
    most_common = [''] * n
    least_common = [''] * n

    for i in range(n):
        if ones[i] >= zeroes[i]:
            most_common[i] = '1'
            least_common[i] = '0'
        else:
            most_common[i] = '0'
            least_common[i] = '1'

    return most_common, least_common


file = open('input.txt')
binaries = file.read().splitlines()

n = len(binaries[0])  # length of each binary

# Oxygen
oxygen_keep = binaries

for i in range(n):
    most_common, least_common = calculate_commons(oxygen_keep)
    keep = []

    for binary in oxygen_keep:
        if binary[i] == most_common[i]:
            keep.append(binary)

    oxygen_keep = keep

    if len(oxygen_keep) == 1:
        break

# CO2
co2_keep = binaries

for i in range(n):
    most_common, least_common = calculate_commons(co2_keep)
    keep = []

    for binary in co2_keep:
        if binary[i] == least_common[i]:
            keep.append(binary)

    co2_keep = keep

    if len(co2_keep) == 1:
        break

print(int(''.join(oxygen_keep), 2) * int(''.join(co2_keep), 2))

This took me more than an hour to solve. But I'm happy because I lasted to the end.

Happy coding!