1
\$\begingroup\$

This program is used to solve Challenge #140 [Intermediate] on /r/dailyprogrammer. The challenge is, given a input set of directed edges, print the corresponding adjacency matrix.

Here is a sample input:

5 5
0 3 -> 1
1 -> 2
2 -> 4
3 -> 4
0 -> 0 3

and the corresponding solution:

11010
00100
00001
01001
00000

Note that there can be more than one edge per line - the set of edges generated is then the Cartesian product of those nodes. For instance, 0 3 -> 1 would generate the edges [(0, 1), (3, 1)].

Here is my solution:

import Data.Function
import Data.Ix
import Data.List
import qualified Data.Set as Set

type Edge = (Integer, Integer)

genGrid :: Integer -> Set.Set Edge -> [[Bool]]
genGrid n edges = (map . map) (`Set.member` edges) coordGrid
  where
    coordGrid = groupBy ((==) `on` fst) coords
    coords = range ((0, 0), (n - 1, n - 1))

parseEdge :: String -> [Edge]
parseEdge s = [(from, to) | from <- outgoing, to <- incoming]
  where
    outgoing = map read (takeWhile (/= "->") split)
    incoming = map read (tail $ dropWhile (/= "->") split)
    split = words s

doChallenge :: [String] -> [String]
doChallenge s = (map . map) pprint (genGrid n edges)
 where
    n = read (head $ words $ head s)
    edges = Set.fromList $ concatMap parseEdge (drop 1 s)
    pprint True = '1'
    pprint _ = '0'

input :: [String]
input = ["5 5", "0 3 -> 1", "1 -> 2", "2 -> 4", "3 -> 4", "0 -> 0 3"]

output :: [String]
output = ["11010", "00100", "00001", "01001", "00000"]

main :: IO ()
main = print $ output == doChallenge input

My main points of focus

  1. Readability of the code
  2. How idiomatic the program is

Assume that the input is well-formed - it's okay if the IO stuff crashes on a bad input.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.