Code Kata: RoboStack

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:

0:

1:

2: 0 1 2 3

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):

• "move a onto b" This command orders the arm to find block a,
  and return any blocks stacked on top of it to their original position. Do the same
  for block b, then stack block a on top of b.
• "move a over b" This command orders the arm to find block a,
  and return any blocks stacked on top of it to their original position. Then stack
  block a on top of the stack of blocks containing b.
• "pile a onto b" This command orders the arm to find the
  stack of blocks containing block b, and return any blocks stacked on top
  of it to their original position. Then the arm must find the stack of blocks containing
  block a, and take the stack of blocks starting from a on upwards
  (in other words, don't do anything with any blocks on top of a) and put that
  stack on top of block b.
• "pile a over b" This command orders the arm to find the
  stack of blocks containing block a and take the stack of blocks starting
  from a on upwards (in other words, don't do anything with any blocks on top
  of a) and put that stack on top of the stack of blocks containing block b (in
  other words, don't do anything with the stack of blocks containing b, either).
• "quit" This command tells the arm to shut down (and thus terminates the
  simulation).

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:]

Challenges:

• Implement the Towers of Hanoi (or as close to it as you can get) using this system.
• Add an optimizer to the arm, in essence reading in the entire program (up to "quit"),
  finding shorter paths and/or different commands to achieve the same result.
• Add a visual component to the simulation, displaying the arm as it moves over each
  block and moves blocks around.
• Add another robotic arm, and allow commands to be given simultaneously. This will
  require some thought—does each arm execute a complete command before allowing the
  other arm to execute (which reduces the performance having two arms might offer),
  or can each arm act entirely independently? The two (or more) arms will probably need
  separate command streams, but you might try running them with one command stream just
  for grins. Note that deciding how to synchronized the arms so they don't conflict
  with one another will probably require adding some kind of synchronization instructions
  into the stream as well.

Enterprise consulting, mentoring or instruction. Java, C++, .NET or XML services.
1-day or multi-day workshops available. Contact
me for details.