Pairwise adding tuples in a list

Question

I have two list of tuples:

 [[1,8],[2,7],[3,14]]
 [[1,5],[2,10],[3,14]]

and a desired sum 20. I need to find two tuples from two list whose second element either add it to the sum i.e 20 or the next lowest sum. In this case if we consider [3,14] and [1,5] the sum is 14+5=19 hence the output should be [3,1]

[1,3000],[2,5000],[3,7000],[4,10000]
[1,2000],[2,3000],[3,4000],[4,5000]]

the sum is 10000. Here we have [2,5000], [4,5000] and [3,7000], [2,3000] so the output should be [2,4] and [3,2]

[[1,2000],[2,4000],[3,6000]]
[[1,2000]]

the sum is 7000. Here since I don't have a combination that sum up to 7000 I consider all the possible combinations 4000(2000+2000), 6000(4000+2000) and 8000(6000+2000) and consider the next lowest number from the desired sum which is 600. For 6000 my output should be [2,4000] and [1,2000] which is [2,1].

import itertools

def optimalUtilization(maximumOperatingTravelDistance,
                       forwardShippingRouteList, returnShippingRouteList):

    result=[]
    t1=[]
    t2=[]
    for miles in forwardShippingRouteList:
        t1.append(miles[1])


    for miles in returnShippingRouteList:
        t2.append(miles[1])

    result.append(t1)
    result.append(t2)
    total_sum=set()


    for element in list(itertools.product(*result)):
        if sum(element)<=maximumOperatingTravelDistance:
            total_sum.add(sum(element))




    total_sum=sorted(total_sum,reverse=True)
    return optimalUtilizationhelper(total_sum[0],
                       forwardShippingRouteList, returnShippingRouteList)


def optimalUtilizationhelper(maximumOperatingTravelDistance,
                       forwardShippingRouteList, returnShippingRouteList):

    dist_dict={}
    for carid,miles in forwardShippingRouteList:
        dist_dict.update({miles:carid})

    result=[]


    for carid,miles in returnShippingRouteList:
        if (maximumOperatingTravelDistance-miles) in dist_dict:
            result.append(list((dist_dict[maximumOperatingTravelDistance-miles],carid)))


    return result

I get the desired result here but the complexity here is \$O(n^2 \log n)\$. What is a better way to do this?

Answer 1

Review

1. No need for all these intermediate temp variables

   You loop over a and b to append to the result which is unnecessary.

   Only afterwards you create the products but this can be done before.

2. The sort is not needed if you keep a running minimum

3. Use a if __name__ == '__main__'

4. Consider adding Docstring and Testcases, (or both in the form of doctests) to make the solution more understandable/testable

5. Read PEP8 the python style guide

   • Functions and variables should be snake_case for instance

Revised Code

def optimal_shipping(a, b, target):
    """
    Finds the optimal shipping by compairing pairwise lists to the target sum

    >>> optimal_shipping([[1,2000],[2,4000],[3,6000]], [[1,2000]], 6000)
    [[2, 1]]
    >>> optimal_shipping([[1,8],[2,7],[3,14]], [[1,5],[2,10],[3,14]], 20)
    [[2, 3]]
    >>> optimal_shipping([[1,3000],[2,5000],[3,7000],[4,10000]], [[1,2000],[2,3000],[3,4000],[4,5000]], 10000)
    [[2, 4], [3, 2]]
    """
    best = 0
    for i, x in a:
        for j, y in b:
            if abs(x + y - target) < abs(target - best):
                best = x + y
                res = [[i, j]]
            elif x + y == best:
                res += [[i, j]]
    return res

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Note If those lists prices are in ascending order, maybe something with a bisect search could work.

Answer 2

Performance: here is a O(n log n) solution, where we sort both lists by the second element and then try to sum maximumOperatingTravelDistance, decreasing sum if we went over it and increasing if not. When the sum is better than what we had, we reset the results. When it is the same as the best we had, we add that to results.

    def optimalUtilization(maximumOperatingTravelDistance, forwardShippingRouteList, returnShippingRouteList):
        forwardShippingRouteList = sorted(forwardShippingRouteList, key = lambda x: x[1])
        returnShippingRouteList = sorted(returnShippingRouteList, key = lambda x: x[1], reverse = True)

        idxf = 0
        idxr = 0
        best = 0
        result = []

        while (idxf  < len(forwardShippingRouteList) and idxr < len(returnShippingRouteList)):
            elSum = forwardShippingRouteList[idxf][1] + returnShippingRouteList[idxr][1]
            if elSum > maximumOperatingTravelDistance:
                idxr += 1
            else:
                if elSum > best:
                    best = elSum
                    result = []
                if elSum == best:
                    result.append([forwardShippingRouteList[idxf][0], returnShippingRouteList[idxr][0]])
                idxf += 1
        return result                   



    print(optimalUtilization(20,  [[1,8],[2,7],[3,14]],  [[1,5],[2,10],[3,14]]))
    print(optimalUtilization(10000, [[1,3000],[2,5000],[3,7000],[4,10000]], [[1,2000],[2,3000],[3,4000],[4,5000]]))
    print(optimalUtilization(7000, [[1,2000],[2,4000],[3,6000]], [[1,2000]]))

Note: This assumes that in each list, there is no repeated second element. Some modifications will be needed if you need to contemplate such cases, as my current code could use the same tuple twice in the result if there are repeated.