The Ordered Jobs Kata
As you may well know, a kata is a training exercise that is performed over and over to build muscle memory and generally improve at whatever it is that we’re practising. The term kata comes from martial arts, but us software guys/gals have started using the term to describe the solving of small problems repeatedly to get better at things like TDD and pairing.
Katas also have the added benefit of making non-geeks think we’re healthy individuals that don’t just sit in dark basements all day. In fact, we’ve started using the word dojo to make absolutely sure our new image sticks.
Anyway, I had an interesting kata-like problem at work and I figured it’d be cool to describe it here for the masses of programmers out there having cold sweats and shaking in need of their next kata fix.
Feel free to have a go, and if you do, please leave a comment linking to your solution so I can collect them all at the bottom of this post. Then we can all mock each other (no pun intended). It’ll also be interesting to see if the choice of programming language affects the solution.
The Kata
Imagine we have a list of jobs, each represented by a character. Because certain jobs must be done before others, a job may have a dependency on another job. For example, a may depend on b, meaning the final sequence of jobs should place b before a. If a has no dependency, the position of a in the final sequence does not matter.
The goal of the kata is to parse the job dependency structure and produce a sequence of jobs in the order that observes their dependency chain.
Start with a method that accepts a single string argument and returns a string which represents the ordered sequence of jobs (since each job is a single character). We’ll refine the algorithm by evolving the requirements with each step, just like the string calculator kata.
Step 1 – Empty String
Given you’re passed an empty string (no jobs), the result should be an empty sequence.
Step 2 – Single Job
Given the following job structure:
a =>
The result should be a sequence consisting of a single job a.
Step 3 – Multiple Jobs
Given the following job structure:
a => b => c =>
The result should be a sequence containing all three jobs abc in no significant order.
Step 4 – Multiple Jobs, Single Dependency
Given the following job structure:
a => b => c c =>
The result should be a sequence that positions c before b, containing all three jobs abc.
Step 5 – Multiple Jobs, Multiple Dependencies
Given the following job structure:
a => b => c c => f d => a e => b f =>
The result should be a sequence that positions f before c, c before b, b before e and a before d containing all six jobs abcdef.
Step 6 – Multiple Jobs, Self Referencing Dependency
Given the following job structure:
a => b => c => c
The result should be an error stating that jobs can’t depend on themselves.
Step 7 – Multiple Jobs, Circular Dependency Chain
Given the following job structure:
a => b => c c => f d => a e => f => b
The result should be an error stating that jobs can’t have circular dependencies.
Completed Solutions
In Ruby
Ash solves the kata using RGL and RSpec
Caius solves the kata using black magic and testrocket
Sam solves the kata using RSpec
Kevin solves the kata in the style of TDD as if you meant it using RSpec
Matt solves the kata using RSpec
In C++
Thomas solves the kata using C++11
In C#
Martin solves the kata using MSpec
Thomas solves the kata using MSTest
Gemma solves the kata using NUnit
In Python
Mark solves the kata using unittest
In SQL (yes, SQL)
Sherwin solves the kata using manual tests
Johnno solves the kata using EYEUnit
Kev solves the kata using manual tests
In CoffeeScript
Tom solves the kata using nodeunit and documents his solution
In Scala
David solves the kata using specs
In JavaScript
Sam solves the kata again using Jasmine
Hi Martin! Not sure if we have spoken before, I’m a friend of Ash. Saw a link to this Kata on Twitter and decided to give it a shot in C++, my solution can be found here:
https://bitbucket.org/drummertom999/ordered-jobs-kata/src
I have used a couple of C++11 features so could only provide VS2010 build solution. The code should be platform agnostic so I may add makefiles for GCC/Unix build at a later date.
Hey Thomas, thanks for doing the kata. I love that you’ve used C++11 too, very interesting. I’ve linked your solution on the post for others to find :)
It was pretty fun! This problem immediately reminded me of the one solved by the Microsoft build system when you set up inter-project dependencies (as it figures out in which order to build each project, and identifies which projects can be safely built in parallel). Perhaps this Kata could be extended to support multiple dependencies per job? I noticed that none of the test cases exhibit this. Sorry to nit pick but have you noticed the trailing “and” after the C++11 link?
Thanks for the challenge!
Another C# solution:
https://bitbucket.org/thomaseyde/the-ordered-jobs-kata/src
Thanks Thomas, I’ve linked to your solution on the post.
I gave it a go in Scala. It’s not exactly a brilliant solution as I’m still learning both scala and the specs library, but it passes all the steps in the kata and I somehow managed it through pure list manipulation :)
https://github.com/workmad3/ordered-jobs-scala
Interesting, the first Scala solution. Added to the list, thanks :)
It was pretty fun! This problem immediately reminded me of the one solved by the Microsoft build system when you set up inter-project dependencies (as it figures out in which order to build each project, and identifies which projects can be safely built in parallel). Perhaps this Kata could be extended to support multiple dependencies per job? I noticed that none of the test cases exhibit this. Sorry to nit pick but have you noticed the trailing “and” after the C++11 link?
+1
Hello Martin,
nice kata. Here’s my solution in Gradle:
https://github.com/jhinrichsen/turf/blob/master/the-ordered-jobs-kata/build.gradle