So yes­ter­day I spent a while try­ing to imple­ment an intu­itive error heuris­tic for Cargo-Bot configurations.

It’s an inter­est­ing exer­cise in test-driven design, and I don’t have the sense I got it done very well the first time, so I’m going to spend a lit­tle while explor­ing in more detail, in the spirit of a cod­ing kata. I can def­i­nitely use some more help with my test-driven dev chops.

I had a bit of trou­ble think­ing it through myself, when I got more for­mal. This might be sim­pler in your lan­guage, in your test­ing frame­work. But I was able to work it all the way through with Ruby/Cucumber yes­ter­day, though I con­fess I pushed the notion of “accep­tance test” pretty close towards unit test­ing in doing so.

If you need some hints, or you want to see how a behavior-driven approach ends up, then take a look at my sce­nar­ios for this one fea­ture (scor­ing dif­fer­ent arrange­ments).

Stacks of Crates

So the prob­lem, briefly, is that you have two dif­fer­ent arrange­ments of (the same) col­ored blocks in a fixed num­ber of stacks. We’ll call one arrange­ment target, since it’s your goal in solv­ing the puzzle-game; we’ll call the other the observed one.

There are many dis­tance met­rics one could con­sider using, but those all seem to per­mit unre­al­is­tic phys­i­cal manip­u­la­tions. For exam­ple, Lev­en­shtein dis­tance mea­sures and their deriv­a­tives, which are used to com­pare strings, per­mit “swaps” between blocks as if that were a context-independent oper­a­tion. You can weight swaps to “cost” more in those met­rics, but those costs have no sense of the dif­fer­ence of swap­ping two blocks sit­ting on top of the same stack, as opposed to two blocks each on the bot­tom of a stack of 50 other blocks.

How I decided to approach the prob­lem is to treat each block’s con­tri­bu­tion to the total score as inde­pen­dent. Yes, this “sim­pli­fi­ca­tion” itself intro­duces unre­al­is­tic con­se­quences almost as heinous as the ones in the Lev­en­shtein exam­ple I just gave, since when you swap two adja­cent blocks in my scheme you’re count­ing the num­ber of moves you use to replace the top block with the bot­tom block, and then also the num­ber of moves you make to replace the bot­tom block with the top block (ignor­ing the fact you could take them both on and put them both back at once).

At this point? I don’t care. I’m the decider.

Now tech­ni­cally what we’re about to do here is imple­ment a heuris­tic or a qua­si­met­ric, not a met­ric. It makes rea­son­able phys­i­cal sense; con­sider two dif­fer­ent arrange­ments of the same blocks:

A: [[:r, :r, :r, :b, :r]]
B: [[:b, :r, :r, :r, :r]]

To review, this nota­tion means that A and B are con­fig­u­ra­tion with a sin­gle stack, con­tain­ing five blocks. The :b block is higher on stack 1 of arrange­ment A, and sits on the bot­tom of stack 1 of arrange­ment B.

If A is the target and B is what you have on hand, then to trans­form B into A you will need to make these changes to fix each block (top to bottom):

1. do noth­ing to fix the cor­rect top block
2. unstack all 5 blocks to get the :b, then stack 3 sup­port blocks, then replace the :b
3. do noth­ing to fix the cor­rect third block up
4. do noth­ing to fix the cor­rect sec­ond block up
5. unstack all 5 blocks, then add an :r to replace the bot­tom block

Notice some­thing else that hap­pens here, which I may not have said out loud before but which is almost cer­tainly impor­tant: I’ve added an extra “space” to the sys­tem, a “pool” where I can just shove things and retrieve them. In my men­tal model of blocks stacked on a table, the “pool” is the table top itself. Within the game Cargo-Bot there’s no such thing, and blocks can only live on stacks or be moved between them. I’m not play­ing Cargo-Bot here, I’m eval­u­at­ing how close one arrange­ment is to another in a phys­i­cally intu­itive way.

On the other hand, if B is the target and A is what you observe:

