Advent of Code 2021 day 10

Day 10 was one where solving part 1 gave you part 2 just about for free.

The key part is to keep track of the closing characters you expect to see, in order, as you move along the input line. As the closing characters appear in reverse order of the corresponding opening characters, a stack is the most appropriate structure to keep track of things.

I found this easiest to think about by considering what would need to be in place while part-way through parsing a chunk.

We need to have a stack of the closing characters we're expecting to see, in order. That stack represents the successful parsing of the input line so far. We're given the next character to assess (and the rest of the text following it). There are five cases:

1. The next character matches the expected closing character for this chunk. In this case, we pop the closing character from the stack and continue with the rest of the text.
2. The next character is an opening character. In this case, we push the corresponding character to the stack and continue with the rest of the text.
3. The next character is a closing character, but not the one we expected! In this case, the chunk is corrupt and we return what we know so far (the stack of expected closing characters, and the remaining text).
4. The stack is now empty. That means the chunk is complete and we return that discovery, along with the remaining text for more chunks to be found.
5. There is no next character! That means the chunk is incomplete and, again, we return what we know so far.

This gives us three parse results, which I'll name in the form of a new data type.

data ParseResult = Complete String -- remaining text
  | Incomplete [Char] -- remaining closing chars
  | Corrupted [Char] String -- remaining closing chars, remaining text
  deriving (Eq, Ord, Show)

The five cases are found with the parseChunk function.

parseChunk :: [Char] -> String -> ParseResult
parseChunk [] remaining = Complete remaining
parseChunk stack [] = Incomplete stack
parseChunk (closer:stack) (next:remaining)
  | next == closer = parseChunk stack remaining -- expected closing character
  | otherwise = case M.lookup next closingChars of 
          -- next is a new opening character
          Just nextCloser -> parseChunk (nextCloser:closer:stack) remaining
          -- wrong character
          Nothing -> Corrupted (closer:stack) (next:remaining)

I also have the closingChars Map to tie opening and closing characters together. Only valid opening characters are keys in the map, so a successful lookup shows if the character is starting a new chunk.

closingChars :: M.Map Char Char
closingChars = M.fromList
  [ ('(', ')')
  , ('[', ']')
  , ('{', '}')
  , ('<', '>')
  ]

The next thing to consider is that a line may contain more than one chunk at the top level (even though there were none in my input). That requires a parseLine function and a parseChunk0 function to start the parsing of a chunk (parsing a chunk starts with an empty stack, but I don't want that to trigger immediately calling the empty chunk complete and therefore not consuming any input).

parseLine :: String -> ParseResult
parseLine [] = Complete ""
parseLine command = case chunk of
        Complete remaining -> parseLine remaining
        _ -> chunk
  where chunk = parseChunk0 command

parseChunk0 :: String -> ParseResult
parseChunk0 [] = Complete ""
parseChunk0 (next:remaining) = case M.lookup next closingChars of
  Just nextCloser -> parseChunk [nextCloser] remaining
  Nothing -> Corrupted [] (next:remaining)

A conscientious handling of the input means that I now have everything needed to answer both puzzle parts. I parse each line, filter the corrupt or incomplete lines depending,  and calculate the scores. If you want those details, look at the code.

Code

You can get the code from my locally-hosed Git repo, or from Gitlab.