9 "{-# LANGUAGE NegativeLiterals #-}\n",
10 "{-# LANGUAGE FlexibleContexts #-}\n",
11 "{-# LANGUAGE OverloadedStrings #-}\n",
12 "{-# LANGUAGE TypeFamilies #-}"
21 "import Prelude hiding ((++))\n",
22 "import Data.Text (Text)\n",
23 "import qualified Data.Text as T\n",
24 "import qualified Data.Text.IO as TIO\n",
26 "import Text.Megaparsec hiding (State)\n",
27 "import qualified Text.Megaparsec.Lexer as L\n",
28 "import Text.Megaparsec.Text (Parser)\n",
29 "import qualified Control.Applicative as CA\n",
31 "import Control.Monad.State.Lazy\n",
32 "import Control.Monad.Reader\n",
34 "import Data.Vector.Unboxed ((!), (++), (//))\n",
35 "import qualified Data.Vector.Unboxed as V\n",
37 "import qualified Data.IntMap as M"
46 "data Step = Spin Int\n",
47 " | Exchange Int Int\n",
48 " | Partner Char Char\n",
49 " deriving (Show, Eq)\n",
51 "type Dancers = V.Vector Char\n",
53 "type DanceHistory = M.IntMap Dancers\n",
55 "type HistoryRecorder = ReaderT [Step] (State DanceHistory) DanceHistory"
66 "\"abcdefghijklmnop\""
70 "output_type": "display_data"
84 "sc = L.space (skipSome spaceChar) CA.empty CA.empty\n",
86 "lexeme = L.lexeme sc\n",
88 "int :: Parser Int\n",
89 "int = read <$> some digitChar\n",
91 "symb = L.symbol sc\n",
93 "dancer = oneOf ['a'..'p']\n",
95 "stepsP = stepP `sepBy` comma\n",
98 "stepP = (try spinP) <|> (try exchangeP) <|> partnerP\n",
100 "spinP = Spin <$> (symb \"s\" *> int)\n",
101 "exchangeP = Exchange <$> (symb \"x\" *> int) <*> (symb \"/\" *> int)\n",
102 "partnerP = Partner <$> (symb \"p\" *> dancer) <*> (symb \"/\" *> dancer)\n",
104 "successfulParse :: Text -> [Step]\n",
105 "successfulParse input = \n",
106 " case parse stepsP \"input\" input of\n",
107 " Left err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err\n",
108 " Right steps -> steps"
113 "execution_count": 6,
119 "[Partner 'o' 'k',Exchange 4 0,Spin 12,Exchange 7 6]"
123 "output_type": "display_data"
127 "successfulParse $ T.pack \"po/k,x4/0,s12,x7/6\""
132 "execution_count": 7,
136 "startingDancers :: Dancers\n",
137 "startingDancers = V.fromList ['a'..'p'] "
142 "execution_count": 8,
148 "\"abcdefghijklmnop\""
152 "output_type": "display_data"
161 "execution_count": 9,
165 "spin :: Int -> Dancers -> Dancers\n",
166 "spin n dancers = back ++ front\n",
167 " where (front, back) = V.splitAt n' dancers\n",
168 " n' = V.length dancers - n"
173 "execution_count": 10,
179 "\"nopabcdefghijklm\""
183 "output_type": "display_data"
187 "spin 3 startingDancers"
192 "execution_count": 11,
196 "exchange :: Int -> Int -> Dancers -> Dancers\n",
197 "exchange a b dancers = dancers // [(a, dancers!b), (b, dancers!a)]"
202 "execution_count": 12,
208 "\"aocdefghijklmnbp\""
212 "output_type": "display_data"
216 "exchange 1 14 startingDancers"
221 "execution_count": 13,
225 "partner :: Char -> Char -> Dancers -> Dancers\n",
226 "partner a b dancers = exchange a' b' dancers\n",
227 " where a' = V.head $ V.elemIndices a dancers\n",
228 " b' = V.head $ V.elemIndices b dancers"
233 "execution_count": 14,
239 "\"abkdefghijclmnop\""
243 "output_type": "display_data"
247 "partner 'c' 'k' startingDancers"
252 "execution_count": 15,
256 "runDance :: [Step] -> State Dancers Dancers\n",
257 "runDance [] = do dancers <- get\n",
259 "runDance (step:steps) = \n",
260 " do dancers <- get\n",
261 " let dancers' = case step of\n",
262 " Spin n -> spin n dancers\n",
263 " Exchange a b -> exchange a b dancers\n",
264 " Partner a b -> partner a b dancers\n",
272 "execution_count": 16,
276 "part1 :: [Step] -> Dancers\n",
277 "part1 instrs = evalState (runDance instrs) startingDancers"
282 "execution_count": 17,
288 " text <- TIO.readFile \"../../data/advent16.txt\"\n",
289 " let instrs = successfulParse text\n",
290 " print $ part1 instrs\n",
291 "-- print $ part2 instrs"
296 "execution_count": 18,
302 "\"giadhmkpcnbfjelo\""
306 "output_type": "display_data"
315 "execution_count": 47,
319 "emptyHistory :: DanceHistory\n",
320 "emptyHistory = M.singleton 0 startingDancers\n",
321 "-- emptyHistory = M.empty"
326 "execution_count": 52,
330 "recordDance :: Dancers -> HistoryRecorder\n",
331 "recordDance dancers = \n",
335 " let dancers' = evalState (runDance instrs) dancers\n",
336 " if dancers' == startingDancers && (not (history == emptyHistory))\n",
337 " then return history\n",
339 "-- instrs <- ask\n",
340 "-- let dancers' = evalState (runDance instrs) dancers\n",
341 " let history' = M.insert (M.size history) dancers' history\n",
343 " recordDance dancers'"
348 "execution_count": 63,
352 "part2 instrs = (M.!) history (1000000000 `rem` M.size history)\n",
353 " where history = evalState (runReaderT (recordDance startingDancers) instrs) emptyHistory"
358 "execution_count": 64,
364 " text <- TIO.readFile \"../../data/advent16.txt\"\n",
365 " let instrs = successfulParse text\n",
366 " print $ part1 instrs\n",
367 " print $ part2 instrs"
372 "execution_count": 65,
378 "\"giadhmkpcnbfjelo\"\n",
379 "\"njfgilbkcoemhpad\""
383 "output_type": "display_data"
392 "execution_count": null,
400 "display_name": "Haskell",
401 "language": "haskell",
405 "codemirror_mode": "ihaskell",
406 "file_extension": ".hs",