By Eric Burden | December 11, 2021
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!