add initial day08 solution

3 files changed, 677 insertions, 0 deletions

diff --git a/aoc.cabal b/aoc.cabal
index 11bd93d..01cebc9 100644
--- a/aoc.cabal
+++ b/aoc.cabal
@@ -63,3 +63,9 @@ executable Day07
   build-depends:       base, aoc, containers, parsec
   default-language:    Haskell2010
   hs-source-dirs:      execs
+
+executable Day08
+  main-is:             Day08.hs
+  build-depends:       base, aoc, containers
+  default-language:    Haskell2010
+  hs-source-dirs:      execs
diff --git a/execs/Day08.hs b/execs/Day08.hs
new file mode 100644
index 0000000..7d3fce8
--- /dev/null
+++ b/execs/Day08.hs
@@ -0,0 +1,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 Set.empty . Map.fromList . zip [0..] 
+    print $ solve1 n
+    print $ solve1 $ head $ filter (doesEnd 0 0 Set.empty . Map.fromList . zip [0..]) $ genAll n
diff --git a/input/08 b/input/08
new file mode 100644
index 0000000..4d50e16
--- /dev/null
+++ b/input/08
@@ -0,0 +1,626 @@
+nop +346
+acc +44
+acc +15
+jmp +473
+acc +29
+acc -13
+jmp +525
+acc +22
+acc +13
+nop +265
+jmp +397
+jmp +39
+acc +39
+nop -1
+acc +36
+acc +25
+jmp +153
+nop +374
+jmp +27
+jmp +282
+jmp +1
+jmp +1
+jmp +15
+acc +33
+acc -3
+jmp +533
+acc +25
+acc -14
+acc -16
+jmp +245
+nop +567
+acc +7
+jmp +147
+acc +26
+acc +40
+acc -9
+jmp +295
+acc +14
+nop +388
+acc -1
+jmp -21
+nop +524
+nop +166
+nop +515
+jmp +18
+jmp +214
+acc +42
+nop -35
+acc +7
+jmp +492
+acc +14
+acc +48
+jmp +326
+acc +48
+acc -18
+acc -5
+jmp +343
+jmp +81
+acc +18
+acc +16
+acc +21
+jmp +355
+acc +48
+nop +358
+acc +49
+acc -2
+jmp +89
+acc +4
+jmp +171
+acc +6
+jmp +299
+acc -8
+jmp +150
+acc +41
+acc -9
+acc +48
+jmp +73
+jmp +523
+nop +471
+jmp +493
+acc -16
+nop +440
+acc +2
+acc +33
+jmp +117
+acc +3
+acc +34
+jmp +310
+acc +8
+jmp +197
+acc +26
+acc +47
+jmp +194
+nop +115
+jmp +259
+nop +456
+jmp +420
+nop +398
+jmp +235
+acc +44
+acc +47
+jmp +218
+jmp +1
+jmp +275
+acc +12
+jmp +434
+acc +50
+acc +10
+nop +361
+jmp +367
+acc -16
+acc +44
+jmp +96
+acc +9
+acc +38
+acc -15
+nop -31
+jmp -55
+nop +421
+acc +50
+acc +12
+jmp -64
+acc +33
+acc +25
+jmp +382
+acc +7
+jmp -22
+jmp +95
+acc +44
+acc +32
+acc +23
+jmp +1
+jmp +456
+acc +49
+jmp +15
+jmp +312
+acc +6
+jmp +216
+acc +7
+jmp +458
+jmp +465
+nop +372
+acc +35
+acc +32
+acc +13
+jmp -35
+acc +50
+nop +32
+jmp +143
+jmp +327
+acc +0
+nop -82
+nop -62
+acc +41
+jmp -81
+acc -10
+nop -106
+jmp +82
+acc +1
+acc +11
+jmp +124
+acc +25
+acc +17
+jmp -73
+nop +8
+acc +29
+acc +33
+acc +10
+jmp +123
+jmp +236
+acc +41
+jmp +370
+acc +17
+acc -13
+acc +35
+jmp -47
+nop +287
+acc +22
+jmp +38
+jmp +1
+nop -52
+nop -9
+acc +22
+jmp +253
+acc +12
+acc -18
+acc +21
+nop -69
+jmp +28
+acc +16
+jmp +392
+jmp +325
+jmp -74
+acc +34
+acc +47
+acc +41
+jmp +201
+nop +361
+acc +50
+jmp +30
+jmp -127
+nop -171
+jmp +349
+acc +11
+nop +156
+acc +1
+acc -18
+jmp +393
+acc -8
+jmp +1
+acc -17
+nop +188
+jmp +134
+acc -9
+acc -14
+jmp +206
+jmp -209
+jmp +1
+acc +49
+nop +112
+acc -4
+jmp -20
+acc +41
+jmp -145
+acc +8
+jmp +276
+acc +48
+jmp -5
+jmp -143
+acc +0
+jmp -161
+jmp +238
+acc +8
+jmp -134
+acc +34
+acc +10
+jmp +1
+nop +109
+jmp -100
+acc +41
+acc -4
+jmp -12
+acc +42
+acc +46
+acc -7
+acc +28
+jmp +85
+jmp +216
+jmp +364
+acc +0
+acc -6
+nop +331
+acc +33
+jmp +163
+acc +37
+acc +20
+acc +33
+acc +45
+jmp -159
+acc +34
+acc +10
+acc +48
+acc +10
+jmp +358
+acc -9
+jmp +276
+acc +27
+acc +45
+nop +129
+acc +32
+jmp +243
+acc +0
+acc -5
+jmp -24
+acc +44
+nop +307
+acc -18
+acc +13
+jmp +37
+acc +5
+nop -125
+nop -126
+acc -18
+jmp +186
+jmp -87
+jmp -262
+nop -20
+jmp -108
+acc +26
+acc +20
+jmp +193
+nop +185
+jmp +129
+acc +26
+jmp +122
+acc -8
+nop +143
+nop +166
+jmp -236
+acc +33
+jmp -139
+acc +38
+jmp +1
+acc +21
+acc +31
+jmp -79
+acc -13
+jmp -78
+acc +29
+jmp +160
+acc +48
+acc -8
+acc +28
+acc +15
+jmp -284
+jmp +25
+acc +24
+jmp +1
+jmp -92
+acc +22
+jmp +169
+acc -15
+acc +16
+acc +4
+jmp -85
+acc -18
+acc -19
+acc -2
+jmp -278
+acc +48
+jmp -195
+jmp -40
+jmp -110
+acc +47
+jmp -26
+acc +26
+nop -187
+acc +40
+acc +42
+jmp +167
+acc +50
+acc +36
+acc -14
+jmp -313
+nop -203
+jmp +227
+acc -15
+acc +22
+jmp -23
+acc +6
+acc +30
+acc +12
+jmp +69
+nop -212
+nop -105
+acc +12
+jmp -155
+nop +69
+acc -16
+jmp -68
+acc -18
+acc +35
+acc +34
+acc +6
+jmp -80
+acc +7
+acc +19
+acc -8
+jmp -94
+acc +12
+nop -148
+acc +33
+nop -41
+jmp -107
+acc +25
+acc +9
+nop +107
+jmp -44
+jmp +1
+jmp -254
+acc +10
+acc +0
+acc +37
+acc +33
+jmp +137
+nop +136
+jmp -225
+acc -4
+acc -17
+acc +39
+jmp -286
+jmp +150
+nop -380
+acc +34
+acc +16
+nop +146
+jmp +105
+jmp +119
+jmp -190
+acc +0
+nop +205
+nop -302
+jmp -17
+acc -4
+jmp -7
+jmp -14
+jmp -394
+acc +34
+acc -1
+acc +37
+acc -17
+jmp -312
+nop -180
+nop -139
+acc +21
+jmp -378
+acc +24
+acc +38
+jmp +129
+acc +26
+jmp +19
+acc +31
+jmp -190
+acc +29
+acc -5
+jmp +14
+nop +186
+acc +12
+acc +9
+acc -16
+jmp +9
+acc +2
+nop -382
+nop -284
+nop -377
+jmp -169
+jmp +129
+acc +49
+jmp -297
+acc +48
+acc +18
+acc +8
+jmp +170
+acc +12
+acc -4
+acc +28
+jmp -20
+acc -11
+jmp -363
+jmp +1
+acc +9
+acc +31
+jmp +31
+acc +36
+acc +42
+acc +2
+nop -131
+jmp -322
+acc +35
+acc +44
+acc +11
+acc +14
+jmp -213
+acc -16
+acc -15
+acc -5
+jmp -277
+acc -17
+jmp -252
+acc -19
+acc +31
+acc -16
+acc -5
+jmp +48
+jmp +1
+jmp -97
+acc +5
+jmp -382
+acc +26
+acc +41
+acc +31
+acc -2
+jmp -392
+acc +41
+jmp -124
+acc +45
+acc +24
+acc +10
+jmp -339
+acc +29
+acc -10
+acc -10
+acc +3
+jmp -456
+jmp -25
+acc +37
+acc +39
+acc -11
+acc -1
+jmp +106
+jmp -328
+jmp -489
+nop -111
+nop -458
+acc +31
+jmp -100
+acc -18
+jmp -258
+acc -17
+nop -46
+acc +43
+acc +45
+jmp -127
+jmp +34
+acc +33
+jmp -200
+nop -90
+acc +20
+jmp -271
+acc +41
+jmp -189
+acc -16
+nop -321
+acc +25
+acc -12
+jmp -62
+acc -1
+jmp +1
+acc +35
+acc +39
+jmp -184
+jmp -236
+nop -331
+acc +12
+jmp +78
+acc +15
+jmp -30
+acc -11
+jmp -117
+jmp -8
+jmp +9
+acc +2
+jmp -497
+acc +10
+acc +0
+acc -6
+jmp -155
+jmp -148
+jmp -95
+jmp -96
+jmp -249
+nop -277
+nop -411
+acc -13
+acc -2
+jmp -383
+acc -13
+jmp -110
+acc +13
+acc +16
+acc +5
+acc -2
+jmp -67
+acc +37
+jmp -491
+acc +35
+acc +34
+acc +32
+acc -2
+jmp -546
+acc -19
+jmp -322
+acc +48
+acc +18
+acc +35
+acc +8
+jmp -448
+acc +41
+acc -15
+acc +34
+acc +46
+jmp -50
+acc +12
+nop -184
+acc +14
+acc +38
+jmp -370
+jmp +10
+acc -14
+acc -16
+nop -259
+nop -300
+jmp -400
+acc +38
+acc +29
+acc +27
+jmp -175
+jmp -456
+acc +30
+jmp -308
+jmp -538
+jmp +1
+acc -16
+nop -127
+jmp -407
+acc +5
+jmp -57
+acc +21
+acc +3
+acc +42
+acc +43
+jmp -521
+acc -9
+acc +20
+nop -217
+jmp -15
+acc +37
+acc -12
+acc -18
+jmp +1
+jmp -465
+acc +37
+nop -577
+acc +8
+acc +43
+jmp +1