Interesting (hopefully) ELISP problem

[Suttles, Andrew]

I recently noted an interesting problem on the beginners@perl.org list,
where a poster was asked, on a job interview, to format the following
data into a tree structure.  After I thought about a potential perl
solution for a few minutes, I thought this might be better solved in
LISP.  I know THIS is not a LISP forum, but ELISP is the only LISP I
know, and I thought this might be an interesting problem to use to try
to sharpen my newbie ELISP skills.  As you see below, my solution is
almost usable, but not quite right.  Thanks for any help anyone can
provide to help me - not even neccessarily to get the correct answer,
but rather to learn how to solve problems in ELISP.


PROBLEM FOLLOWS:
----------------

I have the following data in a text file;

    A B C D E F G
    A B C D E F H
    A B C D E F I J
    A B C D K L
    A B C D M N
    A B C D O P
    A B C D Q R
    A S T
    A S U

I need to massage the data and print it out (to the screen or file) as
follows:

    A 
      B C D 
            E F 
                G
                H
                I J
            K L
            M N
            O P
            Q R
      S 
        T
        U


MY SOLUTION
------------

My first hack on this is below.  Please feel free to comment on any part
of it that you would think would be helpful to my learning (style, data
structure, etc).  For now, I'm only trying to build the tree, I'll print
it later.  Also, if you run this code, please note that I have emacs
installed on a seperate machine from the one that I can e-mail from so
the following is hand copied (hopefull without mistake, but a missing
paren or odd indent may be due to copy error - sorry).



(defun add-branch (tree branch)
  "Add a new branch and leaves to the tree"
  (cond
   ;; Empty Tree
   ((null tree)
    branch)
   ;; Turn Leaf into Branch
   ((atom (car tree))
     (if (eq (car tree) (car branch))
         (cons (car tree) (add-branch (cdr tree) (cdr branch)))
       (list (append tree branch))))
   ;; New Leaves on a Branch
   (t (list
        (append
          (mapcar
            (lambda (x)
              (let ((old-branch
                      (if (atom x) (list x) x))
                    (new-branch branch))
                 (if (eq (car new-branch) (car old-branch))
                     (progn
                       (setq branch nil)
                       (add-branch old-branch new-branch))
                    x)))
               (car tree))
              (if (not (null branch))
                  (list branch)))))))

(defun build-tree (listoflists &optional tree)
   "Build a tree using tail recursion from a list of lists"
   (let ((tree (if tree tree '())))
      (if (null listoflists)
          tree
        (build-tree (cdr listoflists)
                    (add-branch tree (car listoflists))))))

(princ
  (build-tree '((A B C D E F G)
                (A B C D E F H)
                (A B C D E F I J)
                (A B C D K L)
                (A B C D M N)
                (A B C D O P)
                (A B C D Q R)
                (A S T)
                (A S U))))

>> (A (B C D (E F (G H (I J)) K L (M N) (O P) (Q R)) (S U) T))






Andrew Suttles