blob: 654699029b85562bb7ace60f7808e057b6cb7087 (
plain)
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
|
module Main where
import Data.Set (Set)
import qualified Data.Set as Set
import Data.Map (Map)
import qualified Data.Map as Map
import Utils
type Op = (String, Int)
parseLine :: [String] -> Op
parseLine [s, j] = (s, read (dropWhile (== '+') j))
run :: Int -> Int -> Set Int -> Map Int Op -> Int
run acc pc visited operations = if Set.member pc visited then acc else handleCase
where visited' = Set.insert pc visited
handleCase =
case Map.lookup pc operations of
Just ("acc", v) -> run (acc + v) (pc + 1) visited' operations
Just ("nop", _) -> run acc (pc + 1) visited' operations
Just ("jmp", j) -> run acc (pc + j) visited' operations
_ -> acc
doesEnd :: Int -> Int -> Set Int -> Map Int Op -> Bool
doesEnd acc pc visited operations = not (Set.member pc visited) && handleCase
where visited' = Set.insert pc visited
handleCase =
case Map.lookup pc operations of
Just ("acc", v) -> doesEnd (acc + v) (pc + 1) visited' operations
Just ("nop", _) -> doesEnd acc (pc + 1) visited' operations
Just ("jmp", j) -> doesEnd acc (pc + j) visited' operations
_ -> True -- pc has crossed the end!
genAll :: [Op] -> [[Op]]
genAll [] = []
genAll (n@("nop",v):rest) = (("jmp",v):rest) : map (n:) (genAll rest)
genAll (j@("jmp",v):rest) = (("nop",v):rest) : map (j:) (genAll rest)
genAll (acc:rest) = map (acc:) $ genAll rest
main :: IO ()
main = do
n <- map (parseLine . words) . lines <$> readFile "input/08"
let solve1 = run 0 0 mempty . Map.fromList . zip [0..]
print $ solve1 n
print $ solve1 $ head $ filter (doesEnd 0 0 mempty . Map.fromList . zip [0..]) $ genAll n
|
