Advent of Code: Day 10

Yesterday’s task was challenging, the task the day before yesterday wasn’t. The seventh’s day task was pretty straightforward, and the sixth one was kinda tricky to figure out. Today’s task is pretty easy again… I think I’m starting to see the pattern!

Just kidding, I don’t think there are some intentions to make tasks oscillate like this, it’s just that for some people some tasks are harder than the others. Today’s task was practically easy for me because I already wrote something like this, right when I’ve started this whole blog!¹

Syntax Scoring

After we’ve determined which basins to avoid we ask our submarine to find a safe route, but it reports that there’s an error:

Syntax error in navigation subsystem on line: all of them

And here’s our navigation subsystem that we need to fix:

[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]

So all lines are incorrect but for two different reasons. Some lines are just unfinished, e.g. all parentheses and brackets are stacked logically, there’s just not enough closing characters to match them. Other lines are indeed incorrect, because the closing paren doesn’t match the opening one, like here:

{([(<{}[<>[]}>{[]{[(<()>

We’ve expected a matching ] but instead found the }, which is not right. The puzzle claims that all syntax checkers have a scoring system, and in our case, the scores are like this:

• ): 3 points,
• ]: 57 points,
• }: 1197 points,
• >: 25137 points.

Our task is to find all non-matching parentheses in the input, and compute the total score.

day9> (ns day10)
nil
day10> (require '[clojure.string :as str])
nil
day10> (def example-input "
[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]")
#'day10/example-input
day10> (def incorrect-score
         {\) 3
          \] 57
          \} 1197
          \> 25137})
#'day10/incorrect-score
day10> (defn read-input []
         (->> example-input
              str/trim
              str/split-lines))

I’ve defined the score map as described in the task, but I’m using characters instead of strings, as it’s easier to work with them because strings in Clojure can be represented as sequences of characters. Now, we need a way to find what character is not the matching one.

The solution is pretty simple - a stack. We add opening characters to the stack, and when we get a closing one, we check if there’s a matching parenthesis is on the top of the stack. If it matches, we remove it from the stack and continue. If it doesn’t match, we’ve found the culprit.

day10> (def matching
         {\( \),
          \{ \},
          \[ \],
          \< \>})
#'day10/matching
day10> (defn to-stack-or-error-char [line]
         (loop [stack ()
                [paren & parens] line]
           (case paren
             (\( \[ \{ \<) (recur (cons paren stack) parens)
             (\) \] \} \>) (if (= (matching (first stack)) paren)
                             (recur (rest stack) parens)
                             paren)
             stack)))
#'day10/to-stack-or-error-char

This function builds the stack and if there were no mismatching chars it returns it, otherwise, it returns the mismatched character. I’ve also created the matching table, to quickly convert opening parens into the matching closing ones. Here’s how it works:

day10> (to-stack-or-error-char "[({(<(())[]>[[{[]{<()<>>")
(\{ \{ \[ \[ \( \{ \( \[)
day10> (to-stack-or-error-char "{([(<{}[<>[]}>{[]{[(<()>")
\}

Pretty universal, but maybe a bit inconvenient to use. Now, all that’s left is to find mismatches for all lines, and calculate the score:

day10> (defn part-1 [input]
         (->> input
              (keep to-stack-or-error-char)
              (filter char?)
              (map incorrect-score)
              (reduce +)))
#'day10/part-1
day10> (part-1 (read-input))
26397

I’m filtering results, only keeping those that are single characters as the (keep to-stack-or-error-char input) call returns a list of both stacks and chars.

Part two

This solves only half of our problems. We still have a lot of lines that are valid, but unfinished, and our second task is to finish those and compute a completion score:

The completing score is a bit different from the mismatch score:

day10> (def correct-score
         {\) 1
          \] 2
          \} 3
          \> 4})
#'day10/correct-score

To calculate the score, we need to fill the stack first. Except not, we can just use the valid stack and swap all opening parentheses to the closing ones. Then we can score those and calculate the total score. Total score is calculated by this formula (score-so-far * 5) + paren-score for each parenthesis. Sounds like a job for reduce:

day10> (defn score-completion-stack [stack]
         (->> stack
              (map matching)
              (map correct-score)
              (reduce (fn [total score]
                        (+ (* total 5) score)))))
#'day10/score-completion-stack
day10> (score-completion-stack (to-stack-or-error-char "(((({<>}<{<{<>}{[]{[]{}"))
1480781

In the example above I’m passing the correct line, but this function will fail on incorrect inputs. Thankfully we can filter these out by simply checking that elements are collections, similarly to our check in the first part. One last bit we need to make is that to get the correct result we must sort the scores and take exactly the middle one:

day10> (defn get-middle [list]
         (first (drop (quot (count list) 2) list)))
#'day10/get-middle
day10> (defn part-2 [input]
         (->> input
              (map to-stack-or-error-char)
              (filter coll?)
              (map score-completion-stack)
              sort
              get-middle))
#'day10/part-2
day10> (part-2 (read-input))
288957

Clojure doesn’t have a function to get the middle element of the collection directly, but it’s quite easy to do, so it’s not a problem. And the quot function helps avoiding direct use of java.lang.Math/floor or casting fractions to int with int.

Day 10 thoughts

This day’s task was easy. I think this was mostly due to the fact that I’ve already written a Scheme-like language before, where I solved exactly the same problem. Except there I’ve used a bit simpler solution as I’ve only needed to check the last character, as was not planning to automatically complete the stack. InterLisp mapped the ] key to a shortcut that closed all opened parentheses before the cursor. I think this could be possible to be done in the Reader, though it would annoy a lot of text editors as they expect parentheses to be balanced.

Today’s puzzle was fun, and I think it’s even practical as it teaches you how to parse structured data with a stack. And with that, thanks for reading, and until tomorrow!