Fork me on GitHub
#clojure
<
2024-03-02
>
Fredrik Andersson07:03:29

I really can't figure out how to write a tree building algorithm. I have this data ({:context ["root"], :values "lalala1"} {:context ("root" "select-location"), :values "lalala2"} {:context ("root" "select-location"), :values "lalala3"} {:context ("root" "select-vendor"), :values "lalala4"} {:context ("root" "select-vendor"), :values "lalala5"} {:context ("root" "select-vendor"), :values "lalala6"} {:context ["root"], :values "lalala7"} {:context ["root"], :values "lalala8"}) And I want to have this tree at any depth {:context "root", :values ["lalala1" {:context "select-location" :values ["lalala2" "lalala3"]} {:context "select-vendor" :values "lalala4" "lalala5" "lalala6"} "lalala7" "lalala8"]} I can't seem to figure it out 😞

henrik07:03:24

If you give each entry an ID, you can use https://github.com/lilactown/pyramid

Fredrik Andersson07:03:57

Thanks for the suggestion. Seems a little too much to just solve this problem.

kawas08:03:23

What kind of exercise is that? Where did you find it? The output data structure is kind of goofy : Why node values and children nodes are stored in the same place (in any order)? It seems overly complicated to construct 😀

Fredrik Andersson08:03:28

Yeah, it's not an exercise. I'm trying to group logging lines. However I updated the output

Fredrik Andersson08:03:43

I accedentally made it wrong

kawas09:03:51

super goofy solution 😀

(defn update-in-goofy
  [xs ks v]
  (if (empty? ks)
    (conj xs v)
    (let [k (first ks)
          our-context? #(and (map? %) (= k (:context %)) %)
          child (some our-context? xs)]
      (if child
        (conj (remove our-context? xs) (update child :values update-in-goofy (next ks) v))
        (conj xs {:context k
                  :values (update-in-goofy [] (next ks) v)})))))

(defn build-goofy-data
  [data]
  (reduce (fn [acc {:keys [context values]}]
              (update-in-goofy acc context values))
          []
          data))

;; (build-goofy-data input)

Martin Půda11:03:27

(defn solution [data]
  (into [] (comp (partition-by (comp first :context))
                 (mapcat (fn [part]
                           (if (empty? (-> part first :context))
                             (mapv :values part)
                             [{:context (-> part first :context first)
                               :values  (solution (mapv #(update % :context rest) part))}]))))
        data))
(solution data)
=>
[{:context "root",
  :values ["lalala1"
           {:context "select-location", :values ["lalala2" "lalala3"]}
           {:context "select-vendor", :values ["lalala4" "lalala5" "lalala6"]}
           "lalala7"
           "lalala8"]}]

p-himik11:03:56

@U01JYUZRS4V The problem definition is not entirely clear. Your sample data has contexts grouped together - there are no instances of the same context being "split" by a different context. The "root" value is probably special and is always the first item in any :context coll. But what would you expect the result to be when the desired algorithm is applied to this data?

[{:context ["root" "a"] :values 1}
 {:context ["root" "b"] :values 2}
 {:context ["root" "a"] :values 3}]
Is it this?
[{:context "root" :values [{:context "a" :values [1]}
                           {:context "b" :values [2]}
                           {:context "a" :values [3]}]}]
Or this?
[{:context "root" :values [{:context "a" :values [1 3]}
                           {:context "b" :values [2]}]}]
Or something else?

Fredrik Andersson13:03:34

What I really have is a log of activities. I added the context in order to group them because one job could generate hundreds of entries.

Fredrik Andersson13:03:48

And I thought that I could have the context groups foldable in order to make it easier to read the activity log afterwards

Fredrik Andersson13:03:57

so yes, root is a special case, then there can be an arbitrary depth of contexts

Fredrik Andersson13:03:19

everything needs to be rendered in chronological order

p-himik13:03:15

So in those two options in my message above, you need the former one, right? In that case, the solution by Martin is exactly what you need.

Fredrik Andersson13:03:00

yes I would say the first one

Fredrik Andersson13:03:25

and the values beneath context "b" could in turn include contexts

Fredrik Andersson13:03:15

I'm thinking that maybe i should create the context tree first and then hook up the entries into the tree

Fredrik Andersson13:03:36

but that would mess up chronology

p-himik13:03:58

Yeah, just go with the Martin's solution. :) No need to invent something else. Unless your contexts can grow larger than a stack size, but I really doubt that.

Fredrik Andersson13:03:58

No I don't think that's a problem luckily. I'm going to try it out now.

Fredrik Andersson13:03:47

Thank you @U01RL1YV4P7! It seems to be working as I wished.

👍 1