ericnormand/00 Dependency ordering.md

## 00 Dependency ordering.md

      
  Raw
  

              00 Dependency ordering.md
            
          
    task dependencies
Let's say you're writing a project management app. A user will have a bunch of tasks to do and each task might depend on other tasks. Your challenge is to write a function that, given tasks and dependencies, gives at least one order for the tasks such that no task is done before its dependencies are done.
(def tasks [:clean-breakfast :shoes :socks :cook-breakfast :eat-breakfast])

(def dependencies [[:socks :shoes] ;; socks come before shoes; shoes depend on socks
                   [:cook-breakfast :eat-breakfast] ;; cooking comes before eating
                   [:eat-breakfast :clean-breakfast]])
(defn order-tasks [tasks dependencies]
 ;; you fill this out
 )

(order-tasks tasks dependencies) => [:socks :shoes :cook-breakfast :eat-breakfast :clean-breakfast]

  
## Alan Thompson.clj
(ns tst.demo.core
  (:use demo.core tupelo.core tupelo.test)
  (:require
    [schema.core :as s]
    [tupelo.schema :as tsk]
    [clojure.set :as set]))

; use a set of maps, since a set is unordered and maps enforce exactly 2 items/ordering
(s/def deps-orig :- [tsk/Pair]
  [[:socks :shoes]
   [:cook :eat]
   [:eat :clean]])

