Is my triangle on the lattice?

Question

Write a program or function which takes three positive integers \$a, b, c\$ and returns/outputs one value if there is, and a different value if there isn't, a triangle on the square lattice, whose sides' lengths are \$\sqrt{a}, \sqrt{b}, \sqrt{c}\$. By "on the square lattice" I mean that its vertices are in the \$xy\$ plane, and their \$x\$ and \$y\$-coordinates are all integers

This is code-golf so the shortest code in bytes wins.

Test cases:

• 16 9 25: true (3-4-5 triangle)
• 8 1 5: true (e.g. (0,0), (1,0), (2,2))
• 5 10 13: true (e.g. (0,1), (1,3), (3,0); sides needn't be on grid lines)
• 10 2 1: false (not a triangle: long side is too long for short sides to meet)
• 4 1 9: false (not a triangle: three points in a straight line)
• 3 2 1: false (triangle is on the cubic lattice but not the square lattice)
• 3 7 1: false (triangle is on the hex lattice but not the square lattice)
• 25 25 25: false (no such triangle on this lattice)
• 5 5 4: true (isosceles is OK)
• 15 15 12: false (OK shape, wrong size)
• 25 25 20: true (OK shape and size; common prime factor 5 is OK)
• 4 4 5: false (Bubbler's suggestion)
• 17 17 18: true (acute isosceles with equal short sides OK)
• 26 37 41: true (acute scalene is OK)

These same test cases, but just the numbers. First, those that should return true:

16 9 25
8 1 5
5 10 13
5 5 4
25 25 20
17 17 18
26 37 41

Then those that should return false:

10 2 1
4 1 9
3 2 1
3 7 1
25 25 25
15 15 12

Answer 1

Python3, 171 151 142 137 133 bytes

• 151 => 142 Thanks to @user
• 142 => 137 and fixed correctness thanks to @Bubbler
• 137 => 133 thanks to @xnor and @Bubbler

lambda l:l in[[d*d+D*D,e*e+E*E,(d-e)**2+(D-E)**2]for d,e,D,E in product(*[range(-max(l),max(l))]*4)if d*E-e*D]
from itertools import*

Tests here:

TESTS = [
    (16,9,25,True),
    (8,1,5,True),
    (5,10,13,True),
    (10,2,1,False),
    (4,1,9,False),
    (3,2,1,False),
    (3,7,1,False),
    (25,25,25,False),
    (5,5,4,True),
    (15,15,12,False),
    (25,25,20,True),
    (4,4,5,False)
]

for x,y,z,true in TESTS:
    print('testing',x,y,z)
    computed = f([x,y,z])
    assert computed == true

Try it online!

Answer 2

05AB1E, 26 25 bytes

ZD(Ÿ4ãʒÁ2ôPÆĀ}ειDøƪnOQ}à

Port of @TedBrownlow's Python answer, so make sure to upvote him as well!

Very slow. The larger the maximum value in the input-list, the slower it is.

Try it online or verify a few of the smaller test cases.

Explanation:

Z          # Push the maximum of the (implicit) input-list
 D(        # Duplicate this maximum, and negate the copy
   Ÿ       # Pop both, and push a list in the range [max,-max]
    4ã     # Create all possible quartets of this list with the cartesian product
ʒ          # Filter this list of quartets [a,b,c,d] by:
 Á         #  Rotate it once towards the right: [d,a,b,c]
  2ô       #  Split it into parts of size 2: [[d,a],[b,c]]
    P      #  Take the product of each inner pair: [d*a,b*c]
     Æ     #  Reduce the list by subtracting: d*a-b*c
      Ā    #  Check that this is NOT 0 with a Python-style truthify
}ε         # After the filter: map each remaining quartet to:
  ι        #  Uninterleave the list: [[a,c],[b,d]]
   D       #  Duplicate it
    ø      #  Zip/transpose the copy, swapping rows/columns: [[a,b],[c,d]]
     Æ     #  Reduce each by subtracting: [a-b,c-d]
      ª    #  Add this pair to the earlier list: [[a,c],[b,d],[a-b,c-d]]
       n   #  Square each: [[a²,c²],[b²,d²],[(a-b)²,(c-d)²]
        O  #  Take the sum of each inner pair: [a²+c²,b²+d²,(a-b)²+(c-d)²]
         Q #  Check that this list is equal to the (implicit) input-list
 }à        # After the map: check if any were truthy by taking the maximum
           # (after which the result is output implicitly)

Answer 3

05AB1E, 23 22 bytes

-1 thanks to @ovs

