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