10 May 2010

Code Katas are small, relatively simple exercises designed to give you a problem to try and solve. I like to use them as a way to get my feet wet and help write something more interesting than "Hello World" but less complicated than "The Internet's Next Killer App".


This one is from the UVa online programming contest judge system, which I discovered after picking up the book Programming Challenges, which is highly recommended as a source of code katas, by the way. Much of the advice parts of the book can be skimmed or ignored by the long-time professional developer, but it's still worth a read, since it can be an interesting source of ideas and approaches when solving real-world scenarios.


Problem: You work for a manufacturing company, and they have just received their newest piece of super-modern hardware, a highly efficient assembly-line mechanized pneumatic item manipulator, also known in some circles as a "robotic arm". It is driven by a series of commands, and your job is to write the software to drive the arm. The initial test will be to have the arm move a series of blocks around.


Context: The test begins with n number of blocks, laid out sequentially next to each other, each block with a number on it. (You may safely assume that n never exceeds 25.) So, if n is 4, then the blocks are laid out (starting from 0) as:

0: 0

1: 1

2: 2

3: 3

The display output here is the block-numbered "slot", then a colon, then the block(s) that are stacked in that slot, lowest to highest in left to right order. Thus, in the following display:



2: 0 1 2 3


The 3 block is stacked on top of the 2 block is stacked on top of the 1 block is stacked on top of the 0 block, all in slot 2. This can be shortened to the representation [0:, 1:, 2: 0 1 2 3, 3:] for conciseness.


The arm understands a number of different commands, as well as an optic sensor. (Yeah, the guys who created the arm were good enough to write code that knows how to read the number off a block, but not to actually drive the arm. Go figure.) The commands are as follows, where a and b are valid block numbers (meaning they are between 0 and n-1):

Note that if the input command sequence accidentally offers a command where a and b are the same value, that command is illegal and should be ignored.


As an example, then, if we have 4 blocks in the state [0: 0, 1: 1, 2: 2, 3: 3], and run a "move 2 onto 3", we get [0: 0, 1: 1, 2:, 3: 3 2]. If we then run a "pile 3 over 1", we should end up with [0: 0, 1: 1 3 2, 2:, 3:]. And so on.


Input: n = 10. Run these commands:

  1. move 9 onto 1
  2. move 8 over 1
  3. move 7 over 1
  4. move 6 over 1
  5. pile 8 over 6
  6. pile 8 over 5
  7. move 2 over 1
  8. move 4 over 9
  9. quit

The result should be [0: 0, 1: 1 9 2 4, 2:, 3: 3, 4:, 5: 5 8 7 6, 6:, 7:, 8:, 9:]



Tags: languages   design   kata  

Last modified 10 May 2010