Day 3: Binary Diagnostic, part 1 (Advent of Code 2021)

Question

Some notes that I thought would be worth mentioning up front:

• Advent of Code randomizes the input for each user, with the input format being 1,000 12-digit binary numbers delimited by newlines.
• I've verified that my solution works by submitting the generated answer on the website.

Here is the important part of the problem statement, transcribed from Day 3 - Advent of Code 2021:

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.)

My solution

#!/usr/bin/env python3

from pathlib import Path


def load_numbers(input_path: Path) -> list[int]:
    with input_path.open() as f:
        return [
            int(binary_string, 2)
            for line in f
            if (binary_string := line.strip())
        ]


def binary_diagnostic_part_one(input_path: Path) -> int:
    NUM_BINARY_DIGITS = 12
    zero_counts = [0] * NUM_BINARY_DIGITS

    # used to flip all bits in gamma rate to get epsilon rate
    BIT_MASK = 2 ** NUM_BINARY_DIGITS - 1  # 0b1111_1111_1111

    numbers = load_numbers(input_path)

    for number in numbers:
        for i in range(NUM_BINARY_DIGITS):
            binary_digit = (number >> i) & 1
            zero_counts[i] += int(binary_digit == 0)

    # calculate gamma rate from zero counts
    # starting from MSB -> LSB
    n = len(numbers)
    gamma_rate = 0
    for num_zeros in reversed(zero_counts):
        gamma_digit = 0 if num_zeros > n - num_zeros else 1
        gamma_rate = (gamma_rate << 1) | gamma_digit

    epsilon_rate: int = gamma_rate ^ BIT_MASK

    return gamma_rate * epsilon_rate


if __name__ == "__main__":
    print(binary_diagnostic_part_one(Path("input.txt")))

Sample input.txt

A pared-down version of the actual input.txt, for brevity.

010110011101
101100111000
100100000011
111000010001
001100010011
010000111100
001000100011
001000100111
010001111110
111101001011
011000101011

Output

3987500

Answer 1

Fiddling with bits is almost never fun. The crux of the problem is performing a matrix transposition on the bits. Performing this operation on Iterables is simplest as we can just use zip(*binary_string).

import io
from typing import IO


def binary_diagnostic_part_one(data: IO[str]) -> int:
    zero_counts = []
    n = 0
    with data:
        for bits in zip(*data):
            n = len(bits)
            zero_counts.append(sum(
                bit == "0"
                for bit in bits
            ))

    # calculate gamma rate from zero counts
    # starting from MSB -> LSB
    NUM_BINARY_DIGITS = 12
    BIT_MASK = 2 ** NUM_BINARY_DIGITS - 1  # 0b1111_1111_1111
    gamma_rate = 0
    for num_zeros in zero_counts:
        gamma_digit = 0 if num_zeros > n - num_zeros else 1
        gamma_rate = (gamma_rate << 1) | gamma_digit

    epsilon_rate: int = gamma_rate ^ BIT_MASK
    return gamma_rate * epsilon_rate


if __name__ == "__main__":
    # print(binary_diagnostic_part_one(Path("input.txt").open()))
    print(binary_diagnostic_part_one(io.StringIO(
        "010110011101\n"
        "101100111000\n"
        "100100000011\n"
        "111000010001\n"
        "001100010011\n"
        "010000111100\n"
        "001000100011\n"
        "001000100111\n"
        "010001111110\n"
        "111101001011\n"
        "011000101011"
    )))

From here it should be fairly clear we can easily merge the second for loop into the first.

import io
from typing import IO


def binary_diagnostic_part_one(data: IO[str]) -> int:
    gamma = 0
    num_bits = 0
    with data:
        for num_bits, bits in enumerate(zip(*data), 1):
            zeros = sum(
                bit == "0"
                for bit in bits
            )
            gamma_digit = 0 if 2 * zeros > len(bits) else 1
            gamma = (gamma << 1) | gamma_digit

    bit_mask = 2 ** num_bits - 1
    epsilon = gamma ^ bit_mask
    return gamma * epsilon


if __name__ == "__main__":
    # print(binary_diagnostic_part_one(Path("input.txt").open()))
    print(binary_diagnostic_part_one(io.StringIO(
        "010110011101\n"
        "101100111000\n"
        "100100000011\n"
        "111000010001\n"
        "001100010011\n"
        "010000111100\n"
        "001000100011\n"
        "001000100111\n"
        "010001111110\n"
        "111101001011\n"
        "011000101011"
    )))

---

• Advice from Kelly Bundy;

  bits is a tuple, so no need to reinvent zeros = bits.count("0").

• The code also doesn't work if the file ends in a newline. So we need to introduce the if line.strip() stuff.

import io
from typing import IO


def binary_diagnostic_part_one(data: IO[str]) -> int:
    gamma = 0
    num_bits = 0
    with data:
        lines = (
            _line
            for line in f
            if (_line := line.strip())
        )
        for num_bits, bits in enumerate(zip(*lines), 1):
            zeros = bits.count("0")
            gamma_digit = 0 if 2 * zeros > len(bits) else 1
            gamma = (gamma << 1) | gamma_digit

    bit_mask = 2 ** num_bits - 1
    epsilon = gamma ^ bit_mask
    return gamma * epsilon


if __name__ == "__main__":
    # print(binary_diagnostic_part_one(Path("input.txt").open()))
    print(binary_diagnostic_part_one(io.StringIO(
        "010110011101\n"
        "101100111000\n"
        "100100000011\n"
        "111000010001\n"
        "001100010011\n"
        "010000111100\n"
        "001000100011\n"
        "001000100111\n"
        "010001111110\n"
        "111101001011\n"
        "011000101011\n"
    )))