5
\$\begingroup\$

The truncated octahedron is a shape that has the interesting property that it can tessellate an entire 3D space so that any two solids that meet by an edge or corner also meet by a face, in a configuration called the bitruncated cubic honeycomb.

This gives it the special property that there is only one metric for adjacency distance [unlike a cubic grid where two cubes touching by only a corner have a face distance of 3], a property which is shared by a hexagonal grid in two dimensions.

Any solid in the bitruncated cubic honeycomb can be represented by the 3D coordinates (a+h, b+h, c+h) where a, b, c are integers and h is either 0 or 1/2. Any solid at (x, y, z) is adjacent to the solids at the following locations:

x, y, z+1
x, y, z-1
x, y+1, z
x, y-1, z
x+1, y, z
x-1, y, z
x+1/2, y+1/2, z+1/2
x+1/2, y+1/2, z-1/2
x+1/2, y-1/2, z+1/2
x+1/2, y-1/2, z-1/2
x-1/2, y+1/2, z+1/2
x-1/2, y+1/2, z-1/2
x-1/2, y-1/2, z+1/2
x-1/2, y-1/2, z-1/2

Your task is to build a program that, given the locations of two truncated octahedrons in the above arrangement, finds their distance. You can take input in any format you wish.

The shortest code to do this in any language wins.

\$\endgroup\$
4
  • \$\begingroup\$ Hmm... it seems to me the unit sphere for this metric is the rhombic dodecahedron, is it so? \$\endgroup\$ – John Dvorak Dec 12 '13 at 6:35
  • \$\begingroup\$ I think it's actually the tetrakis cube. \$\endgroup\$ – Joe Z. Dec 12 '13 at 7:43
  • \$\begingroup\$ Why did you accept an answer so quickly? Shouldn't you wait for a short time before doing so? \$\endgroup\$ – Justin Dec 12 '13 at 7:58
  • \$\begingroup\$ I will switch the accepted answer if a better solution comes along. However, you're right that I did it a little too quickly - my policy is usually to wait until there at least two answers. \$\endgroup\$ – Joe Z. Dec 12 '13 at 8:01
1
\$\begingroup\$

Golfscript, 10 13 characters

~{$~\-}%$~+\;

input: a space-separated array of three two-element arrays of integers, wrapped in square brackets. Each pair of integers denotes the coordinates of both octahedra in one axis. If half-coordinate inputs are to be supported, the input should be scaled up by an even factor (say, 10).

output: a single integer, scaled up by the same amount as the input

reads: "eval the input, for each axis: {sort both coordinates, then subtract the smaller from the larger}, sort the differences, then dump them onto the stack (resulting in three separate numbers), add the top two (= largest two coordinates) and discard the element just below".

proof:

the algorithm to reach a destination in this amount of steps is:

  • If all three coordinate differences are nonzero, make a diagonal step. This reduces all three differences by 0.5, meaning their order doesn't change and the sum of the largest two differences reduces by 1
  • If only one coordinate difference is nonzero, make an orthogonal step. This reduces the largest difference by 1
  • If two of the difference are nonzero, either of these steps can be chosen.

Thus, this algorithm never underestimates the distance. Also, it is not possible to reduce the sum of top largest two differences by more than 1 in a single step, meaning this algorithm never overestimates either. Thus, the algorithm "sum of the largest two absolute values of coordinate differences" is correct.

example:

;"[[20 0] [30 0] [20 -20]]"
~{$~\-}%$~+\;
#70

test: http://golfscript.apphb.com/?c=OyJbWzIwIDBdIFszMCAwXSBbMjAgLTIwXV0iCn57JH5cLX0lJH4rXDs%3D

\$\endgroup\$
9
  • \$\begingroup\$ Yeah, negative coordinates have to be supported as the honeycomb extends infinitely in all directions. \$\endgroup\$ – Joe Z. Dec 12 '13 at 7:46
  • \$\begingroup\$ Even so, 10 characters is amazingly short. \$\endgroup\$ – Joe Z. Dec 12 '13 at 7:47
  • \$\begingroup\$ Maybe I am blind, but where is the second octahedron? \$\endgroup\$ – Howard Dec 12 '13 at 7:59
  • \$\begingroup\$ I was wondering that too. Maybe Jan's code sort of automatically assumes that the second one is located at the origin. (Which shouldn't happen.) \$\endgroup\$ – Joe Z. Dec 12 '13 at 8:01
  • \$\begingroup\$ @JoeZ. oh. I was computing the distance from the origin. Sorry for that. Will fix. \$\endgroup\$ – John Dvorak Dec 12 '13 at 9:38
1
\$\begingroup\$

APL, 14 13

x+.×1<⍋x←|⎕-⎕

1 char saving if I'm allowed to change system variables in configurations

Prompts for input twice, enter space-separated coords both times.

Thanks to Jan

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.