1. do noth­ing to fix the top block
2. take 2 blocks off the remove the incor­rect :b, then add back 1 :r to fix the sec­ond block down
3. mid­dle is right
4. sec­ond one up is right
5. take five blocks off to remove the wrong :r, but you’ve already set the :b aside in the “pool” by doing that, so you can just add the :b with one move

As I count them, the result we’ll get say­ing A is target is 15 moves, and if we say B is target it’s 9 moves. And that’s OK, as far as I’m con­cerned. Grav­ity is a thing, order mat­ters, and not every­thing in the world has the sort of sym­me­try math­e­mati­cians presume.

What’s wrong with this block?

Notice what we just did, though: we eval­u­ated each block in turn, then added it all up. I don’t care if in “fix­ing” one block you acci­den­tally “fix” another. If we counted all those, we’d be in inte­ger pro­gram­ming and constraint-solving land, and I don’t need that headache now.

We’re count­ing each block as though every­thing else were incon­se­quen­tial, and adding the inde­pen­dent cleanup moves for that one box.

I hope you can tell from the exam­ple we just walked through, each crate or block or box (I find myself slip­ping with the word, so for­give me) falls into one of sev­eral sim­ple classes. Let’s treat them in turn.

I’ll make the notional “pool” vis­i­ble, even though the algo­rithm I ended up with didn’t bother imple­ment­ing it. Turns out you can make do with count­ing, once you’ve explored the possibilities.

The block is OK

If the block in the target is the same color as the block in the same posi­tion in the same stack of the observed arrange­ment, no cleanup is necessary.

  target: [[:r]]
observed: [[:r]]
    pool: {}

Score = 0 cleanup for that block.

The block is com­pletely missing

I know I said the block arrange­ments were the “same”, but I get para­noid when I’m test­ing, and as it hap­pens there is a strange sort of edge-case in Cargo-Bot where a block can appear to dis­ap­pear: when it’s left in the claw.

So in these cases, I just want to note, “Hey, something’s not right here!” so I slapped a penalty of 100 points for any block in the target which is com­pletely absent from the observed state.

  target: [[:r]]
observed: [[  ]]
    pool: {}

Score = 100 for that block.

The block is in another stack, maybe with blocks on it

Here’s an exam­ple, with two stacks:

  target: [[:r, :b], [:g]]
observed: [[:r], [:g, :b]]
    pool: {}

Let’s con­sider the :b block only. There is no block in the posi­tion 2 of stack 1 in the observed setup. So we have to go find it. Aha! there it is! How many moves does it take to get it in the right position?

It’s on top of stack 2, so we can just un-stack it, where I like to think of it end­ing up in a sort of notional “pool”:

  target: [[:r, :b], [:g]]
observed: [[:r], [:g]]
    pool: {:b}

It’s avail­able for use, so we can plop on stack 1 and be done.

What hap­pens if the :b is deeper, as in

  target: [[:r, :b], [:g]]
observed: [[:r], [:b, :g]]
    pool: {}

Well, we need that :b. So we unstack it, along with every­thing on top of it, tak­ing 2 moves…

  target: [[:r, :b], [:g]]
observed: [[:r], []]
    pool: {:b, :g}

and then we can replace it. Do we care about the extra :g? No, it doesn’t sig­nify for this par­tic­u­lar case. It had to be moved (so we count the removal), but it can sit there.

The block is wrong

  target: [[:r, :b], [:g]]
observed: [[:r, :g], [:b]]
    pool: {}

So, again think­ing only of the :b in our exam­ple, what do we do? First we can free up the :b and place it in the “pool”.

  target: [[:r, :b], [:g]]
observed: [[:r, :g], []]
    pool: {:b}

Then we need to remove the wrong block that’s in the way (also to the pool):

  target: [[:r, :b], [:g]]
observed: [[:r], []]
    pool: {:b, :g}

… and then we can move the cor­rect :b onto the first stack.

  target: [[:r, :b], [:g]]
