I came across this site quite a while back and have been meaning to blog about it. The site is CodeKata, and the premise is essentially to give reasonably interesting problems that can be solved using code in order to practice and hone your skills. Not everything is a coding problem, but where I can see these coming in handy are using the katas to learn new languages. I always learn better when I have something to implement as I learn. Anyway, my original intention was to just link to the site, however it looks like the site hasn’t been updated in 4 years! It concerns me that it might not be around if I merely link to it, so I am going to copy the katas here for future reference. I hope Dave doesn’t mind.
Kata 16 – Business Rules
How can you tame a wild (and changing) set of business rules?
Imagine you’re writing an order processing application for a large company. In the past, this company used a fairly random mixture of manual and ad-hoc automated business practices to handle orders; they now want to put all these various ways of hanadling orders together into one whole: your application. However, they (and their customers) have come to cherish the diversity of their business rules, and so they tell you that you’ll have to bring all these rules forward into the new system.
When you go in to meet the existing order entry folks, you discover that their business practices border on chaotic: no two product lines have the same set of processing rules. To make it worse, most of the rules aren’t written down: you’re often told something like "oh, Carol on the second floor handles that kind of order."
During first day of meetings, you’ve decided to focus on payments, and in particular on the processing required when a payment was received by the company. You come home, exhausted, with a legal pad full of rule snippets such as:
- If the payment is for a physical product, generate a packing slip for shipping.
- If the payment is for a book, create a duplicate packing slip for the royalty department.
- If the payment is for a membership, activate that membership.
- If the payment is an upgrade to a membership, apply the upgrade.
- If the payment is for a membership or upgrade, e-mail the owner and inform them of the activation/upgrade.
- If the payment is for the video "Learning to Ski," add a free "First Aid" video to the packing slip (the result of a court decision in 1997).
- If the payment is for a physical product or a book, generate a commission payment to the agent.
- and so on, and so on, for seven long, yellow pages.
And each day, to your horror, you gather more and more pages of these rules.
Now you’re faced with implementing this system. The rules are complicated, and fairly arbitrary. What’s more, you know that they’re going to change: once the system goes live, all sorts of special cases will come out of the woodwork.
Objectives
How can you tame these wild business rules? How can you build a system that will be flexible enough to handle both the complexity and the need for change? And how can you do it without condemming yourself to years and years of mindless support?
Kata 17 - More Business Processing
The rules that specify the overall processing of an order can be complex too, particularly as they often involve waiting around for things to happen.
In Kata Sixteen we had a look at the business rules that applied when we received payment for various kinds of product. Handling payments is just a small part of the overall workflow required to process an order. For the company whose application we’re looking at, order processing looks something like:
- If we accept an order over the web, then we have to wait for payment to arrive, unless it’s a credit-card order. In the case of credit card orders, we can process the order immediately and ship the goods, but only if the goods are in stock. If they are not currently in stock, we have to delay processing credit card orders until the become available again.
- We can receive a check in payment of an existing order, in which case we ship the goods (unless they are not in stock, in which case we hold the check until the goods become available).
- We can receive a purchase order (PO) for a new order (we only accept these from companies with an established credit account). In this case we ship the goods (assuming they are in stock) and also generate an invoice against the PO. At some point in the future we’ll receive payment against this invoice and the order will be complete.
- At any time before the goods are shipped the customer may cancel an order.
Each step in this process may occur many days after the previous step. For example, we may take an order over the web on Monday, receive a check for this order on Thursday, then ship the goods and deposit the check when the item is received from our own suppliers on the following Tuesday.
How can we design an application to support these kinds of rules? Of course, businesses change the rules all the time, so we better make sure that anything we come up makes it easy to update the workflow.
Kata 18 – Transitive Dependencies
Let’s write some code that calculates how dependencies propagate between things such as classes in a program.
Highly coupled code is code where the dependencies between things are dense, lots of things depend on other things. This kind of program is hard to understand, tough to maintain, and tends to be fragile, breaking easily when things change.
There are many different kinds of coupling in code. One of the easiest to work with programatically is \emph{static coupling}, where we’re concerned with the relationships between chunks of source code. Simplisticly, we can say that class A is statically coupled to class B if the compiler needs the definition of B in order to compile
- In many languages, static dependencies can be determined by source
code analysis. Tools such as makedepend (for C programs) and JDepend (for Java) look for explicit dependencies in the source and list them out.
One of the insidious things about dependencies is that they are transitive—if A depends on B and B depends on C, then A also depends on C. So, let’s write some code that calculates the full set of dependencies for a group of items. The code takes as input a set of lines where the first token is the name of an item. The remaining tokens are the names of things that this first item depends on. Given the following input, we know that A directly depends on B and C, B depends on C and E, and so on.
A B C
B C E
C G
D A F
E F
F H
The program should use this data to calculate the full set of dependencies. For example, looking at B, we see it directly depends on C and E. C in turn relies on G, E relies on F, and F relies on H. This means that B ultimately relies on C, E, F, G, and H. In fact, the full set of dependencies for the previous example is:
A B C E F G H
B C E F G H
C G
D A B C E F G H
E F H
F H
Let’s express this using unit tests. The following code assumes that our dependency calculator is a class with an add_direct() method to add the direct dependencies for an item, and a dependencies_for() method to return the full list of dependencies for an item. The code uses Ruby’s %w{…} construct, which builds an array of strings from its argument.
def test_basic
dep = Dependencies.new
dep.add_direct('A', %w{ B C } )
dep.add_direct('B', %w{ C E } )
dep.add_direct('C', %w{ G } )
dep.add_direct('D', %w{ A F } )
dep.add_direct('E', %w{ F } )
dep.add_direct('F', %w{ H } )
assert_equal( %w{ B C E F G H }, dep.dependencies_for('A'))
assert_equal( %w{ C E F G H }, dep.dependencies_for('B'))
assert_equal( %w{ G }, dep.dependencies_for('C'))
assert_equal( %w{ A B C E F G H }, dep.dependencies_for('D'))
assert_equal( %w{ F H }, dep.dependencies_for('E'))
assert_equal( %w{ H }, dep.dependencies_for('F'))
end
Stop reading now, and start coding. Once you’ve got your code working, try feeding it the following dependencies.
A B
B C
C A
Does it work correctly? If not, ask yourself is this is a condition you should have considered during testing.
Once you’ve got your code working with all the various test cases you can imagine, let’s think for a minute about performance. Say we were using this code to find all the relationships between the inhabitants of the United Kingdom. How would your code perform with 55-60 million items?
Kata 19 – Word Chains
Write a program that solves word-chain puzzles.
There’s a type of puzzle where the challenge is to build a chain of words, starting with one particular word and ending with another. Successive entries in the chain must all be real words, and each can differ from the previous word by just one letter. For example, you can get from "cat" to "dog" using the following chain.
cat
cot
cog
dog
The objective of this kata is to write a program that accepts start and end words and, using words from thedictionary, builds a word chain between them. For added programming fun, return the shortest word chain that solves each puzzle. For example, my Powerbook running Ruby can turn "lead" into "gold" in four steps (lead, load, goad, gold), taking about 20 seconds. Turning "ruby" into "code" takes six steps (ruby, rubs, robs, rods, rode, code) and 90 seconds, while turning "code" into "ruby" (again in six steps) takes about an hour. Go figure…
Update: It turns out that my original algorithm was pretty dumb: a better approach greatly speeds up search and makes it symetrical. It now does all the above examples in between 0.5s and 1s.
Kata 20 – Klondike
Experiment with different heuristics for playing the solitaire game Klondike.
The solitaire game Klondike is probably the most widely played in the world (particularly if you’re a Window’s user, where it has been available since Windows 3.1). It’s a simple game.
Cards are dealt face down onto the seven piles in the tableau. The first pile receives one card, the next two, up to the seventh pile, which not surprisingly has seven cards initially. The top card on each pile is turned face-up, and the undealt cards are placed on the Stock pile, all face down. Here’s a picture of the game (52kb) if you haven’t seen it before.
The idea is to build up four piles of cards in their suits on the foundation area (one pile for the clubs, one for the diamonds, and so on). The piles must start with the ace and end with the king.
The available moves (in no particular order) are:
- If the Stock becomes empty, turn the entire discard pile over and make it the new Stock.
- Turn over the top card of the Stock and place it face-up on the Discard pile.
- Move a card from the tableau or discard pile to one of the foundation piles. If the foundation pile is empty, only an Ace can be placed there, otherwise only the next highest card in the appropriate suit can be placed (so if a foundation pile is currently showing a four of hearts, only the five of hearts may be placed there).
- Move the top card of the discard pile to one of the tableau piles. This card must be one less in rank and opposite in color to the card at the top of the destination tableau.
- Move one or more cards from one tableau pile to another. If multiple cards are moved, they must be a sequence ascending in rank and alternating in color. The card moved (or the top of the sequence moved) must be one less in rank and opposite in color to the card at the top of the destination tableau. If the move leaves a face-down card to the top of the original pile, turn it over.
- If a move leaves a tableau pile empty, an exposed King at the top of a tableau or discard pile, or a sequence starting with a King on a tableau pile, may be moved to it.
So, in the game pictured about, a possible first set of moves might be:
- Move the Queen of Hearts onto the King of Clubs.
- This leaves the first pile in the tableau empty, so the combined King/Queen can be moved to it. The card originally beneath the King is turned over.
- The Jack of Clubs can be moved on to the Queen of Hearts, and the card beneath the Jack revealed.
The game is won when all cards are moved to the foundation, and lost when the only remaining moves form an endless loop.
The game is simple to play, but the strategy isn’t immediately obvious. For example, is it always a good idea to move a card from the tableau to the foundation, or is it sometimes better to leave it there to give yourself something to build down on? Is it a good idea to make a move which leaves a tableau pile empty if you don’t immediately have a King to move into the gap? If you have two possible moves which will result in exposing a new tableau card, should you expose the one on the longest or shortest tableau?
This kata is in two parts.
- Come up with an infrastructure so you can have the computer deal and play games of Klondike.
- Use that infrastructure to experiment with strategies to see if you can increase the number of times you win (perhaps you could tabulate the number of times the machine wins a random set of 1,000 games for each strategy you try).
Objectives
- At one level, this is an exercise in design—how can the basic game be modeled in code? Where should the validation of moves be located (in the cards, in the various piles, in some kind of game overseer, or …)? How can we detect that we’ve lost?
- Once the basic game is in place, it becomes an exercise in imagination: what strategies can be applied, and how do various sub-strategies interact?
Kata 21 – Simple Lists
Perhaps there’s more to the humble list of values than you might think. Let’s experiment with some basic list processing.
Lists are one of the first data structures we learn as programmers. But familiarity doesn’t mean that we can’t learn a little from them.
For this kata we’re going to code up three implementations of a list that has the following basic interface:
- The list consists of nodes. Each node has a string value, along with whatever housekeeping the list itself needs.
- New nodes are added to the end of the list.
- You can ask the list if it contains a given string. If it does, it returns the node containing that string.
- You can delete a node from the list.
- You can ask the list to return an array of all its values.
Here’s a basic set of unit tests to illustrate the behavior.
list = List.new
assert_nil(list.find("fred"))
list.add("fred")
assert_equal("fred", list.find("fred").value())
assert_nil(list.find("wilma"))
list.add("wilma")
assert_equal("fred", list.find("fred").value())
assert_equal("wilma", list.find("wilma").value())
assert_equal(["fred", "wilma"], list.values())
list = List.new
list.add("fred")
list.add("wilma")
list.add("betty")
list.add("barney")
assert_equal(["fred", "wilma", "betty", "barney"], list.values())
list.delete(list.find("wilma"))
assert_equal(["fred", "betty", "barney"], list.values())
list.delete(list.find("barney"))
assert_equal(["fred", "betty"], list.values())
list.delete(list.find("fred"))
assert_equal(["betty"], list.values())
list.delete(list.find("betty"))
assert_equal([], list.values())
For the kata, where the idea is to practice, let’s write three implementations of the list:
- A singly linked list (each node has a reference to the next node).
- A doubly linked list (each node has a reference to both the next and previous nodes).
- Some other implementation of your choosing, except that it should use no references (pointers) to collect nodes together in the list.
Obviously, we won’t be using predefined library classes as our list implementations…
Objectives
There’s nothing magical or surprising in list implementations, but there are a fair number of boundary conditions. For example, when deleting from the singly-linked list, did you have to deal with the case of deleting the first element in the list specially?
For this kata, concentrate on ways of removing as many of these boundary conditions as possible. Then ask yourself: Is the resulting code, which will contain fewer special cases, easier to read and maintain? How easy was it to eliminate these special cases? Were there trade-offs, where removing a special case in one area complicated the code in another. Is there a sweet-spot when it comes to simplifying code?