Day 3/2021 - Binary Diagnostic

Day three of AoC 2021 (available at https://adventofcode.com/2021/day/3) has us running diagnostics on the submarine. The input is a list of binary numbers, and we need to analyze bit patterns across all of them.

Time to count some zeros and ones.

Parsing the Input

Each line is a binary string. I'm representing bits as literal string types:

type Bit = "0" | "1";

const processInput = (day: number): Bit[][] => {
    const lines = readInputLines(day);
    return lines.map(line => line.split("") as Bit[]);
};

Yes, using strings to represent bits is "wasteful." But it works, it's clear, and the input is small. Save the bit-twiddling heroics for when you need them.

Part One: Most and Least Common Bits

For each bit position, find the most common bit across all numbers. That forms the gamma rate. The epsilon rate is the complement (least common bits).

First, count zeros and ones at each position:

type Count = { "0": number; "1": number };

const getCounts = (input: Bit[][]): Count[] => {
    const width = input[0].length;
    const counts: Count[] = Array.from({ length: width }, () => ({ "0": 0, "1": 0 }));
    
    for (const row of input) {
        for (let i = 0; i < row.length; i++) {
            counts[i][row[i]]++;
        }
    }
    
    return counts;
};

Then extract gamma and epsilon:

const partOne = (input: Bit[][], debug: boolean) => {
    const counts = getCounts(input);
    
    const gamma = counts.map(c => c["0"] > c["1"] ? "0" : "1").join("");
    const epsilon = counts.map(c => c["0"] > c["1"] ? "1" : "0").join("");
    
    const gValue = parseInt(gamma, 2);
    const eValue = parseInt(epsilon, 2);
    
    return gValue * eValue;
};

JavaScript's parseInt(str, 2) handles binary-to-decimal conversion. No need to manually calculate powers of two.

Part Two: Filtering Reports

Part two is more complex. We filter the list based on bit criteria, position by position, until one number remains.

For the oxygen generator rating: at each position, keep numbers with the most common bit (ties favor 1).

For the CO2 scrubber rating: keep numbers with the least common bit (ties favor 0).

type Histogram = { most: Bit; least: Bit };

const getHistogram = (reports: Bit[][], index: number): Histogram => {
    let zeros = 0;
    let ones = 0;
    
    for (const row of reports) {
        if (row[index] === "0") zeros++;
        else ones++;
    }
    
    return {
        most: zeros > ones ? "0" : "1",   // Ties favor 1
        least: ones < zeros ? "1" : "0"   // Ties favor 0
    };
};

const partTwo = (input: Bit[][], debug: boolean) => {
    // Oxygen generator rating
    let o2Reports = [...input];
    let o2Index = 0;
    while (o2Reports.length > 1) {
        const hist = getHistogram(o2Reports, o2Index);
        o2Reports = o2Reports.filter(row => row[o2Index] === hist.most);
        o2Index++;
    }
    const o2Value = parseInt(o2Reports[0].join(""), 2);
    
    // CO2 scrubber rating
    let co2Reports = [...input];
    let co2Index = 0;
    while (co2Reports.length > 1) {
        const hist = getHistogram(co2Reports, co2Index);
        co2Reports = co2Reports.filter(row => row[co2Index] === hist.least);
        co2Index++;
    }
    const co2Value = parseInt(co2Reports[0].join(""), 2);
    
    return o2Value * co2Value;
};

The code is duplicated between O2 and CO2 calculations. I could extract a helper, but we're only calling it twice. For AoC, clarity beats DRY.

The Tie-Breaker Trap

The puzzle specifies that ties favor 1 for most-common and 0 for least-common. This asymmetry is easy to miss. My histogram logic handles it:

most: zeros > ones ? "0" : "1"   // Equal means 1 wins
least: ones < zeros ? "1" : "0"  // Equal means 0 wins

If zeros and ones are equal, zeros > ones is false, so we return "1". The least-common check is inverted similarly.

Performance

Both parts run in under 10 milliseconds combined. The algorithm is essentially linear — we're iterating through the input a handful of times.

I'm sure there's a clever bit-manipulation solution hiding here. You could probably XOR and AND your way to the answer faster. But the naive approach is fast enough and obviously correct. Optimization can wait for puzzles where it matters.

Takeaways

1. Strings are fine for small inputs: Representing bits as "0" and "1" strings is wasteful but clear. Premature optimization is the root of all evil.

2. parseInt(str, 2) is your friend: JavaScript handles binary parsing natively. No need for manual conversion.

3. Literal types catch errors: type Bit = "0" | "1" means TypeScript will complain if you accidentally use "2" or forget to handle a case.

4. Copy before filtering: The [...input] spread creates a copy so the original array isn't mutated. Important when you need to process the same data twice with different criteria.

5. Watch for tie-breaker rules: The asymmetric handling of ties (favor 1 vs favor 0) is the kind of detail that's easy to miss on first read.

The full solution is available in the repository.