amalloy-4clojure-solution130.clj

;; amalloy's solution to Tree reparenting
;; https://4clojure.com/problem/130

(fn [new-root tree]
  (let [connections ((fn links [tree]
                       (when-let [[root & children] (seq tree)]
                         (let [child-links (apply merge {} (map links children))
                               conj (fnil conj [])]
                           (reduce (fn [m [child]]
                                     (-> m
                                         (update-in [root] conj child)
                                         (update-in [child] conj root)))
                                   child-links
                                   children))))
                     tree)]
    (second
     ((fn dangle [edges root]
        (if-let [children (not-empty (get edges root))]
          (let [edges (reduce (fn [edges from]
                                (update-in edges [from]
                                           #(remove #{root} %)))
                              (dissoc edges root)
                              children)]
            (reduce (fn [[edges tree] child]
                      (let [[new-edges new-tree] (dangle edges child)]
                        [new-edges (conj tree new-tree)]))
                    [edges [root]]
                    children))
          [edges [root]]))
      connections new-root))))