homework.hs

pacMan :: Int -> [Dependency] -> [Package]
pacMan n deps
    | outOfBounds         = error "Impossible to resolve"
    | Just xs <- try deps = xs ++ top xs
    | otherwise           = error "Impossible to resolve"
    where outOfBounds = any (> n) $ deps >>= (\(x, y) -> [x, y])
          try d | null d    = Just []
          try d = do
              let dependedOn = S.fromList $ map snd d
              let dependers  = S.fromList $ map fst d
              let free       = S.difference dependedOn dependers
              when (S.null free) Nothing
              let minimal   = S.findMin free
              let remainder = filter ((/= minimal) . snd) d
              (minimal :) <$> try remainder
          top xs = S.toList $ S.fromList [1..n] `S.difference` S.fromList xs