observed: [[:r, :b], []]
    pool: {:g}

Stuff is in the way

What about things that are “in the way” of the block we’re gath­er­ing or the one we’re replac­ing? We move them too. Let’s fix the :b block here:

  target: [[:r, :b, :y], [:g, :y, :y, :y]]
observed: [[:r, :g, :y], [:b, :y, :y, :y]]
    pool: {}

... gather correct :b (4 moves)
  target: [[:r, :b, :y], [:g, :y, :y, :y]]
observed: [[:r, :g, :y], []]
    pool: {:b, :y, :y, :y}

... clear out incorrect :g (2 moves)
  target: [[:r, :b, :y], [:g, :y, :y, :y]]
observed: [[:r], []]
    pool: {:b, :y, :y, :y, :g, :y}

... place correct :b (1 move from pool)
  target: [[:r, :b, :y], [:g, :y, :y, :y]]
observed: [[:r, :b], []]
    pool: {:y, :y, :y, :g, :y}

So by now (espe­cially if you’re imple­ment­ing these as we go), you should be notic­ing some patterns:

• to swap out a block from a stack, first shift it and all blocks above it into the pool
• to obtain a replace­ment block, first shift it and all blocks above it into the pool

Which choice?

Sup­pose there’s more than one place to obtain a replace­ment block. Let’s look at the:b in stack 1

  target: [[:r, :y, :b], [:g, :y], [:b, :g]]
observed: [[:r, :y, :y], [:g, :b], [:b, :g]]
    pool: {}

There are two places we could get our replace­ment :b in the observed arrange­ment: from the top of stack 2, or the bot­tom of stack 3. In this case, the sim­pli­fy­ing rule is: Choose the one that requires the min­i­mum num­ber of steps.

What does that mean in prac­tice? Well, here’s how I see it: look at every stack in the observed arrange­ment and find the depth of the top­most (or in com­put­erese, “right­most”) replace­ment. You don’t actu­ally need to move any­thing, since the score you’re adding in is just the min­i­mum depth to retrieve the replacement.

In this sit­u­a­tion, the num­ber of blocks moved to retrieve the right­most :b in each of the three observed stacks would be (using Ruby nota­tion here) [nil, 1, 2]: there is no :b in stack 1, there’s one requir­ing 1 move to retrieve from stack 2, and one requir­ing 2 moves to retrieve from stack 3.

Float­ing blocks

What about the case where our target block is not only miss­ing, but lacks a place to stand? Let’s score good old :b again:

  target: [[:r, :r, :r, :b], []]
observed: [[:r], [:r, :b, :r]]
    pool: {}

Well, clearly he’ll take more moves than just the ones to retrieve the cor­rect :b: we’ll need to shore him up somehow.

... free up missing :b to pool (2 moves)
  target: [[:r, :r, :r, :b], []]
observed: [[:r], [:r]]
    pool: {:b, :r}

... free up enough support blocks (1 more move)
  target: [[:r, :r, :r, :b], []]
observed: [[:r], []]
    pool: {:b, :r, :r}

... fill in supports (2 moves)
  target: [[:r, :r, :r, :b], []]
observed: [[:r, :r, :r], []]
    pool: {:r}

... replace :b (1 move)
  target: [[:r, :r, :r, :b], []]
observed: [[:r, :r, :r, :b], []]
    pool: {}

This can be a bit tricky, but it’s not algo­rith­mi­cally too nasty: You know how many blocks you moved to the pool to free up the cor­rect block, and you know how many blocks you have to have in the pool to build up to the place where the cor­rect block needs to stand.

If you don’t have enough blocks in the pool to make that stack, even after you’ve retrieved the cor­rect color, you’ll need to get them some­where. They can be any color, so imag­ine them pop­ping off any other stacks in the arrangement.

Pre­sum­ing there is no dif­fer­ence in the num­ber of blocks in the two arrange­ments. I hon­estly don’t know what we’d do if there was.…

