print $ part2 mem
part1 mem = _fromStart $ snd $ M.findMin $ M.filter (containsGoal) hull
- where hull = fst $ head $ searchHull $ initialHullBoundary mem
+ where hull = searchHull $ initialHullBoundary mem
part2 mem = fillTime hull S.empty [(start, 0)] 0
hull = M.singleton (0, 0) (Empty {_droid = droid, _fromStart = 0, _isGoal = False})
-searchHull :: (Hull, Boundary) -> [(Hull, Boundary)]
-searchHull hullBoundary = dropWhile goalNotFound $ iterate searchHullStep hullBoundary
+searchHull :: (Hull, Boundary) -> Hull
+searchHull hullBoundary = fst $ head $ dropWhile goalNotFound $ iterate searchHullStep hullBoundary
completeHull :: (Hull, Boundary) -> Hull
completeHull hullBoundary = fst $ head $ dropWhile incomplete $ iterate searchHullStep hullBoundary
-fillTime _ _ [] t = t
-fillTime hull closed ((here, t):boundary) maxt
- | hull!here == Wall = fillTime hull closed boundary maxt
- | S.member here closed = fillTime hull closed boundary maxt
- | otherwise = fillTime hull closed' (boundary ++ neighbours) (max maxt t)
- where closed' = S.insert here closed
- neighbours = map (\d -> (step here d, t + 1)) directions
- directions = [North, East, South, West] :: [Direction]
-
-
searchHullStep :: (Hull, Boundary) -> (Hull, Boundary)
-- searchHullStep (hull, _) | trace (showHull hull) False = undefined
searchHullStep (hull, []) = (hull, [])
, _isGoal = (found == Goal)
}
+fillTime :: Hull -> (S.Set Position) -> [(Position, Integer)] -> Integer -> Integer
+fillTime _ _ [] t = t
+fillTime hull closed ((here, t):boundary) maxt
+ | hull!here == Wall = fillTime hull closed boundary maxt
+ | S.member here closed = fillTime hull closed boundary maxt
+ | otherwise = fillTime hull closed' (boundary ++ neighbours) (max maxt t)
+ where closed' = S.insert here closed
+ neighbours = map (\d -> (step here d, t + 1)) directions
+ directions = [North, East, South, West] :: [Direction]
+
goalNotFound :: (Hull, Boundary) -> Bool
goalNotFound (hull, _boundary) = M.null $ M.filter containsGoal hull