Day 10: Syntax Scoring

Puzzle description

https://adventofcode.com/2021/day/10

Solution overview

Day 10 focuses on detecting unbalanced markers in the navigation system of the submarine. The possible markers are ()[]{}<>. The input contains several lines, our task is to check whether each line is balanced, incomplete or invalid.

I propose a solution centered around the algorithm that verifies each line and that will be used in both part 1 and part 2.

An input is represented by a LazyList[List[Symbol]] where each List[Symbol] is a line of the input. Symbols are defined by the kind (parenthesis, bracket, brace or diamond) and the direction (open or close):

enum Direction:
  case Open, Close

enum Kind:
  case Parenthesis, Bracket, Brace, Diamond

case class Symbol(kind: Kind, direction: Direction):
  def isOpen: Boolean = direction == Direction.Open

In this encoding, { is represented by Symbol(Brace, Open).

The function that verifies a line produces a value of type CheckResult which encapsulates the possible results of the check:

Ok if the input is valid
Incomplete(pending) if the line finishes leaving some markers open. For example then line [ is incomplete and will result in Incomplete(List(Symbol(Bracket, Open)))
IllegalClosing(expected, found) if a line contains a symbol closed by a symbol whose kind is not correct. For example [} is corrupted and will result in IllegalClosing(Some(Symbol(Bracket, Close)), Symbol(Brace, Close))

An enum is used to encode this hierarchy:

enum CheckResult:
  case Ok
  case IllegalClosing(expected: Option[Symbol], found: Symbol)
  case Incomplete(pending: List[Symbol])

Line checking algorithm

The algorithm is implemented in the tail-recursive function iter nested in the checkChunks function. It consumes one character at a time, retrieving it from the input list. It also maintains a stack (LIFO) of pending markers. I use List as a stack relying on pattern matching against head :: tail to pop or push elements on the stack.

Consider the base case: when input is empty (Nil) then the algorithm reached the end of the line. In this situation, the result is Ok if there are no unmatched markers (when the pending stack is empty). Otherwise the line is incomplete:

      case Nil =>
        if pending.isEmpty then CheckResult.Ok
        else CheckResult.Incomplete(pending)

When input contains at least one symbol, we pop it from the list. If the symbol is an open marker (direction is Open) then we push it on the pending stack and we continue iterating over the rest of the row.

Otherwise, when the new symbol is a closing marker, we need to check if it matches the top of the pending stack. Therefore if this stack is empty or if the top of the stack has a different kind (for example it is brace and the new symbol is a bracket) then we can stop and declare the line as corrupted (returning a IllegalClosing). If the line is not corrupted, then the symbol closes the marker opened by the top of the stack: we can remove the top of the stack and continue with the rest of the input.

      case nextChar :: remainingChars =>
        // a new opening marker: push it on pending and continue analysing the row
        if nextChar.isOpen then iter(nextChar :: pending, remainingChars)
        else pending match
          // pending is empty: nextChar closes a marker that was not opened
          case Nil => CheckResult.IllegalClosing(None, nextChar)
          case lastOpened :: previouslyOpened =>
            // nextChar closes the marker opened by lastOpened, we can continue after popping
            // the top of the stack.
            if lastOpened.kind == nextChar.kind then iter(previouslyOpened, remainingChars)
            // nextChar closes a marker that was not opened by the top of the stack: error
            else CheckResult.IllegalClosing(Some(lastOpened), nextChar)

Solution of Part 1

To solve the first part, I analyze all the lines in the input and retain the corrupted ones. As the symbol causing corruption is maintained inside the IllegalClosing object, I can compute the score of each mistake and add them up.

extension (illegalClosing: CheckResult.IllegalClosing)
  def score: Int =
    import Kind.*
    illegalClosing.found.kind match
      case Parenthesis => 3
      case Bracket => 57
      case Brace => 1197
      case Diamond => 25137

def part1(input: String): Int =
  val rows: LazyList[List[Symbol]] =
    input.linesIterator
      .to(LazyList)
      .map(parseRow)

  rows.map(checkChunks)
    .collect { case illegal: CheckResult.IllegalClosing => illegal.score }
    .sum

Solution of Part 2

In the second part, we focus on incomplete lines. For each line, I use an iteration accumulator currentScore initialized to 0 and I iterate over each missing symbol, at each step I multiply the accumulator by 5 and add the score corresponding to the missing symbol.

I know what symbol is missing from the input because CheckResult.Incomplete contains all the symbols opening a marker which is not closed. Therefore missing symbols can be obtained by iterating over the pending stack from top to bottom:

This iteration is performed by foldLeft:

extension (incomplete: CheckResult.Incomplete)
  def score: BigInt =
    incomplete.pending.foldLeft(BigInt(0)) { (currentScore, symbol) =>
      val points = symbol.kind match
        case Parenthesis => 1
        case Bracket => 2
        case Brace => 3
        case Diamond => 4

      currentScore * 5 + points
    }

Once I have the scores of all incomplete lines, I sort the scores and retrieve the element in the middle:

def part2(input: String): BigInt =
  val rows: LazyList[List[Symbol]] =
    input.linesIterator
      .to(LazyList)
      .map(parseRow)

  val scores =
    rows.map(checkChunks)
      .collect { case incomplete: CheckResult.Incomplete => incomplete.score }
      .toVector
      .sorted

  scores(scores.length / 2)

Run it locally

You can get this solution locally by cloning the scalacenter/scala-advent-of-code repository.

$ git clone https://github.com/scalacenter/scala-advent-of-code
$ cd scala-advent-of-code

You can run it with scala-cli.

$ scala-cli 2021 -M day10.part1
The solution is 367059
$ scala-cli 2021 -M day10.part2
The solution is 1952146692

You can replace the content of the input/day10 file with your own input from adventofcode.com to get your own solution.

Solutions from the community

Share your solution to the Scala community by editing this page.

Day 10: Syntax Scoring

Puzzle description​

Solution overview​

Line checking algorithm​

Solution of Part 1​

Solution of Part 2​

Run it locally​

Solutions from the community​