20
\$\begingroup\$

proposed by @Adám in chat

Given an even number of finite points return a line \$y=mx+b\$ that evenly splits the points on both sides.

Specs

  • Take a list of distinct points \$(x,y)\$ (or a list of x-coordinates and a list of y-coordinates), output a possible \$(m,b)\$ pair
  • Half of the points should be true for \$y>mx+b\$, the other half should be true for \$y<mx+b\$
  • All \$x, y\$ pairs are integers
  • There will always exist a line \$y=mx+b\$ which divides the points, in which \$m\$ and \$b\$ are integers, but you can output rationals

Test cases

[(1, 1), (-1, -1)] -> -1, 0
[(0, 0), (2, -3)] -> 1, -3
[(3, 4), (0, 0), (-2, -6), (4, -5), (-2, 1), (-23, -18)] -> (-2, -1)]
\$\endgroup\$
3
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – math scat
    Commented Feb 15, 2023 at 12:53
  • \$\begingroup\$ Is it allowed to take input as a list of x-coordinates and a list of y-coordinates? \$\endgroup\$
    – Yousername
    Commented Feb 16, 2023 at 17:18
  • \$\begingroup\$ @Downvoters please leave a comment below if the challenge is unclear \$\endgroup\$
    – math scat
    Commented Feb 18, 2023 at 20:05

9 Answers 9

9
\$\begingroup\$

Vyxal, 22 21 bytes

Þn:Ẋλ⁰∩YṘ÷*+-±₌A∑¬∧;c

Try it Online!

-1 byte: Fixed a bug and saved a byte thanks to @KevinCruijssen

Simply tries all integer pairs until one works.

Þn                      # all integers
  :                     # duplicate
   Ẋ                    # cartesian product
    λ               ;c  # find first pair [m,b] such that:  
     ⁰∩                 #   transposed input [x-coords, y-coords]
       Y                #   interleave [m, x-coords, b, y-coords]
        Ṙ               #   reverse [y-coords, b, x-coords, m]
         ÷              #   push each to stack
          *             #   multiply
           +            #   add
            -           #   subtract
             ±          #   sign
              ₌A∑¬∧     #   are all non zero and is the sum 0?
\$\endgroup\$
0
8
\$\begingroup\$

MATL, 39 38 bytes

