This quest was one where I spotted and solved the general case first, which meant that I solved all three parts of the puzzle at once.
You're given a set of comparisons between axes, showing which is harder than the other. The input looks like (several rows of) this:
4<3 2<5 3>1 1>2 1<5 4<1 3>2 4<2 3>5 4<5You have to find the global order of hardness among the axes.
If you treat each comparison as an edge in a directed graph, finding the ordering is finding a topological ordering of the directed graph. That's enough to solve all three parts of the puzzle. But, me being me, I decided to solve it three ways.
Representation and parsing
I used a simple data type to represent the comparisons, and used attoparsec to parse the input.
data Harder = Harder Int Int -- Harder a b means a is harder than b
deriving (Show, Eq, Ord)
-- parse the input file
groupsP :: Parser [S.Set Harder]
comparisonsP :: Parser (S.Set Harder)
comparisonP, softerP, harderP :: Parser Harder
groupsP = comparisonsP `sepBy` endOfLine
comparisonsP = S.fromList <$> comparisonP `sepBy` (char ' ')
comparisonP = softerP <|> harderP
softerP = (flip Harder) <$> decimal <* "<" <*> decimal
harderP = Harder <$> decimal <* ">" <*> decimal
successfulParse :: Text -> [S.Set Harder]
successfulParse input =
case parseOnly groupsP input of
Left _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
Right groups -> groupsApproach 1: direct solution
I used a fairly direct implementation of Kahn's algorithm to find the topological sort. The first thing to do is find all the alloys being tested: this starts as being implict in the set of comparisons. As I'm generating a list of alloys, treating the algorithm as an unfold seems appropriate.
handleGroup :: (S.Set Harder) -> [Int]
handleGroup comparisons = unfoldr findHardest (comparisons, alloys)
where alloys = S.union (S.map (\(Harder a _) -> a) comparisons)
(S.map (\(Harder _ b) -> b) comparisons)I'm unfolding the combination of the set of comparisons (e.g. edges in the graph) and the set of alloys.
The main work happens when there are comparisons remaining. Kahn's algorithm finds a vertex that does not exist in the destination of any edges; in this case, I find a (the) alloy that isn't softer than any other alloy. That vertex (alloy) is removed from the set of remaining alloys, and all edges (comparisons) from that vertex are removed from the set of remaining edges. The algorithm then repeats that work in the next step (by returning Just the revised state).
That leaves two other cases. When I've run out of both comparisons and alloys, the algorithm returns Nothing to stop the process. The final case is trickier. When I've run out of comparisons to process, there are still some alloys left: the alloys that are on the softer end of all comparisons. Those need to be moved into the result list as well.
Putting those three cases together gives this function to do one step of Kahn's algorithm.
findHardest :: (S.Set Harder, S.Set Int) -> Maybe (Int, (S.Set Harder, S.Set Int))
findHardest (comparisons, alloys)
| (S.null comparisons) && (S.null alloys) = Nothing
| (S.null comparisons) = Just (mAlloy, (S.empty, mAlloys'))
| otherwise = Just (hardest, (comparisons', alloys'))
where (mAlloy, mAlloys') = S.deleteFindMin alloys
softers = S.filter isSofter alloys
isSofter alloy = any (\(Harder _ b) -> b == alloy) comparisons
hardest = S.findMin $ S.difference alloys softers
alloys' = S.delete hardest alloys
comparisons' = S.filter (\(Harder a _) -> a /= hardest) comparisonsFinally, the I convert the list of alloys into the number signature.
part1 :: [S.Set Harder] -> Int
part1 groups = sum $ fmap (summarise . handleGroup) groups
summarise :: [Int] -> Int
summarise ds = foldl' (\t n -> t * 10 + n) 0 dsThis version is in the Main.hs file.
Approach 2: using the Graph library
Haskell comes with a Data.Graph library in the containers package, and that has a topSort function built in. Can I use that?
Yes, but the plumbing needed isn't worth it for this case.
To use the topSort function, first I need to build the graph. The expected way to do this is with the graphFromEdges function, which takes a list of vertices with their out-edges. There's no way to extend a graph once it's built. That means I need to find all the vertices and edges, even the implicit ones.
I thought the easiest way to get to this was to use a series of Map structures, each having a key of an alloy and a value of all the alloys that are known to be softer. I start by converting each comparison into a Map from one alloy to exactly one other.
That means a new type for Harder and new parsing code to directly create the initial maps.
type Harder = M.Map Int (S.Set Int)
groupsP :: Parser [[Harder]]
comparisonsP :: Parser [Harder]
comparisonP, softerP, harderP :: Parser Harder
groupsP = comparisonsP `sepBy` endOfLine
comparisonsP = comparisonP `sepBy` (char ' ')
comparisonP = softerP <|> harderP
softerP = softify <$> decimal <* "<" <*> decimal
where softify b a = M.singleton a (S.singleton b)
harderP = hardify <$> decimal <* ">" <*> decimal
where hardify a b = M.singleton a (S.singleton b)
successfulParse :: Text -> [[Harder]]
successfulParse input =
case parseOnly groupsP input of
Left _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
Right groups -> groupsI can combine all those maps with the unionsWith function, and that will take care of combining all the edges. In the end, each key in the map will be one alloy, and the value will be all the alloys that are softer.
As above, I need to have an explicit list of all the alloys on both ends of the comparisons. I've already got a Map for each alloy on the harder end. I can create a Map for each alloy on the softer end, with the value being an empty set.
That all gets done in the revised handleGroup. I generate some leaves for the softer alloy in each comparison. I take the maps for all the comparisons and all the leaves and merge them into one large merged map. I then walk over merged to generate the list of "edges" that feed into graphFromEdges. Finally, I call topSort and extract the alloy IDs.
handleGroup :: [Harder] -> [Int]
handleGroup harders = sortedKeys
where leaves = [ M.singleton leaf S.empty
| h <- harders
, leaf <- S.toList (head $ M.elems h)
]
merged = M.unionsWith S.union (harders ++ leaves)
edges = [ (k, k, S.toList vs) | (k, vs) <- M.toList merged]
(graph, nodeFromVertex, _vertexFromKey) = G.graphFromEdges edges
sortedGraph = G.topSort graph
sortedKeys = [k | v <- sortedGraph, let (k, _, _) = nodeFromVertex v]All in all, a lot of faff to make use of one library function. For this example, I think the direct implementation of Kahn's algorithm was less effort.
This version is in the MainGraph.hs file.
Approach 3: exploiting some special features
The input to this puzzle was kind, in that all the alloys were indexed by integers, starting at 1. By coincidence, the Data.Graph library uses integers internally to represent vertices. That meant I could cheat a bit and use the supplied alloy numbers as the same integers in the library, bypassing the need to have a richer representation of vertices. All I needed to find was the range of the integers used in the input, then pass all the comparisons to the buildG function.
handleGroup :: S.Set Harder -> [Int]
handleGroup harders = G.topSort graph
where allAlloys = foldl' (\acc (Harder a b) -> S.union acc $ S.fromList [a, b]) S.empty harders
maxAlloy = maximum allAlloys
edges = [(a, b) | (Harder a b) <- S.toList harders]
graph = G.buildG (1, maxAlloy) edgesThis is neater than the other versions, but not as general. This version is in the MainGraph2.hs file.
Code
You can get the code from Codeberg. or on my self-hosted Git site.