From 86c404c1f31915fb3ce41a3fc5679cdf001a41b3 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Fri, 22 Nov 2019 16:29:08 +0000 Subject: [PATCH] Day 21 mostly done --- advent-of-code.cabal | 10 ++ data/advent21.txt | 32 ++++++ problems/day20.html | 238 +++++++++++++++++++++++++++++++++++++++ src/advent21/advent21.hs | 228 +++++++++++++++++++++++++++++++++++++ 4 files changed, 508 insertions(+) create mode 100644 data/advent21.txt create mode 100644 problems/day20.html create mode 100644 src/advent21/advent21.hs diff --git a/advent-of-code.cabal b/advent-of-code.cabal index dd2f207..68d29fa 100644 --- a/advent-of-code.cabal +++ b/advent-of-code.cabal @@ -240,3 +240,13 @@ executable advent20 , text , megaparsec , linear + +executable advent21 + hs-source-dirs: src/advent21 + main-is: advent21.hs + default-language: Haskell2010 + build-depends: base >= 4.7 && < 5 + , containers + , mtl + , text + , megaparsec \ No newline at end of file diff --git a/data/advent21.txt b/data/advent21.txt new file mode 100644 index 0000000..8ae617f --- /dev/null +++ b/data/advent21.txt @@ -0,0 +1,32 @@ +#ip 3 +seti 123 0 1 +bani 1 456 1 +eqri 1 72 1 +addr 1 3 3 +seti 0 0 3 +seti 0 0 1 +bori 1 65536 2 +seti 10605201 9 1 +bani 2 255 5 +addr 1 5 1 +bani 1 16777215 1 +muli 1 65899 1 +bani 1 16777215 1 +gtir 256 2 5 +addr 5 3 3 +addi 3 1 3 +seti 27 3 3 +seti 0 3 5 +addi 5 1 4 +muli 4 256 4 +gtrr 4 2 4 +addr 4 3 3 +addi 3 1 3 +seti 25 3 3 +addi 5 1 5 +seti 17 5 3 +setr 5 5 2 +seti 7 6 3 +eqrr 1 0 5 +addr 5 3 3 +seti 5 8 3 diff --git a/problems/day20.html b/problems/day20.html new file mode 100644 index 0000000..1646a8c --- /dev/null +++ b/problems/day20.html @@ -0,0 +1,238 @@ + + + + +Day 20 - Advent of Code 2018 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 38*

   sub y{2018}

+ + + +
+

--- Day 20: A Regular Map ---

While you were learning about instruction pointers, the Elves made considerable progress. When you look up, you discover that the North Pole base construction project has completely surrounded you.

+

The area you are in is made up entirely of rooms and doors. The rooms are arranged in a grid, and rooms only connect to adjacent rooms when a door is present between them.

+

For example, drawing rooms as ., walls as #, doors as | or -, your current position as X, and where north is up, the area you're in might look like this:

+
#####
+#.|.#
+#-###
+#.|X#
+#####
+
+

You get the attention of a passing construction Elf and ask for a map. "I don't have time to draw out a map of this place - it's huge. Instead, I can give you directions to every room in the facility!" He writes down some directions on a piece of parchment and runs off. In the example above, the instructions might have been ^WNE$, a regular expression or "regex" (your puzzle input).

+

The regex matches routes (like WNE for "west, north, east") that will take you from your current room through various doors in the facility. In aggregate, the routes will take you through every door in the facility at least once; mapping out all of these routes will let you build a proper map and find your way around.

+

^ and $ are at the beginning and end of your regex; these just mean that the regex doesn't match anything outside the routes it describes. (Specifically, ^ matches the start of the route, and $ matches the end of it.) These characters will not appear elsewhere in the regex.

+

The rest of the regex matches various sequences of the characters N (north), S (south), E (east), and W (west). In the example above, ^WNE$ matches only one route, WNE, which means you can move west, then north, then east from your current position. Sequences of letters like this always match that exact route in the same order.

+

Sometimes, the route can branch. A branch is given by a list of options separated by pipes (|) and wrapped in parentheses. So, ^N(E|W)N$ contains a branch: after going north, you must choose to go either east or west before finishing your route by going north again. By tracing out the possible routes after branching, you can determine where the doors are and, therefore, where the rooms are in the facility.

+

For example, consider this regex: ^ENWWW(NEEE|SSE(EE|N))$

+

This regex begins with ENWWW, which means that from your current position, all routes must begin by moving east, north, and then west three times, in that order. After this, there is a branch. Before you consider the branch, this is what you know about the map so far, with doors you aren't sure about marked with a ?:

+
#?#?#?#?#
+?.|.|.|.?
+#?#?#?#-#
+    ?X|.?
+    #?#?#
+
+

After this point, there is (NEEE|SSE(EE|N)). This gives you exactly two options: NEEE and SSE(EE|N). By following NEEE, the map now looks like this:

+
#?#?#?#?#
+?.|.|.|.?
+#-#?#?#?#
+?.|.|.|.?
+#?#?#?#-#
+    ?X|.?
+    #?#?#
+
+

Now, only SSE(EE|N) remains. Because it is in the same parenthesized group as NEEE, it starts from the same room NEEE started in. It states that starting from that point, there exist doors which will allow you to move south twice, then east; this ends up at another branch. After that, you can either move east twice or north once. This information fills in the rest of the doors:

+
#?#?#?#?#
+?.|.|.|.?
+#-#?#?#?#
+?.|.|.|.?
+#-#?#?#-#
+?.?.?X|.?
+#-#-#?#?#
+?.|.|.|.?
+#?#?#?#?#
+
+

Once you've followed all possible routes, you know the remaining unknown parts are all walls, producing a finished map of the facility:

+
#########
+#.|.|.|.#
+#-#######
+#.|.|.|.#
+#-#####-#
+#.#.#X|.#
+#-#-#####
+#.|.|.|.#
+#########
+
+

Sometimes, a list of options can have an empty option, like (NEWS|WNSE|). This means that routes at this point could effectively skip the options in parentheses and move on immediately. For example, consider this regex and the corresponding map:

+
^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$
+
+###########
+#.|.#.|.#.#
+#-###-#-#-#
+#.|.|.#.#.#
+#-#####-#-#
+#.#.#X|.#.#
+#-#-#####-#
+#.#.|.|.|.#
+#-###-###-#
+#.|.|.#.|.#
+###########
+
+

