Three arrays algorithm bug-CodePudding

Given three sorted (non-empty) arrays A, B, and C. It is necessary to find a triplet of numbers A[i], B[j], C[k] for which the expression (max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) would be the minimum of all possible triples. If there are several triplets with the same value, print the one closest to the beginning of the arrays (priority A, B, C).

I'm trying to implement this algorithm problem, but I'm getting runtime error at the second testcase.

A = []
x = int(input())
for i in range(0, x):
    ele = int(input())
    A.append(ele)

fnum = A[0]

B = []
y = int(input())
for i in range(0, y):
    ele2 = int(input())
    B.append(ele2)

C = []
z = int(input())
for i in range(0, z):
    ele3 = int(input())
    C.append(ele3)


def solve(A, B, C):
    i = len(A) - 1
    j = len(B) - 1
    k = len(C) - 1

    min_diff = abs(max(A[i], B[j], C[k]) -
                   min(A[i], B[j], C[k]))

    while i != -1 and j != -1 and k != -1:
        current_diff = abs(max(A[i], B[j],
                               C[k]) - min(A[i], B[j], C[k]))

        if current_diff < min_diff:
            min_diff = current_diff

        max_term = max(A[i], B[j], C[k])

        if A[i] == max_term:
            i -= 1
        elif B[j] == max_term:
            j -= 1
        else:
            k -= 1
    return min_diff


print("Numbers =", fnum, ele2, ele3)
print("Result =", solve(A, B, C))

CodePudding user response：

You could use the product function (from itertools) to "brute force" the combination analysis picking the triplet that has the lowest difference between max and min:

from itertools import product
def maxmin(A,B,C):
    return min((max(p)-min(p),p) for p in product(A,B,C))

output:

A = [10, 11, 12, 13, 14]
B = [1, 2, 3, 4, 5]
C = [8]

print(*maxmin(A,B,C))
    
5 (10, 5, 8)

The equivalent logic, without using libraries, would require 3 nested loops:

def maxmin(A,B,C):
    n, abc = None, None
    for a in A:
        for b in B:
            for c in C:
                d = max(a,b,c)-min(a,b,c)
                if not abc or d<n:
                    n, abc = d, (a,b,c)
    return n, abc

although you could place that in a comprehension:

def maxmin(A,B,C):
    return min(((max(a,b,c)-min(a,b,c),(a,b,c)) 
                 for a in A for b in B for c in C))

maxmin(A,B,C)
5 (10, 5, 8)

CodePudding user response：

The input lists are sorted and you could solve in linear time by iterating over them and advancing the index on the list with the minimum element (with the goal of increasing its value), until you don't reach the end on one of the input lists.

Example:

def min_diff(l1, l2, l3):

    best_min = float("inf")
    best_tuple = None

    i = j = k = 0
    while i < len(l1) and j < len(l2) and k < len(l3):
        curr_sol = l1[i], l2[j], l3[k]
        curr_diff = max(curr_sol) - min(curr_sol)
        
        curr_min = min(curr_sol)
        if l1[i] == curr_min:
            i  = 1
        elif l2[j] == curr_min:
            j  = 1
        else:
            k  = 1

        if curr_diff < best_min:
            best_min = curr_diff
            best_tuple = curr_sol

    return best_tuple, best_min


>>> print(min_diff([10, 11, 12, 13, 14], [1, 2, 3, 4, 5], [8]))
((10, 5, 8), 5)

For 3 lists of 10k elements each the time take would be milliseconds vs several minutes of a bruteforce approach.