Coordinates for a Heronian tetrahedron

Question

Did you know that Heronian Tetrahedra Are Lattice Tetrahedra? A Heronian tetrahedron is a tetrahedron where

1. the length of each edge is an integer,
2. the area of each face is an integer, and
3. the volume of the tetrahedron is an integer.

It's always possible to place such a tetrahedron in space such that all of the vertices have integer coordinates: \$(x,y,z) \in \mathbb{Z}^3\$.

Example

Consider the tetrahedron oriented so that the base is a triangle \$\triangle ABC\$ and the fourth point is \$D\$ and where \$AB = 200\$, \$AC = 65\$, \$AD = 119\$, \$BC = 225\$, \$BD = 87\$, and \$CD = 156\$.

(You can check that the faces all have areas that are integers, and the volume is an integer too.)

Then we can give explicit integer coordinates: \begin{align*} A &= (0,60,0)\\ B &= (96,180,128)\\ C &= (15,0,20)\\ D &= (63,144,56) \end{align*}

(This is shifted from the tetrahedron illustrated in Susan H. Marshall and Alexander R. Perlis's paper.)

Example Data

From Jan Fricke's paper On Heron Simplices and Integer Embedding

 AB  | AC  | AD  | BC  | BD  | CD  | coordinates
-----+-----+-----+-----+-----+-----+------------------------------------------------
 117 |  84 |  80 |  51 |  53 |  52 | (0,0,0)  (108,36,27)   (84,0,0)      (64,48,0)
 160 | 153 | 120 |  25 |  56 |  39 | (0,0,0)  (128,96,0)    (108,108,9)   (72,96,0)
 225 | 200 |  87 |  65 | 156 | 119 | (0,0,0)  (180,108,81)  (120,128,96)  (36,72,33)

Challenge

This is a code-golf challenge. Given a list of lengths of sides of a Heronian tetrahedron [AB, AC, AD, BC, BD, CD], return any valid collection of integer coordinates for \$A = (x_A, y_A, z_A)\$, \$B = (x_B, y_B, z_B)\$, \$C = (x_C, y_C, z_C)\$, and \$D = (x_D, y_D, z_D)\$. If one of the coordinates is the origin, you can omit it.

Answer 1

Charcoal, 90 bytes

≔…·±⌈θ⌈θηＦηＦηＦη⊞υ⟦ικλ⟧≔⟦⟧ηＦυＦυＦυＦ⁼Ｘ§θ²¦²ΣＸλ²⊞η⟦ικλ⟧ＦηＦＥ³Φ⮌ι⁻νκ⊞ιＥ⊟κ⁻맧κ⁰μＩ…⊟Φη⁼Ｘθ²ＥＸι²Σλ³

No TIO link because this is so horribly inefficient it fails to complete even the first test case on my local PC. Explanation:

≔…·±⌈θ⌈θη

From a range from -l to l inclusive, where l is the largest of any of the input lengths.

ＦηＦηＦη⊞υ⟦ικλ⟧

Get the triple Cartesian product of that range, i.e. a list of all points in the 2l+1 size cube centred at the origin.

≔⟦⟧ηＦυＦυＦυＦ⁼Ｘ§θ²¦²ΣＸλ²⊞η⟦ικλ⟧

Get the triple Cartesian product of those points, i.e. a list of all tetrahedra within the 2l+1 size cube with one point at the origin in the form AB, AC, AD.

ＦηＦＥ³Φ⮌ι⁻νκ⊞ιＥ⊟κ⁻맧κ⁰μ

Calculate the pairwise differences between the three points, i.e. the offsets BC, BD and CD.

Ｉ…⊟Φη⁼Ｘθ²ＥＸι²Σλ³

Print the last of the sets of points for which the lengths of the line segments equals the input.

Adding minimal filtering to the generated lists speeds it up and it can complete the first test case in under four hours on my PC:

≔…·±⌈θ⌈θηＦηＦηＦη⊞υ⟦ικλ⟧≔Φυ№Ｘ…賦²ΣＸι²υ≔⟦⟧ηＦυＦ∧⁼Ｘ§θ⁰¦²ΣＸι²υＦ∧⁼Ｘ§θ¹¦²ΣＸκ²υＦ⁼Ｘ§θ²¦²ΣＸλ²⊞η⟦ικλ⟧ＦηＦＥ³Φ⮌ι⁻νκ⊞ιＥ⊟κ⁻맧κ⁰μＩ…⊟Φη⁼Ｘθ²ＥＸι²Σλ³

Eventually I was able to apply sufficient filtering to come up with a version that can complete the first test case on TIO:

≔Ｘ…⁰⊗⌈θ²η≔…±⌈θ⊕⌈θζＦ…θ³ＦζＦζＦ⌕Ａη⁻×ιι⁺×κκ×λλ«⊞υ⟦κλ±μ⟧⊞υ⟦κλμ⟧»≔Ｅ…θ³Φυ⁼×ιιΣＸλ²ε≔⟦⟧υＦ§ε⁰ＦΦ§ε¹⁼Ｘ§θ³¦²ΣＸＥκ⁻μ§ιν²ＦＥＥ§ε²⟦ικλ⟧⁺λＥＥＥ³Φ⮌λ⁻ρν⁺⊟ν⟦⮌⊟ν⟧Ｅ⊟ν⁻π⊟ν⊞υλＩ…⊟Φυ⁼Ｘθ²ＥＸι²Σλ³

Try it online! Link is to verbose version of code.

Answer 2

JavaScript (Node.js), 334 bytes

([P,Q,R,S,T,U],f=(n,j=0,c=n**.5|0)=>j>1?c*c==n?[[-c],[c]]:[['']]:[...Array(1+2*c)].flatMap((_,i)=>i?f(n-(i-c)**2,j+1).map(b=>[i-c,...b]).filter(e=>!e.includes('')):[]),t=(y,z)=>y.map((e,i)=>Z+=(e-z[i])**2,Z=0)|Z)=>[...f(R*R).flatMap(e=>f(T*T).flatMap(E=>f(U*U).map(d=>[e,E,d]))).find(([a,b,c])=>t(a,b)==P*P&&t(a,c)==Q*Q&&t(b,c)==S*S)]

Try it online!

Omits D, which is the origin.

The code assumes that D is the origin. There is an f function, defined as a default argument, which returns all representations of a positive integer as a sum of three squares of positive and/or negative integers. It then returns the first list of possible triplets of A, B and C coordinates, derived from calling f on the AD, BD and CD distances, that satisfy the distance requirements.

The code works on the first two testcases. The second one is shown in the TIO link above. Segmentation fault on the third one.

Thanks to @Neil for saving 2 bytes.

Answer 3

Ruby, 213 bytes

f=->a{a[8]?((0..8).map{|i|i%3>0||a<<0;a[-1]+=(a[j=i/3][i%3]-a[-~j%3][i%3])**2};a[6,3].map{|i|i*i}==a[9,3]&&p(a[0,3])):
(r=a[2];(s=*0..r).product(s).map{|x,y|q=[x,y,z=(r*r-x*x-y*y)**0.5];z.real?&&z%1>0||f[[q]+a]})}

Try it online!

A recursive function taking input in the form of an array as follows. A is assumed to be the origin.

[AD,AC,AB,DC,CB,BD]

Alternatively, with relabelling B<>D, this is equivalent to the form below (this still requires the last two columns to be swapped with respect to the test case table in the question, as permitted by the rules.)

[AB,AC,AD,BC,CD,DB]

The function works on element [2] of the input array. When it finds integer coordinates that correspond to the lengths AB,AC,AD of the input array, it prepends them to the array and calls itself recursively. The data that was previously in elements [1] and [0] therefore ends up being shifted into element [2].

Once a full set of three possible coordinates for B,C,D are added, the array contains 9 elements (tested by seeing if element [8] is present.) Now the lengths of DC,CB and BD are checked and if a solution has been found it is output.

Caveats

In its current form, the code only considers the case where (x,y,z) are nonnegative for all vertices. This can be achieved in most (perhaps all) cases by careful selection of the input to ensure A is the most pointy vertex. Negative x and y can be easily considered by changing the code to s=-r..r. This costs an extra byte but doesn't actually make the score any higher as there is an unnecessary newline after : which can be removed. Within these limits the code should eventually find ALL solutions. (Solutions tend to be in groups of 6 corresponding to the 6 permutations of (x,y,z)) . A few more bytes would be need to stop at the first answer.

The code is slow but has been tested locally long enough to find first solutions to the first two test cases. A previous version was finding an answer to case 1 in Tio.run before timing out, but the current version always times out before finding any solutions. I've therefore added a rearrangement (swap of vertices B and C) to Tio.run in order to show an example of a solution returned within the time limit.

Note also that testcase 3 in the question corresponds to the same case as in the question text, but with vertices relabelled to avoid a negative coordinate.

The reason for the code being slow is that it searches for three vertices B,C,D at distances AB,AC,AD before checking the geometry of the other edges. A faster algorithm would be to calculate two vertices (plus the origin) and then calculate the final vertex. The code may be longer then, however.

Commented code

f=->a{a[8]?(                                                 #Does a contain (at least) 9 elements? If so iterate through 3 coordinates of 3 points.
  (0..8).map{|i|i%3>0||a<<0                                  #If i%3=0 append a zero to a to calculate the sum of squares of coordinate differences. 
     a[-1]+=(a[j=i/3][i%3]-a[-~j%3][i%3])**2};               #Add the squares of the x,y,z differences between the current and subsequent vertex to get the squared distance.
  a[6,3].map{|i|i*i}==a[9,3]&&p(a[0,3])                      #Calclulate the three squared lengths of lines DC,CB,BD in a [6..8]. 
                                                             #Compare with three distances between coordinates in a[9..11]. If a solution is found print it.
):                                                           #ELSE
  (r=a[2];                                                   #let r be the length of the line AB,AC or AD
   (s=*0..r).product(s).map{|x,y|q=[x,y,z=(r*r-x*x-y*y)**0.5]#find possible integer coordinates for the point B,C or D
   z.real?&&z%1>0||f[[q]+a]})}                               #if the z coordinate is real and an integer, prepend to a and recurse.