The one tricky case: same stack

OK, so there’s one class of sit­u­a­tions I’ve been avoid­ing. It’s the one that trips me up, frankly.

What about when the “replace­ment” block is in the same stack as the “wrong” one?

  target: [[:r, :r, :r, :r, :b, :r]]
observed: [[:b, :r, :r, :r, :r, :r]]
    pool: {}

OK, well let’s see how it goes when we try to score the :b:

... free up missing :b to pool (6 moves)
  target: [[:r, :r, :r, :r, :b, :r]]
observed: [[]]
    pool: {:b, :r, :r, :r, :r, :r}

... replace supports (4 moves)
  target: [[:r, :r, :r, :r, :b, :r]]
observed: [[:r, :r, :r, :r]]
    pool: {:b, :r}

... add :b (1 move)
  target: [[:r, :r, :r, :r, :b, :r]]
observed: [[:r, :r, :r, :r, :b]]
    pool: {:r}

Not too bad. The trick of course is that your algo­rithm may be assum­ing that the stacks are dif­fer­ent. Mine was, and that’s when this head-scratcher comes along:

... remove incorrect :r in position 5 (2 moves)
  target: [[:r, :r, :r, :r, :b, :r]]
observed: [[:b, :r, :r, :r]]
    pool: {:r, :r}

... free up :b (? moves)
  target: [[:r, :r, :r, :r, :b, :r]]
observed: [[:r, :r, :r, :r]]
    pool: {:b, :r}

Notice what hap­pened there? Depend­ing on whether we “free up cor­rect one” or “remove incor­rect one” first, the path-dependence of manip­u­lat­ing the same stack sud­denly matters.

Now I was try­ing, as I imple­mented this all, to avoid actu­ally sim­u­lat­ing the manip­u­la­tion of blocks. The lit­tle dia­grams I’ve been draw­ing for you have been help­ful ped­a­gogic sketches, but what I wanted (and still want) to do was just add up the points for maneu­vers. Up into this case, we’ve had no inter­ac­tion between the events on one stack and the events on another: To dig out a wrong one, move it and all the blocks above it; to dig out a right one, move it and all the blocks above it; to find sup­ports, grab more from some­where else as needed.

So my algo­rithm (which I tried ever so dili­gently to use TDD to design) takes the form of some con­di­tion­als and adding stuff up. Until we get here. Maybe your design was more sim­u­la­tory (if that’s a word?), and you actu­ally did more like the lit­tle dia­grams and shifted blocks around. I don’t know if that’s bet­ter or not.

So what to do?

Me, I came up with some­thing that works, but it’s unsat­is­fy­ing still.

How about you?

Sewing it together

Now I have one more story (assum­ing I can read my own code) that’s important.

I think we both see that the score for a stack should be the sum of the scores for each block in the target (com­pared to the observed), and that the score for an arrange­ment is the sum of the scores of each stack.

In work­ing through these sto­ries, though, I came across one more sit­u­a­tion of inter­est: What about a stack that’s empty in the target, but has junk in it in the observed arrange­ment? Given the rules I just sketched, since there’s noth­ing in the target stack we won’t actu­ally count any points for it, even though it feels wrong.

So one more rule for scor­ing a stack: If there are more boxes on the observed stack, we need to charge to remove each one.

  target: [[:r, :r, :r, :r, :r], []]
observed: [[], [:r, :r, :r, :r, :r]]
    pool: {}

Stack 1 gets scored by the rules we’ve already explored. But I also think stack 2 is both­er­some. How many moves would it take to remove each extra crate on stack 2, con­sid­ered indi­vid­u­ally? 1 move for the top one; 2 for the sec­ond; 3 for the third and so on.

So here’s another exam­ple, where I’m just look­ing at the two first stacks:

  target: [[:r, :r], …]
observed: [[:r, :r, :r, :r, :r], …]

There are three extra boxes on the observed stack, com­pared with the target height. So charge that 6 points (1+2+3).