(s/def all-tasks :- #{s/Keyword}
  (into #{} (flatten deps-orig)))

(def DepsMap  { s/Keyword [s/Keyword]})
(s/def deps :- DepsMap
  "A map from a task to everything it depends on"
  (let [base-deps-map (zipmap all-tasks (repeat []))
        result        (reduce (s/fn [deps-accum :- DepsMap
                                     curr-dep :- tsk/Pair]
                                (let [[task-1 task-2] curr-dep]
                                  (update deps-accum task-2 append task-1)))
                        base-deps-map
                        deps-orig)]
    result))

(s/defn deps-satisfied? :- s/Bool
  "Return true iff a task has all deps satisfied"
  [task :- s/Keyword
   tasks-done :- [s/Keyword]]
  (let [task-deps      (set (grab task deps))
        deps-remaining (set/difference task-deps (set tasks-done))
        result         (empty? deps-remaining)]
    result))

(s/defn order-tasks []
  (loop [tasks-done      []
         tasks-remaining all-tasks] ; a set
    (if (empty? tasks-remaining)
      tasks-done
      (let [tasks-ready (keep-if #(deps-satisfied? % tasks-done) tasks-remaining) ; aka `filter` , returns a set
            >>          (when (empty? tasks-ready)
                          (throw (ex-info "Could not find available task!" (vals->map tasks-done tasks-remaining tasks-ready))))
            task-next   (rand-nth (vec tasks-ready))] ; must convert set -> vector before `rand-nth`
        (recur
          (append tasks-done task-next)
          (disj tasks-remaining task-next))))))

(dotest
  (is= all-tasks #{:cook :shoes :socks :eat :clean})
  (is= deps {:cook [], :shoes [:socks], :socks [], :eat [:cook], :clean [:eat]} )
  (is (deps-satisfied?  :cook []))
  (isnt (deps-satisfied?  :shoes []))
  (is (deps-satisfied? :shoes [:socks]))
  (dotimes [i 5]
    (spyx (order-tasks)))
  )

## Eric Normand.clj
(def tasks [:clean-breakfast :shoes :socks :cook-breakfast :eat-breakfast])

(def dependencies [[:socks :shoes] ;; socks come before shoes; shoes depend on socks
                   [:cook-breakfast :eat-breakfast] ;; cooking comes before eating
                   [:eat-breakfast :clean-breakfast]])

(defn grouping
  "Group elements of coll into a map. The key for grouping is
  found by calling keyfn on the element. The value is found
  by calling valfn on the element. Elements are added to a
  set in the map.

  Example: (grouping first second [[:a 1] [:b 2] [:a 3] [:c 2]])

  => {:a #{1 3} :b #{2} :c #{2}}
  "
  [keyfn valfn coll]
  (reduce (fn [acc val]
            (let [k (keyfn val)
                  v (valfn val)]
              (update acc k (fnil conj #{}) v)))
          {} coll))

(defn ungroup
  "Remove a nested value from a grouping. If removing the
  value results in an empty collection, remove the key as
  well.

  Example: (ungroup {:a #{1 3} :b #{2} :c #{2}} :a 3)
  ;; removes this 3         ^   given key & val ^  ^
  => {:a #{1} :b #{2} :c #{2}}
  "
  [map k v]
  (let [vs (get map k)
        vs' (disj vs v)]
    (if (empty? vs')
      (dissoc map k)
      (assoc map k vs'))))

(defn order-tasks
  "Order tasks according to a list of dependencies. Only
  returns one possible order. If no order is possible, it
  returns the keyword :no-order. This could happen if
  dependencies are unmet (don't appear in the tasks
  collection) or there is a cycle in the dependencies.

  dependencies must be a list of pairs. The pair indicates
  that the first element must precede the second."
  [tasks dependencies]
  (let [rdeps (grouping first second dependencies)]
    (loop [deps (grouping second first dependencies)
           remaining (set tasks)
           order []]
      (let [possible (filter #(empty? (get deps %)) remaining)
            f (first possible)]
        (cond
          (empty? remaining)
          order

          (empty? possible)
          :no-order

          :else
          (recur (reduce #(ungroup %1 %2 f) deps (get rdeps f))
                 (disj remaining f)
                 (conj order f)))))))

(defn order-tasks-recursive
  "Order tasks according to a list of dependencies. Only
  returns one possible order. If no order is possible, it
  returns the keyword :no-order. This could happen if
  dependencies are unmet (don't appear in the tasks
  collection) or there is a cycle in the dependencies.

  dependencies must be a list of pairs. The pair indicates
  that the first element must precede the second."
  ([tasks dependencies]
   (order-tasks-recursive (grouping first second dependencies)
                          (grouping second first dependencies)
                          (set tasks)))
  ([rdeps deps remaining]
   (let [possible (filter #(empty? (get deps %)) remaining)
         f (first possible)]
     (cond
       (empty? remaining)
       ()

       (empty? possible)
       :no-order

       :else
       (let [next (order-tasks-recursive
                   rdeps
                   (reduce #(ungroup %1 %2 f) deps (get rdeps f))
                   (disj remaining f))]
         (if (coll? next)
           (cons f next)
           next))))))
	(ns tst.demo.core
	(:use demo.core tupelo.core tupelo.test)
	(:require
	[schema.core :as s]
	[tupelo.schema :as tsk]
	[clojure.set :as set]))

	; use a set of maps, since a set is unordered and maps enforce exactly 2 items/ordering
	(s/def deps-orig :- [tsk/Pair]
	[[:socks :shoes]
	[:cook :eat]
	[:eat :clean]])

	(s/def all-tasks :- #{s/Keyword}
	(into #{} (flatten deps-orig)))

	(def DepsMap { s/Keyword [s/Keyword]})
	(s/def deps :- DepsMap
	"A map from a task to everything it depends on"
	(let [base-deps-map (zipmap all-tasks (repeat []))
	result (reduce (s/fn [deps-accum :- DepsMap
	curr-dep :- tsk/Pair]
	(let [[task-1 task-2] curr-dep]
	(update deps-accum task-2 append task-1)))
	base-deps-map
	deps-orig)]
	result))

	(s/defn deps-satisfied? :- s/Bool
	"Return true iff a task has all deps satisfied"
	[task :- s/Keyword
	tasks-done :- [s/Keyword]]
	(let [task-deps (set (grab task deps))
	deps-remaining (set/difference task-deps (set tasks-done))
	result (empty? deps-remaining)]
	result))

	(s/defn order-tasks []
	(loop [tasks-done []
	tasks-remaining all-tasks] ; a set
	(if (empty? tasks-remaining)
	tasks-done
	(let [tasks-ready (keep-if #(deps-satisfied? % tasks-done) tasks-remaining) ; aka `filter` , returns a set
	>> (when (empty? tasks-ready)
	(throw (ex-info "Could not find available task!" (vals->map tasks-done tasks-remaining tasks-ready))))
	task-next (rand-nth (vec tasks-ready))] ; must convert set -> vector before `rand-nth`
	(recur
	(append tasks-done task-next)
	(disj tasks-remaining task-next))))))

	(dotest
	(is= all-tasks #{:cook :shoes :socks :eat :clean})
	(is= deps {:cook [], :shoes [:socks], :socks [], :eat [:cook], :clean [:eat]} )
	(is (deps-satisfied? :cook []))
	(isnt (deps-satisfied? :shoes []))
	(is (deps-satisfied? :shoes [:socks]))
	(dotimes [i 5]
	(spyx (order-tasks)))
	)
	(def tasks [:clean-breakfast :shoes :socks :cook-breakfast :eat-breakfast])

	(def dependencies [[:socks :shoes] ;; socks come before shoes; shoes depend on socks
	[:cook-breakfast :eat-breakfast] ;; cooking comes before eating
	[:eat-breakfast :clean-breakfast]])

	(defn grouping
	"Group elements of coll into a map. The key for grouping is
	found by calling keyfn on the element. The value is found
	by calling valfn on the element. Elements are added to a
	set in the map.

	Example: (grouping first second [[:a 1] [:b 2] [:a 3] [:c 2]])

	=> {:a #{1 3} :b #{2} :c #{2}}
	"
	[keyfn valfn coll]
	(reduce (fn [acc val]
	(let [k (keyfn val)
	v (valfn val)]
	(update acc k (fnil conj #{}) v)))
	{} coll))

	(defn ungroup
	"Remove a nested value from a grouping. If removing the
	value results in an empty collection, remove the key as
	well.

	Example: (ungroup {:a #{1 3} :b #{2} :c #{2}} :a 3)
	;; removes this 3 ^ given key & val ^ ^
	=> {:a #{1} :b #{2} :c #{2}}
	"
	[map k v]
	(let [vs (get map k)
	vs' (disj vs v)]
	(if (empty? vs')
	(dissoc map k)
	(assoc map k vs'))))

	(defn order-tasks
	"Order tasks according to a list of dependencies. Only
	returns one possible order. If no order is possible, it
	returns the keyword :no-order. This could happen if
	dependencies are unmet (don't appear in the tasks
	collection) or there is a cycle in the dependencies.

	dependencies must be a list of pairs. The pair indicates
	that the first element must precede the second."
	[tasks dependencies]
	(let [rdeps (grouping first second dependencies)]
	(loop [deps (grouping second first dependencies)
	remaining (set tasks)
	order []]
	(let [possible (filter #(empty? (get deps %)) remaining)
	f (first possible)]
	(cond
	(empty? remaining)
	order

	(empty? possible)
	:no-order

	:else
	(recur (reduce #(ungroup %1 %2 f) deps (get rdeps f))
	(disj remaining f)
	(conj order f)))))))

	(defn order-tasks-recursive
	"Order tasks according to a list of dependencies. Only
	returns one possible order. If no order is possible, it
	returns the keyword :no-order. This could happen if
	dependencies are unmet (don't appear in the tasks
	collection) or there is a cycle in the dependencies.

	dependencies must be a list of pairs. The pair indicates
	that the first element must precede the second."
	([tasks dependencies]
	(order-tasks-recursive (grouping first second dependencies)
	(grouping second first dependencies)
	(set tasks)))
	([rdeps deps remaining]
	(let [possible (filter #(empty? (get deps %)) remaining)
	f (first possible)]
	(cond
	(empty? remaining)
	()

	(empty? possible)
	:no-order

	:else
	(let [next (order-tasks-recursive
	rdeps
	(reduce #(ungroup %1 %2 f) deps (get rdeps f))
	(disj remaining f))]
	(if (coll? next)
	(cons f next)
	next))))))