Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
Part 1
Flashbacks to AoC 2019, anyone? Day 8 asks us to write an emulator and execute a program. The CPU in this problem seems simpler than 2019's, though (for now).
import D8input
-- input :: [(String, String)]
import qualified Data.Maybe as Maybe
import qualified Data.Set as Set
import qualified Data.Map.Strict as Map
-- Maps PC to the (op, arg) pair.
type Program = Map.Map Int (String, String)
-- Holds current PC and ACC values.
type ProgramState = (Int, Int)
getAccAtRepeat :: Program -> ProgramState -> Set.Set Int -> Maybe Int
getAccAtRepeat prog (pc, acc) visited
| Set.member pc visited = Just acc
| otherwise =
let newVisited = Set.union visited (Set.singleton pc)
in case Map.lookup pc prog of
Nothing -> Nothing
Just (op, arg) ->
case op of
"nop" -> getAccAtRepeat prog (pc + 1, acc) newVisited
"acc" -> getAccAtRepeat prog (pc + 1, acc + (read arg)) newVisited
"jmp" -> getAccAtRepeat prog (pc + (read arg), acc) newVisited
solve :: Int
solve = Maybe.fromJust $ getAccAtRepeat (Map.fromList $ zip [0..] input) (0, 0) Set.empty
main :: IO ()
main = print $ solve
We express our program as a map of Int to (String, String), intended to represent program counter (PC) mapped to (command, argument). As we execute our program, we store the current PC and the accumulator (ACC) value in an (Int, Int).
getAccAtRepeat is the function that runs through the program and detects the halting condition. It takes the program with the current program state, as well as a set of PCs that have already been visited. If we ever attempt to run a PC that we've seen before, we can halt and return the ACC from the program state. Otherwise, we look up the next instruction and execute it by modifying program state accordingly and then continuing the program via recursive call, making sure to add the current PC to the set of visited PC's.
getAccAtRepeat returns a Maybe Int in preparation for detecting ill-formed programs. It allows us to more elegantly handle the Nothing case of the map lookup, but other than that, it's not really used in part 1 since the input is guaranteed not to run out of bounds. Returning a Maybe will become useful very soon though.
Part 2
There are two things we need to do to extend our solution to handle Part 2. The first is to handle the different termination condition. This is done by passing an additional "terminating PC" and terminating the recursion when the PC matches. Moreover, invalid programs (i.e., programs that run a single PC more than once) are now signaled by returning Nothing.
getAccAtTerminate :: Program -> ProgramState -> Int -> Set.Set Int -> Maybe Int
getAccAtTerminate prog (pc, acc) end visited
| pc == end = Just acc
| Set.member pc visited = Nothing
| otherwise =
let newVisited = Set.union visited (Set.singleton pc)
in case Map.lookup pc prog of
Nothing -> Nothing
Just (op, arg) ->
case op of
"nop" -> getAccAtTerminate prog (pc + 1, acc) end newVisited
"acc" -> getAccAtTerminate prog (pc + 1, acc + (read arg)) end newVisited
"jmp" -> getAccAtTerminate prog (pc + (read arg), acc) end newVisited
The next step is to figure out how to make modifications to the program and then iterate over all resulting programs to find the one that properly terminates.
modifyProgram :: Program -> Int -> Maybe Program
modifyProgram prog pc =
case Map.lookup pc prog of
Nothing -> Nothing
Just (op, arg) ->
case op of
"acc" -> Nothing
"nop" -> Just $ Map.insert pc ("jmp", arg) prog
"jmp" -> Just $ Map.insert pc ("nop", arg) prog
tryChange :: Program -> Int -> Maybe Int
tryChange prog pcToChange = do
l <- Just (length prog)
newProg <- modifyProgram prog pcToChange
result <- getAccAtTerminate newProg (0, 0) l Set.empty
return result
solve :: Int
solve =
let prog = Map.fromList $ zip [0..] input
in head $ Maybe.catMaybes $ List.map (tryChange prog) [0..]
main :: IO ()
main = print $ solve
modifyProgram is the function that makes the prescribed modification to the program at the specified PC. This is accomplished by using insert to replace the jmp and nop instructions. Again, we do not expect to ever call this with an invalid PC, so we never expect the lookup to return Nothing, but returning a Maybe Program ourselves makes this function easier to use in tryChange below.
tryChange is a function that takes the original program and a candidate PC to be modified. It returns Nothing if the change was not the one we were looking for (i.e., the program still repeats a PC). It returns the ACC value at termination if our change successfully allowed the program to run to completion. I believe this is also the first instance in this blog series of using do notation.
I'm nowhere near qualified enough to attempt to explain monads and do notation in general here. In this case, since we are dealing with the Maybe monad (seen from the fact that tryChange returns a Maybe Int), we can view tryChange as follows. tryChange is effectively a series of statements executed in order. The right side of each statement must yield a Maybe (which is why we cannot just write l <- length prog, but needed to wrap it with Just). If any of them evaluate to Nothing, the result of the entire tryChange is Nothing. Otherwise, we can return the final result. Once that is understood, the implementation of tryChange is easy to understand - it just chains together the functions we've written so far.
The final step, implemented in solve, is to tryChange on the program for all PCs in the program. We know from the guarantees of the problem that this will result in a list of mostly Nothing (corresponding to the changes that left the program still invalid), with one element that is a Just Int (corresponding to ACC value resulting from the one change that let the program run to completion). The neat catMaybes function will convert that into a list containing that one element with the Maybe stripped off. head extracts that element, providing us with our answer.
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25