CODEWITHSUNDEEP
listclojuretree
user5877947
user5877947

Reputation:

Creating a tree from a list in Clojure

Hello I am new to Clojure,

I am trying to solve the following problem1

My first step into solving this problem is to write a function that receives a list (in my case, of place names) and turns that into a tree.

(list 'Karlsruhe 'Stuttgart '100 'Stuttgart 'Ulm '80 'Ulm 'Muenchen '120)

I would like the tree to look like this:2

The reason I want the tree to look like that is, I plan to write a function that receives a goal and destination, searches the newly created tree for the goal keeping a note of all the right hand nodes, then at the end, does a check to see which is the smallest and returns that.

I would just like some help/guidance Thanks.

M.

Upvotes: 0

Views: 221

Answers (1)

leetwinski
leetwinski

Reputation: 17859

the thing you are trying to do could be perfectly done without constructing the tree. You have triplets here in your list with source, destination and some number. So i would make a map of source to [destination number] here, for better lookup, and then recursively traverse it:

(def items (list 'Karlsruhe 'Stuttgart '100 
                 'Stuttgart 'Ulm '80 
                 'Ulm 'Muenchen '120))

(def items-lookup-map (into {} 
                        (map (juxt first rest) 
                             (partition 3 items)))

now your lookup map looks like this:

{Karlsruhe (Stuttgart 100), 
 Stuttgart (Ulm 80), 
 Ulm (Muenchen 120)}

so now you can easily write a function that finds a path from source to destination:

(defn find-path [source dest lookup-map]
  (let [[prev [dest & _]] (split-with
                           #(and (not (nil? %)) (not= % dest))
                           (iterate #(first (lookup-map %))
                                    source))]
    (when dest (concat prev [dest]))))

let's test:

user> (find-path 'Karlsruhe 'Ulm items-lookup-map)
(Karlsruhe Stuttgart Ulm)
user> (find-path 'Karlsruhe 'Prague items-lookup-map)
nil
user> (find-path 'Moscau 'Ulm items-lookup-map)
nil

now you can do whatever you want with it, for example find a minimum number in path:

(defn min-distance [src dest lookup-map]
  (when-let [path (seq (find-path src dest lookup-map))]
    (apply min (map #(second (lookup-map %)) (butlast path)))))

user> (min-distance 'Karlsruhe 'Muenchen items-lookup-map)
80

Upvotes: 1

Related Questions