website/content/wiki/aoc/2021/03.md

title	date	day	stars
AoC 2021 - Day 3	2021-12-03T16:51:41+01:00	3	2

Today's challenge is here. It turned out to be pretty tricky with many possible approaches to solve it. First task was pretty trivial, but I kind of feel like my second solution was a bit overengineered 😄

Loading data is pretty simple, all I had to do here was to load strings:

def load_input() -> list[str]:
    with open('../.input/day03', 'r') as f:
        return [line.strip() for line in f.readlines()]

Task 1

Here we had to find two binary numbers based on the frequency of digits at each position. I used a dict to store count of 0s and 1s at each position for all binary numbers. Then I used this dict to construct two binary numbers. The number for gamma consists of the most frequent digits at each position, and the number for epsilon consists of the least frequent digits at each position.

def solve1() -> int:
    input = load_input()
    cache = [{"0": 0, "1": 0} for _ in range(len(input[0]))]

    for binary in input:
        for i, c in enumerate(binary):
            cache[i][c] += 1
    
    gamma, epsilon = map(sum, zip(*[
        (2**i, 0) if c["1"] > c["0"] else (0, 2**i)
        for i, c in enumerate(reversed(cache))
    ]))
    return gamma * epsilon

After finding the binary numbers I converted both of them to decimal and multiplied them. An interesting part here is the usage of zip(*iterable]) notation to turn a list of tuples into a tuple of lists.

It can be visualized as: [(x1, y1), (x2, y2), ...] -> [[x1, x2, ...], [y1, y2, ...]]

Task 2

Here we had to find a single remaining binary number for each case - oxygen and carbon. I used a dict once again to store the frequency of each digit at each position. Then I used this data to filter out the binary numbers until there is only one left. The part where I filter the numbers is also where I update the dict by subtracting the frequency, so that it stays up to date for the next iteration.

def find_single(input: list[str], reverse: bool = False) -> int:
    cache = [{"0": 0, "1": 0} for _ in range(len(input[0]))]
    remaining = input[:]
    
    for binary in remaining:
        for i, digit in enumerate(binary):
            cache[i][digit] += 1
    
    for i, c in enumerate(cache):
        if len(remaining) == 1:
            break

        generator = (entry for entry in remaining)
        remaining = []
        winning_digit = ("0" if c["0"] <= c["1"] else "1") if reverse else ("1" if c["1"] >= c["0"] else "0")
        for binary in generator:
            if binary[i] == winning_digit:
                remaining.append(binary)
            else:
                for digit, cache_dict in zip(binary, cache):
                    cache_dict[digit] -= 1
    
    return remaining[0]

Here I use the function to find the multiply from the resulting numbers for oxygen and cargon:

def solve2() -> int:
    input = load_input()
    oxygen, carbon = input[:], input[:]
    res_o = sum(2**int(i) for i, x in enumerate(reversed(find_single(oxygen, reverse=False))) if x == "1")
    res_c = sum(2**int(i) for i, x in enumerate(reversed(find_single(carbon, reverse=True))) if x == "1")
    return res_o * res_c

Bonus: Task 1 in NumPy

The way this works is it loads all data into a single matrix, calculates mean value for each place, converts to nearest integer. The other thing is the logical_not of that. Then you get decimal number by calculating dot product of the binary number and a [1, 2, 4, 8, ...] vector reversed.

import numpy as np


def load_input_np() -> np.ndarray:
    with open('../.input/day03', 'r') as f:
        return np.array([list(map(np.int32, list(i.strip()))) for i in f.readlines()])


def solve1_np() -> int:
    input = load_input_np()
    binary = input.mean(axis=0) >= 0.5
    invert = ~binary
    decimalize = 2 ** np.arange(binary.shape[0])[::-1]
    return sum(binary * decimalize) * sum(invert * decimalize)