Day 10/2021 - Syntax Scoring

Day ten of AoC 2021 (available at https://adventofcode.com/2021/day/10) brings us to every developer's favorite game: finding the missing parenthesis. Time to go crawling through brackets, braces, and angle brackets.

The input has lines of nested brackets. Some lines are corrupted (wrong closing bracket), others are incomplete (missing closing brackets).

The Stack Solution

When someone says "match nested brackets," experienced developers reach for a stack. Push opening brackets, pop when you see closers. If the popped opener doesn't match the closer, you've found corruption.

interface InvalidParseResult {
    line: string;
    success: false;
    errorIndex: number;
}

interface ValidParseResult {
    line: string;
    success: true;
    completion: string[];
}

type ParseResult = InvalidParseResult | ValidParseResult;

const parseLine = (line: string): ParseResult => {
    const stack = [];
    const openers = ['(', '{', '[', '<'];
    const closers = [')', '}', ']', '>'];
    
    for (let index = 0; index < line.length; index++) {
        const char = line[index];
        if (openers.includes(char)) {
            stack.push(char);
        } else if (closers.includes(char)) {
            const opener = stack.pop();
            const closerIndex = closers.indexOf(char);
            if (opener !== openers[closerIndex]) {
                return {
                    line: line,
                    success: false,
                    errorIndex: index,
                };
            }
        } else {
            throw new Error(`Invalid character ${char}`);
        }
    }

    return {
        line,
        success: true,
        completion: stack.reverse().map(c => closers[openers.indexOf(c)]),
    };
};

The discriminated union type (ParseResult = InvalidParseResult | ValidParseResult) lets TypeScript narrow the type based on the success property.

The key insight: openers and closers are parallel arrays. openers[0] matches closers[0], etc. Index lookup gives us the matching pair.

Part One: Finding Corruption

Filter to corrupted lines, score them by which wrong character appeared:

const partOne = (input: string[], debug: boolean) => {
    const costs = {
        ')': 3,
        ']': 57,
        '}': 1197,
        '>': 25137,
    };

    const parsed = input.map(line => parseLine(line));
    const invalids = parsed.filter(pr => !pr.success) as InvalidParseResult[];
    const result = invalids
        .map(pr => pr.line[pr.errorIndex])
        .reduce((acc, cur) => acc + costs[cur], 0);
    return result;
};

The Transcription Bug

My first attempt gave the wrong answer. The algorithm was correct — I verified with the example input. The bug? I transcribed the scoring table wrong:

// Wrong - I typed 197 instead of 1197
"}": 197,

I spent way too long debugging my reduce function and verifying my counts in Excel, when the actual bug was a simple typo in a constant. Always double-check your magic numbers.

Part Two: Completing Lines

For valid (incomplete) lines, the stack contains all unmatched openers. Reverse it and convert each to its corresponding closer:

const scoreCompletion = (completion: string[]) => {
    const costs = {
        ')': 1,
        ']': 2,
        '}': 3,
        '>': 4,
    };

    return completion.reduce((acc, cur) => 5 * acc + costs[cur], 0);
};

const partTwo = (input: string[], debug: boolean) => {
    const parsed = input.map(line => parseLine(line));
    const valids = parsed.filter(pr => pr.success) as ValidParseResult[];
    const scores = valids
        .map(pr => scoreCompletion(pr.completion))
        .sort((a, b) => a - b);
    const result = scores[(scores.length - 1) / 2];
    return result;
};

The scoring is base-5 encoding: multiply by 5, add the character value. This ensures longer completions score higher, and earlier characters matter more.

Why Not Regex?

Someone always asks: "Can't you match brackets with regex?"

Technically, some regex engines support recursive patterns. But this way lies madness. The bracket structure is inherently recursive — brackets within brackets within brackets. Regex is designed for regular languages; nested structures are context-free.

A stack is the right tool: simple, efficient, and obvious. Don't fight the tool hierarchy.

The Algorithm Visualized

For a line like {([(<>)]}:

Character | Stack      | Action
----------|------------|--------
{         | {          | Push
(         | {(         | Push
[         | {([        | Push
(         | {([(       | Push
<         | {([(<      | Push
>         | {([(       | Pop, matches <
)         | {([        | Pop, matches (
]         | {(         | Pop, matches [
}         | ERROR!     | Pop gives (, expected ) not }

We expected ) but got }. Corrupted line, error at index 8.

Performance

Both parts run in ~2-3ms. We traverse each line once, and stack operations are O(1). Sorting the completion scores is O(n log n) but n is small.

Takeaways

1. Stacks for bracket matching: This is the canonical use case. Push openers, pop for closers, check for match.

2. Parallel arrays for lookup: openers and closers having the same indices makes conversion trivial.

3. Check your constants: Algorithmic bugs are dramatic. Typos in magic numbers are subtle and frustrating. Double-check transcribed values.

4. Don't use regex for nested structures: Regex handles regular languages. Nested brackets are context-free. Use the right tool.

5. Reverse the stack for completion: What's left on the stack (reversed) tells you exactly what closers are needed.

The full solution is available in the repository.