Start by munging the input:

parse = graph . map (l . words . filter (/= ':')) . lines
  where
    l (node : edges) = (node, edges)

Our graph representation is a map of nodes to the list of outgoing edges:

import qualified Data.Map as M

graph ls =
  M.union
    (M.fromList ls)
    (M.fromList [(e, []) | (_, es) <- ls, e <- es])

This, the edge list (a list of (node, edge)) is given by:

edges = concatMap (\(n, e) -> map (n,) e) . M.toList

And the list of nodes is simply:

nodes = M.keys

The list of neighbours of a node:

neighbours = (M.!)

That forms our primitive graph library, onto the solution itself!

The first part requires us to find all paths from one node in the digraph to another node. An algorithm for this is to traverse the graph in topological order, and the number of “ways” into each node would be them sum of ways into all neighbours.

To first sort the nodes in topo-order however, we need to know the indegrees of all nodes. Every destination node in the edge-list has an indegree of 1, so sum those up, and then combine with all nodes. The second step is necessary to include those nodes aren’t present in the edge-list already. Recall that M.union is left-biased, so we won’t be overwriting calculations.

indeg :: (Ord a) => M.Map a [a] -> M.Map a Int
indeg =
  M.union
    <$> M.fromListWith (+) . map ((,1) . snd) . edges
    <*> M.fromList . map (,0) . nodes

Thus, our toposort algorithm is given by:

toposort m
  | M.size m == 0 = []
  | otherwise = start ++ toposort rest
  where
    start = nodes . M.filter (== 0) $ indeg m
    rest = foldr M.delete m start

Now, to calculate the number of paths, given a graph, a start node and an end node, we define paths like so:

paths g src dst = foldl' go start (toposort g) M.! dst
  where
    start =
      M.insert src 1
        . M.fromList
        . map (,0)
        . nodes
        $ g

    go ways node =
      M.unionWith (+) ways (upd ways node)

    upd ways node =
      M.fromList
        . map (,ways M.! node)
        $ neighbours g node

To explain a bit further

• start: this is the initial Map containing the number of paths from start to all other nodes in the graph. The number of paths from start to itself is 1
• go: this is the fold function that runs on every node in topo-order. We simply update the ways map and combine with the existing map
• upd: find the neighbours of this node, and update their entry in the ways Map to be equal to the number of ways to get to node

Thus, the solution to the first part is given as:

p1 n = paths n "you" "out"

And the solution to the second part is given as:

p2 n =
  product
    [ paths n "svr" "fft",
      paths n "fft" "dac",
      paths n "dac" "out"
    ]
  +
  product
    [ paths n "svr" "dac",
      paths n "dac" "fft",
      paths n "fft" "out"
    ]

Because in a digraph, the number of paths from A -> B via C, is given by the product of paths from A -> B and B -> C.

Finally, a main function to wrap it all up:

main = do
  n <- parse <$> getContents
  print $ p1 n
  print $ p2 n