# Advent of Code, day 7 [spoilers]

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.

steemstem (73)3 years agoThis post has been voted on by the

SteemSTEMcuration 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.witnessandcurie!For additional information please join us on the

SteemSTEM discordand to get to know the rest of the community!