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\).

No comments: