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.