Merge two sorted linear graphs I have code for a function to calculator the addition of two sorted List. Each element of List is tuple type (xi, yi) that represents graph individual (x,y) points at coordinate system.


  two input List is sorted by x value and length of A, B list may be different
  [(Ax0, Ay0),..., (Axi, Ayi), (Axi+1, Ayi+1),, ...(Axn, Ayn)][(Bx0, By0),..., (Bxi, Byi), (Bxi+1, Byi+1),, ...(Bxk, Byk)]


example 1:
A:[(1, 1]]=&gt; one point: 1, at x coordinate, 0 at y coordinate
B:[(0, 0]]=&gt; one point: 0, at x coordinate, 0 at y coordinate
=&gt; graph_addition(A, B) == [(0,0), (1,1)] 
a line with two point (0,0) and (1,1)

example 2:
A:[(3, 3), (5,5)]=&gt; one line at (3,3), (5,5)
B:[(4, 4), (5, 5), (10, 8)]=&gt; 2 segment line: 
ex: graph_addition(A, B) = [(3, 3), (4, 8.0), (5, 10)] 
3 segment line with 3 point [(3, 3), (4, 8.0), (5, 10), (10, 8)]
For A when x at 4, y should be 4 based on slope calculation

example 3:
A:[(3,3), (5,5), (6,3), (7,5)]
B:[(0,0), (2,2), (4,3), (5,3), (10,2)]
explanation
when x = 0 at B line, y=0, at A line y = 0 =&gt; (0, 0)
when x = 2 at B line, y=2, at A line y = 0 =&gt; (0, 0)
when x = 4 at B line, y=3, at A line y = (5-3 / 5-3 * 4) =&gt; (4, 7)
when x = 5 at B line, y=3, at A line y = 5 =&gt; (5, 8)
when x = 6 at B line, y= (2 - 3)/(10-5) * 6, at A line y = 3 =&gt; (6, 0)
when x = 7 at B line, y= (2 - 3)/(10-5) * 7, at A line y = 5 =&gt; (7, 1.5)
when x = 10 at B line, y=3, at A line y = (5-3 / 5-3 * 4) =&gt; (4, 7)
=&gt; [(0, 0), (2, 2), (3, 5.5), (4, 7.0), (5, 8), (6, 5.8), (7, 7.6), (10, 2)]


Is there a better way for me to not using bruteforce way to calculate x, y values?

def graph_addition(A, B):
     if not A or not B: return A or B
     res = []
     i = j = 0
     while i &lt; len(A) and j &lt; len(B):
         if A[i][0] &lt; B[0][0]:
             x, y = A[i]
             i += 1
         elif B[j][0] &lt; A[0][0]:
             x, y = B[j]
             j += 1
         elif A[i][0] &lt; B[j][0]:
             x = A[i][0]
             y = (B[j][1] - B[j - 1][1]) / (B[j][0] - B[j - 1][0]) * (x - B[j - 1][0]) + B[j - 1][1] + A[i][1]
             i += 1
         elif A[i][0] &gt; B[j][0]:
             x = B[j][0]
             y = (A[i][1] - A[i - 1][1]) / (A[i][0] - A[i - 1][0]) * (x - A[i - 1][0]) + A[i - 1][1] + B[j][1]
             j += 1
         else:
             x = A[i][0]
             y = A[i][1] + B[j][1]
             i += 1
             j += 1
         res.append((x, y))
     if A[i:]: res += A[i:]
     if B[j:]: res += B[j:]
     return res
Use yield instead of building a list. There is no need for an explicit list.
At start of method or input with [] for cleaner None checks.
Move interpolation into a function. This avoid repeated code.
Move all the casework into the interpolation function.


def graph_value(L, i, x):
    if x == L[i][0]: return L[i][1]
    if i == 0: return 0
    m = (L[i][1] - L[i - 1][1]) / (L[i][0] - L[i - 1][0])
    return m * (x - L[i - 1][0]) + L[i - 1][1]

def graph_addition(A, B):
    A = A or []
    B = B or []
    i = j = 0
    while i &lt; len(A) and j &lt; len(B):
        x = min(A[i][0], B[j][0])
        y = graph_value(A, i, x) + graph_value(B, j, x)
        i += (x == A[i][0])
        j += (x == B[j][0])
        yield (x,y)
    yield from A[i:]
    yield from B[j:]


Exercise to the reader: write a version that takes in two arbitrary iterables and performs the same functionality.