Finally done day 24
[advent-of-code-19.git] / 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