Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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]
(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))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.