This regex has one main route which, at three locations, can optionally include additional detours and be valid: (NEWS|), (WNSE|), and (SWEN|). Regardless of which option is taken, the route continues from the position it is left at after taking those steps. So, for example, this regex matches all of the following routes (and more that aren't listed here):

+
    +
  • ENNWSWWSSSEENEENNN
  • +
  • ENNWSWWNEWSSSSEENEENNN
  • +
  • ENNWSWWNEWSSSSEENEESWENNNN
  • +
  • ENNWSWWSSSEENWNSEEENNN
  • +
+

By following the various routes the regex matches, a full map of all of the doors and rooms in the facility can be assembled.

+

To get a sense for the size of this facility, you'd like to determine which room is furthest from you: specifically, you would like to find the room for which the shortest path to that room would require passing through the most doors.

+
    +
  • In the first example (^WNE$), this would be the north-east corner 3 doors away.
  • +
  • In the second example (^ENWWW(NEEE|SSE(EE|N))$), this would be the south-east corner 10 doors away.
  • +
  • In the third example (^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$), this would be the north-east corner 18 doors away.
  • +
+

Here are a few more examples:

+
Regex: ^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$
+Furthest room requires passing 23 doors
+
+#############
+#.|.|.|.|.|.#
+#-#####-###-#
+#.#.|.#.#.#.#
+#-#-###-#-#-#
+#.#.#.|.#.|.#
+#-#-#-#####-#
+#.#.#.#X|.#.#
+#-#-#-###-#-#
+#.|.#.|.#.#.#
+###-#-###-#-#
+#.|.#.|.|.#.#
+#############
+
+
Regex: ^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$
+Furthest room requires passing 31 doors
+
+###############
+#.|.|.|.#.|.|.#
+#-###-###-#-#-#
+#.|.#.|.|.#.#.#
+#-#########-#-#
+#.#.|.|.|.|.#.#
+#-#-#########-#
+#.#.#.|X#.|.#.#
+###-#-###-#-#-#
+#.|.#.#.|.#.|.#
+#-###-#####-###
+#.|.#.|.|.#.#.#
+#-#-#####-#-#-#
+#.#.|.|.|.#.|.#
+###############
+
+

What is the largest number of doors you would be required to pass through to reach a room? That is, find the room for which the shortest path from your starting location to that room would require passing through the most doors; what is the fewest doors you can pass through to reach it?

+
+

To begin, get your puzzle input.

+

Answer:

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file diff --git a/src/advent21/advent21.hs b/src/advent21/advent21.hs new file mode 100644 index 0000000..198154b --- /dev/null +++ b/src/advent21/advent21.hs @@ -0,0 +1,228 @@ +{-# LANGUAGE NegativeLiterals #-} +{-# LANGUAGE FlexibleContexts #-} +{-# LANGUAGE OverloadedStrings #-} +{-# LANGUAGE TypeFamilies #-} +{-# LANGUAGE BangPatterns #-} + +import Debug.Trace + +-- import Prelude hiding ((++)) +import Data.Text (Text) +import qualified Data.Text as T +import qualified Data.Text.IO as TIO + +import Data.Void (Void) +import Text.Megaparsec hiding (State) +import Text.Megaparsec.Char +import qualified Text.Megaparsec.Char.Lexer as L +import qualified Control.Applicative as CA + +import qualified Data.Map.Strict as M +import Data.Map.Strict ((!)) +import qualified Data.Set as S +import Data.Bits ((.&.), (.|.)) + +import Control.Monad (when) +import Control.Monad.State.Strict +import Control.Monad.Reader +import Control.Monad.Writer + +type Memory = M.Map Integer Integer + +data Location = Literal Integer | Register Integer deriving (Show, Eq) +data Instruction = + Addr Integer Integer Integer + | Addi Integer Integer Integer + | Mulr Integer Integer Integer + | Muli Integer Integer Integer + | Banr Integer Integer Integer + | Bani Integer Integer Integer + | Borr Integer Integer Integer + | Bori Integer Integer Integer + | Setr Integer Integer Integer + | Seti Integer Integer Integer + | Gtir Integer Integer Integer + | Gtri Integer Integer Integer + | Gtrr Integer Integer Integer + | Eqir Integer Integer Integer + | Eqri Integer Integer Integer + | Eqrr Integer Integer Integer + deriving (Eq, Show, Ord) + + +data Machine = Machine { _registers :: M.Map Integer Integer + , _pc :: Int + , _history :: S.Set Integer + , _previous :: Integer + -- , _pcReg :: Integer + } + deriving (Show, Eq) + +type ProgrammedMachine = WriterT [Integer] (ReaderT (Integer, [Instruction]) (State Machine)) () + +emptyMachine = Machine { _registers = M.fromList (zip [0..5] (repeat 0)) + , _pc = 0 + , _history = S.empty + , _previous = 0 + } + +main :: IO () +main = do + text <- TIO.readFile "data/advent21.txt" + let (ip, instrs) = successfulParse text + -- print (ip, instrs) + -- print $ zip [0..] instrs + print $ part1 ip instrs + print $ part2 ip instrs + +part1 ip instructions = + runState ( + runReaderT ( + runWriterT executeInstructions1 + ) + (ip, instructions) + ) + emptyMachine + +part2 ip instructions = + runState ( + runReaderT ( + runWriterT executeInstructions2 + ) + (ip, instructions) + ) + emptyMachine + + +-- part2 ip instructions = head (dropWhile terminates [11592302..]) - 1 +-- part2 ip instructions = terminates 11592301 +-- where emptyRegisters = _registers emptyMachine +-- m2 reg0 = emptyMachine {_registers = M.insert 0 reg0 emptyRegisters} +-- terminates reg0 = null $ runResult (m2 reg0) ip instructions + +-- runResult machine ip instructions = r1Repeat +-- where +-- r1Repeat = snd $ fst $ result +-- result = +-- runState ( +-- runReaderT ( +-- runWriterT executeInstructions2 +-- ) +-- (ip, instructions) +-- ) +-- machine + + +executeInstructions1 = + do (_, instrs) <- ask + m <- get + if (_pc m == 28) then do + tell [(_registers m)!1] + else do + when (_pc m >= 0 && _pc m < length instrs) + $ + do executeInstruction + executeInstructions1 + +executeInstructions2 = + do (_, instrs) <- ask + m0 <- get + let r1 = (trace ("R1 = " ++ (show $ (_registers m0)!1) ++ " :: " ++ (show $ S.size (_history m0)))) $ (_registers m0)!1 + if (_pc m0 == 28 && (S.member r1 (_history m0))) then do + -- abort as found a loop + tell $ [_previous m0] + else do + when (_pc m0 == 28) + $ + do + let m0' = m0 { _history = S.insert ((_registers m0)!1) (_history m0) + , _previous = (_registers m0)!1 } + -- let x = trace ("PC = 28, register 1 = " ++ (show ((_registers m0)!1))) $! True + put m0' + m <- get + when (_pc m >= 0 && _pc m < length instrs) + $ + do executeInstruction + executeInstructions2 + + +executeInstruction :: ProgrammedMachine +executeInstruction = + do (pcIs, instrs) <- ask + m <- get + let instr = instrs!!(_pc m) + let memory0 = _registers m + let memory1 = M.insert pcIs (fromIntegral (_pc m)) memory0 + let memory2 = perform instr memory1 + let pc' = fromIntegral ((memory2!pcIs) + 1) + -- let aaa = trace ("pc: " ++ show (_pc m) ++ " m0: " ++ show memory0 ++ " m1: " ++ show memory1 ++ "m2: " ++ show memory2 ++ "pc': " ++ show pc') $! True + let m' = m {_registers = memory2, _pc = pc'} + put m' + + +perform :: Instruction -> Memory -> Memory +-- perform instr memory | ((memory!5 == 7) || ((memory!5 == 3) && (memory!1 == 1))) && (trace ("Perform " ++ show instr ++ " " ++ show memory) False) = undefined +-- perform instr memory | trace ("Perform " ++ show instr ++ " " ++ show memory) False = undefined +perform (Addr a b c) !memory = M.insert c (memory!a + memory!b) memory +perform (Addi a b c) !memory = M.insert c (memory!a + b) memory +perform (Mulr a b c) !memory = M.insert c (memory!a * memory!b) memory +perform (Muli a b c) !memory = M.insert c (memory!a * b) memory +perform (Banr a b c) !memory = M.insert c (memory!a .&. memory!b) memory +perform (Bani a b c) !memory = M.insert c (memory!a .&. b) memory +perform (Borr a b c) !memory = M.insert c (memory!a .|. memory!b) memory +perform (Bori a b c) !memory = M.insert c (memory!a .|. b) memory +perform (Setr a b c) !memory = M.insert c (memory!a) memory +perform (Seti a b c) !memory = M.insert c a memory +perform (Gtir a b c) !memory = M.insert c (if a > (memory!b) then 1 else 0) memory +perform (Gtri a b c) !memory = M.insert c (if (memory!a) > b then 1 else 0) memory +perform (Gtrr a b c) !memory = M.insert c (if (memory!a) > (memory!b) then 1 else 0) memory +perform (Eqir a b c) !memory = M.insert c (if a == memory!b then 1 else 0) memory +perform (Eqri a b c) !memory = M.insert c (if (memory!a) == b then 1 else 0) memory +perform (Eqrr a b c) !memory = M.insert c (if (memory!a) == (memory!b) then 1 else 0) memory + + +-- evaluate :: Machine -> Location -> Integer +-- evaluate _ (Literal i) = i +-- evaluate m (Register r) = M.findWithDefault 0 r (registers m) + + + +type Parser = Parsec Void Text + +sc :: Parser () +sc = L.space (skipSome spaceChar) CA.empty CA.empty + +lexeme = L.lexeme sc +integer = lexeme L.decimal +symb = L.symbol sc + + +instructionsP = (,) <$> headerP <*> many instructionP +instructionP = choice [ addrP, addiP, mulrP, muliP, banrP, baniP, + borrP, boriP, setrP, setiP, gtirP, gtriP, gtrrP, + eqirP, eqriP, eqrrP ] + +headerP = symb "#ip" *> integer + +addrP = Addr <$> (try (symb "addr") *> integer) <*> integer <*> integer +addiP = Addi <$> (try (symb "addi") *> integer) <*> integer <*> integer +mulrP = Mulr <$> (try (symb "mulr") *> integer) <*> integer <*> integer +muliP = Muli <$> (try (symb "muli") *> integer) <*> integer <*> integer +banrP = Banr <$> (try (symb "banr") *> integer) <*> integer <*> integer +baniP = Bani <$> (try (symb "bani") *> integer) <*> integer <*> integer +borrP = Borr <$> (try (symb "borr") *> integer) <*> integer <*> integer +boriP = Bori <$> (try (symb "bori") *> integer) <*> integer <*> integer +setrP = Setr <$> (try (symb "setr") *> integer) <*> integer <*> integer +setiP = Seti <$> (try (symb "seti") *> integer) <*> integer <*> integer +gtirP = Gtir <$> (try (symb "gtir") *> integer) <*> integer <*> integer +gtriP = Gtri <$> (try (symb "gtri") *> integer) <*> integer <*> integer +gtrrP = Gtrr <$> (try (symb "gtrr") *> integer) <*> integer <*> integer +eqirP = Eqir <$> (try (symb "eqir") *> integer) <*> integer <*> integer +eqriP = Eqri <$> (try (symb "eqri") *> integer) <*> integer <*> integer +eqrrP = Eqrr <$> (try (symb "eqrr") *> integer) <*> integer <*> integer + +successfulParse :: Text -> (Integer, [Instruction]) +successfulParse input = + case parse instructionsP "input" input of + Left _error -> (0, []) -- TIO.putStr $ T.pack $ parseErrorPretty err + Right instructions -> instructions \ No newline at end of file -- 2.34.1