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.
at

6 comments:

  1. Arcane SentimentMarch 12, 2012 at 2:57 PM

    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?

    ReplyDelete
  2. UnknownMarch 12, 2012 at 8:11 PM

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

    http://paste.lisp.org/+2R05

    ReplyDelete
  3. chturneMarch 13, 2012 at 6:10 AM

    Took me 10 times longer :-)

    http://paste.lisp.org/display/128318

    ReplyDelete
  4. Christopher OliverMarch 13, 2012 at 9:29 AM

    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.

    http://sprunge.us/PGWV?scheme

    ReplyDelete
  5. UnknownMarch 13, 2012 at 1:26 PM

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

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

    ReplyDelete
  6. UnknownMarch 15, 2012 at 9:02 PM

    Third try:

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

    Highlighted at paste.lisp.org

    ReplyDelete