16
\$\begingroup\$

Task

Write a program/function that when given three 2d points in cartesian coordinates as input outputs a truthy value if they are collinear otherwise a falsey value

Three points are said to be collinear if there exists a straight line that passes through all the points

You may assume that the coordinates of the three points are integers and that the three points are distinct.

Scoring

This is so shortest bytes wins

Sample Testcases

(1, 1), (2, 2), (3, 3) -> Truthy
(1, 1), (2, 2), (10, 10) -> Truthy
(10, 1), (10, 2), (10, 3) -> Truthy
(1, 10), (2, 10), (3, 10) -> Truthy
(1, 1), (2, 2), (3, 4) -> Falsey
(1, 1), (2, 0), (2, 2) -> Falsey
(-5, 70), (2, 0), (-1, 30) -> Truthy
(460, 2363), (1127, 2392), (-1334, 2285) -> Truthy
(-789, -215), (-753, -110), (518, -780) -> Falsey
(227816082, 4430300), (121709952, 3976855), (127369710, 4001042) -> Truthy
(641027, 3459466), (475989, 3458761), (-675960, 3453838) -> Falsey
\$\endgroup\$
  • 3
    \$\begingroup\$ May we take the input points as complex numbers? \$\endgroup\$ – fireflame241 Jul 8 at 3:42
  • 3
    \$\begingroup\$ Are three points guaranteed to be distinct? \$\endgroup\$ – Bubbler Jul 8 at 3:55
  • \$\begingroup\$ @fireflame241 yes complex numbers as input is acceptable \$\endgroup\$ – Mukundan314 Jul 8 at 5:00
  • \$\begingroup\$ @Bubbler the three points are guaranteed to be different updated the question to reflect that \$\endgroup\$ – Mukundan314 Jul 8 at 5:02

19 Answers 19

14
\$\begingroup\$

Octave, 21 bytes

Takes a matrix [x1, y1; x2, y2; x3, y3] as input.

@(a)~det([a,[1;1;1]])

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can shorten to @(a)~det([a,e(3,1)]) (the output is suject to floating-point errors even with your current approach) \$\endgroup\$ – Luis Mendo Jul 8 at 13:09
12
\$\begingroup\$

JavaScript (Node.js), 39 bytes

(a,b,c,d,e,f)=>a*d+c*f+e*b==b*c+d*e+f*a

Try it online!

Accepts input as (x1, y1, x2, y2, x3, y3). Uses the shoelace formula to determine if the enclosed area is 0.

Explanation

The shoelace formula states that, the area of a polygon can be calculated using the coordinates of its vertices. Specifically, assuming the vertices are \$P_1, P_2, \cdots, P_n\$ so that \$P_1P_2, P_2P_3, \cdots, P_{n-1}P_n, P_nP_1\$ are the edges of the polygon, then the area \$A\$ can be calculated with

$$A=\frac{1}{2}\left|(x_1y_2+x_2 y_3+\cdots+x_{n-1}y_n+x_ny_1)-(y_1x_2+y_2x_3 +\cdots+y_{n-1}x_n+y_nx_1)\right|$$

where \$(x_n,y_n)\$ are the coordinates of \$P_n\$.

Taking \$n=3\$, we have the formula for the area of a triangle with coordinates \$(x_1,y_1)\$, \$(x_2,y_2)\$ and \$(x_3,y_3)\$:

$$A=\frac{1}{2}\left|(x_1y_2+x_2y_3+x_3y_1)-(y_1x_2+y_2x_3+y_3x_1)\right|$$

Three points are collinear if and only if the triangle constructed by these points has a zero area (otherwise, one of the points lies away from the line segment between the other two points, giving a non-zero area to the triangle). Since we only need to check whether the area is 0, the 1/2 and the absolute can be ignored. This boils down to checking whether

$$(x_1y_2+x_2y_3+x_3y_1)-(y_1x_2+y_2x_3+y_3x_1)=0$$

or after rearranging terms

$$x_1y_2+x_2y_3+x_3y_1=y_1x_2+y_2x_3+y_3x_1$$

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ I love this. It's exactly the same length as (c-a)*(f-b)==(d-b)*(e-a) (which seemed more intuitive to me), but now I've been introduced to the 'shoelace formula' that I'd never heard of before! \$\endgroup\$ – Dominic van Essen Jul 8 at 8:35
11
\$\begingroup\$

Jelly, 4 bytes

_ÆḊ¬

Try it online!

Takes the differences [(a-b), (a-c)] via automatic vectorization of a-[b-c] then checks if the determinant (ÆḊ) is 0 (¬).

| improve this answer | |
\$\endgroup\$
10
\$\begingroup\$

APL (Dyalog Unicode), 9 8 bytes

0=11○÷.-

