+type Agenda e = P.MinPQueue Int (Agendum e)
+-- type Candidates e = S.Set (Int, Agendum e)
+
+instance ExplorerC Explorer1 where
+ successors explorer =
+ do let here = _position1 explorer
+ let locations0 = possibleNeighbours here
+ cave <- asks _cave
+ keys <- asks _keys
+ doors <- asks _doors
+ let keysHeld = _keysHeld1 explorer
+ let locations1 = Q.filter (`S.member` cave) locations0
+ let locations2 = Q.filter (hasKeyFor doors keysHeld) locations1
+ return $ fmap (\l -> explorer { _position1 = l, _keysHeld1 = pickupKey keys keysHeld l}) locations2
+
+ estimateCost explorer = -- return 0
+ do keys <- asks _keys
+ let (r, c) = _position1 explorer
+ let unfoundKeys = M.keysSet $ M.filter (`S.notMember` (_keysHeld1 explorer)) keys
+ let (minR, maxR, minC, maxC) = bounds $ unfoundKeys
+ -- = minimum $ map fst $ M.keys unfoundKeys
+ -- let minC = minimum $ map snd $ M.keys unfoundKeys
+ -- let maxR = maximum $ map fst $ M.keys unfoundKeys
+ -- let maxC = maximum $ map snd $ M.keys unfoundKeys
+ let spanR = spanV r minR maxR
+ let spanC = spanV c minC maxC
+ if S.null unfoundKeys
+ then return 0
+ else return $ fromIntegral (spanR + spanC)
+ -- return $ sum $ map (manhattan here) $ M.keys unfoundKeys
+
+ -- positionE = _position1
+ keysHeldE = _keysHeld1
+ emptyExplorer = Explorer1 { _position1 = (0, 0), _keysHeld1 = S.empty }
+
+instance ExplorerC Explorer4 where
+ successors explorer =
+ do let rawHeres = _position4 explorer
+ let heres = setToSeq $ allSplits rawHeres
+ let locations0 = over (traversed . _1) possibleNeighbours heres
+ cave <- asks _cave
+ keys <- asks _keys
+ doors <- asks _doors
+ let keysHeld = _keysHeld4 explorer
+ let locations1 = over (traversed . _1) (Q.filter (`S.member` cave)) locations0
+ let locations2 = over (traversed . _1) (Q.filter (hasKeyFor doors keysHeld)) locations1
+ let locations3 = fmap (\(ls, hs) -> fmap (\l -> (l, hs)) ls) locations2
+ let locations4 = foldl1 (><) locations3
+ return $ fmap (\(l, hs) -> explorer { _position4 = S.insert l hs, _keysHeld4 = pickupKey keys keysHeld l}) locations4
+
+ estimateCost explorer = -- return 0
+ do keys <- asks _keys
+ let unfoundKeys = M.keysSet $ M.filter (`S.notMember` (_keysHeld4 explorer)) keys
+ let (minR, maxR, minC, maxC) = bounds unfoundKeys
+ let (minDR, maxDR, minDC, maxDC) = bounds $ _position4 explorer
+ let dr = abs (minR - minDR) + abs (maxR - maxDR)
+ let dc = abs (minC - minDC) + abs (maxC - maxDC)
+ if S.null unfoundKeys
+ then return 0
+ else return $ fromIntegral (dr + dc)
+ -- return $ sum $ map (manhattan here) $ M.keys unfoundKeys
+
+ -- positionE = _position1
+ keysHeldE = _keysHeld4
+ emptyExplorer = Explorer4 { _position4 = S.fromList $ replicate 4 (0, 0), _keysHeld4 = S.empty }