Calculate the bitruncated cubic distance between two points
Golfscript, 10 13 characters
~{$~\-}%$~+\;

input: a space-separated array of three two-element arrays of integers, wrapped in square brackets. Each pair of integers denotes the coordinates of both octahedra in one axis. If half-coordinate inputs are to be supported, the input should be scaled up by an even factor (say, 10).
output: a single integer, scaled up by the same amount as the input
reads: &quot;eval the input, for each axis: {sort both coordinates, then subtract the smaller from the larger}, sort the differences, then dump them onto the stack (resulting in three separate numbers), add the top two (= largest two coordinates) and discard the element just below&quot;.
proof:
the algorithm to reach a destination in this amount of steps is:

If all three coordinate differences are nonzero, make a diagonal step. This reduces all three differences by 0.5, meaning their order doesn't change and the sum of the largest two differences reduces by 1
If only one coordinate difference is nonzero, make an orthogonal step. This reduces the largest difference by 1
If two of the difference are nonzero, either of these steps can be chosen.

Thus, this algorithm never underestimates the distance. Also, it is not possible to reduce the sum of top largest two differences by more than 1 in a single step, meaning this algorithm never overestimates either. Thus, the algorithm &quot;sum of the largest two absolute values of coordinate differences&quot; is correct.
example:
;&quot;[[20 0] [30 0] [20 -20]]&quot;
~{$~\-}%$~+\;
#70

test: http://golfscript.apphb.com/?c=OyJbWzIwIDBdIFszMCAwXSBbMjAgLTIwXV0iCn57JH5cLX0lJH4rXDs%3D