Chris Houser contributed the very pretty problem 130 to 4clojure. I won’t repeat the problem statement here, just my thoughts on how to approach the problem, and my solution.

The strategy is to decompose a complex task into a sequence of simpler tasks. The complex task is to transform a tree: we are given a tree with root r, and some designated node n. The goal is to rewrite the tree representation so that n is the new root. The further n is from r, the more complex the task. It turns out that the task is fairly simple if n is an immediate descendant of r. So the strategy is this. Find the path (sequence of nodes) from r to n, say it is [r a b c n]. We first rewrite the tree so a is the root. Then rewrite that tree so b is the root, etc. It’s that simple.

In the code I will refer to labels rather than nodes. I think of the trees this way. We have a set L of labels. Trees are constructed by induction, as follows.

  • For any element x in L, [x] is a tree.
  • Any vector whose first element is a label and remaining elements are trees is itself a tree.

We consider only trees wherein all labels are distinct, otherwise the problem has no unique solution. Here’s the code.

(defn get-label [x]
  (when (sequential? x) (first x)))

(defn path-to
  "The path from the root of the tree to the label."
  ([label tree] (path-to [] label tree))
  ([path label tree]
     (let [lbl (get-label tree) path (conj path lbl)]
       (if (= label lbl)
         path
         (mapcat (partial path-to path label)
                 (rest tree))))))

(defn lift-local
  "Rewrite the tree so that label is the root.
   Here label is required to belong to a subtree
   immediately descended from the root."
  [tree label]
  (let [match  #(= label (get-label %))
        subtree     (first (filter match tree))
        but-subtree (remove match tree)]
    ;; append but-subtree to subtree
    (concat subtree (list but-subtree))))

(defn lift
  "Rewrite the tree so that label is the root."
  [label tree]
  (reduce lift-local
          tree
          (rest (path-to label tree))))

Final thoughts: I inductively defined trees in terms of vectors, but the code does not depend on vector specific operations, and should work with trees represented by either vectors or lists. For a very different take on this problem, see Meikel Brandmeyer’s solution using logic programming.