# Is my triangle on the lattice?

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

• As far as I can tell this seems perfectly clear. I would be interested to know what people would like clarified. Just flagging it as unclear alone is not really enough to help this author fix the issue. Jan 10 at 16:34
• I think the only way this could be improved is if $a,b,c$ were guaranteed to be square. Otherwise, answers will have to deal with floating point issues, and the question should make it clear how to handle those (e.g. works in theory, but doesn’t have to in practice, answers must handle floating point issues etc.) Jan 10 at 17:06
• Suggested test case: 4 4 5 -> false, which prevents set-based comparison of side lengths. Jan 10 at 23:48
• I think it would help to list test cases in a way that is easy to copy-paste in addition to the annotation ones.
– xnor
Jan 11 at 0:59
• @xnor Seeing as different languages will have different syntax requirements, how should I do this? Jan 12 at 15:29

# Python3, 171151142137 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!

• You can use TIO like this and in there get a code-golf link you can simply paste into your answer. Jan 10 at 22:42
• Since repeat is really long, it is shorter to call product with 4 ranges. And sets can be declared with curly brackets: Try it online!
– ovs
Jan 10 at 23:40
• Fails at 4 4 5 -> false, which can be fixed by using range(-max(l),max(l)) and removing set conversion entirely. Jan 10 at 23:50
• The itertools import should be in the code and count for bytes.
– xnor
Jan 11 at 1:02
• @xnor Not that it really matters here, but l in(...) is a bit faster and uses very little memory.
– ovs
Jan 11 at 9:18

# 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

• {RćsO‹ can be a byte shorter with : {R+‹
– ovs
Jan 11 at 12:48

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

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)

• I also found a different <s>25</s> 24 bytes solution: ZÝã3ãʒÁ-nOIQ}gĀIt{RćsO‹* Jan 11 at 9:02
• Actually it can be 23 bytes by also doing what you did with map instead of filter Jan 11 at 9:10
• Nice alternative approach, but I'm afraid it fails for test case [4,4,5]->false that Bubbler suggested in the comments. Not sure what a good fix for that would be in your approach unfortunately. Btw, you can drop the first I within your filter for -1 byte, since it's used implicitly. Jan 11 at 9:12
• I think this is just a bug I accidentally introduced when removing the duplicate in the filter, as adding it works - ZÝã3ãεDÁ-nOQ}àIt{RćsO‹* Jan 11 at 9:48
• @CommandMaster That indeed seems to work. :) Nice alternative approach. Do you want me to add it to my answer as a golf, or you want to post it as your own since it's quite a bit different? Either is fine by me. Jan 11 at 9:52

# C (gcc), 281244225215192 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!

• You can still use @ceilingcat suggestion ;) Try it online! Jan 13 at 15:40
• @AZTECCO thank you, I did some research and now I get the usage of |=. And I noticed you improved @ceilingcat's suggestion with r=r in place of return r :) Jan 13 at 17:32
• @Davide nice to help! I tried the eax trick also in the previous suggestion but it didn't worked for some reason Jan 13 at 17:44
• Here: codegolf.stackexchange.com/a/106067/100356 they say that unless you use only only multiplication and division, it is undefined behaviour. So @ceilincat code is just luckier than yours :) Jan 13 at 17:55
• @ceilingcat whoo that's clever I missed it Jan 14 at 10:58

# Wolfram Language (Mathematica), 7669 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.

# Charcoal, 907973 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 \$$.

• Your code (in your TIO page) wrongly gives 0 instead of 1 for some acute triangles. Jan 12 at 15:18
• @RosieF Ah yes I hadn't thought of the 17, 17, 18 case. After my latest golf I think I'll be able to rearrange to code to cope with that.
– Neil
Jan 12 at 15:50
• @RosieF Fixed; thanks for letting me know.
– Neil
Jan 12 at 16:00

# 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


# 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!