Discussion on: Advent of Code 2020 Solution Megathread - Day 8: Handheld Halting

View post

hello! Sorry did not post yesterday as was visiting my mum in hospital, but completed day 7 this morning, which I have to say was a bit messy!

Day 8 on the other hand seems a lot of fun and I'm remembering more Haskel (and cateory theory) each new day. It's been a while :-) Anywhy, below is today's soloution(s). I did give into using Parser combinators as it just seemed simplier, but other than that it is all fairly standard.

-- anamorphism for lists, used to generate our program traces and modifications
unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
unfoldr f b = case f b of
                Just (a, b') -> a : unfoldr f b'
                Nothing -> []

-- our 3 known opcodes
data Op = NOp Int | Acc Int | Jmp Int
    deriving (Show, Eq)

type Program = [Op]
type PC = Int

-- Simple parser
lexer = Token.makeTokenParser (TP.emptyDef { Token.reservedNames   = [ "nop", "acc", "jmp" ] })
reserved   = Token.reserved   lexer -- op code
integer    = Token.integer    lexer -- integer
whiteSpace = Token.whiteSpace lexer -- whitespace

-- parse individual opcode
pOpcode :: TP.Parser (Int -> Op)
pOpcode = (reserved "nop" >> return NOp) <|> (reserved "acc" >> return Acc) <|> (reserved "jmp" >> return Jmp)

-- parse an individual instruction
pInstruction :: TP.Parser Op
pInstruction = 
    do op <- pOpcode
       whiteSpace
       op . fromIntegral <$> integer

-- parse all ops
parseOps :: String -> [Op]
parseOps = either (error . show) id . TP.parse (TP.many1 (whiteSpace >> pInstruction)) ""

-- given a PC and a set of visited PC, have we been there before?
halt :: PC -> DS.Set Int -> Bool
halt = DS.member

-- execute a single op, returning a new acc and a function to compute next PC
executeOp :: Op -> Int -> (Int, PC -> PC)
executeOp (NOp _) acc = (acc, (+1))
executeOp (Acc inc) acc = (acc+inc, (+1))
executeOp (Jmp i) acc = (acc, (+i))

-- step a single op for a given program, at PC, seen PCs, and current Acc
step :: (Program, PC, DS.Set Int, Int) -> Maybe ((Bool, Int), (Program, PC, DS.Set Int, Int))
step (ps, pc, seen, acc) 
    | pc >= length ps = Nothing
    | otherwise = let (acc', next) = executeOp (ps!!pc) acc
                      pc' = next pc
                  in Just ((halt pc' seen, acc'), (ps, pc', DS.insert pc' seen, acc') )

-- modify an op (NOP => JMP and JMP => NOP), if possible
modOp :: Op -> Maybe Op
modOp (NOp i) = Just (Jmp i)
modOp (Acc inc) = Nothing
modOp (Jmp i) = Just (NOp i)

-- generate a modified program, if possible, given a Program and PC
mods :: (Program, PC) -> Maybe (Maybe Program, (Program, PC))
mods (ps, pc) = if pc < length ps
                then Just (maybe (Nothing, (ps, pc+1)) aux (modOp (ps!!pc)))
                else Nothing
    where
        aux op = (Just (take pc ps ++ [op] ++ drop (pc+1) ps), (ps, pc+1))

-- produce all traces of a programs execution
execute :: Program -> [(Bool, Int)]
execute ps = unfoldr step (ps, 0, DS.empty, 0)

-- find acc at the point when a single op is executed twice
part1 = snd . head . dropWhile (not . fst) . execute

-- find a acc for a modified program that terminates
part2 = fromMaybe 0 . head . dropWhile (==Nothing) . map (p . execute) . 
            foldr (\a b -> maybe b (:b) a) [] . unfoldr mods . (\ps -> (ps,0))
    where
        p [(False, v)] = Just v 
        p ((True,_):_) = Nothing
        p (_:xs)       = p xs

-- run task 1 and task 2 for AOC ay 8
main = do ops <- readFile "day8_input" <&> parseOps
          print (part1 ops)
          print (part2 ops)