Day 10 - Instruction Processing

Dec 10

All 2022 Problems

Problem Overview

Today we're processing some very simple machine instructions. The only instructions we have are "noop" (which does nothing) and "addx", which adds (or subtracts) an integer to a single register value.

In the first part, we'll deal with the "signal strength", which multiplies the cycle number by the current register value at certain cycles.

In the second part, we'll actually render a message using the register value in a very interesting way! The full instructions for this are a bit intricate. But essentially, depending on the register value and the cycle number, we either render a light bit # or a dark bit ., and then rearrange these bits in a 40-column by 6-row grid.

Solution Approach and Insights

The main thing here is determining how to handle the cycle updates. The stateful nature of the problem makes it a bit tricky - off-by-one issues are lurking everywhere! But if the cycle update is correct, the rest of the problem is pretty simple.

Relevant Utilities

In this problem, we're parsing integers, but they can be positive or negative. So here's a utility parser that can handle that:

parseSignedInteger :: (Monad m) => ParsecT Void Text m Int
parseSignedInteger = parsePositiveNumber <|> parseNegativeNumber

parseNegativeNumber :: (Monad m) => ParsecT Void Text m Int
parseNegativeNumber = do
  char '-'
  ((-1) *) <$> parsePositiveNumber

parsePositiveNumber :: (Monad m) => ParsecT Void Text m Int
parsePositiveNumber = read <$> some digitChar

Parsing the Input

Now, let's parse our problem input. Here's a small sample:

noop
addx 3
addx -5

We have "no-op" commands and "add" commands with a number. We start with an Instruction type to represent these:

data Instruction =
  Noop |
  Addx Int
  deriving (Show)

type InputType = [LineType]
type LineType = Instruction

And parsing each line is a simple alternative.

parseLine :: (MonadLogger m) => ParsecT Void Text m LineType
parseLine = (string "noop" >> return Noop) <|> do
  string "addx "
  Addx <$> parseSignedInteger

parseInput :: (MonadLogger m) => ParsecT Void Text m InputType
parseInput = sepEndBy1 parseLine eol

Getting the Solution

This will be another folding solution, where we process a single instruction at a time. So we need a stateful type to capture all the information we need about the problem. We'll track the following fields:

The cycle number
The register value
The accumulated signal strength - this is our answer for part 1.
The accumulated render string - this will give us the answer for part 2.

Here's what the type looks like, along with its initial value.

initialMachineState :: MachineState
initialMachineState = MachineState 1 1 0 ""

data MachineState = MachineState
  { cycleNum :: Int
  , registerValue :: Int
  , accumSignalStrength :: Int
  , renderedString :: String
  }

So the question becomes…how do we process a single instruction?

processInstruction :: (MonadLogger m) => MachineState -> Instruction -> m MachineState

This is a little tricky because the no-op instruction only takes one cycle, while the add instruction takes two cycles. And it's only at the end of those two cycles that the register value is updated. So the key to this is another helper that bumps the cycle values without worrying about adding.

bumpCycle :: (MonadLogger m) => MachineState -> m MachineState

Here's how we apply this function within processInstruction:

processInstruction :: (MonadLogger m) => MachineState -> Instruction -> m MachineState
processInstruction ms Noop = bumpCycle ms
processInstruction ms0 (Addx i) = do
  ms1 <- bumpCycle ms0
  ms2 <- bumpCycle ms1
  return $ ms2 { registerValue = registerValue ms0 + i}

A no-op does nothing except bump the cycle. For adding, we bump twice and then update the register value using the instruction.

So what actually happens when we bump the cycle? Well most obviously, we increment the cycle number and keep the register value the same.

bumpCycle :: (MonadLogger m) => MachineState -> m MachineState
bumpCycle (MachineState cNum regVal accumSignal render) = do
  ...
  return $ MachineState (cNum + 1) regVal (...) (...)

So what happens with the other values? First let's think about the signal strength. At certain cycles (20, 60, 100, 140, 180, 220), we multiply the register value by the cycle number, and add this to the previous signal strength value.

bumpCycle :: (MonadLogger m) => MachineState -> m MachineState
bumpCycle (MachineState cNum regVal accumSignal render) = do
  let maybeAccum = if HS.member cNum signalCycles
        then regVal * cNum
        else 0
  ...
  return $ MachineState (cNum + 1) regVal (accumSignal + maybeAccum) (...)

signalCycles :: HS.HashSet Int
signalCycles = HS.fromList [20, 60, 100, 140, 180, 220]

And now for the second part, we need to render the right character. First, we need the "column" for the cycle number. We subtract 1 and mod by 40. Then we want to check if that value is equal to the register value (+/- 1). If it is, we'll use a "light" bit #. Otherwise, it's a "dark" bit .. And this completes our function!

bumpCycle :: (MonadLogger m) => MachineState -> m MachineState
bumpCycle (MachineState cNum regVal accumSignal render) = do
  let maybeAccum = if HS.member cNum signalCycles
        then regVal * cNum
        else 0
  let newChar = if ((cNum - 1) `mod` 40) `elem` [regVal - 1, regVal, regVal + 1] then '#' else '.'
  return $ MachineState (cNum + 1) regVal (accumSignal + maybeAccum) (newChar : render)

Answering the Question

For the "easy" part, we fold the instructions and collect the accumulated signal strength:

type EasySolutionType = Int

processInputEasy :: (MonadLogger m) => InputType -> m EasySolutionType
processInputEasy inputs = accumSignalStrength <$> foldM processInstruction initialMachineState inputs

For the "hard" part, we instead reverse the rendered string.

type HardSolutionType = String

processInputHard :: (MonadLogger m) => InputType -> m HardSolutionType
processInputHard inputs = reverse . renderedString <$> foldM processInstruction initialMachineState inputs

And now we're basically done! The only wrinkle is that you'll want to print the final string properly in order to see what the letters are! You'll want to use chunksOf 40.

solveEasy :: FilePath -> IO (Maybe Int)
solveEasy fp = runStdoutLoggingT $ do
  input <- parseFile parseInput fp
  Just <$> processInputEasy input

solveHard :: FilePath -> IO (Maybe String)
solveHard fp = runStdoutLoggingT $ do
  input <- parseFile parseInput fp
  result <- processInputHard input
  mapM_ (logErrorN . pack) (chunksOf 40 result)
  return $ Just result

And that's all!

Video

YouTube Link

Advent of Code

James Bowen