advent08/src/advent08.hs

   1 -- import Debug.Trace
   2
   3 import Data.Text (Text)
   4 import qualified Data.Text as T
   5 import qualified Data.Text.IO as TIO
   6
   7 import Data.Attoparsec.Text
   8 -- import Data.Attoparsec.Combinator
   9 import Control.Applicative
  10
  11 import qualified Data.Set as S
  12 import qualified Data.Vector as V
  13 import Data.Vector ((!), (//))
  14
  15 data Instruction = Acc Int | Jmp Int | Nop Int
  16   deriving (Show, Eq)
  17
  18 type Program = V.Vector Instruction
  19
  20 data Machine = Machine
  21   { machineProgram :: Program
  22   , machineIP :: Int
  23   , machineAcc :: Int
  24   }
  25
  26 data MachineResult = Looped Int | Terminated Int | OutOfBounds Int Int
  27   deriving (Show, Eq)
  28
  29
  30 main :: IO ()
  31 main =
  32   do  text <- TIO.readFile "data/advent08.txt"
  33       let program = successfulParse text
  34       -- print program
  35       let machine = Machine program 0 0
  36       print $ part1 machine
  37       print $ part2 program
  38
  39 part1 machine = executeMany S.empty machine
  40
  41 part2 program = filter terminates $ map runProgram programs
  42   where programs = altPrograms program
  43         runProgram p = executeMany S.empty (Machine p 0 0)
  44         terminates (Terminated _) = True
  45         terminates (OutOfBounds _ _) = True
  46         terminates _ = False
  47
  48
  49 executeMany visited machine
  50   | currentIP `S.member` visited = Looped (machineAcc machine)
  51   | currentIP == programSize     = Terminated (machineAcc machine)
  52   | currentIP > programSize      = OutOfBounds (machineAcc machine) currentIP
  53   | otherwise                    = executeMany visited' machine'
  54   where machine' = executeStep machine
  55         currentIP = machineIP machine
  56         visited' = S.insert currentIP visited
  57         programSize = V.length $ machineProgram machine
  58
  59
  60 executeStep m = execute ((machineProgram m)!(machineIP m)) m
  61
  62 execute (Acc n) m = m { machineIP = machineIP m + 1
  63                       , machineAcc = machineAcc m + n
  64                       }
  65 execute (Jmp n) m = m { machineIP = machineIP m + n }
  66 execute (Nop n) m = m { machineIP = machineIP m + 1 }
  67
  68
  69 altPrograms program = map (mutateProgram program) [0..(V.length program - 1)]
  70
  71 mutateProgram program i = go (program!i)
  72   where go (Nop n) = program // [(i, Jmp n)]
  73         go (Jmp n) = program // [(i, Nop n)]
  74         go _ = program
  75
  76 -- -- Parse the input file
  77
  78
  79 instructionP = accP <|> jmpP <|> nopP
  80
  81 accP = Acc <$> ("acc " *> signed decimal)
  82 jmpP = Jmp <$> ("jmp " *> signed decimal)
  83 nopP = Nop <$> ("nop " *> signed decimal)
  84
  85 programP = V.fromList <$> sepBy instructionP endOfLine
  86
  87 successfulParse :: Text -> Program
  88 successfulParse input =
  89   case parseOnly programP input of
  90     Left  _err -> V.empty -- TIO.putStr $ T.pack $ parseErrorPretty err
  91     Right program -> program