--- Writeup at https://work.njae.me.uk/2021/12/13/advent-of-code-2021-day-13/
-
+-- Writeup at https://work.njae.me.uk/2021/12/16/advent-of-code-2021-day-15/
import Debug.Trace
-- import qualified Data.Text.IO as TIO
--- import qualified Data.Map.Strict as M
--- import Data.Map.Strict ((!))
import qualified Data.PQueue.Prio.Min as P
import qualified Data.Set as S
import qualified Data.Sequence as Q
import Data.Maybe (fromMaybe)
import Linear (V2(..), (^+^), (^-^), (*^), (^*))
import Data.Array.IArray
--- import Data.List
-
pattern Empty <- (Q.viewl -> Q.EmptyL) where Empty = Q.empty
pattern x :< xs <- (Q.viewl -> x Q.:< xs) where (:<) = (Q.<|)
type CaveContext = Reader Cave
-
data Agendum s =
Agendum { _current :: s
, _trail :: Q.Seq s
class (Eq s, Ord s, Show s) => SearchState s where
unwrapPos :: s -> BasePosition
+ emptySearchState :: s
successors :: s -> CaveContext (Q.Seq s)
estimateCost :: s -> CaveContext Int
- emptySearchState :: s
isGoal :: s -> CaveContext Bool
entryCost :: s -> CaveContext Int
emptySearchState = Position (V2 0 0)
-- successors :: Position -> CaveContext (Q.Seq Position)
- successors here =
+ successors (Position here) =
do grid <- asks _grid
let neighbours =
filter (inRange (bounds grid))
- [ (unwrapPos here) ^+^ delta
+ [ here ^+^ delta
| delta <- [V2 -1 0, V2 1 0, V2 0 -1, V2 0 1]
]
let succs = Q.fromList $ map Position neighbours
return succs
-- estimateCost :: Position -> CaveContext Int
- estimateCost here =
+ estimateCost (Position here) =
do goal <- asks _goal
- let (V2 dr dc) = (unwrapPos here) ^-^ goal
+ let (V2 dr dc) = here ^-^ goal
return $ (abs dr) + (abs dc)
-- isGoal :: here -> CaveContext Bool
- isGoal here =
+ isGoal (Position here) =
do goal <- asks _goal
- return $ (unwrapPos here) == goal
+ return $ here == goal
- entryCost here =
+ entryCost (Position here) =
do grid <- asks _grid
- return $ grid ! (unwrapPos here)
+ return $ grid ! here
instance SearchState TiledPosition where
- emptySearchState = TiledPosition (V2 0 0)
-
unwrapPos (TiledPosition p) = p
+ emptySearchState = TiledPosition (V2 0 0)
+
-- successors :: Position -> CaveContext (Q.Seq Position)
successors (TiledPosition here) =
do grid <- asks _grid