-
Notifications
You must be signed in to change notification settings - Fork 0
/
run.hs
78 lines (63 loc) · 1.88 KB
/
run.hs
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
{-# LANGUAGE TypeApplications #-}
import Data.Bits (xor)
import Data.Ord (comparing)
import Data.Maybe
import Data.List
import Data.Set (Set)
import qualified Data.Set as Set
type Arg = Int
data Inst = Acc Arg
| Jmp Arg
| Nop Arg
deriving (Show, Eq)
instance Read Inst where
readsPrec _ x = do
let (inst, ' ':val) = break (== ' ') x
(arg, rest) <- reads . dropWhile (== '+') $ val
let inst' = case inst of
"acc" -> Acc
"jmp" -> Jmp
"nop" -> Nop
pure (inst' arg, rest)
parseAll =
map (read @Inst)
. lines
execStep :: (Int, Int, [Inst]) -> Maybe (Int, Int, [Inst])
execStep (pc, acc, prog) =
case drop pc prog of
(Acc v:_) -> Just (pc + 1, acc + v, prog)
(Jmp v:_) -> Just (pc + v, acc, prog)
(Nop _:_) -> Just (pc + 1, acc, prog)
[] -> Nothing
exec prog = iterate (>>= execStep) $ Just (0, 0, prog)
execUntilLoop input =
let execution = mapMaybe id
. takeWhile isJust
$ exec input
in listToMaybe
. filter fst
. map (\(v, (pc, acc, _)) -> (pc `Set.member` v, acc))
$ zip (visited execution) execution
visited = scanl f Set.empty
where f pcs (pc, _, _) = Set.insert pc pcs
loops = isJust . execUntilLoop
singleMap f [] = []
singleMap f (x:xs) = (f x:xs):map (x:) (singleMap f xs)
mutate (Acc _) = Nothing
mutate (Jmp v) = Just (Nop v)
mutate (Nop v) = Just (Jmp v)
part1 = maybe undefined snd . execUntilLoop
part2 input =
let candidates = mapMaybe sequence
. singleMap (>>= mutate)
. map pure
$ input
correct = head . filter (not . loops) $ candidates
Just (_, acc, _) = last
. takeWhile isJust
$ exec correct
in acc
main = do
input <- parseAll <$> readFile "input.txt"
print (part1 input)
print (part2 input)