The Day 7 puzzle is about parallel builds. So, just convert your input into a Makefile and solve it with GNU Make!
OK, maybe not. I probably could have gotten that working in less time than it took me to wrestle with the Data.Graph library, though.
Input looks like this:
exampleInput = [r|Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.|]
I over-parsed it; note that the characters are always in the same location within each line. (Also, the steps only go A through Z in the full input.)
stepToVertex :: Char -> Int
stepToVertex c = (ord c) - (ord 'A')
vertexToStep :: Int -> Char
vertexToStep i = chr (i + (ord 'A'))
parseDependency :: String -> (Int, Int)
parseDependency s =
let tok = splitOn " " s in
(stepToVertex (head (tok !! 1)),
stepToVertex (head (tok !! 7)))
dependencies = sort( map parseDependency (splitOn "\n" input) )
maxVertex = maximum (concat [[s,t] | (s,t) <- dependencies])
g = buildG (0,maxVertex) dependencies
OK, looks fairly straightforward, right? This was version 2. Originally I tried keeping the labels of the graph as the original characters. Python's networkx library makes that easy, and it's what I was used to working with. So my first version was thins:
parseDependency :: String -> (Char, Char)
parseDependency s =
let tok = splitOn " " s in
(head (tok !! 1),
head (tok !! 7))
dependencies = sort( map parseDependency (splitOn "\n" input) )
dependentEdges = groupBy (\x -> \y -> (fst x) == (fst y)) dependencies
toNode ((src,dst):rest) = ( src, src, [dst] ++ (map snd rest) )
dependentAdj = map toNode dependentEdges
(g, nodeFromVertex, vertexFromKey) =
graphFromEdges dependentAdj
The name "graphFromEdges" is a lie. It doesn't take a list of edges. It takes a list of 3-tuples (key, node, [adjacency list]). So, I figured out groupBy which wasn't too bad. But this code has a near-fatal error.
The problem is that the final node of the dependency tree has no outgoing edges, so it doesn't appear in dependentEdges, and so it's not one of the three-tuples. But graphFromEdges doesn't complain about the edges leading to a nonexistent node, no, that would be too easy and helpful. Instead it just ignores them silently.
This interface is the worst ever.
So I rewrote it to use the method that actually does take an edge list, but the price is I had to do all the vertex->integer conversion myself. Whatever.
The version of topological sort on RosettaCode is incomprehensible to me, so I wrote one that does the job recursively, at the cost of inefficient queue management.
type IndegreeMap = Array Int Int
initIndegrees = indegree g
initQueue = map fst (filter (\x -> (snd x) == 0) (assocs initIndegrees))
nextNode :: [Vertex] -> Vertex
nextNode = minimum
myTopSort :: [Vertex] -> Array Vertex Int -> [Vertex] -> [Vertex]
myTopSort [] _ visited = visited
--myTopSort queue indegrees visited
-- | trace ( "Q" ++ (show queue) ++ " I" ++ (show indegrees) ++ " V" ++ (show visited )) False = undefined
myTopSort queue indegrees visited =
let n = nextNode queue in
let out = g ! n in
(myTopSort
( (delete n queue) ++ (filter (\nb -> (indegrees ! nb) == 1 ) out) )
(accum (-) indegrees [ (o,1) | o <- out ] )
(visited ++ [n])
)
visit = myTopSort initQueue initIndegrees []
With this approach, part 2 is a butt-buster and I haven't finished it yet. I really don't have any clue how to actually simulate all the build steps in Haskell in a good way. I wrote a big data structure and am working on operations on the state, like "start a job" and "finish a job" and "advance time." But this feels very non-Haskell-ish.
data WorkerState = WorkerState {
time :: Int,
availableWorkers :: Int,
jobDependencies :: Array Vertex Int,
availableJobs :: [Vertex],
jobsInProgress :: [(Int,Vertex)]
finishedJobs :: [(Int,Vertex)]
} deriving Show
Probably I'm missing something clever and graph-theoretical.
This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @curie.
If you appreciate the work we are doing then consider voting both projects for witness by selecting stem.witness and curie!
For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!