advent07/src/advent07.hs

   1 import Debug.Trace
   2
   3 import Intcode
   4
   5 import qualified Data.Text.IO as TIO
   6
   7 import qualified Data.IntMap.Strict as M
   8 import Data.IntMap.Strict ((!))
   9 import Data.List
  10 import Data.Function (on)
  11
  12
  13 data EncapsulatedMacine = EncapsulatedMacine
  14     { _machine :: Machine
  15     , _executionState :: ExecutionState
  16     , _initialInput :: [Integer]
  17     , _currentInput :: [Integer]
  18     , _machineOutput :: [Integer]
  19     } deriving (Show, Eq)
  20
  21 type Pipeline = M.IntMap EncapsulatedMacine
  22
  23
  24 main :: IO ()
  25 main = do
  26         text <- TIO.readFile "data/advent07.txt"
  27         let mem = parseMachineMemory text
  28         print $ part1 mem
  29         print $ part2 mem
  30
  31
  32 part1 mem = maximum outputs
  33     where inputs = permutations [0..4]
  34           outputs = map (chainMachines mem) inputs
  35
  36 chainMachines mem settings = foldl' (chainMachine mem) 0 settings
  37
  38 chainMachine mem prevOutput setting = last output
  39     where (_, _, output) = runProgram [setting, prevOutput] mem
  40
  41
  42 part2 mem = maximum outputs
  43     where   inputs = permutations [5..9]
  44             pipelines = map (buildPipeline mem) inputs
  45             outputs = map runPipeline pipelines
  46
  47 buildPipeline :: [Integer] -> [Integer] -> Pipeline
  48 buildPipeline mem input = M.insert 0 machine0' pipeline
  49     where pipeline = M.fromList $ zip [0..] $ map (encapsulate mem) input
  50           machine0 = pipeline!0
  51           machine0' = machine0 { _initialInput = (_initialInput machine0) ++ [0]}
  52
  53
  54 encapsulate :: [Integer] -> Integer -> EncapsulatedMacine
  55 encapsulate mem input = EncapsulatedMacine
  56     { _machine = makeMachine mem
  57     , _executionState = Runnable
  58     , _initialInput = [input]
  59     , _machineOutput = []
  60     , _currentInput = [input]
  61     }
  62
  63
  64 runPipeline :: Pipeline -> Integer
  65 -- runPipeline pipeline | trace (pipelineTrace pipeline) False = undefined
  66 runPipeline pipeline
  67     | finished pipeline = last $ _machineOutput $ snd $ M.findMax pipeline
  68     | otherwise = runPipeline pipeline''
  69     where   (indexToRun, machineToRun) = M.findMin $ runnableMachines pipeline
  70             feedsIntoIndex = (indexToRun + 1) `mod` (M.size pipeline)
  71             feedsIntoMachine = pipeline!feedsIntoIndex
  72             fimi = _initialInput feedsIntoMachine
  73             machine' = runEncapsulatedMachine machineToRun
  74             fullOutput = _machineOutput machine'
  75             feedsIntoState = case (_executionState feedsIntoMachine) of
  76                                   Blocked -> Runnable
  77                                   Terminated -> Terminated
  78                                   Runnable -> Runnable
  79             feedsIntoMachine' = feedsIntoMachine {_executionState = feedsIntoState, _currentInput = fimi ++ fullOutput}
  80             pipeline' = M.insert indexToRun machine' pipeline
  81             pipeline'' = M.insert feedsIntoIndex feedsIntoMachine' pipeline'
  82
  83
  84
  85 pipelineTrace :: Pipeline -> String
  86 pipelineTrace pipeline = show $ M.toList $ M.map emTrace pipeline
  87
  88 emTrace e = intercalate " ; " terms
  89     where terms = [ show $ _executionState e
  90                   , "in"
  91                   , show $ _currentInput e
  92                   , "out"
  93                   , show $ _machineOutput e
  94                   ]
  95
  96 finished :: Pipeline -> Bool
  97 finished = M.null . runnableMachines
  98
  99 runnableMachines :: Pipeline -> Pipeline
 100 runnableMachines = M.filter (\e -> _executionState e == Runnable)
 101
 102 runEncapsulatedMachine :: EncapsulatedMacine -> EncapsulatedMacine
 103 runEncapsulatedMachine e = e { _machine = machine'
 104                              , _executionState = halted
 105                              , _machineOutput = (_machineOutput e) ++ output
 106                              }
 107     where   machine = _machine e
 108             input = _currentInput e
 109             (halted, machine', output) = runMachine input machine