Advent of Code 2021 - Day 10

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 10 - Syntax Scoring

Find the problem description HERE.

The Input - Simplicity Itself

I’m mostly just leaving this section in today for the sake of consistency. Reading in the data today is just a matter of reading each line and collecting it into a Vector{Char}, then returning the list of lines.

function ingest(path)
    return open(path) do f
        [collect(line) for line in readlines(f)]
    end
end

Part One - Chunkopolypse

Ah, my favorite error message: “Everything is wrong!”. Essentially, each line consists of a string of brackets (in four different flavors) that is not well-formed in some way, either because some of the closing brackets are missing (called “incomplete”) or because an opening bracket is closed by an bracket that does not match (called “corrupted”). The “corrupted” bracket may be separated from the opening bracket by any number of opening and closing brackets. First, we need to identify all the “corrupted” closing brackets, get the corresponding score, then sum all the scores.

The simplest way I know to identify the “corrupted” closing bracket is to iterate over the characters from left to right, adding each opening bracket to the top of a stack. Whenever a closing bracket is found, check the top of the stack. If the two make a matched pair, remove the opening bracket from the top of the stack and move on. If not, then we’ve found our “corrupted” bracket!

# Some useful constants
OPENING_BRACKETS = Set(['(', '[', '{', '<'])
CLOSING_BRACKETS = Set([')', ']', '}', '>'])
MATCHES = Dict([
    '(' => ')', '[' => ']', '{' => '}', '<' => '>',
    ')' => '(', ']' => '[', '}' => '{', '>' => '<'
])
POINTS = Dict([')' => 3, ']' => 57, '}' => 1197, '>' => 25137])

# Some useful utility functions
isopening(b) = b in OPENING_BRACKETS
isclosing(b) = b in CLOSING_BRACKETS
ismatch(lhs, rhs) = !ismissing(rhs) && !ismissing(lhs) && rhs == MATCHES[lhs] 

# Search a line for the "corrupted" character by putting all opening
# brackets onto a stack, removing them when we find a match, and
# returning the unmatched bracket if it doesn't match.
function getcorruptedchar(line)
    stack = []; sizehint!(stack, length(line))
    for bracket in line
        if isopening(bracket)
            push!(stack, bracket)
            continue
        end

        lastbracket = pop!(stack)
        ismatch(lastbracket, bracket) && continue
        return bracket            
    end
    return missing
end

# Get the "corrupted" character from each line, look up its score,
# then add it to the total score.
function part1(input)
    total = 0
    for char in map(getcorruptedchar, input)
        ismissing(char) && continue
        total += POINTS[char]
    end
    return total
end

I feel like finding “balanced” brackets/parentheses is a pretty common problem. At least, it’s one I’ve seen pop up in a couple of different places, so it seems like this algorithm is a pretty good one to have on hand.

Part Two - Stack Attack

Part two is very similar to part one, except now we’re iterating over our lines from back to front, and keeping “all” the unmatched brackets instead of just one.

# Another useful constant
SCORE_FOR = Dict([')' => 1, ']' => 2, '}' => 3, '>' => 4])

# And another utility function!
notcorrupted(line) = ismissing(getcorruptedchar(line))

# Similar to before. This time, we start adding brackets from
# the end of the line to our stack. If it's a closing bracket, 
# we add it to our stack. If it's an opening bracket, we get the 
# closing bracket off the top of our stack. If they match, we just
# keep going. If not, we add the bracket to our list of unmatched
# opening brackets.
function getclosingbrackets(line)
    closingbrackets = []; sizehint!(closingbrackets, length(line))
    stack = []; sizehint!(stack, length(line))

    while !isempty(line)
        bracket = pop!(line)

        if isclosing(bracket)
            push!(stack, bracket)
            continue
        end

        if isopening(bracket)
            stackbracket = isempty(stack) ? missing : pop!(stack)
            ismatch(bracket, stackbracket) && continue
            push!(closingbrackets, MATCHES[bracket])
        end
    end
    return closingbrackets
end

# Given a list of opening brackets, look up each bracket's corresponding
# score and add it to a running total.
function calculatescore(unmatched)
    total = 0
    for bracket in unmatched
        total *= 5
        total += SCORE_FOR[bracket]
    end
    return total
end

# For each line, get the unmatched opening brackets, and calculate the
# score for that line. With all the line scores, we just sort them and
# return the score from the middle.
function part2(input)
    (scores
     = input
     |> (lines -> filter(notcorrupted, lines))
     |> (lines -> map(getclosingbrackets, lines))
     |> (lines -> map(calculatescore, lines)))

    sort!(scores)
    middle = (length(scores) + 1) ÷ 2
    return scores[middle]
end

Nice.It’s basically part one in reverse. No sweat!

Wrap Up

This was a bit of a breather, but probably in large part because I’ve seen a couple of different variations on this puzzle before. I suspect it could be a bit tricky if you’re trying to come up with the algorithm from scratch. I don’t have a lot else to say about this one, so I’ll see you tomorrow!

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!