10
\$\begingroup\$

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

Figure 2 from the paper. An illustration of the tetrahedron given above.

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

\$\endgroup\$
7
  • \$\begingroup\$ Can we take the input in any order? Also, the edges of a tetrahedron form three opposite pairs AB/CD, AC/BD and AD/BC - does the input have to be a one dimensional array, or are other formats, such as 2D arrays, three complex numbers, etc, acceptable? \$\endgroup\$ Feb 24 at 23:46
  • \$\begingroup\$ Any reasonable input is fine—including all of the examples you give. \$\endgroup\$ Feb 24 at 23:46
  • 3
    \$\begingroup\$ May we output three vertices, with the fourth taken to be the origin? \$\endgroup\$
    – att
    Feb 25 at 1:34
  • 2
    \$\begingroup\$ Please add some more testcases. \$\endgroup\$
    – tsh
    Feb 25 at 2:38
  • 1
    \$\begingroup\$ @DialFrost I think Peter adjusted the coordinates in the text to eliminate the -60 in the diagram. Anyway that's just an example of the math. The challenge is the three lines at the bottom of the question. Most solutions are going to consider the orign as one of the four points - hence att is asking whether we need to output it. \$\endgroup\$ Feb 25 at 2:40

3 Answers 3

4
\$\begingroup\$

Charcoal, 90 bytes

≔…·±⌈θ⌈θηFηFηFη⊞υ⟦ικλ⟧≔⟦⟧ηFυFυFυF⁼X§θ²¦²ΣXλ²⊞η⟦ικλ⟧FηFE³Φ⮌ι⁻νκ⊞ιE⊟κ⁻맧κ⁰μI…⊟Φη⁼Xθ²EXι²Σλ³

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.

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

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.

≔⟦⟧ηFυFυFυF⁼X§θ²¦²ΣXλ²⊞η⟦ικλ⟧

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.

FηFE³Φ⮌ι⁻νκ⊞ιE⊟κ⁻맧κ⁰μ

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

I…⊟Φη⁼Xθ²EXι²Σλ³

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:

≔…·±⌈θ⌈θηFηFηFη⊞υ⟦ικλ⟧≔Φυ№X…賦²ΣXι²υ≔⟦⟧ηFυF∧⁼X§θ⁰¦²ΣXι²υF∧⁼X§θ¹¦²ΣXκ²υF⁼X§θ²¦²ΣXλ²⊞η⟦ικλ⟧FηFE³Φ⮌ι⁻νκ⊞ιE⊟κ⁻맧κ⁰μI…⊟Φη⁼Xθ²EXι²Σλ³

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

≔X…⁰⊗⌈θ²η≔…±⌈θ⊕⌈θζF…θ³FζFζF⌕Aη⁻×ιι⁺×κκ×λλ«⊞υ⟦κλ±μ⟧⊞υ⟦κλμ⟧»≔E…θ³Φυ⁼×ιιΣXλ²ε≔⟦⟧υF§ε⁰FΦ§ε¹⁼X§θ³¦²ΣXEκ⁻μ§ιν²FEE§ε²⟦ικλ⟧⁺λEEE³Φ⮌λ⁻ρν⁺⊟ν⟦⮌⊟ν⟧E⊟ν⁻π⊟ν⊞υλI…⊟Φυ⁼Xθ²EXι²Σλ³

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Can't c==n**.5 be n==c*c? \$\endgroup\$
    – Neil
    Feb 26 at 8:19
1
\$\begingroup\$

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