--- /dev/null
+graph Maze {
+# AA_O -- XI_O [ label = "6" style = "solid"];
+AA_O -- YA_I [ label = "60" style = "solid"];
+AM_I -- AM_O [ label = "" style = "dashed"];
+AM_I -- YO_O [ label = "44" style = "solid"];
+AM_O -- DM_I [ label = "74" style = "solid"];
+AW_O -- AW_I [ label = "" style = "dashed"];
+AW_O -- XI_I [ label = "50" style = "solid"];
+AW_I -- GY_O [ label = "44" style = "solid"];
+CQ_O -- CQ_I [ label = "" style = "dashed"];
+CQ_O -- CV_I [ label = "64" style = "solid"];
+CQ_I -- WH_O [ label = "60" style = "solid"];
+CV_O -- CV_I [ label = "" style = "dashed"];
+CV_O -- YO_I [ label = "78" style = "solid"];
+CY_O -- CY_I [ label = "" style = "dashed"];
+CY_O -- GY_I [ label = "48" style = "solid"];
+CY_I -- JV_O [ label = "52" style = "solid"];
+DM_O -- DM_I [ label = "" style = "dashed"];
+DM_O -- GC_I [ label = "58" style = "solid"];
+GC_I -- GC_O [ label = "" style = "dashed"];
+GC_O -- PP_I [ label = "54" style = "solid"];
+GL_O -- GL_I [ label = "" style = "dashed"];
+GL_O -- HB_I [ label = "60" style = "solid"];
+GL_I -- UC_O [ label = "40" style = "solid"];
+GY_I -- GY_O [ label = "" style = "dashed"];
+HB_I -- HB_O [ label = "" style = "dashed"];
+HB_O -- KK_I [ label = "50" style = "solid"];
+JV_I -- JV_O [ label = "" style = "dashed"];
+JV_I -- PP_O [ label = "44" style = "solid"];
+JV_I -- PY_I [ label = "4" style = "solid"];
+JV_I -- XZ_O [ label = "46" style = "solid"];
+KK_O -- KK_I [ label = "" style = "dashed"];
+KK_O -- WH_I [ label = "56" style = "solid"];
+KY_I -- KY_O [ label = "" style = "dashed"];
+KY_I -- YA_O [ label = "52" style = "solid"];
+KY_O -- XZ_I [ label = "52" style = "solid"];
+LM_I -- LM_O [ label = "" style = "dashed"];
+LM_I -- UM_O [ label = "44" style = "solid"];
+LM_O -- YF_I [ label = "44" style = "solid"];
+NZ_O -- NZ_I [ label = "" style = "dashed"];
+NZ_O -- UC_I [ label = "72" style = "solid"];
+# NZ_O -- ZZ_O [ label = "8" style = "solid"];
+NZ_I -- PN_O [ label = "80" style = "solid"];
+PN_O -- PN_I [ label = "" style = "dashed"];
+PN_I -- YF_O [ label = "66" style = "solid"];
+PP_O -- PP_I [ label = "" style = "dashed"];
+PP_O -- PY_I [ label = "42" style = "solid"];
+PP_O -- XZ_O [ label = "4" style = "solid"];
+PY_I -- PY_O [ label = "" style = "dashed"];
+PY_I -- XZ_O [ label = "44" style = "solid"];
+PY_O -- TL_I [ label = "56" style = "solid"];
+TL_O -- TL_I [ label = "" style = "dashed"];
+TL_O -- UM_I [ label = "42" style = "solid"];
+UC_I -- UC_O [ label = "" style = "dashed"];
+UC_I -- ZZ_O [ label = "66" style = "solid"];
+UM_I -- UM_O [ label = "" style = "dashed"];
+WH_I -- WH_O [ label = "" style = "dashed"];
+XI_I -- XI_O [ label = "" style = "dashed"];
+XI_O -- YA_I [ label = "64" style = "solid"];
+XZ_O -- XZ_I [ label = "" style = "dashed"];
+YA_O -- YA_I [ label = "" style = "dashed"];
+YF_O -- YF_I [ label = "" style = "dashed"];
+YO_I -- YO_O [ label = "" style = "dashed"];
+
+}
import qualified Data.Set as S
import qualified Data.Sequence as Q
import Data.Sequence ((<|)) -- , (|>), (><))
-import Data.Foldable (foldl', any, sum) -- (toList, foldr', foldl', all)
+import Data.Foldable (foldl', sum) -- (toList, foldr', foldl', all)
import Data.Char
import Control.Monad.Reader
import Control.Lens hiding ((<|), (|>))
type Position = (Int, Int) -- r, c
+
+data Location = Inner | Outer deriving (Eq, Ord, Show)
data Portal = Portal { _label :: String
, _position :: Position
+ , _location :: Location
} deriving (Eq, Ord, Show)
makeLenses ''Portal
} deriving (Eq, Ord, Show)
makeLenses ''Edge
-type Maze = S.Set Edge
+type Edges = S.Set Edge
+
+-- type Maze = S.Set Edge
+data Maze = Maze { _maze :: Edges
+ , _costPerLevel :: Int
+ , _costToFinish :: Int
+ } deriving (Eq, Ord, Show)
+-- makeLenses ''Maze
type MazeContext = Reader Maze
-type ExploredStates = S.Set Portal
+class (Eq s, Ord s, Show s) => SearchState s where
+ successors :: s -> MazeContext (Q.Seq (s, Edge))
+ estimateCost :: s -> MazeContext Int
+ emptySearchState :: Portal -> s
+ isGoal :: s -> MazeContext Bool
+
+data LevelledSearchState = LevelledSearchState
+ { _portalS :: Portal
+ , _levelS :: Int
+ } deriving (Eq, Ord, Show)
+makeLenses ''LevelledSearchState
+
-data Agendum = Agendum { _current :: Portal
- , _trail :: Q.Seq Edge
- , _cost :: Int} deriving (Show, Eq)
+type ExploredStates s = S.Set s
+
+data Agendum s =
+ Agendum { _current :: s
+ , _trail :: Q.Seq Edge
+ , _cost :: Int
+ } deriving (Show, Eq)
makeLenses ''Agendum
-type Agenda = P.MinPQueue Int (Agendum)
+type Agenda s = P.MinPQueue Int (Agendum s)
main :: IO ()
main = do
- -- text <- readFile "data/advent20a.txt"
- -- let mc = buildComplex text
- -- print mc
- -- let maze = contractMaze mc
- -- print maze
maze <- setup
+ -- print maze
putStrLn $ showContracted maze
print $ part1 maze
- -- print $ S.size $ edgeC $ _caveE ccE
- -- print $ S.size $ _cave $ contractCave ccE [startPosition]
- -- putStrLn $ showContracted $ contractCave ccE [startPosition]
- -- let (re, ce) = startPosition
- -- let startPositions = [(re - 1, ce - 1), (re - 1, ce + 1), (re + 1 , ce - 1), (re + 1, ce + 1)]
- -- let cavern0 = ccE ^. caveE
- -- let cavern = cavern0 `S.difference` [(re, ce), (re + 1, ce), (re - 1, ce), (re, ce + 1), (re, ce - 1)]
- -- let caveComplex = ccE & caveE .~ cavern
- -- let cc = contractCave caveComplex startPositions
- -- putStrLn $ showContracted cc
- -- print $ part1 ccE startPosition
- -- print $ part2 ccE startPosition
-
--- edgeC ec = S.foldl' ecAdd S.empty ec
--- where ecAdd es n = S.union (eds n) es
--- eds n = S.map (\m -> S.fromList [n, m]) $ nbrs n
--- nbrs n = S.intersection ec $ possibleNeighbours n
-
+ print $ part2 maze
setup = do
text <- readFile "data/advent20.txt"
let mc = buildComplex text
-- print mc
- return $ contractMaze mc
-- print maze
+ return $ contractMaze mc
--- part1 :: Maze -> Int
-part1 maze = result -- maybe 0 _cost result
- where result = runReader searchMaze maze
+part1 :: Maze -> Int
+-- part1 :: Maze -> Maybe (Agendum Portal)
+part1 maze = maybe 0 _cost result
+ where result = runReader searchMaze maze :: Maybe (Agendum Portal)
+part2 :: Maze -> Int
+-- part2 :: Maze -> Maybe (Agendum LevelledSearchState)
+part2 maze = maybe 0 _cost result
+ where result = runReader searchMaze maze :: Maybe (Agendum LevelledSearchState)
buildComplex :: String -> MazeComplex
-buildComplex text = mc & portalLocs .~ pLocs
+buildComplex text = mc & portalLocs .~ pLocs & portalsE .~ portals'
where mc = foldl' (buildMazeRow rows) mc0 [0..l]
mc0 = MazeComplex {_mazeE = S.empty, _portalsE = S.empty, _portalLocs = S.empty}
rows = lines text
l = length rows - 1
+ minR = 2
+ maxR = l - 2
+ minC = 2
+ maxC = length (rows!!2) - 3
pLocs = S.map _position (mc ^. portalsE)
+ portals = mc ^. portalsE
+ portals' = S.map (classifiyPortal minR maxR minC maxC) portals
+
+classifiyPortal :: Int -> Int -> Int -> Int -> Portal -> Portal
+classifiyPortal minR maxR minC maxC portal = portal & location .~ loc
+ where (r, c) = portal ^. position
+ loc = if (r == minR) || (r == maxR) || (c == minC) || (c == maxC)
+ then Outer
+ else Inner
buildMazeRow :: [String] -> MazeComplex -> Int -> MazeComplex
buildMazeRow rows mc r = foldl' (buildMazeCell rows r) mc [0..l]
makePortal portals rows hc r c
| isUpper rc = if pr == '.'
- then S.insert (Portal [hc, rc] (r, c + 2)) portals
- else S.insert (Portal [hc, rc] (r, c - 1)) portals
+ then S.insert (Portal { _label = [hc, rc], _position = (r, c + 2), _location = Outer } ) portals
+ else S.insert (Portal { _label = [hc, rc], _position = (r, c - 1), _location = Outer } ) portals
| isUpper dc = if pd == '.'
- then S.insert (Portal [hc, dc] (r + 2, c)) portals
- else S.insert (Portal [hc, dc] (r - 1, c)) portals
+ then S.insert (Portal { _label = [hc, dc], _position = (r + 2, c), _location = Outer } ) portals
+ else S.insert (Portal { _label = [hc, dc], _position = (r - 1, c), _location = Outer } ) portals
| otherwise = portals
where -- lc = charAt rows r (c - 1)
rc = charAt rows r (c + 1)
-- pl = charAt rows r (c - 1)
pr = charAt rows r (c + 2)
+
charAt :: [String] -> Int -> Int -> Char
charAt rows r c = atDef ' ' (atDef "" rows r) c
contractMaze :: MazeComplex -> Maze
-contractMaze expanded = S.union mazeW mazeP
+contractMaze expanded = Maze
+ { _maze = S.union mazeW mazeP
+ , _costPerLevel = cpl
+ , _costToFinish = ctf
+ }
where starts = expanded ^. portalsE
- mazeW = S.foldr (contractFrom expanded) S.empty starts
- mazeP = S.foldr (addWarp starts) S.empty starts
-
+ mazeP = S.foldr (contractFrom expanded) S.empty starts
+ mazeW = S.foldr (addWarp starts) S.empty starts
+ cpl = minimum $ map (^. distance) $ S.toList $ S.filter (\e -> e ^. edgeType == Walk) mazeP
+ ctf = minimum $ map (^. distance) $ S.toList $ S.filter (edgeTouches term) mazeP
+ term = S.findMin $ S.filter (\p -> p ^. label == "ZZ") starts
-contractFrom :: MazeComplex -> Portal -> Maze -> Maze
+contractFrom :: MazeComplex -> Portal -> Edges -> Edges
contractFrom expanded start maze0 = S.union maze0 reachables
where startPos = start ^. position
reachables = reachableFrom [(startPos, 0)] S.empty expanded' start
& portalLocs %~ (S.delete startPos)
-- & mazeE %~ (S.delete startPos)
-reachableFrom :: [(Position, Int)] -> (S.Set Position) -> MazeComplex -> Portal -> Maze
+reachableFrom :: [(Position, Int)] -> (S.Set Position) -> MazeComplex -> Portal -> Edges
reachableFrom [] _closed _expanded _start = S.empty
-reachableFrom ((here, distance):boundary) closed expanded start
+reachableFrom ((here, dist):boundary) closed expanded start
| here `S.member` closed = reachableFrom boundary closed expanded start
| here `S.member` ps = S.insert edge $ reachableFrom boundary closed' expanded start
| otherwise = reachableFrom boundary' closed' expanded start
closed' = S.insert here closed
ps = expanded ^. portalLocs
other = S.findMin $ S.filter (\p -> p ^. position == here) $ expanded ^. portalsE
- edge = Edge { _connects = mkConnection start other, _edgeType = Walk, _distance = distance }
- neighbours = S.map (\n -> (n, distance + 1)) nbrs
+ edge = Edge { _connects = mkConnection start other, _edgeType = Walk, _distance = dist }
+ neighbours = S.map (\n -> (n, dist + 1)) nbrs
boundary' = boundary ++ (S.toAscList neighbours)
-addWarp :: Portals -> Portal -> Maze -> Maze
+addWarp :: Portals -> Portal -> Edges -> Edges
addWarp portals portal warps
| S.null others = warps
| otherwise = S.insert warp warps
other = S.findMin others
warp = Edge {_connects = mkConnection portal other, _edgeType = Teleport, _distance = 1}
-
portalsConnect :: String -> Position -> Portal -> Bool
-portalsConnect lab pos portal = (pLabel == lab) && (not (pPos == pos))
+portalsConnect lab pos portal = (pLabel == lab) && (pPos /= pos)
where pLabel = portal ^. label
pPos = portal ^. position
mkConnection :: Portal -> Portal -> EdgeConnects
mkConnection a b = if a < b then (a, b) else (b, a)
+
edgeTouches :: Portal -> Edge -> Bool
edgeTouches p e
| p == a = True
| otherwise = False
where (a, b) = e ^. connects
--- anyEdgeTouch :: S.Set Portal -> Edge -> Bool
--- -- anyEdgeTouch xs e = S.foldl' (\t x -> t || (edgeTouches e x)) False xs
--- anyEdgeTouch xs e = any (edgeTouches e) xs
-
edgeOther :: Portal -> Edge -> Portal
edgeOther x e
| x == a = b
in S.insert p1 $ S.insert p2 ps
-
-searchMaze :: MazeContext (Maybe (Agendum))
+searchMaze :: SearchState s => MazeContext (Maybe (Agendum s))
searchMaze =
do agenda <- initAgenda
aStar agenda S.empty
-initAgenda :: MazeContext (Agenda)
+initAgenda :: SearchState s => MazeContext (Agenda s)
initAgenda =
- do edges <- ask
+ do edges <- asks _maze
let portals = mazePortals edges
let portal = S.findMin $ S.filter (\p -> p ^. label == "AA") portals
- cost <- estimateCost portal
- return $ P.singleton cost Agendum { _current = portal, _trail = Q.empty, _cost = cost}
+ let ss = emptySearchState portal
+ c <- estimateCost ss
+ return $ P.singleton c Agendum { _current = ss, _trail = Q.empty, _cost = c}
-aStar :: Agenda -> ExploredStates -> MazeContext (Maybe (Agendum))
+aStar :: SearchState s => Agenda s -> ExploredStates s -> MazeContext (Maybe (Agendum s))
aStar agenda closed
-- | trace ("Peeping " ++ (show $ fst $ P.findMin agenda) ++ ": " ++ (show reached) ++ " <- " ++ (show $ toList $ Q.take 1 $ _trail $ currentAgendum) ++ " :: " ++ (show newAgenda)) False = undefined
-- | trace ("Peeping " ++ (show $ _current $ snd $ P.findMin agenda) ) False = undefined
else aStar newAgenda (S.insert reached closed)
-isGoal :: Portal -> MazeContext Bool
-isGoal portal = return $ portal ^. label == "ZZ"
-
-candidates :: Agendum -> ExploredStates -> MazeContext (Q.Seq (Agendum))
+candidates :: SearchState s => Agendum s -> ExploredStates s -> MazeContext (Q.Seq (Agendum s))
candidates agendum closed =
do let candidate = agendum ^. current
let previous = agendum ^. trail
+ -- let prevCost = agendum ^. cost
succs <- successors candidate
let nonloops = Q.filter (\s -> not $ (fst s) `S.member` closed) succs
mapM (makeAgendum previous) nonloops
-makeAgendum :: (Q.Seq Edge) -> (Portal, Edge) -> MazeContext (Agendum)
+makeAgendum :: SearchState s => (Q.Seq Edge) -> (s, Edge) -> MazeContext (Agendum s)
makeAgendum previous (newP, newE) =
do predicted <- estimateCost newP
- let incurred = (newE ^. distance) + (sum $ fmap (^. distance) previous)
+ let newTrail = newE <| previous
+ let incurred = sum $ fmap (^. distance) newTrail
return Agendum { _current = newP
- , _trail = newE <| previous
+ , _trail = newTrail
, _cost = incurred + predicted
}
-successors :: Portal -> MazeContext (Q.Seq (Portal, Edge))
-successors portal =
- do maze <- ask
- let edges = S.filter (edgeTouches portal) maze
- let locations = S.map (\e -> (edgeOther portal e, e)) edges
- let succs = S.foldr' (<|) Q.empty locations
- return succs
-
-estimateCost :: Portal -> MazeContext Int
-estimateCost portal = return 0
- -- do let heres = explorer ^. position
- -- ks <- asks _keys
- -- cavern <- asks _cave
- -- let kH = explorer ^. keysHeld
- -- let unfound = ks `S.difference` kH
- -- let unfoundEdges0 = S.filter (\e -> edgeTouch heres e) cavern
- -- let unfoundEdges = S.filter (\e -> not $ anyEdgeTouch kH e) unfoundEdges0
- -- let furthest = S.findMax $ S.insert 0 $ S.map _distance unfoundEdges
- -- return $ max 0 $ furthest + (S.size unfound) - 1
-
-
-
+instance SearchState Portal where
+
+ emptySearchState portal = portal
+
+ -- successors :: Portal -> MazeContext (Q.Seq (Portal, Edge))
+ successors portal =
+ do maze <- asks _maze
+ let edges = S.filter (edgeTouches portal) maze
+ let locations = S.map (\e -> (edgeOther portal e, e)) edges
+ let succs = S.foldr' (<|) Q.empty locations
+ return succs
+
+ -- estimateCost :: Portal -> MazeContext Int
+ estimateCost _portal = return 0
+
+ -- isGoal :: Portal -> MazeContext Bool
+ isGoal portal = return $ portal ^. label == "ZZ"
+
+instance SearchState LevelledSearchState where
+ emptySearchState portal = LevelledSearchState {_portalS = portal, _levelS = 0}
+
+ -- successors :: LevelledSearchState -> MazeContext (Q.Seq (LevelledSearchState, Edge))
+ successors ss =
+ do maze <- asks _maze
+ let lvl = ss ^. levelS
+ let portal = ss ^. portalS
+ let edges = S.filter (edgeTouches portal) maze
+ let lvlEdges = S.filter (edgeAtLevel portal lvl) edges
+ let locations = S.map (\e -> (newLSS portal lvl e, e)) lvlEdges
+ let locations' = S.filter (\(s, _) -> (s ^. levelS) >= 0) locations
+ let succs = S.foldr' (<|) Q.empty locations'
+ return succs
+
+ -- estimateCost :: Portal -> MazeContext Int
+ estimateCost ss = -- return 0
+ do let lvl = ss ^. levelS
+ cpl <- asks _costPerLevel
+ ctf <- asks _costToFinish
+ let cplT = if ss ^. portalS . location == Outer
+ then cpl * (lvl - 1) + 1
+ else cpl * lvl
+ if isTerminal (ss ^. portalS)
+ then return 0
+ else return (cplT + ctf)
+
+ -- isGoal :: LevelledSearchState -> MazeContext Bool
+ isGoal ss = return $ ss ^. portalS . label == "ZZ"
+
+edgeAtLevel portal lvl edge
+ -- | (lvl == 0) && (isTerminal other) && (et == Walk) = True
+ | (lvl /= 0) && (isTerminal other) && (et == Walk) = False
+ | (lvl == 0) && (not $ isTerminal other) && (et == Walk) && ((other ^. location) == Outer) = False
+ | otherwise = True
+ where other = edgeOther portal edge
+ et = edge ^. edgeType
+
+isTerminal p = (p ^. label == "AA") || (p ^. label == "ZZ")
+
+newLSS :: Portal -> Int -> Edge -> LevelledSearchState
+newLSS portal lvl edge
+ | et == Teleport && pl == Outer = LevelledSearchState { _portalS = otherPortal, _levelS = lvl - 1 }
+ | et == Teleport && pl == Inner = LevelledSearchState { _portalS = otherPortal, _levelS = lvl + 1 }
+ | otherwise = LevelledSearchState { _portalS = otherPortal, _levelS = lvl } -- et == Walk
+ where pl = portal ^. location
+ et = edge ^. edgeType
+ otherPortal = edgeOther portal edge
showContracted :: Maze -> String
-showContracted maze = "graph Maze {\n" ++ bulk ++ "\n}"
- where bulk = S.foldr (\e s -> (showEdge e) ++ s) "" maze
+showContracted m = "graph Maze {\n" ++ bulk ++ "\n}"
+ where bulk = S.foldr (\e s -> (showEdge e) ++ s) "" (_maze m)
showEdge :: Edge -> String
-showEdge e = (showPortal h) ++ " -- " ++ (showPortal t) ++ " [ label = \"" ++ (edgeLabel e) ++ "\"];\n"
- where edgeLabel e = (show (e ^. edgeType)) ++ ", " ++ (show (e ^. distance))
+showEdge e = (showPortal h) ++ " -- " ++ (showPortal t) ++ " [ label = \"" ++ edgeLabel ++ "\" style = \"" ++ style ++ "\"];\n"
+ where -- edgeLabel e = (show (e ^. edgeType)) ++ ", " ++ (show (e ^. distance))
+ (edgeLabel, style) =
+ if (e ^. edgeType) == Walk
+ then (show (e ^. distance), "solid")
+ else ("", "dashed")
(h, t) = e ^. connects
- showPortal p = p ^. label ++ (show (fst (p ^. position))) ++ "c" ++ (show (snd (p ^. position)))
+ -- showPortal p = p ^. label ++ (show (fst (p ^. position))) ++ "c" ++ (show (snd (p ^. position))) ++ (take 1 $ show (p ^. location))
+ showPortal p = p ^. label ++ "_" ++ (take 1 $ show (p ^. location))
--- /dev/null
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 20 - Advent of Code 2019</title>
+<!--[if lt IE 9]><script src="/static/html5.js"></script><![endif]-->
+<link href='//fonts.googleapis.com/css?family=Source+Code+Pro:300&subset=latin,latin-ext' rel='stylesheet' type='text/css'>
+<link rel="stylesheet" type="text/css" href="/static/style.css?24"/>
+<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
+<link rel="shortcut icon" href="/favicon.png"/>
+</head><!--
+
+
+
+
+Oh, hello! Funny seeing you here.
+
+I appreciate your enthusiasm, but you aren't going to find much down here.
+There certainly aren't clues to any of the puzzles. The best surprises don't
+even appear in the source until you unlock them for real.
+
+Please be careful with automated requests; I'm not a massive company, and I can
+only take so much traffic. Please be considerate so that everyone gets to play.
+
+If you're curious about how Advent of Code works, it's running on some custom
+Perl code. Other than a few integrations (auth, analytics, ads, social media),
+I built the whole thing myself, including the design, animations, prose, and
+all of the puzzles.
+
+The puzzles are most of the work; preparing a new calendar and a new set of
+puzzles each year takes all of my free time for 4-5 months. A lot of effort
+went into building this thing - I hope you're enjoying playing it as much as I
+enjoyed making it for you!
+
+If you'd like to hang out, I'm @ericwastl on Twitter.
+
+- Eric Wastl
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+-->
+<body>
+<header><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2019/about">[About]</a></li><li><a href="/2019/events">[Events]</a></li><li><a href="https://teespring.com/adventofcode-2019" target="_blank">[Shop]</a></li><li><a href="/2019/settings">[Settings]</a></li><li><a href="/2019/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2019/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">40*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap">//</span><a href="/2019">2019</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2019">[Calendar]</a></li><li><a href="/2019/support">[AoC++]</a></li><li><a href="/2019/sponsors">[Sponsors]</a></li><li><a href="/2019/leaderboard">[Leaderboard]</a></li><li><a href="/2019/stats">[Stats]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2019/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://www.novetta.com/careers/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Novetta</a> - While Santa has elves, we have TS/SCI data scientists rapidly prototyping ML solutions...hot chocolate included. Check us out.</div></div>
+</div><!--/sidebar-->
+
+<main>
+<script>window.addEventListener('click', function(e,s,r){if(e.target.nodeName==='CODE'&&e.detail===3){s=window.getSelection();s.removeAllRanges();r=document.createRange();r.selectNodeContents(e.target);s.addRange(r);}});</script>
+<article class="day-desc"><h2>--- Day 20: Donut Maze ---</h2><p>You notice a strange pattern on the surface of Pluto and land nearby to get a closer look. Upon closer inspection, you realize you've come across one of the famous space-warping mazes of the long-lost Pluto civilization!</p>
+<p>Because there isn't much space on Pluto, the civilization that used to live here thrived by inventing a method for folding spacetime. Although the technology is no longer understood, mazes like this one provide a small glimpse into the <span title="So really, this puzzle is more archaeology than math, right?">daily life of an ancient Pluto citizen</span>.</p>
+<p>This maze is shaped like a <a href="https://en.wikipedia.org/wiki/Torus">donut</a>. Portals along the inner and outer edge of the donut can instantly teleport you from one side to the other. For example:</p>
+<pre><code> A
+ A
+ #######.#########
+ #######.........#
+ #######.#######.#
+ #######.#######.#
+ #######.#######.#
+ ##### B ###.#
+BC...## C ###.#
+ ##.## ###.#
+ ##...DE F ###.#
+ ##### G ###.#
+ #########.#####.#
+DE..#######...###.#
+ #.#########.###.#
+FG..#########.....#
+ ###########.#####
+ Z
+ Z
+</code></pre>
+<p>This map of the maze shows solid walls (<code>#</code>) and open passages (<code>.</code>). Every maze on Pluto has a start (the open tile next to <code>AA</code>) and an end (the open tile next to <code>ZZ</code>). Mazes on Pluto also have portals; this maze has three pairs of portals: <code>BC</code>, <code>DE</code>, and <code>FG</code>. When on an open tile next to one of these labels, a single step can take you to the other tile with the same label. (You can only walk on <code>.</code> tiles; labels and empty space are not traversable.)</p>
+<p>One path through the maze doesn't require any portals. Starting at <code>AA</code>, you could go down 1, right 8, down 12, left 4, and down 1 to reach <code>ZZ</code>, a total of 26 steps.</p>
+<p>However, there is a shorter path: You could walk from <code>AA</code> to the inner <code>BC</code> portal (4 steps), warp to the outer <code>BC</code> portal (1 step), walk to the inner <code>DE</code> (6 steps), warp to the outer <code>DE</code> (1 step), walk to the outer <code>FG</code> (4 steps), warp to the inner <code>FG</code> (1 step), and finally walk to <code>ZZ</code> (6 steps). In total, this is only <em>23</em> steps.</p>
+<p>Here is a larger example:</p>
+<pre><code> A
+ A
+ #################.#############
+ #.#...#...................#.#.#
+ #.#.#.###.###.###.#########.#.#
+ #.#.#.......#...#.....#.#.#...#
+ #.#########.###.#####.#.#.###.#
+ #.............#.#.....#.......#
+ ###.###########.###.#####.#.#.#
+ #.....# A C #.#.#.#
+ ####### S P #####.#
+ #.#...# #......VT
+ #.#.#.# #.#####
+ #...#.# YN....#.#
+ #.###.# #####.#
+DI....#.# #.....#
+ #####.# #.###.#
+ZZ......# QG....#..AS
+ ###.### #######
+JO..#.#.# #.....#
+ #.#.#.# ###.#.#
+ #...#..DI BU....#..LF
+ #####.# #.#####
+YN......# VT..#....QG
+ #.###.# #.###.#
+ #.#...# #.....#
+ ###.### J L J #.#.###
+ #.....# O F P #.#...#
+ #.###.#####.#.#####.#####.###.#
+ #...#.#.#...#.....#.....#.#...#
+ #.#####.###.###.#.#.#########.#
+ #...#.#.....#...#.#.#.#.....#.#
+ #.###.#####.###.###.#.#.#######
+ #.#.........#...#.............#
+ #########.###.###.#############
+ B J C
+ U P P
+</code></pre>
+<p>Here, <code>AA</code> has no direct path to <code>ZZ</code>, but it does connect to <code>AS</code> and <code>CP</code>. By passing through <code>AS</code>, <code>QG</code>, <code>BU</code>, and <code>JO</code>, you can reach <code>ZZ</code> in <em>58</em> steps.</p>
+<p>In your maze, <em>how many steps does it take to get from the open tile marked <code>AA</code> to the open tile marked <code>ZZ</code>?</em></p>
+</article>
+<p>Your puzzle answer was <code>556</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Strangely, the exit isn't open when you reach it. Then, you remember: the ancient Plutonians were famous for building <em>recursive spaces</em>.</p>
+<p>The marked connections in the maze aren't portals: they <em>physically connect</em> to a larger or smaller copy of the maze. Specifically, the labeled tiles around the inside edge actually connect to a smaller copy of the same maze, and the smaller copy's inner labeled tiles connect to yet a <em>smaller</em> copy, and so on.</p>
+<p>When you enter the maze, you are at the outermost level; when at the outermost level, only the outer labels <code>AA</code> and <code>ZZ</code> function (as the start and end, respectively); all other outer labeled tiles are effectively walls. At any other level, <code>AA</code> and <code>ZZ</code> count as walls, but the other outer labeled tiles bring you one level outward.</p>
+<p>Your goal is to find a path through the maze that brings you back to <code>ZZ</code> at the outermost level of the maze.</p>
+<p>In the first example above, the shortest path is now the loop around the right side. If the starting level is <code>0</code>, then taking the previously-shortest path would pass through <code>BC</code> (to level <code>1</code>), <code>DE</code> (to level <code>2</code>), and <code>FG</code> (back to level <code>1</code>). Because this is not the outermost level, <code>ZZ</code> is a wall, and the only option is to go back around to <code>BC</code>, which would only send you even deeper into the recursive maze.</p>
+<p>In the second example above, there is no path that brings you to <code>ZZ</code> at the outermost level.</p>
+<p>Here is a more interesting example:</p>
+<pre><code> Z L X W C
+ Z P Q B K
+ ###########.#.#.#.#######.###############
+ #...#.......#.#.......#.#.......#.#.#...#
+ ###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
+ #.#...#.#.#...#.#.#...#...#...#.#.......#
+ #.###.#######.###.###.#.###.###.#.#######
+ #...#.......#.#...#...#.............#...#
+ #.#########.#######.#.#######.#######.###
+ #...#.# F R I Z #.#.#.#
+ #.###.# D E C H #.#.#.#
+ #.#...# #...#.#
+ #.###.# #.###.#
+ #.#....OA WB..#.#..ZH
+ #.###.# #.#.#.#
+CJ......# #.....#
+ ####### #######
+ #.#....CK #......IC
+ #.###.# #.###.#
+ #.....# #...#.#
+ ###.### #.#.#.#
+XF....#.# RF..#.#.#
+ #####.# #######
+ #......CJ NM..#...#
+ ###.#.# #.###.#
+RE....#.# #......RF
+ ###.### X X L #.#.#.#
+ #.....# F Q P #.#.#.#
+ ###.###########.###.#######.#########.###
+ #.....#...#.....#.......#...#.....#.#...#
+ #####.#.###.#######.#######.###.###.#.#.#
+ #.......#.......#.#.#.#.#...#...#...#.#.#
+ #####.###.#####.#.#.#.#.###.###.#.###.###
+ #.......#.....#.#...#...............#...#
+ #############.#.#.###.###################
+ A O F N
+ A A D M
+</code></pre>
+<p>One shortest path through the maze is the following:</p>
+<ul>
+<li>Walk from <code>AA</code> to <code>XF</code> (16 steps)</li>
+<li>Recurse into level 1 through <code>XF</code> (1 step)</li>
+<li>Walk from <code>XF</code> to <code>CK</code> (10 steps)</li>
+<li>Recurse into level 2 through <code>CK</code> (1 step)</li>
+<li>Walk from <code>CK</code> to <code>ZH</code> (14 steps)</li>
+<li>Recurse into level 3 through <code>ZH</code> (1 step)</li>
+<li>Walk from <code>ZH</code> to <code>WB</code> (10 steps)</li>
+<li>Recurse into level 4 through <code>WB</code> (1 step)</li>
+<li>Walk from <code>WB</code> to <code>IC</code> (10 steps)</li>
+<li>Recurse into level 5 through <code>IC</code> (1 step)</li>
+<li>Walk from <code>IC</code> to <code>RF</code> (10 steps)</li>
+<li>Recurse into level 6 through <code>RF</code> (1 step)</li>
+<li>Walk from <code>RF</code> to <code>NM</code> (8 steps)</li>
+<li>Recurse into level 7 through <code>NM</code> (1 step)</li>
+<li>Walk from <code>NM</code> to <code>LP</code> (12 steps)</li>
+<li>Recurse into level 8 through <code>LP</code> (1 step)</li>
+<li>Walk from <code>LP</code> to <code>FD</code> (24 steps)</li>
+<li>Recurse into level 9 through <code>FD</code> (1 step)</li>
+<li>Walk from <code>FD</code> to <code>XQ</code> (8 steps)</li>
+<li>Recurse into level 10 through <code>XQ</code> (1 step)</li>
+<li>Walk from <code>XQ</code> to <code>WB</code> (4 steps)</li>
+<li>Return to level 9 through <code>WB</code> (1 step)</li>
+<li>Walk from <code>WB</code> to <code>ZH</code> (10 steps)</li>
+<li>Return to level 8 through <code>ZH</code> (1 step)</li>
+<li>Walk from <code>ZH</code> to <code>CK</code> (14 steps)</li>
+<li>Return to level 7 through <code>CK</code> (1 step)</li>
+<li>Walk from <code>CK</code> to <code>XF</code> (10 steps)</li>
+<li>Return to level 6 through <code>XF</code> (1 step)</li>
+<li>Walk from <code>XF</code> to <code>OA</code> (14 steps)</li>
+<li>Return to level 5 through <code>OA</code> (1 step)</li>
+<li>Walk from <code>OA</code> to <code>CJ</code> (8 steps)</li>
+<li>Return to level 4 through <code>CJ</code> (1 step)</li>
+<li>Walk from <code>CJ</code> to <code>RE</code> (8 steps)</li>
+<li>Return to level 3 through <code>RE</code> (1 step)</li>
+<li>Walk from <code>RE</code> to <code>IC</code> (4 steps)</li>
+<li>Recurse into level 4 through <code>IC</code> (1 step)</li>
+<li>Walk from <code>IC</code> to <code>RF</code> (10 steps)</li>
+<li>Recurse into level 5 through <code>RF</code> (1 step)</li>
+<li>Walk from <code>RF</code> to <code>NM</code> (8 steps)</li>
+<li>Recurse into level 6 through <code>NM</code> (1 step)</li>
+<li>Walk from <code>NM</code> to <code>LP</code> (12 steps)</li>
+<li>Recurse into level 7 through <code>LP</code> (1 step)</li>
+<li>Walk from <code>LP</code> to <code>FD</code> (24 steps)</li>
+<li>Recurse into level 8 through <code>FD</code> (1 step)</li>
+<li>Walk from <code>FD</code> to <code>XQ</code> (8 steps)</li>
+<li>Recurse into level 9 through <code>XQ</code> (1 step)</li>
+<li>Walk from <code>XQ</code> to <code>WB</code> (4 steps)</li>
+<li>Return to level 8 through <code>WB</code> (1 step)</li>
+<li>Walk from <code>WB</code> to <code>ZH</code> (10 steps)</li>
+<li>Return to level 7 through <code>ZH</code> (1 step)</li>
+<li>Walk from <code>ZH</code> to <code>CK</code> (14 steps)</li>
+<li>Return to level 6 through <code>CK</code> (1 step)</li>
+<li>Walk from <code>CK</code> to <code>XF</code> (10 steps)</li>
+<li>Return to level 5 through <code>XF</code> (1 step)</li>
+<li>Walk from <code>XF</code> to <code>OA</code> (14 steps)</li>
+<li>Return to level 4 through <code>OA</code> (1 step)</li>
+<li>Walk from <code>OA</code> to <code>CJ</code> (8 steps)</li>
+<li>Return to level 3 through <code>CJ</code> (1 step)</li>
+<li>Walk from <code>CJ</code> to <code>RE</code> (8 steps)</li>
+<li>Return to level 2 through <code>RE</code> (1 step)</li>
+<li>Walk from <code>RE</code> to <code>XQ</code> (14 steps)</li>
+<li>Return to level 1 through <code>XQ</code> (1 step)</li>
+<li>Walk from <code>XQ</code> to <code>FD</code> (8 steps)</li>
+<li>Return to level 0 through <code>FD</code> (1 step)</li>
+<li>Walk from <code>FD</code> to <code>ZZ</code> (18 steps)</li>
+</ul>
+<p>This path takes a total of <em>396</em> steps to move from <code>AA</code> at the outermost layer to <code>ZZ</code> at the outermost layer.</p>
+<p>In your maze, when accounting for recursion, <em>how many steps does it take to get from the open tile marked <code>AA</code> to the open tile marked <code>ZZ</code>, both at the outermost layer?</em></p>
+</article>
+<p>Your puzzle answer was <code>6532</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
+<p>At this point, you should <a href="/2019">return to your Advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="20/input" target="_blank">get your puzzle input</a>.</p>
+<p>You can also <span class="share">[Share<span class="share-content">on
+ <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Donut+Maze%22+%2D+Day+20+%2D+Advent+of+Code+2019&url=https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F20&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="javascript:void(0);" onclick="var mastodon_instance=prompt('Mastodon Instance / Server Name?'); if(typeof mastodon_instance==='string' && mastodon_instance.length){this.href='https://'+mastodon_instance+'/share?text=I%27ve+completed+%22Donut+Maze%22+%2D+Day+20+%2D+Advent+of+Code+2019+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F20'}else{return false;}" target="_blank">Mastodon</a
+></span>]</span> this puzzle.</p>
+</main>
+
+<!-- ga -->
+<script>
+(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+ga('create', 'UA-69522494-1', 'auto');
+ga('set', 'anonymizeIp', true);
+ga('send', 'pageview');
+</script>
+<!-- /ga -->
+</body>
+</html>
\ No newline at end of file
projects / advent-of-code-19.git / commitdiff
