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.

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.

1. In other words, you start from the point A and hop to any of the 8 (2D) or 26 (3D) nearest lattice points. You repeat this process, until you reach B.

2. In 3D, an individual hop may be of length \(1, \sqrt{2}, \sqrt{3}\).

3. The shortest path itself may not be unique, but the shortest length is.

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

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.

**Additional Notes/Hints**:1. In other words, you start from the point A and hop to any of the 8 (2D) or 26 (3D) nearest lattice points. You repeat this process, until you reach B.

2. In 3D, an individual hop may be of length \(1, \sqrt{2}, \sqrt{3}\).

3. The shortest path itself may not be unique, but the shortest length is.

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

## No comments:

Post a Comment