Advent of Code 2021: Stack-Based Bracket Matching in C

Advent of Code 2021 was running and I had a few evenings free. I knocked out four days – the first three in Python for speed, and Day 10 in C because it was a perfect excuse to build a stack from scratch.

Days 1-3: Python for Quick Wins

The early AoC days are warm-ups. Python is the right tool when the goal is “solve it before midnight”:

Day 1 (Sonar Sweep): Count depth increases in a list. Part 2 adds a sliding window of size 3. Straightforward loop with index arithmetic. Five minutes.

Day 2 (Dive!): Parse submarine commands (forward 5, down 3, up 2). Part 1 tracks position directly. Part 2 introduces an aim variable that changes how forward affects depth. Used re.match() for parsing – slightly over-engineered when split() would do, but old habits.

Day 3 (Binary Diagnostic): Bit counting across 12-bit binary numbers. Part 1 finds gamma/epsilon rates. Part 2 iteratively filters candidates by most/least common bit at each position – the oxygen generator and CO2 scrubber ratings.

The Day 3 solution was ugly enough that the commit message was honest about it: “super ugly solution that needs refactor… got it working, make it pretty next.” The “make it pretty” part never happened, which is the most realistic thing about this entire exercise.

Day 10: Syntax Scoring in C

Day 10 was the one I actually wanted to write about. The problem: given lines of nested brackets ((), [], {}, <>), find corrupted lines (wrong closing bracket) and incomplete lines (missing closing brackets). Score them differently.

This is a textbook stack problem, and I wanted to build the stack myself.

The Stack

A character array with push, pop, peek, and isEmpty. Nothing fancy, but the implementation decisions matter:

char parens[ARRAY_LEN];
int indeX = 0;  // "index" clashed with something else

bool push(char val)
{
    if (indeX < ARRAY_LEN) {
        parens[indeX++] = val;
        return true;
    }
    return false;
}

char pop(void)
{
    if (indeX > 0) {
        char tmp = peek();
        indeX--;
        parens[indeX] = ' ';
        return tmp;
    }
    return ' ';
}

The push returns a boolean for overflow protection. The pop clears the vacated slot (not strictly necessary, but makes debugging easier when you print the array). The index variable is named indeX because index collided with another symbol – the kind of naming compromise that only happens in C.

Part 1: Corrupted Lines

Walk each line character by character. Open brackets get pushed. Closing brackets check if they match the top of the stack:

if (c == '(' || c == '[' || c == '{' || c == '<')
{
    push(c);
}
else
{
    if (isMatch(c))
        pop();       // correct close, continue
    else
        // CORRUPTED: expected one thing, got another
}

The isMatch function uses a switch statement to map closing brackets to their opening counterparts. Score the first illegal character per line: ) = 3, ] = 57, } = 1197, > = 25137.

Part 2: Incomplete Lines

Lines that aren’t corrupted but still have items on the stack at end-of-line are incomplete. Pop remaining open brackets, map each to its closing counterpart, and compute a score:

while (!isEmpty())
{
    char c = pop();
    uint64_t tmp = 0;
    if (c == '(') tmp = 1;
    else if (c == '[') tmp = 2;
    else if (c == '{') tmp = 3;
    else if (c == '<') tmp = 4;
    score = score * 5 + tmp;
}

The score * 5 + value accumulation produces large numbers fast, which is why the score is a uint64_t. The final answer is the median of all incomplete line scores, computed via qsort with a custom comparator:

int compare(const void* a, const void* b)
{
    const uint64_t ai = *(const uint64_t*)a;
    const uint64_t bi = *(const uint64_t*)b;
    if (ai < bi) return -1;
    else if (ai > bi) return 1;
    else return 0;
}

qsort(invalidScores, invalidScoreCount, sizeof(uint64_t), compare);
printf("INVALID SCORE %ju", invalidScores[invalidScoreCount / 2]);

The comparator can’t just return a - b like you’d do with int – uint64_t subtraction wraps around, so explicit comparison is required. A common gotcha.

The Pragmatic Choice: Embedded Puzzle Input

Rather than reading from a file, I embedded the entire 94-line puzzle input as a C string literal in main(). Is it elegant? No. Did it let me skip writing file I/O and focus on the actual algorithm? Yes. AoC is about solving puzzles, not building production infrastructure.

What I Took Away

The split between Python and C was deliberate. Days 1-3 are parsing and arithmetic – Python’s wheelhouse. Day 10 is a data structure problem where building the stack is the interesting part. Using C forced me to think about:

• Memory layout. The stack is a contiguous character array. Push increments an index. Pop decrements it. No linked list, no dynamic resizing, just an array and a counter. For a bounded problem like AoC, this is the right trade.
• Type safety with large numbers. The uint64_t for scores, the explicit comparator for qsort – these are details that Python’s arbitrary-precision integers hide from you. Knowing when integer overflow matters is a systems skill.
• State management. The stack’s global state (parens[], indeX) needs to be reset between lines. In a real codebase you’d pass a stack struct by pointer. For a puzzle, a memset and index reset between lines is fine.

Four days isn’t a deep AoC run, but Day 10 alone was worth it for the stack exercise. The full source is on GitHub.