`,Xrk]XJxXIx0G"1@g0Jh-lIh&v0&|ZS/+]]IJ

Input is a cell array of 1×2 vectors. Output is m, then b.

This produces a random output among all valid outputs, possibly different in each run. Running time is also random, but the code ends in finite time with probability 1.

Try it online!

Or try at MATL Online including a plot with the points and the solution line.

How it works

The code randomly picks integer values for m and b until a solution is found. The choice of each of those two values follows a normalized Gaussian distribution rounded down. This ensures that each integer pair has a non-zero probability, and will eventually be tried with probability 1.

For each m and b, the value b is first subtracted from the y-coordinate of all points. This has the effect of shifting the line vertically so now it passes through the origin with direction given by the vector [1, m].

To test which side of the line a point [x, y] is in, the vector product of [1, m] and [x, y] is computed. This is equivalent to the determinant of the 2×2 matrix formed by those vectors. The sign of the result indicates the side, with a 0 meaning that the point is exactly on the line. Thus, a line is valid if and only if the sum of all signs is 0 and no sign was 0. This is tested by computing the sum of the inverses of the signs and checking if it is 0 (if a sign is 0 the sum will give an infinite result).

\$\endgroup\$
0
6
\$\begingroup\$

Python, 54 bytes

lambda L:[m:=1+L.ptp(),sorted(L@[-m,1])[len(L)//2]-.5]

Attempt This Online!

Takes an Nx2 NumPy array.

Slightly longer but more readable version:

Python, 58 bytes

lambda L:[m:=1+ptp(L),median(L@[-m,1])]
from numpy import*

Attempt This Online!

How?

This chooses a slope larger than the "diameter" of the given point cloud to avoid any ties.

\$\endgroup\$
5
  • \$\begingroup\$ 50 bytes if you accept L as a pandas DataFrame: lambda L:[m:=1+L.values.ptp(),(L@[-m,1]).median()] \$\endgroup\$
    – tsh
    Commented Feb 16, 2023 at 2:47
  • \$\begingroup\$ @tsh Thanks! Is there a site that has pandas (ATO doesn't seem to)? \$\endgroup\$
    – loopy walt
    Commented Feb 16, 2023 at 4:07
  • \$\begingroup\$ I don't have one. I tested it on my locale machine. \$\endgroup\$
    – tsh
    Commented Feb 16, 2023 at 5:27
  • \$\begingroup\$ Doesn't the first answer also need to include a numpy import, since it uses numpy arrays? \$\endgroup\$ Commented Feb 17, 2023 at 15:49
  • 1
    \$\begingroup\$ @97.100.97.109 No. \$\endgroup\$
    – loopy walt
    Commented Feb 17, 2023 at 16:05
5
\$\begingroup\$

Python, 169 bytes

def g(P,*p):
 a,b,c=p or[0]*3
 for i,(x,y)in enumerate(P):l=2*(i<len(P)/2)-1;q=a*x+b*y+c;v=(q*l<=0)*(l-q);a+=v*x;b+=v*y;c+=v;z=a,b,c
 return z!=p and g(sorted(P),*z)or z

Attempt This Online!

Sort of cheating, since it outputs the values \$(a,b,c)\$ defining the line \$ax+by+c=0 \Rightarrow y = (-ax-c)/b = -\frac{a}{b}x - \frac{c}{b}\$.

Explanation to be added later, but in brief:

  • Sorts the points, then says that the first half of the list is in one group and the second half is in another (I believe this always produces two sets which are separable, but I haven't proved it).
  • Uses a perceptron algorithm to find the line which classifies those points.
\$\endgroup\$
5
\$\begingroup\$

Jelly, 30 bytes

A lot of bytes, and extra computation, to effectively break on the first found solution :(

×Ṛ_+⁸ṪṠ
ŒRṗ2çⱮS¬ȧẠƲ¥Ƈ
1ç1#Ṫç⁸Ḣ

A monadic Link that accepts a list of the coordinates that yields a pair of integers, \$[m, b]\$.

Try it online!

How?

×Ṛ_+⁸ṪṠ - Link 1 side of the line: L=[m, b]; P=[x, y]
×       - (L) multiply (P) -> [mx, by]
 Ṛ      - reverse (that)   -> [by, mx]
  _     - subtract (P)     -> [by-x, mx-y]
    ⁸   - chain's left argument = L
   +    - add              -> [by-x+m, mx-y+b]
     Ṫ  - tail             -> mx-y+b = (mx+b)-y
      Ṡ - sign -> 1 (below), 0 (on), or -1 (above)

ŒRṗ2çⱮS¬ȧẠƲ¥Ƈ - Link 2 find solutions: integer k, coordinates C
ŒR            - span-range -> [-abs(k)..abs(k)]
  ṗ2          - second Cartesian power -> all [m,b] using values from -k to k
            Ƈ - filter keep those for which:
           ¥  -   last two links as a dyad - f(L=[m,b], C)
     Ɱ        -     map (across each coordinate pair, P, in C) with:
    ç         -       call Link 1 - f(L, P) -> side of the line
          Ʋ   -     last four links as a monad - f(A=that):
      S       -       sum (A)
       ¬      -       logical NOT (that)
         Ạ    -       all (A)?
        ȧ     -       logical AND

1ç1#Ṫç⁸Ḣ - Link: coordinates C
1        - set the left argument to one
  1#     - find the first one integers, k (incrementing), for which:
 ç       -   call Link 2 - f(k, C) -> empty lists are falsey
    Ṫ    - tail -> get the k value found
      ⁸  - chain's left argument = C
     ç   - call Link 2 - f(found k, C)
       Ḣ - head (that)
\$\endgroup\$
4
\$\begingroup\$

Python3, 268 bytes:

import math as M,statistics as S
K=lambda p,x,y:(m:=M.tan(S.median([M.atan2(Y-y,X-x)for X,Y in p])),y-m*x)
def v(p,x,y):
 t=[0,0]
 for X,Y in p:t[Y<(x*X+y)]+=1
 return t[0]==t[1]
f=lambda p:[R for t in p for T in p-{t} if v(p,*(R:=K(p,(t[0]+T[0])/2,(t[1]+T[1])/2)))][0]

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 250 bytes \$\endgroup\$
    – okie
    Commented Feb 16, 2023 at 0:45
  • \$\begingroup\$ 5 more saved i think putting v and f together saves more \$\endgroup\$
    – okie
    Commented Feb 16, 2023 at 1:17
  • \$\begingroup\$ Save 2 more bytes by moving f= out of the main code block \$\endgroup\$
    – jezza_99
    Commented Feb 16, 2023 at 6:39
4
\$\begingroup\$

Charcoal, 39 bytes

≔Eθ↨ι⁰η≔⊕⁻⌈η⌊ηηW⁻Eθ↨κ±ηυ⊞υ⌊ιI⟦η⁻§υ⊘Lυ·⁵

Try it online! Link is to verbose version of code. Explanation: Inspired by @loopywalt's NumPy answer.

≔Eθ↨ι⁰η≔⊕⁻⌈η⌊ηη

Calculate m as the incremented maximum y extent between any two points.

W⁻Eθ↨κ±ηυ⊞υ⌊ι

Calculate and sort what the y-intercepts would be for lines of gradient m that pass through each point. (These must all be different due to the size of m calculated above.)

I⟦η⁻§υ⊘Lυ·⁵

Output m and a y-intercept that divides the set of points into two.

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

05AB1E, 29 bytes

∞<D(.ιæ2ù.ΔIø.ιR`*+-DĀPs.±O_*

