To find whether a given line (equation) is able to separate the two lists of points sucessfully in python – Code Utility

[

I’m given a problem that explicitly asks me to not use either numpy or pandas

Problem :

Given two set of data points in the form of list of tuples like

Red =[(R11,R12),(R21,R22),(R31,R32),(R41,R42),(R51,R52),..,(Rn1,Rn2)]
Blue=[(B11,B12),(B21,B22),(B31,B32),(B41,B42),(B51,B52),..,(Bm1,Bm2)]

and set of line equations(in the string format, i.e list of strings)

Lines = [a1x+b1y+c1,a2x+b2y+c2,a3x+b3y+c3,a4x+b4y+c4,..,K lines]

Note: You need to do string parsing here and get the coefficients of x,y and intercept.

Your task here is to print “YES”/”NO” for each line given. You should print YES, if all the red points are one side of the line and blue points are on other side of the line, otherwise you should print NO.

Ex:

Red= [(1,1),(2,1),(4,2),(2,4), (-1,4)]
Blue= [(-2,-1),(-1,-2),(-3,-2),(-3,-1),(1,-3)]
Lines=["1x+1y+0","1x-1y+0","1x+0y-3","0x+1y-0.5"]


Output:
YES
NO
NO
YES

Mathematically, you take the equation of the line say S

Suppose S(x)(y) = 1x+1y+0

Now take points (1,1) and (-6,-1)

S(1)(1) = 1(1)+ 1(1) = 2 >0

S(-6)(-1) = 1(-6)+(1)(-1) = -7 <0

Therefore, we can conclude that (1,1) and (-6,-1) lie on different sides of the line S.

Now in the given problem, given an equation S all red should be on one side of the equation and blue on the other side.

The issue here is that, I’m not sure how you substitute values of the points in the lists in the equation given in the form of a string using python.

Also, I’m falling short of coming up with a logic (how to use loops accroding to our requirement) for the code to solve the above to solve the above question.

Would appreciate insights on this question. Thanks in advance.

,

Assuming you strings are always of the form

ax+by+c

(in that order), you could write

import re

for line in Lines:
    a, b, c = [float(coef.strip()) for coef in re.split('x|y', line)]
    ...

,

use your_string.replace() and eval() function,
replace x and y characters with it’s values,
eval() to execute string as equation

for element in red:
    equation=line.replace('x','*'+str(element[0]))
    equation=equation.replace('y','*'+str(element [1]))
    result=eval(equation)
    if result > 0:
        pass
    else:
        return "NO"
#code for blue
return "Yes"

,

Python3 program to check if two points lie on the same side

def pointsAreOnSameSideOfLine(a, b, c, x1, y1, x2, y2): 
fx1 = 0 # Variable to store a * x1 + b * y1 - c 
fx2 = 0 # Variable to store a * x2 + b * y2 - c 
fx1 = a * x1 + b * y1 - c 
fx2 = a * x2 + b * y2 - c 

# If fx1 and fx2 have same sign 
if ((fx1 * fx2) > 0): 
    return True
return False

Driver code

a, b, c = 1, 1, 1
x1, y1 = 1, 1
x2, y2 = 2, 1
if (pointsAreOnSameSideOfLine(a, b, c, x1, y1, x2, y2)): 
    print("Yes") 
else: 
    print("No") 

,

@hemanth ravavarapu, re.split(x|y) will be splitting line equation based on x or y. i.e if you give space then it will split based on space same here also it splitting where ever it found x or y.

,

e1 = []
e2 = []
def points():
    for k in Lines:
        a=k[0];b=k[2]+k[3];c=k[5]+k[6]
        n = [];m=[]
        for i in Red:
            x1=i[0];y1=i[1]
            eq1 = int(a) * int(x1) + int(b) * int(y1)-int(c)
            n.append(eq1)
        e1.append(n)
        for j in Blue:
            x2=j[0];y2=j[1]
            eq2 = int(a) * int(x2) + int(b) * int(y2)-int(c)
            m.append(eq2)
        e2.append(m)
    print(e1)
    print('----------------------------------------------------------------------')
    print(e2)
    print('----------------------------------------------------------------------')
    p=[]
    for i,j in zip(e1,e2):
        q = []
        for k,l in zip(i,j):
            x=k*l
            if x<0:
                q.append(x)
        p.append(q)
    print(p)
    for i in p:
        if len(i)==5:
            print('yes')
        else:
            print('No')

Red= [(1,1),(2,1),(4,2),(2,4),(-1,4)]
Blue= [(-2,-1),(-1,-2),(-3,-2),(-3,-1),(1,-3)]
Lines=["1x+1y+0","1x-1y+0","1x+0y-3","0x+1y-0.5"]
points()

,

For string parsing :

def getCor(s):

    first = s.split('x')
    a = float(first[0])
    
    second = first[1].split('y')
    b = float(second[0])
    c = float(second[1])
    
    return (a,b,c)

getCor('24x+1y-0.5')

Output :

(24.0, 1.0, -0.5)

,

import math

def getCor(s):
 
    first = s.split('x')
    a = float(first[0])
    
    second = first[1].split('y')
    b = float(second[0])
    c = float(second[1])
    
    return (a,b,c)


def getSide(t,p):
    
    cal = (t[0] * p[0]) + (t[1] * p[1]) + (t[2])

    if cal > 0:
        return 1
    elif cal < 0:
        return -1
    elif cal == 0:
        return 0
    return -2


def getAns(red,blue,line):
    
    sign_red = getSide(getCor(line),red[0])
    sign_blue = getSide(getCor(line),blue[0])
        
    for j in range(len(red)):
        if sign_red != getSide(getCor(line),red[j]):
            return 'no'

    for j in range(len(blue)):

        if sign_blue != getSide(getCor(line),blue[j]):
            return 'no'
    return 'Yes'


Red= [(1,1),(2,1),(4,2),(2,4), (-1,4)]   
Blue= [(-2,-1),(-1,-2),(-3,-2),(-3,-1),(1,-3)]
Lines=["1x+1y+0","1x-1y+0","1x+0y-3","0x+1y-0.5"]

for i in Lines:
    ans = getAns(Red, Blue, i)
    print(ans)

output:

Yes
no
no
Yes

,

import math
# write your python code here
# you can take the above example as sample input for your program to test
# it should work for any general input try not to hard code for only given input strings


# you can free to change all these codes/structure
def i_am_the_one(red,blue,line):
    # your code
    for i in red:
        eq=line.replace('x','*'+str(i[0]))
        eq=eq.replace('y','*'+str(i[1]))
        answer=eval(eq)
        if answer>0:
            pass
        else:
            return "NO"
        
    # Code for Blue
    for j in blue:
        eq1=line.replace('x','*'+str(j[0]))
        eq1=eq1.replace('y','*'+str(j[1]))
        answer1=eval(eq1)
        if answer1<0:
            pass
        else:
            return "NO"
    return "Yes"

Red= [(1,1),(2,1),(4,2),(2,4), (-1,4)]
Blue= [(-2,-1),(-1,-2),(-3,-2),(-3,-1),(1,-3)]
Lines=["1x+1y+0","1x-1y+0","1x+0y-3","0x+1y-0.5"]

for i in Lines:
    yes_or_no = i_am_the_one(Red, Blue, i)
    print(yes_or_no)

]