Discussion  - 
here's a programing challenge: Constructing a Tree Given Its Edges.
want to try in emacs lisp?

#lisp #python #haskell #ruby #javascript
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. this means, the root node's name is 4. It has 2 branches, named 1 and 2.
Kalman Reti's profile photo
Emacs lisp:

(defun tree-from-edges (foo)
  "reconstruct tree from list of (child parent) lists"
  ;; recursive function to simplify internal data structure for answer
  (flet ((prune (list)
        (cond ((null list) nil)
              ((not (listp list)) list)
              (t (cons (prune (car list)) (loop for i in (cddr list) collect (prune i)))))))

  ;;hash table entries are triples of pid, parent dotted to list of children
  (loop with ht = (make-hash-table :test 'equal)
    for (child parent) in foo
    for child-entry = (gethash child ht)
    for parent-entry = (gethash parent ht)
    if child-entry
    do (when (null (second child-entry))
         (setf (second child-entry) parent))
    do (setq child-entry (setf (gethash child ht) (list child parent-entry)))
    if parent-entry
    do (push child-entry (cddr parent-entry))
    do (setq parent-entry (setf (gethash parent ht) (list parent nil child-entry)))
       (setf (second child-entry) parent-entry)
    finally (return (loop for x being the hash-values of ht
                  for (pid parent . children) = x
                  when (null parent)
                  collect (prune x))))))

;; In scratch buffer
(tree-from-edges '((0 2) (3 0) (1 4) (2 4))) =>
((4 (2 (0 (3))) (1)))
For larger test cases, I used

ps -eaf | awk '{print $2, $3}'

in a shell buffer then

(defun read-data (symbol)
  (set symbol (loop for child = (ignore-errors (read (current-buffer)))
            while child
            for parent = (read (current-buffer))
            collect (list child parent))))

 (read-data 'foo)

to get the data into a variable.  I compared my output with pstree.  From start to finish, about an hour.
Add a comment...