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   -- if currentIP `S.member` visited
  51   -- then Looped (machineAcc machine)
  52   -- else if currentIP == programSize
  53   --      then Terminated (machineAcc machine)
  54   --      else if currentIP > programSize
  55   --           then OutOfBounds (machineAcc machine) currentIP
  56   --           else executeMany visited' machine'
  57   | currentIP `S.member` visited = Looped (machineAcc machine)
  58   | currentIP == programSize     = Terminated (machineAcc machine)
  59   | currentIP > programSize      = OutOfBounds (machineAcc machine) currentIP
  60   | otherwise                    = executeMany visited' machine'
  61   where machine' = executeStep machine
  62         currentIP = machineIP machine
  63         visited' = S.insert currentIP visited
  64         programSize = V.length $ machineProgram machine
  65
  66
  67 executeStep m = execute ((machineProgram m)!(machineIP m)) m
  68
  69 execute (Acc n) m = m { machineIP = machineIP m + 1
  70                       , machineAcc = machineAcc m + n
  71                       }
  72 execute (Jmp n) m = m { machineIP = machineIP m + n }
  73 execute (Nop n) m = m { machineIP = machineIP m + 1 }
  74
  75
  76 altPrograms program = map (mutateProgram program) [0..(V.length program - 1)]
  77
  78 mutateProgram program i = go (program!i)
  79   where go (Nop n) = program // [(i, Jmp n)]
  80         go (Jmp n) = program // [(i, Nop n)]
  81         go _ = program
  82
  83 -- -- Parse the input file
  84
  85
  86 instructionP = accP <|> jmpP <|> nopP
  87
  88 accP = Acc <$> ("acc " *> signed decimal)
  89 jmpP = Jmp <$> ("jmp " *> signed decimal)
  90 nopP = Nop <$> ("nop " *> signed decimal)
  91
  92 programP = V.fromList <$> sepBy instructionP endOfLine
  93
  94 successfulParse :: Text -> Program
  95 successfulParse input =
  96   case parseOnly programP input of
  97     Left  _err -> V.empty -- TIO.putStr $ T.pack $ parseErrorPretty err
  98     Right program -> program