The Ordered Jobs Kata: Dependency Sorting with TDD in C#

A code kata is a small exercise you repeat to sharpen a skill. The Ordered Jobs kata is a favourite because it is tiny to state, rich enough to teach real design, and a perfect match for test-driven development. This article walks through it in C#.

The problem

You are given a list of jobs, each identified by a single letter, and some jobs depend on others. Produce a sequence in which every job appears after the job it depends on. The input is a string such as:

a =>
b => c
c => f
d => a
e => b
f =>

Each line is a job, an arrow, and an optional dependency. Here b depends on c, and c depends on f. A valid answer puts f before c before b. Several orders are valid; any correct one will do.

Two errors must be reported: a job that depends on itself, and circular dependencies such as a needing b needing c needing a.

Why it is a good kata

Underneath, this is a topological sort of a directed graph, a classic algorithm. But the kata does not begin with the algorithm. It begins with the simplest case and lets the algorithm emerge. That is the TDD lesson: the tests drive out the design.

Step by step

Step 1: the empty list

The first test is almost insultingly easy.

[TestMethod]
public void Empty_input_gives_empty_sequence()
{
    Assert.AreEqual("", new JobSorter().Sort(""));
}

Make it pass with the dullest code you can write: return an empty string. Resist the urge to build the final solution now.

Step 2: one job

Assert.AreEqual("a", new JobSorter().Sort("a =>"));

Now you need to parse a line. Introduce a small parsing step that turns each line into a job name and an optional dependency.

Step 3: several independent jobs

var result = new JobSorter().Sort("a =>\nb =>\nc =>");
Assert.AreEqual(3, result.Length);
CollectionAssert.AreEquivalent(new[] {'a','b','c'}, result.ToCharArray());

Notice the assertion: it checks the contents, not an exact order, because any order is valid. Writing tests that tolerate legitimate variation is a skill in itself.

Step 4: one dependency

var result = new JobSorter().Sort("a =>\nb => c\nc =>");
Assert.IsTrue(result.IndexOf('c') < result.IndexOf('b'));

This is where behaviour appears. A helper that asserts "x comes before y" keeps later tests readable.

Step 5: a chain

Use the example from the problem statement. By now the solution needs to follow dependencies recursively. The simplest approach is a depth-first visit: to place a job, first place its dependency.

public string Sort(string input)
{
    var deps = Parse(input);          // Dictionary<char, char?>
    var result = new List<char>();

    foreach (var job in deps.Keys)
        Visit(job, deps, result);

    return new string(result.ToArray());
}

private void Visit(char job, Dictionary<char, char?> deps, List<char> result)
{
    if (result.Contains(job)) return;

    var dep = deps[job];
    if (dep.HasValue) Visit(dep.Value, deps, result);

    result.Add(job);
}

Step 6: a job that depends on itself

[TestMethod]
[ExpectedException(typeof(InvalidOperationException))]
public void Self_dependency_is_rejected()
{
    new JobSorter().Sort("a => a");
}

Add a guard in the parser. Currently the code would recurse forever, so the test fails dramatically, which is useful feedback.

Step 7: circular dependencies

The self-dependency is a loop of length one. Longer loops need a general check. Track the jobs currently being visited:

private void Visit(char job, Dictionary<char, char?> deps,
                   List<char> result, HashSet<char> visiting)
{
    if (result.Contains(job)) return;
    if (!visiting.Add(job))
        throw new InvalidOperationException("Circular dependency at " + job);

    var dep = deps[job];
    if (dep.HasValue) Visit(dep.Value, deps, result, visiting);

    visiting.Remove(job);
    result.Add(job);
}

If you reach a job that is already on the current path, you have walked in a circle. The self-dependency case is now handled by the same code, so the special guard from step 6 can be deleted, and the test still passes. That deletion is the refactoring part of red, green, refactor.

Reflect on the result

Look at what happened. No up-front diagram, yet you ended with a correct topological sort and cycle detection. Every behaviour has a test that names it. If you break something later, a test says exactly which promise you broke.

Variations

1. Allow several dependencies per job, such as a => b, c.
2. Use full words for job names, not single letters.
3. Return the cycle path in the error message.
4. Implement Kahn's algorithm instead of a depth-first visit and compare readability.
5. Do it in another language, or with only immutable data structures.

Practice habits

A kata is for repetition. Do it again next week, and ask what you would do differently. Keep a note of where you hesitated. Try the same steps with a different test order and see how the design changes. If you want ideas about how people actually pick up skills like this, read how developers really learn. And when the code you are sorting reaches for the clock or the file system, the techniques in isolating code with Moles and Fakes or injected delegates keep your tests quick.