Day 1/2023 - Trebuchet?!

The first puzzle of 2023's AoC (available at https://adventofcode.com/2023/day/1) starts with us being loaded into a trebuchet. The calibration document has been "amended" by an elf, and we need to extract calibration values from each line by combining the first digit and the last digit into a two-digit number.

For a line like a1b2c3d, the first digit is 1, the last is 3, giving us 13.

Parsing and Part One

Each line needs to yield its first and last digit. JavaScript's find and findLast on character arrays work nicely:

const mapFirstLast = (input: string[]): { first: number; last: number }[] => {
    return input.map(line => {
        const chars = line.split("");
        const digitRegex = /\d/;
        
        const first = chars.find(c => digitRegex.test(c))!;
        const last = chars.findLast(c => digitRegex.test(c))!;
        
        return { first: +first, last: +last };
    });
};

const partOne = (input: string[], debug: boolean) => {
    const fls = mapFirstLast(input);
    return fls.reduce((sum, { first, last }) => sum + first * 10 + last, 0);
};

Part one returns 55621 for my input. Straightforward enough.

Part Two: The Trap

Part two reveals that spelled-out numbers (one, two, etc.) also count as digits. Simple, right? Just do a find-and-replace: one → 1, two → 2, and so on.

Wrong.

Consider the string oneight. If you replace one with 1, you get 1ight. The eight is destroyed. But according to the puzzle, looking from the start, the first digit is one (1). Looking from the end, the last digit is eight (8). The answer should be 18, not 11.

This trap caught everyone. I saw discussions everywhere about it. Even Uncle Bob tweeted about falling into this hole. Part one tricks you into a pattern of thinking, and part two punishes you for it.

The Fix: Search From Both Ends

Instead of modifying the string, search from the start for the first digit and from the end for the last digit:

const getFirstDigit = (input: string, map: Record<string, number>): number => {
    // Terribly inefficient, but works
    for (let index = 0; index < input.length; index++) {
        const part = input.substring(index);
        for (const key in map) {
            if (part.startsWith(key)) {
                return map[key];
            }
        }
    }
    return -Infinity; // Should never happen
};

const getLastDigit = (input: string, map: Record<string, number>): number => {
    for (let index = input.length; index >= 0; index--) {
        const part = input.substring(0, index);
        for (const key in map) {
            if (part.endsWith(key)) {
                return map[key];
            }
        }
    }
    return -Infinity;
};

For part one, the map is simple: { "1": 1, "2": 2, ... "9": 9 }.

For part two, we extend it: { "1": 1, "one": 1, "2": 2, "two": 2, ... }.

const partTwoMap: Record<string, number> = {
    "1": 1, "one": 1,
    "2": 2, "two": 2,
    "3": 3, "three": 3,
    "4": 4, "four": 4,
    "5": 5, "five": 5,
    "6": 6, "six": 6,
    "7": 7, "seven": 7,
    "8": 8, "eight": 8,
    "9": 9, "nine": 9,
};

const partTwo = (input: string[], debug: boolean) => {
    let total = 0;
    for (const line of input) {
        const first = getFirstDigit(line, partTwoMap);
        const last = getLastDigit(line, partTwoMap);
        total += first * 10 + last;
    }
    return total;
};

Now oneight correctly returns 18.

Performance

The nested loops are O(n × m × k) where n is string length, m is number of keys, and k is key length. That's terrible algorithmically, but with ~1,000 lines and small strings, it runs in under 60 milliseconds. Good enough.

A regex-based solution could be more elegant, but this brute-force approach is easy to understand and debug.

The Lesson

Part one's test input and real input only contained numeric digits. Part two's test input was different from part one's — a hint that something fundamental changed, not just an extension.

The overlapping number problem (twone, oneight, sevenine) doesn't appear in obvious test cases. You only discover it when your answer is wrong and you start debugging.

When the puzzle says "the first digit" and "the last digit," it means exactly that — search from each end independently. Don't try to transform the string into something part one can handle.

Takeaways

1. Read the puzzle carefully: "First digit" and "last digit" implies searching from both directions, not finding-and-replacing.

2. Test inputs can mislead: Part two's test input was intentionally different. The real traps only appear in the actual input.

3. Simple brute force works: Nested loops are ugly but clear. With small inputs, clarity beats cleverness.

4. Everyone makes mistakes: When Uncle Bob falls into the same trap, you're in good company.

5. startsWith and endsWith are your friends: These string methods make the directional search clean and readable.

The full solution is available in the repository.