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.


Arcane Sentiment said...

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?

Unknown said...

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

chturne said...

Took me 10 times longer :-)

Christopher Oliver said...

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.

Unknown said...

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

Unknown said...

Third try:

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

Highlighted at