## Monday, January 13, 2014

### Solution: Shortest distance between points on a cubic grid

One simple algorithmic solution to the puzzle is as follows.

1. Define $\Delta x = |x_A - x_B|, \Delta y = |y_A - y_B|, \Delta z = |z_A - z_B|$.
2. Sort these quantities: $[\text{min, med, max}] = \text{sort}[\Delta x, \Delta y, \Delta z].$
3. Set $n_{111} = \text{min}$, $n_{110} = \text{med-min}$, $n_{100} = \text{max-med}$.
4. The minimum distance is given by $d_{min} = \sqrt{3} n_{111} + \sqrt{2} n_{110} + n_{100}$
As an example consider A = (5, 3, 2) and B = (4, -1, 2).

1. $\Delta x = 1, \Delta y = 4, \Delta z = 0$.
2. [min, med, max] = [0, 1, 4]
3. $n_{111} = 0$, $n_{110} = 1$, $n_{100} = 3$.
4. Minimum distance is $\sqrt{2} + 3$.