1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
import Control.Monad
import Data.Char
import Data.Maybe
import qualified Data.Map.Strict as Map
data Ref = Reg Char | Num Int
deriving Show
data Ins = Set Char Ref | Add Char Ref | Mul Char Ref | Mod Char Ref | Snd Ref | Rcv Char | Jgz Ref Ref
deriving Show
parseRef :: String -> Ref
parseRef str = if all (\c -> isDigit c || c == '-') str then Num (read str) else Reg (head str)
parse :: String -> Ins
parse str = case words str of
["set", [d], s] -> Set d (parseRef s)
["add", [d], s] -> Add d (parseRef s)
["mul", [d], s] -> Mul d (parseRef s)
["mod", [d], s] -> Mod d (parseRef s)
["snd", r] -> Snd (parseRef r)
["rcv", [d]] -> Rcv d
["jgz", c, t] -> Jgz (parseRef c) (parseRef t)
_ -> undefined
get :: Ref -> Map.Map Char Int -> Int
get (Num i) _ = i
get (Reg c) vmap = fromMaybe 0 (Map.lookup c vmap)
exec1 :: [Ins] -> Int
exec1 inss' = go inss' 0 Map.empty 0
where
go :: [Ins] -> Int -> Map.Map Char Int -> Int -> Int
go inss idx vmap snd
| idx < 0 = undefined
| idx >= length inss = undefined
| otherwise = case inss !! idx of
Set d ref -> go inss (idx+1) (Map.insert d (get ref vmap) vmap) snd
Add d ref -> go inss (idx+1) (Map.insert d (get (Reg d) vmap + get ref vmap) vmap) snd
Mul d ref -> go inss (idx+1) (Map.insert d (get (Reg d) vmap * get ref vmap) vmap) snd
Mod d ref -> go inss (idx+1) (Map.insert d (get (Reg d) vmap `mod` get ref vmap) vmap) snd
Snd ref -> go inss (idx+1) vmap (get ref vmap)
Rcv d -> if get (Reg d) vmap == 0 then go inss (idx+1) vmap snd else snd
Jgz cd tg -> go inss (idx + if get cd vmap > 0 then get tg vmap else 1) vmap snd
data State = State [Ins] Int (Map.Map Char Int) [Int]
deriving Show
makeState :: [Ins] -> Int -> State
makeState inss pid = State inss 0 (Map.fromList [('p', pid)]) []
supplyInput :: State -> [Int] -> State
supplyInput (State inss idx vmap inp) input = State inss idx vmap (inp ++ input)
exec2 :: State -> (State, [Int])
exec2 state@(State inss idx vmap inp)
| idx < 0 = (state, [])
| idx >= length inss = (state, [])
| otherwise = case inss !! idx of
Set d ref -> exec2 $ State inss (idx+1) (Map.insert d (get ref vmap) vmap) inp
Add d ref -> exec2 $ State inss (idx+1) (Map.insert d (get (Reg d) vmap + get ref vmap) vmap) inp
Mul d ref -> exec2 $ State inss (idx+1) (Map.insert d (get (Reg d) vmap * get ref vmap) vmap) inp
Mod d ref -> exec2 $ State inss (idx+1) (Map.insert d (get (Reg d) vmap `mod` get ref vmap) vmap) inp
Snd ref -> fmap (get ref vmap :) $ exec2 $ State inss (idx+1) vmap inp
Rcv d -> case inp of
[] -> (state, [])
x:xs -> exec2 $ State inss (idx+1) (Map.insert d x vmap) xs
Jgz cd tg -> exec2 $ State inss (idx + if get cd vmap > 0 then get tg vmap else 1) vmap inp
parallel :: State -> State -> Int
parallel state0 state1 =
let (state0', out0) = exec2 state0
(state1', out1) = exec2 (supplyInput state1 out0)
state0'' = supplyInput state0' out1
in if null out0 && null out1
then 0
else length out1 + parallel state0'' state1'
main :: IO ()
main = do
input <- liftM (map parse . lines) (readFile "18.in")
print (exec1 input)
print $ parallel (makeState input 0) (makeState input 1)
|
