On Wednesday, January 8, 2014 6:57:58 AM UTC-8, Nicolas Neuss wrote:
|Xah Lee writes:
|
||Programing Challenge: Constructing a Tree Given Its Edges.
||Show you are the boss.
||
http://xahlee.info/perl-python/python_construct_tree_from_edge.html
|
||here's plain text.
||────────── ────────── ────────── ────────── ──────────
|
||Problem: given a list of edges of a tree: [child, parent], construct the tree.
||Here's a sample input: [[0, 2], [3, 0], [1, 4], [2, 4]].
|
||Here's a sample print of a tree data structure:
|
||4
|| 1
|| 2
|| 0
|| 3
||You can choose your own data structure for the output.
|
|Hmm, isn't
|
| (defun make-tree (edges)
| edges)
|
|already a correct answer?
|
|Took me 10 seconds.
|
|Nicolas
Well, assuming that the output is supposed to be in some sort of indented tree output form, I came up with the following. Still don't understand why it should take 5 hours, though.
This isn't as efficient as it could be, since the search for root nodes in the data structure is N^2. It would be more efficient to keep track of the root nodes in a separate structure and update it. I'll leave that as an exercise for the reader:
(defstruct node id children)
(defun print-tree (node &optional (depth 0))
(format t "~vT~S~%" (* 2 depth) (node-id node))
(incf depth)
(loop for child in (node-children node)
do (print-tree child depth)))
(defun get-root-nodes (node-hashtable)
(flet ((is-root (node node-hashtable)
(loop for n being the hash-values of node-hashtable
never (member node (node-children n)))))
(loop for node being the hash-values of node-hashtable
when (is-root node node-hashtable) collect node)))
(defun output-trees (node-hashtable)
(loop for root in (get-root-nodes node-hashtable)
do (print-tree root)))
(defun make-tree (edges)
(let ((nodes (make-hash-table)))
(loop for (child parent) in edges
do (let ((child-node (gethash child nodes))
(parent-node (gethash parent nodes)))
(unless child-node
(setq child-node (make-node :id child))
(setf (gethash child nodes) child-node))
(unless parent-node
(setq parent-node (make-node :id parent))
(setf (gethash parent nodes) parent-node))
(push child-node (node-children parent-node))))
nodes))