ZÝã3ãεDÁ-nOQ}àIt{R`+‹*

Try it online!

very very slow.

Explanation:

Z maximum
Ý push the range [0, maximum]
ã cartesien power which defaults to 2, returning all pairs
3ã cartesien power with 3, returning all possible traingles in the box (0,0,maximum,maximum)
ε map
 D duplicate
 Á rotate left 1
 - subtract # the offset between the three points
 n square
 O sum      # the side lengths of the triangle
 Q check if equals to the implicit input, returning 0/1
}
à maximum  # 1 if one of the cases was 1, 0 otherwise
I push the input
t square root
{ sort         # increasing order, e.g. [1,2,3]
R reverse      # e.g. [3, 2, 1]
` dump         # dump the array to stack e.g. 3, 2, 1
+ addition     # e.g. 3, 3
‹ is less than
* multiply, works as AND

Answer 4

Wolfram Language (Mathematica), 76 69 65 bytes

{}=!=Solve[Norm/@{a={w,x},b={y,z},a+b}^2==#&&w z!=x y,,Integers]&

Try it online!

If no solution exists, Solve returns an empty list {}; otherwise, since the variables to solve for are not given, it remains unevaluated. From there it's just a matter of collapsing unevaluated Solves into a single form.

Answer 5

C (gcc), 281 244 225 215 192 179 bytes

-14 thanks to @AZTECCO
-9 thanks to @ceilingcat

#define s(x,y)x>y?x^=y^=x^=y:0;
#define f(x,y)for(x=~b;x++<b;)for(y=~b;y++<b;)if(x*x+y*y==
r,i,j,k,l;t(a,b,c){r=0;s(a,c)s(b,c)s(a,b)f(i,j)a)f(k,l)b)r|=j*k&&c-a-b==i*k+j*l<<1;r=r;}

Try it online!

Answer 6

Charcoal, 90 79 73 71 bytes

≔⌈θη≔⁻Σθ⁺η⌊θζ≔…·±ζζεＦεＦε¿⁼⌊θ⁺Ｘι²Ｘκ²ＦεＦε¿⁼ζ⁺Ｘλ²Ｘμ²¿⁻×ιμ×κλＰ⁼η⁺Ｘ⁺ιλ²Ｘ⁺κμ²

Try it online! Link is to verbose version of code. Output is a Charcoal boolean, i.e. - if there is a solution, nothing if not. Edit: Saved 11 bytes by explicitly ranging one coordinate over negative values instead of testing both of its signs. Saved 6 bytes by using a colinearity test instead of a triangle test. Saved 2 bytes by inlining a variable. Made all variables range over negative values to fix the case where the three sides point in different quadrants, fortunately without costing any more bytes. Explanation: Uses brute force to find a solution.

≔⌈θη≔⁻Σθ⁺η⌊θζ≔…·±ζζε

Get the maximum and middle squared lengths. Call these \$ f \$ and \$ e \$. Create a range from \$ -e \$ to \$ e \$.

ＦεＦε¿⁼⌊θ⁺Ｘι²Ｘκ²

Find integers \$ -e \le g \le e \$ and \$ -e \le h \le e \$ such that \$ d = g^2 + h^2 \$ where \$ d \$ is the minimum squared length.

ＦεＦε¿⁼ζ⁺Ｘλ²Ｘμ²

Find integers \$ -e \le i \le e \$ and \$ -e \le j \le e \$ such that \$ e = i^2 + j^2 \$.

¿⁻×ιμ×κλ

If the two sides are not colinear, ...

Ｐ⁼η⁺Ｘ⁺ιλ²Ｘ⁺κμ²

... check whether \$ f = (g + i)^2 + (h + j)^2 \$.

Answer 7

JavaScript (ES6), 115 bytes

Expects three distinct arguments. Returns either 0 or a non-zero integer.

(a,b,c)=>(F=(C,m=M=a|b|c)=>m+M&&C(m)|F(C,m-1))(w=>F(x=>F(y=>F(z=>a-w*w-x*x|b-y*y-z*z|c-a-b^w*y+x*z<<1?0:x*y-w*z))))

Try it online!

How?

This is similar to other answers, but the main test has been modified some more to save a few bytes (at least in JS). Besides, we use a|b|c instead of Math.max(a,b,c). This is \$2\cdot\max(a,b,c)-1\$ in the worst case.

Given \$(w,x,y,z)\$, we want to know if we have:

$$w^2+x^2=a\tag{1}$$ $$y^2+z^2=b\tag{2}$$ $$(x+z)^2+(w+y)^2=c\tag{3}$$

\$(3)\$ is turned into:

$$x^2+z^2+2xz+w^2+y^2+2wy=c$$

Provided that \$(1)\$ and \$(2)\$ are true, this becomes:

$$a+b+2(xz+wy)=c$$

or:

$$c-a-b=2(xz+wy)$$

Hence the JavaScript expression:

c-a-b^w*y+x*z<<1

Answer 8

JavaScript (Node.js), 136 bytes

(p,q,r)=>(g=(n,t,x=0,y=(n-x*x)**.5)=>y%1==0&&t(x,y)|t(x,-y)||1/y&&g(n,t,x<0?-x:~x))(p,(a,b)=>g(q,(c,d)=>(a+c)**2+(b+d)**2==r&&a*d!=b*c))

Try it online!