Monday, March 12, 2012

1 minute puzzle

Given a procedure that returns a list of the children of a given node of a tree, write a procedure that returns a list of all the descendants of that node.


  1. OK (interpreting 'descendants' as including the root).

    Incorrect solution (descendants = concatMap descendants . children): 20 seconds
    Unsuccessfully trying to look up the Racket equivalent of concatMap: 5 minutes (it's append-map, but I had to consult SRFI-1 to discover that)
    Deciding to stick with Haskell: 5 seconds
    Deciding to actually test it, and finding codepad (via Try Haskell): 1 minute and a painful admission of fallibility
    Implementation, and fixing the bug: 3 minutes
    Vacillating between different tree structures: 5 minutes
    Type errors (recursive type synonym and confusing print with shows): 4 minutes

    That adds up to one minute, right?

  2. Hmmm, took 24 times longer than the title, but I did it for graphs, not trees I suppose.

  3. Took me 10 times longer :-)

  4. It likely took me a minute to cruft up a simple car/cdr/cons stack DFS version, but I succumbed to a fit of generalization and result order dinking.

  5. Heh, took me longer to figure out how to format the comment for :-)

    def descent(node, childrenOf):
    ..for child in childrenOf(node):
    ....yield child
    ....for deep in descent(child, childrenOf):
    ......yield deep

  6. Third try:

    (defun descendants^ (node)
    ____(append (children node) (mapcan #'descendants^ (children node))))

    Highlighted at