Try it online!

-1 byte thanks to @Jo King.

Takes one complex number (A) on the left, and two complex numbers (B and C) on the right. APL automatically maps scalars, so A - B C gives (A-B)(A-C). Then divide between the two ÷., and check if the result's imaginary part 11○ is zero 0=.

Uses ⎕DIV←1, so if division by zero would occur (because A=C), ÷ returns 0 instead, which obviously has imaginary part of zero, giving truthy as a result.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Would cause a division by zero if A=C. Maybe check if the phases 12○ are equal or (A-B)*conjugate of (A-C) is real. \$\endgroup\$ – fireflame241 Jul 8 at 3:54
  • \$\begingroup\$ @fireflame241 Phase equal doesn't work because the two can be in opposite direction. Multiplying conjugate sounds good, and is also free from possible float inaccuracies (should work at the cost of 2 bytes). \$\endgroup\$ – Bubbler Jul 8 at 4:00
  • 1
    \$\begingroup\$ "Uses ⎕DIV←1" - this is necesssary and is code (not a flag making a different "language") so shouldn't it be part of the byte count? \$\endgroup\$ – Jonathan Allan Jul 8 at 12:05
  • \$\begingroup\$ @JonathanAllan It is a system setting, which can be set outside the interpreter as an environment variable. Not counting system setting in code length is also mentioned here. \$\endgroup\$ – Bubbler Jul 8 at 22:59
  • \$\begingroup\$ @JoKing Of course it does. \$\endgroup\$ – Bubbler Jul 8 at 22:59
8
\$\begingroup\$

Python 2, 39 bytes

lambda a,b,c:(a-b)*(a-c-(a-c)%1*2)%1==0

Try it online!

Input: the 3 points as 3 complex numbers
Output: True or False.

How

Let the 3 points be \$(a,A), (b,B), (c,C)\$

The 3 points are colinear iff \$(a-b)*(A-C)=(A-B)*(a-c)\$. Note that this formula doesn't have division, and thus won't have floating point issue. Consider the following complex multiplication: $$ \big((a-b)+(A-B)i\big) * \big((a-c)-(A-C)i\big)$$ The imaginary part of the result is: $$(a-c)(A-B)-(a-b)(A-C)$$ which must be \$0\$ for the 3 points to be colinear.

Let a, b, c be the complex representation of the 3 points, then the condition above is equivalent to:

t = (a-b) * (a-c).conjugate()
t.imag == 0

Instead of using imag and conjugate, we can take advantage of the fact that all points are integers. For a complex number t where both the real and imaginary parts are integers, t%1 gives the imaginary part of t. Thus:

t % 1 == t.imag * 1j
t - t % 1 * 2 == t.conjugate()

Old solution that doesn't use complex number

Python 3, 43 bytes

lambda a,A,b,B,c,C:(a-b)*(A-C)==(A-B)*(a-c)

Try it online!

Input: the 2 coordinates of the first point, then the 2nd point, then the 3rd point.
Output: True or False.


This should work theoretically, but doesn't because of floating point imprecision:

Python 3, 34 bytes

lambda a,b,c:((a-b)/(a-c)).imag==0

Try it online!

Input: 3 points, each represented by a complex number
Output: True or False.

| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

J, 13 7 bytes

0=-/ .*

Try it online!

Uses the determinant. J's generalized determinant u .v is defined for non-square matrices, still multiplying (*) each x value with the difference of the other two y values (-/), finally reducing that result (-/). -/ .* calculates the determinant, check if it is 0=.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Change ,. to , by taking the input transposed. \$\endgroup\$ – Bubbler Jul 8 at 8:19
  • \$\begingroup\$ @Bubbler it's even simpler. :-) \$\endgroup\$ – xash Jul 8 at 8:33
7
\$\begingroup\$

R, 22 bytes

function(x)lm(1:3~x)$d

Try it online!

Finally a challenge which calls for lm!

The function lm performs linear regression. Here, we are using the input x as covariates, and 1 2 3 as observations (any vector of length 3 would do).

The output is an object with many components; of interest here is df.residual (which can be accessed with the unambiguous abbreviation $d), the residual degrees of freedom. This number corresponds to the number of observations minus the number of parameters being estimated. Now:

  • if the points are not collinear, the regression proceeds normally, estimating 3 parameters, so df.residual == 0.
  • if the points are collinear, there is an identifiability issue and only 2 parameters can be estimated (the last will be given as NA), so df.residual == 1.

Note that the final test case fails due to numerical precision issues.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

Wolfram Language (Mathematica), 20 19 bytes

Det@{#2-#,#3-#}==0&

Try it online!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

R, 27 bytes

function(m)!det(cbind(1,m))

Try it online!

Port of alephalpha's Octave answer.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Bah! You beat me by 22 bytes within 11 seconds! \$\endgroup\$ – Dominic van Essen Jul 8 at 7:58
  • \$\begingroup\$ Well, it's just a different approach that, btw, I have learned just now :D \$\endgroup\$ – Kirill L. Jul 8 at 8:00
  • \$\begingroup\$ 22 bytes using lm: codegolf.stackexchange.com/a/206894/86301 :-) \$\endgroup\$ – Robin Ryder Jul 8 at 22:15
  • 1
    \$\begingroup\$ det(diff(m)) would work, I think \$\endgroup\$ – Giuseppe Jul 8 at 22:42
  • \$\begingroup\$ @Giuseppe, not really, the penultimate test case already gives a quite noticeable deviation from zero: TIO \$\endgroup\$ – Kirill L. Jul 9 at 7:36
4
\$\begingroup\$

Raku, 21 19 bytes

{!im [/] $^a X-@_:}

Try it online!

Takes input as three complex numbers and returns a boolean. Note that if the last and first points are identical (which is disallowed in the challenge spec), then the division operation would return NaN for dividing by zero, which boolifies to True for some reason, so this would fail.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

R, 49 bytes

function(p,q=p-p[,1])q[1,3]*q[2,2]==q[2,3]*q[1,2]

Try it online!

How?

  • Subtract first point from the other two:
  • if points are on a line, the line must now pass through (x=0,y=0)
  • so we check that the gradient=y/x is identical for both other points: y2/x2==y3/x3
  • but to avoid dividing by zero, we rearrange: y2x3==y3x2

Edit:

  • which, thanks to Kirill, alephalpha and Wikipedia, I've now discovered is simply the determinant of the matrix (x2,y2,x3,y3)
  • so, for only 29 bytes: function(p)!det(p[,-1]-p[,1])
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 18 17 27 21 bytes

-Dн_iIн¹нQë`s/Uн¹н-X*¹θ+IθQ

Try it online!

Verify All Test Cases!

-1 byte due to remembering implicit input exists and that variable assignment pops values

+10 due to bug fix regarding vertical lines :-(

-6 thanks to the wonderful @Kevin, who always manages to golf my 05AB1E answers! :D. Go and upvote his posts!

Explained

Before we even begin to look at the program, let's take a look at the maths needed to see if three points are collinear. Let our first point have co-ordinates \$(x_1, y_1)\$, our second point have co-ordinates \$(x_2, y_2)\$ and our third point have co-ordinates \$(x_3, y_3)\$.

If the three points are collinear, then point three will lie on the line formed by joining points one and two. In other words, \$x_3\$, when plugged into the equation formed by the line joining points 1 and 2, gives \$y_3\$.

"But what's the line between point 1 and 2?" I hear you ask. Well, we use the good old "point-graident" method to find the line's equation:

$$ y - y_1 = m(x - x_1), m = \frac{y_2 - y_1}{x_2 - x_1}\\ y - y_1 = \frac{y_2 - y_1}{x_2 - x_1}(x - x_1) $$

Now, we add \$y_1\$ to both sides to get an equation where plugging in an x value gives a single y value:

$$ y = \frac{y_2 - y_1}{x_2 - x_1}(x - x_1) + y_1 $$

Substituting \$x\$ for \$x_3\$ and \$y\$ for \$y_3\$ gives an equality that determines if three points are collinear.

Alright, time for the code (as explained by Kevin).

-                     "[x2-x1, y2-y1]"\
 V                    "pop and store it in variable `Y`"\
  ¹-                  "[x3-x1, y3-y1]"\
    н                 "Pop and leave only x3-x1"\
     Yн_i             "If x2-x1 from variable `Y` == 0:"\
         _            " Check if the x3-x1 at the top == 0"\
        ë             "Else:"\
         Y`s/         " Divide (y2-y1) by (x2-x1) from variable `Y`"\
             *        " Multiply it by the x3-x1 at the top"\
              ¹θ+     " Add x1"\
                 Q    " Check [x3 == this value, y3 == this value] with the implicit third input"\
                  θ   " And only keep the last one: y3 == this value"\
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @KevinCruijssen I accidentally left the X0Q from a previous explanation. But still, yes, it should be _ instead. \$\endgroup\$ – Lyxal Jul 8 at 7:17
  • \$\begingroup\$ I still have to verify all test cases (I'll try to write a test suite in a bit), but I think this 21 byter should work without changing your formula. \$\endgroup\$ – Kevin Cruijssen Jul 8 at 7:33
  • 1
    \$\begingroup\$ @KevinCruijssen codegolf.stackexchange.com/q/6467/78850 \$\endgroup\$ – Lyxal Jul 8 at 8:01
  • 1
    \$\begingroup\$ Oh, thank you! :) Tbh, I enjoy golfing other people's answers as much as writing answer myself. Glad I could help, and thanks for the bounty! \$\endgroup\$ – Kevin Cruijssen Jul 8 at 8:02
  • 1
    \$\begingroup\$ @KevinCruijssen No worries. It seems only fair given the amount of times I've had to write "-x bytes thanks to @Kevin"! ;P \$\endgroup\$ – Lyxal Jul 8 at 8:03
