14
\$\begingroup\$

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
\$\endgroup\$
7
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – Wheat Wizard Jan 10 at 16:34
  • 2
    \$\begingroup\$ 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.) \$\endgroup\$ – Dude coinheringaahing Jan 10 at 17:06
  • 3
    \$\begingroup\$ Suggested test case: 4 4 5 -> false, which prevents set-based comparison of side lengths. \$\endgroup\$ – Bubbler Jan 10 at 23:48
  • 3
    \$\begingroup\$ I think it would help to list test cases in a way that is easy to copy-paste in addition to the annotation ones. \$\endgroup\$ – xnor Jan 11 at 0:59
  • \$\begingroup\$ @xnor Seeing as different languages will have different syntax requirements, how should I do this? \$\endgroup\$ – Rosie F Jan 12 at 15:29
5
\$\begingroup\$

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!

\$\endgroup\$
9
  • 1
    \$\begingroup\$ You can use TIO like this and in there get a code-golf link you can simply paste into your answer. \$\endgroup\$ – Noodle9 Jan 10 at 22:42
  • 2
    \$\begingroup\$ 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! \$\endgroup\$ – ovs Jan 10 at 23:40
  • 2
    \$\begingroup\$ Fails at 4 4 5 -> false, which can be fixed by using range(-max(l),max(l)) and removing set conversion entirely. \$\endgroup\$ – Bubbler Jan 10 at 23:50
  • 2
    \$\begingroup\$ The itertools import should be in the code and count for bytes. \$\endgroup\$ – xnor Jan 11 at 1:02
  • 4
    \$\begingroup\$ @xnor Not that it really matters here, but l in(...) is a bit faster and uses very little memory. \$\endgroup\$ – ovs Jan 11 at 9:18
5
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ {RćsO‹ can be a byte shorter with `: {R`+‹ \$\endgroup\$ – ovs Jan 11 at 12:48
4
\$\begingroup\$

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)
\$\endgroup\$
5
  • \$\begingroup\$ I also found a different <s>25</s> 24 bytes solution: ZÝã3ãʒÁ-nOIQ}gĀIt{RćsO‹* \$\endgroup\$ – Command Master Jan 11 at 9:02
  • \$\begingroup\$ Actually it can be 23 bytes by also doing what you did with map instead of filter \$\endgroup\$ – Command Master Jan 11 at 9:10
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Jan 11 at 9:12
  • 1
    \$\begingroup\$ 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‹* \$\endgroup\$ – Command Master Jan 11 at 9:48
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen Jan 11 at 9:52
4
\$\begingroup\$

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!

\$\endgroup\$
7
  • \$\begingroup\$ You can still use @ceilingcat suggestion ;) Try it online! \$\endgroup\$ – AZTECCO Jan 13 at 15:40
  • \$\begingroup\$ @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 :) \$\endgroup\$ – Sheik Yerbouti Jan 13 at 17:32
  • \$\begingroup\$ @Davide nice to help! I tried the eax trick also in the previous suggestion but it didn't worked for some reason \$\endgroup\$ – AZTECCO Jan 13 at 17:44
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ – Sheik Yerbouti Jan 13 at 17:55
  • \$\begingroup\$ @ceilingcat whoo that's clever I missed it \$\endgroup\$ – Sheik Yerbouti Jan 14 at 10:58
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 90 79 73 71 bytes

≔⌈θη≔⁻Σθ⁺η⌊θζ≔…·±ζζεFεFε¿⁼⌊θ⁺Xι²Xκ²FεFε¿⁼ζ⁺Xλ²Xμ²¿⁻×ιμ×κλP⁼η⁺X⁺ιλ²X⁺κμ²

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

FεFε¿⁼⌊θ⁺Xι²Xκ²

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.

FεFε¿⁼ζ⁺Xλ²Xμ²

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

P⁼η⁺X⁺ιλ²X⁺κμ²

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

\$\endgroup\$
3
  • \$\begingroup\$ Your code (in your TIO page) wrongly gives 0 instead of 1 for some acute triangles. \$\endgroup\$ – Rosie F Jan 12 at 15:18
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Jan 12 at 15:50
  • \$\begingroup\$ @RosieF Fixed; thanks for letting me know. \$\endgroup\$ – Neil Jan 12 at 16:00
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

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