104 lines
4.2 KiB
Common Lisp
104 lines
4.2 KiB
Common Lisp
|
|
;; The challenge: You are given a list of tasks, some of which depend on
|
|
;; others. Write a function which will takes a subset of those tasks and
|
|
;; returns an ordered list of all the tasks to run.
|
|
|
|
|
|
;; My algorithm for append dependancies uses a recursive function
|
|
;; This treats the dependancies like a tree
|
|
;; The recursive algorithm traverses down the tree, then comes back up
|
|
;; appending along the way
|
|
|
|
|
|
;; Recursive function to add each task to the list
|
|
;; Use caution as recursive functions can overwhelm the stack
|
|
;; Recursion is used here as it simplifies appending new values
|
|
(def add-next (defined-depends, ordered-tasks, chosen-task)
|
|
(var is-valid-task false)
|
|
;; Grab the task we are attempting to add and check it's dependancies
|
|
(each (each-defined-depends) defined-depends
|
|
(if (= each-defined-depends.task chosen-task) (do
|
|
(assign is-valid-task true)
|
|
(each (each-depends-depend) each-defined-depends.depends
|
|
;; If the dependancy has not been added
|
|
;; Add it using add-next, this keeps things in order
|
|
(unless (includes? ordered-tasks each-depends-depend)
|
|
(assign ordered-tasks
|
|
(add-next defined-depends ordered-tasks each-depends-depend)
|
|
)
|
|
)
|
|
)
|
|
))
|
|
)
|
|
|
|
;; If we are given a valid task include it if it's not already there
|
|
;; If it's a bad task append "undefined" to be checked later
|
|
(if is-valid-task
|
|
(if (not (includes? ordered-tasks chosen-task))
|
|
(assign ordered-tasks (append ordered-tasks chosen-task))
|
|
)
|
|
(assign ordered-tasks (append ordered-tasks "undefined"))
|
|
)
|
|
ordered-tasks
|
|
)
|
|
|
|
;; Determines all tasks needed in what order
|
|
(def determine-order (defined-depends, chosen-tasks)
|
|
;; Loop through each of the chosen tasks to add them to the list
|
|
;; Use add-next recursive function
|
|
(var sorted [])
|
|
(each (each-chosen-task) chosen-tasks
|
|
(assign sorted (add-next defined-depends sorted each-chosen-task))
|
|
)
|
|
|
|
;; If any part of the returned result is undefined we were given bad tasking
|
|
(if (includes? sorted "undefined")
|
|
(assign sorted ["undefined"])
|
|
)
|
|
|
|
sorted
|
|
)
|
|
|
|
;; Run the tests and verify the results
|
|
;; expected-result is ", " sperated string representing the array
|
|
(def run-test (test-num example-defined-depends chosen-tasks expected-result)
|
|
(assign test-var (join (determine-order example-defined-depends chosen-tasks) ", "))
|
|
;;(assign test-var (determine-order example-defined-depends chosen-tasks))
|
|
(if (= test-var expected-result)
|
|
(console.log ("-- success -- Test " test-num " -- " test-var))
|
|
(console.log ("-- failure -- Test " test-num " -- " test-var))
|
|
)
|
|
)
|
|
|
|
;; Test set sandwich
|
|
(var example-tasks
|
|
[
|
|
{task "make a sandwich", depends ["buy groceries"]}
|
|
{task "buy groceries", depends ["go to the store"]}
|
|
{task "go to the store", depends []}
|
|
]
|
|
)
|
|
|
|
(run-test 1 example-tasks ["make a sandwich"] "go to the store, buy groceries, make a sandwich")
|
|
(run-test 2 example-tasks ["buy groceries" "make a sandwich"] "go to the store, buy groceries, make a sandwich")
|
|
(run-test 3 example-tasks ["buy groceries"] "go to the store, buy groceries")
|
|
(run-test 4 example-tasks ["make a sandwich" "buy groceries"] "go to the store, buy groceries, make a sandwich")
|
|
(run-test 5 example-tasks ["make sandwich" "buy groceries"] "undefined")
|
|
|
|
;; Test set wrap
|
|
(var example-tasks
|
|
[
|
|
{task "make a wrap", depends ["buy hummus", "buy wrap", "buy veggies"]}
|
|
{task "buy hummus", depends ["go to the store"]}
|
|
{task "buy wrap", depends ["go to the store"]}
|
|
{task "buy veggies", depends ["go to the store"]}
|
|
{task "go to the store", depends []}
|
|
]
|
|
)
|
|
|
|
(run-test 6 example-tasks ["make a wrap"] "go to the store, buy hummus, buy wrap, buy veggies, make a wrap")
|
|
(run-test 7 example-tasks ["go to the store" "make a wrap"] "go to the store, buy hummus, buy wrap, buy veggies, make a wrap")
|
|
(run-test 8 example-tasks ["buy wrap" "go to the store" "make a wrap"] "go to the store, buy wrap, buy hummus, buy veggies, make a wrap")
|
|
(run-test 9 example-tasks ["go to the store" "make a sandwich"] "undefined")
|
|
|