The Ordered Jobs Kata

"""
The Ordered Jobs Kata

Python solution by Mark Frimston (@Frimkron)

Kata by Martin Rue (@MartinRue)
http://invalidcast.com/2011/09/the-ordered-jobs-kata#more-513
"""


def walk_deps(deps,job,result,path):

    for d in deps[job]:
        if d in path:
            raise ValueError("Jobs cannot have circular dependencies")

        walk_deps(deps,d,result,path+[job])

    if not job in result:
        result.append(job)


def order_jobs(jobs):

    if len(jobs) == 0:
        return ""

    deps = {}
    for line in jobs.split("\n"):
        j,d = map(str.strip, line.split("=>"))
        if j == d:
            raise ValueError("Jobs cannot depend on themselves")
        if not j in deps:
            deps[j] = []
        if len(d)>0:
            deps[j].append(d)

    result = []
    for j in deps:
        walk_deps(deps,j,result,[])

    return "".join(result)


if __name__ == "__main__":
    import unittest

    class TestOrderJobs(unittest.TestCase):

        def test_empty_string(self):
            self.assertEquals("",order_jobs(""))

        def test_single_job(self):
            self.assertEquals("a", order_jobs("a =>"))

        def test_multiple_jobs(self):
            result = order_jobs(
                "a =>\n"
                +"b =>\n"
                +"c =>"
            )
            self.assertTrue(all([j in result for j in "abc"]))

        def test_single_dependency(self):
            result = order_jobs(
                "a =>\n"
                +"b => c\n"
                +"c =>"
            )
            self.assertTrue(all([j in result for j in "abc"]))
            self.assertTrue(result.index("c") < result.index("b"))

        def test_multiple_dependencies(self):
            result = order_jobs(
                "a =>\n"
                +"b => c\n"
                +"c => f\n"
                +"d => a\n"
                +"e => b\n"
                +"f =>"
            )
            self.assertTrue(all([j in result for j in "abcdef"]))
            self.assertTrue(result.index("c") < result.index("b"))
            self.assertTrue(result.index("f") < result.index("c"))
            self.assertTrue(result.index("a") < result.index("d"))
            self.assertTrue(result.index("b") < result.index("e"))

        def test_self_referencing(self):
            try:
                order_jobs(
                    "a =>\n"
                    +"b =>\n"
                    +"c => c"
                )
                self.assertTrue(False)
            except Exception as e:
                self.assertEquals(ValueError, type(e))
                self.assertEquals("Jobs cannot depend on themselves",str(e))

        def test_circular_dependency(self):
            try:
                order_jobs(
                    "a =>\n"
                    +"b => c\n"
                    +"c => f\n"
                    +"d => a\n"
                    +"e =>\n"
                    +"f => b"
                )
                self.assertTrue(false)
            except Exception as e:
                self.assertEquals(ValueError, type(e))
                self.assertEquals("Jobs cannot have circular dependencies",str(e))


    unittest.main()