Wednesday, December 25, 2013

Puzzle: Shortest distance between points on a cubic grid

This is a middle or high-school level puzzle aimed at encouraging algorithmic thinking.

We know that the distance between two points A and B is $d_{AB} = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2 + (z_A - z_B)^2},$ where x, y, and z denote the Cartesian co-ordinates.

Suppose the points A and B lie on a cubic grid or lattice. That is the Cartesian co-ordinates are integers.

What is the shortest distance between the points along the lattice?

In the 2D example below (assuming each small square has sides of length 1), the shortest distance between points  A and B with and without the lattice constraint is $3 \sqrt{2} + 1$ and 5, respectively.

2. In 3D, an individual hop may be of length $1, \sqrt{2}, \sqrt{3}$.
4. It may be useful to rephrase the problem in terms of $\Delta x = |x_A - x_B|, \Delta y = |y_A - y_B|, \Delta z = |z_A - z_B|$.