Port of @AndrovT's Vyxal answer.

Try it online or verify all test cases.

Explanation:

∞           # Push an infinite positive list: [1,2,3,...]
 <          # Decrease it to a non-negative list: [0,1,2,...]
  D(        # Push a negative copy: [0,-1,-2,...]
    .ι      # Interleave the lists together: [0,0,1,-1,2,-2,...]
      æ     # Get the powerset of this list
       2ù   # Only keep all pairs: [[0,0],[0,1],[0,1],[0,-1],[0,-1],[1,-1],[0,2],...]
.Δ          # Pop and keep the first pair [m,b] that's truthy for:
  Iø        #  Push the transposed/zipped input-list, swapping its rows/columns
    .ι      #  Interleave it with the current pair: [m,x-coords,b,y-coords]
      R`    #  Push it in reversed order to the stack
        *   #  Multiply m to the x-coords
         +  #  Add b to each
          - #  Subtract each from the y-coords
  DĀPs.±O_* #  Check that there is an equal amount of positive/negative values and no 0s:
  D         #   Duplicate the list
   Ā        #   != 0 check on each
    P       #   Product to check all are truthy
     s      #   Swap so the list is at the top again
      .±    #   Signs of each integer
        O   #   Sum them together
         _  #   ==0 check
          * #   Check if both are truthy
            # (after which the found [m,b]-pair is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 162 bytes

Catch[n=0;While[True,m=(-1)^n⌊(n+1)/2⌋;a=#[[2]]-m#[[1]]&/@#1;Do[If[Values@CountsBy[b-a,Sign]=={#2,#2},Throw[{m,b}]],{b,Range@@MinMax@a}];n++]]&[#,Length@#/2]&

Try it online!

Start from \$m = 0\$. Going through \$0, -1, 1, -2, 2, …\$ (OEIS A130472)
Find \$b_{min}\$ and \$b_{max}\$ that bounded array of points with given \$m\$ (here \$m = -2\$):

enter image description here

Scan from \$b_{min}\$ to \$b_{max}\$. If the test line halves the array and does not pass through any point then throw-catch {m,b}. Else test the next \$m\$.
Fast and reliable algorithm, find \$m\$ closest to \$0\$, so solution for the last test case is {0, -4} (but we can start from any other value).

Ungolfed version:

halfline[pts_] := With[{h = Length@pts/2},
    n = 0;
    Catch[
     While[True,
      m = (-1)^n ⌊(n + 1)/2⌋;
      arr = #[[2]] - m #[[1]] & /@ pts;
      Do[
       If[Values@CountsBy[b - arr, Sign] == {h, h}, 
         Throw[{m, b}]
         ]
       , {b, Range @@ MinMax@arr}];
      n++
      ]
     ]
    ] /; MatrixQ[pts, IntegerQ];

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.