# Counting Collinear Points

Given two points $$\(x_1, y_1)\$$ and $$\(x_2, y_2)\$$ with integer coordinates, calculate the number of integer points (excluding the given points) that lie on the straight line segment joining these two points. Use any maths formula you like, such as

$$gcd(|x_2 - x_1|, |y_2 - y_1|) - 1$$

Input

Four integer coordinates of the two points: $$\x_1, y_1, x_2, y_2\$$.

Output

Number of integer points between the two given points.

# Test Cases

Integer Coordinates In-between Points
(5,10),(10,5) 4
(-8,5),(0,5) 7
(-3,-3),(2,2) 4
• You should give some harder test cases, like slope of 3/2.
– qwr
Jan 9 at 2:25
• And include one that goes down and to the left. I thought I could golf one, but it failed on just that case.
– Tbw
Jan 9 at 8:41
• Consider add some testcases that result is 0: (0,0),(1,1), (1,1),(8,24), some test cases that x0=x1: (0,0),(0,5)
– tsh
Jan 10 at 3:10
• Do we need to handle vertical / horizontal lines? Jan 10 at 4:01
• @noodleman yes, that's one of the test cases.
– qwr
Jan 10 at 20:06

# Vyxal, 3 bytes

εġ‹

Try it Online!

Port of Jonathan Allan's Jelly answer.

ε   # Absolute difference - [|x1-x2|,|y1-y2|]
ġ  # gcd of that list
‹ # decrement

# Jelly, 4 bytes

ạg/’

A dyadic Link that accepts a point as a pair on each side and yields the count.

Try it online!

### How?

Implements the provided greatest common divisor formula.

ạg/’ - Link: pair of integers [x1, x2]; pair of integers [y1, y2]
ạ    - absolute difference (vectorises) -> [|x1-y1|, |x2-y2|]
/  - reduce by:
g   -   greatest common divisor -> GCD(|x1-y1|, |x2-y2|)
’ - decrement -> GCD(|x1-y1|, |x2-y2|) - 1
• Thanks for stating the method. I'm interested to see the various maths formulas that arise from this challenge. Jan 9 at 1:12
• There's pretty much only variations of gcd.
– qwr
Jan 9 at 2:27

# Desmos, 17 bytes

f(A,B)=gcd(A-B)-1

Takes input as two two-element lists.

This uses the formula as stated in the question, but it seems like gcd is always positive even with negative numbers, so I don't need to take the absolute difference, but rather just regular difference.

Try It On Desmos!

# Nekomata, 4 bytes

≈đG←

Attempt This Online!

Takes input as two pairs of numbers, e.g. [-8,5] [0,5].

≈đG←
≈       Absolute difference (vectorized)
đ      Unpair; get the two elements of a pair
G     GCD
←    Decrement

I wonder how an approach that defines the solution to be an integer point on the line, and using -n for the final result. (I haven't really tried to learn Nekomata yet and somehow doubt it would be shorter for this problem, but seems interesting) – noodle man

The shortest I can get using this approach is 10 bytes:

# Nekomata + -n, 10 bytes

≈:Ṁᵉ{~Z*}¦

Attempt This Online!

≈:Ṁᵉ{~Z*}¦      Take [-8,5] [0,5] as an example
≈           Absolute difference (vectorized)
[-8,5] [0,5] -> [8,0]
:          Duplicate
[8,0] -> [8,0] [8,0]
Ṁ         Maximum
[8,0] [8,0] -> [8,0] 8
ᵉ{       Apply the following block and then push the original top of stack
~Z       Choose any integer in [1,n)
[8,0] 8 -> [8,0] 1 or [8,0] 2 or ... or [8,0] 7
*      Multiply
[8,0] 1 -> [8,0]
[8,0] 2 -> [16,0]
...
[8,0] 7 -> [56,0]
}   End the block (ᵉ pushes the original top of stack)
[8,0] -> [8,0] 8
[16,0] -> [16,0] 8
...
[56,0] -> [56,0] 8
¦  Divide and check if the result is an integer
[8,0] 8 -> [1,0]
[16,0] 8 -> [2,0]
...
[56,0] 8 -> [7,0]

-n counts the number of solutions, so the output is 7.

• I wonder how an approach that defines the solution to be an integer point on the line, and using -n for the final result. (I haven't really tried to learn Nekomata yet and somehow doubt it would be shorter for this problem, but seems interesting) Jan 10 at 3:59

# APL(Dyalog Unicode), 7 bytes SBCS

¯1+∨/⍤-

Try it on APLgolf!

A tacit function which takes vectors on the left and right and returns an integer. I believe this solution also works in any dimension, not just 2D. It takes the difference of the points, GCD all of the differences, and adds -1.

# Charcoal, 28 bytes

ＮθＮη≧⁻Ｎθ≔∨⁻ηＮθηＩＬΦ↔η∧ι¬﹪×ιθη

Try it online! Link is to verbose version of code. Explanation: No vectorised difference or gcd, so I have to do things the hard way.

ＮθＮη

Input the first co-ordinate.

≧⁻Ｎθ≔∨⁻ηＮθη

Subtract the second co-ordinate, but if it is horizontal then make it diagonal, which has the same number of intermediate points.

ＩＬΦ↔θ∧ι¬﹪×ιηθ

Generate a list of intermediate y-coordinates and see how many x-coordinates are integers.

• Maybe failed for 0 0 0 5
– tsh
Jan 10 at 3:16
• @tsh Thanks, I've spent 3 bytes on a fix.
– Neil
Jan 10 at 8:23

# Uiua, 12 bytes SBCS

-1;⍢⊃◿∘±°⊟⌵-

Try it!

-1;⍢⊃◿∘±°⊟⌵-
-  # difference
⌵   # absolute value
°⊟    # uncouple pair to stack
;⍢⊃◿∘±      # GCD
-1            # decrement

# Retina 0.8.2, 97 bytes

,(.+),(.+),
,$2¶$1,
%O[^,]+
\d+
$* -(1+),(1+)$1$2 (1+),-?\1|[^1¶] mO^^.* ^(1(1*))\1*¶\1*$
$.2 Try it online! Link includes test cases. Explanation: ,(.+),(.+), ,$2¶$1, Exchange the first y-coordinate with the second x-coordinate and split the coordinates onto separate lines. %O[^,]+ Ensure that if either coordinate is negative then the first one is. \d+$*

Convert to unary.

-(1+),(1+)
$1$2

If the co-ordinates have different signs then add their absolute values together.

(1+),-?\1|[^1¶]

Otherwise take the absolute difference.

mO^^.*

Sort them descending in case the first difference is zero.

^(1(1*))\1*¶\1*.2

Calculate the decremented GCD.

# R, 62 bytes

\(x,y)max((y=1:max(z<-abs(x-y)))[!z[1]%%y&!z[2]%%y|!all(z)])-1

Attempt This Online!

Base R has no built in for GCD.

# JavaScript (Node.js), 50 bytes

(p,q,r,s)=>(g=r=>s?g(s,s=r%s):r*r)(r-p,s-=q)**.5-1

Try it online!

Basically based on the formula in the question. Calculate

$$\sqrt{\left(\text{gcd}(x_2-x_1,y_2-y_1)\right)^2}-1$$

where $$\\text{gcd}\$$ is defined as

$$\text{gcd}(x,y)=\begin{cases} x & y=0 \\ \text{gcd}(y,x \bmod y) & \text{otherwise} \end{cases}$$

• The square root seems unnecessary.
– Neil
Jan 11 at 17:05
• @Neil it is replacement of absolute values.
– tsh
Jan 12 at 4:57
• I've figured it out now... sorry for the confusion.
– Neil
Jan 12 at 11:44

¯1+∨/∣⎕-⎕

test&how use:

¯1+∨/∣⎕-⎕
⎕:
¯8 5
⎕:
0 5
7
~

¯1+∨/∣⎕-⎕
⎕:
5 10
⎕:
10 5
4
~

# C (gcc), 104 bytes

-5 bytes, thanks to @ceilingcat

g(a,b){return b?g(b,a%b):abs(a);}main(x,y,a,b){scanf("%d%d%d%d",&x,&y,&a,&b);printf("%u",g(x-a,y-b)-1);}

Try it online!

• I think meta consensus is that you can write a function instead of a whole program.
– qwr
Jan 12 at 0:58