2
\$\begingroup\$

C# (Visual C# Interactive Compiler), 39 bytes

(a,A,b,B,c,C)=>(b-a)/(B-A)==(c-a)/(C-A)

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is interesting. I notice that it only works if you declare the input variables as doubles, otherwise it gives a divide-by-zero error when A equals B or C. So I'm wondering whether the variable declaration needs to be included in the byte count...? \$\endgroup\$ – Dominic van Essen Jul 12 at 8:15
  • \$\begingroup\$ The requirement for doubles is obviously removed by rearranging like this... \$\endgroup\$ – Dominic van Essen Jul 12 at 8:18
1
\$\begingroup\$

Charcoal, 21 bytes

NθNηNζ⁼×⁻ηN⁻θN×⁻ηN⁻θζ

Try it online! Link is to verbose version of code. Takes input as six integers and outputs a Charcoal boolean, i.e. - for collinear, nothing if not. Uses @SurculoseSputum's original formula. Explanation:

Nθ                      Input `a`
  Nη                    Input `A`
    Nζ                  Input `b`
         η              `A`
        ⁻               Minus
          N             Input `B`
       ×                Multiplied by
            θ           `a`
           ⁻            Minus
             N          Input `c`
      ⁼                 Equals
                η       `A`
               ⁻        Minus
                 N      Input `C`
              ×         Multiplied by
                   θ    `a`
                  ⁻     Minus
                    ζ   `b`
                        Implicitly print
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

[Excel], 37 bytes

=0=MDETERM(A1:C3+{0,0,1;0,0,1;0,0,1})

Example: enter image description here

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

[Google Sheets], 27 bytes

=0=MDETERM({A1:B3,{1;1;1}})

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 3562 bytes

sub d{($a,$b,$c,$d,$e,$f)=@_;$b*($c-$e)+$d*($e-$a)+$f*($a-$c)}

Try it online!

I've put the wrapping on as explained in the comments, and golfed the original "guts" down by picking out some common factors

$b*($c-$e)+$d*($e-$a)+$f*($a-$c)

(--First attempt --)

$b*$c+$d*$e+$f*$a-$a*$d-$c*$f-$e*$b

Try it online!

  • Not sure if this follows the rules (where are they?) for header and footer, as much trying out "tio" as anything.
  • This takes the test text as per the question and outputs the exact same text! In other words it's equivalent to while(<>){print}, provided you feed it a crib sheet. If you remove (or change) the answers from the input, it will supply them.
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't know Perl very well, but this seems like it takes input as predefined variables, which is not permitted since it would make this a snippet rather than a program/function. You can fix this e.g. by turning it into a full program (taking input from STDIN or other allowed in the linked meta) or including the full function header (sub det etc) in the code. Btw, welcome back to Code Golf! \$\endgroup\$ – fireflame241 Jul 11 at 3:01
  • 1
    \$\begingroup\$ Nice, but I think that the syntax works even better in AWK (which automatically divides the variables up in exactly the way you've used)... so I've stolen the approach, with acknowledgment. \$\endgroup\$ – Dominic van Essen Jul 12 at 7:44
  • \$\begingroup\$ The consensus for submissions are either full programs or functions, of which this is neither. Valid input/output formats are listed here. Usually people use headers to assign anonymous functions which are then called in the footer, possibly with some formatting of the input \$\endgroup\$ – Jo King Jul 12 at 11:15
  • 1
    \$\begingroup\$ Your actual submission be this at 83 bytes (though this is obviously golfable) \$\endgroup\$ – Jo King Jul 12 at 11:18
1
\$\begingroup\$

Husk, 7 bytes

EẊoF/z-

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

AWK, 45 bytes

{print!($2*$3+$4*$5+$6*$1-$1*$4-$2*$5-$3*$6)}

Try it online!

Near-identical to Rich Farmbrough's Perl answer, but the syntax seemed better-suited to AWK than Perl. Thanks Rich!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I extracted some common factors, and saved a few bytes. \$\endgroup\$ – Rich Farmbrough Jul 13 at 14:10
  • \$\begingroup\$ @Rich Farmbrough Well done! That would bring the AWK clone to 42 bytes, although copying you a second time seems sneaky so I'm leaving it here in the comment section... \$\endgroup\$ – Dominic van Essen Jul 13 at 14:48

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.