Advent of Code 2021 – Day 10

By: Julia on Eric Burden

Re-posted from: https://ericburden.work/blog/2021/12/11/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!