Merge two sorted linear graphs

Question

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]]=> one point: 1, at x coordinate, 0 at y coordinate
B:[(0, 0]]=> one point: 0, at x coordinate, 0 at y coordinate
=> 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)]=> one line at (3,3), (5,5)
B:[(4, 4), (5, 5), (10, 8)]=> 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 => (0, 0)
when x = 2 at B line, y=2, at A line y = 0 => (0, 0)
when x = 4 at B line, y=3, at A line y = (5-3 / 5-3 * 4) => (4, 7)
when x = 5 at B line, y=3, at A line y = 5 => (5, 8)
when x = 6 at B line, y= (2 - 3)/(10-5) * 6, at A line y = 3 => (6, 0)
when x = 7 at B line, y= (2 - 3)/(10-5) * 7, at A line y = 5 => (7, 1.5)
when x = 10 at B line, y=3, at A line y = (5-3 / 5-3 * 4) => (4, 7)
=> [(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 < len(A) and j < len(B):
 if A[i][0] < B[0][0]:
 x, y = A[i]
 i += 1
 elif B[j][0] < A[0][0]:
 x, y = B[j]
 j += 1
 elif A[i][0] < 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] > 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

• Benjamin Kuykendall: Hello @Alee. I do not understand the intended functionality from your brief description or example. Could you edit the question to include more detail?

Answer 1

1. Use yield instead of building a list. There is no need for an explicit list.
2. At start of method or input with [] for cleaner None checks.
3. Move interpolation into a function. This avoid repeated code.
4. 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 < len(A) and j < 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.

• A.Lee: nice code. totally agree yield make the code more clean and any better way for not doing the math calculation you can think of?