match.py

def findBreakEvenIndex(buyers, sellers):
    breakEvenIndex = 0
    for i in range(max(len(buyers), len(sellers))):
        breakEvenIndex = i
        if buyers[i] < sellers[i]:
            break
    return breakEvenIndex


def orderMarket(buyers, sellers):
    buyers = buyers[:]
    sellers = sellers[:]
    buyers.sort(reverse=True)
    sellers.sort()
    return buyers, sellers


def match(buyers, sellers):
    (orderedBuyers, orderedSellers) = orderMarket(buyers, sellers)
    breakEvenIndex = findBreakEvenIndex(orderedBuyers, orderedSellers)
    price = (orderedBuyers[breakEvenIndex] + orderedSellers[breakEvenIndex]) / 2.0
    ordersMade = []
    for i in range(breakEvenIndex+1):
        # Pop the first item from both the buyers and the sellers.
        order = (buyers.pop(0), sellers.pop(0))
        ordersMade.append(order)
    return ordersMade, price


buyers = [23, 7, 6, 4, 3, 3, 3, 2, 1]
sellers = [3, 5, 7]


match(buyers, sellers)

# >>> buyers = [23, 7, 6, 4, 3, 3, 3, 2, 1]
# >>> sellers = [3, 5, 7]
# >>>
# >>>
# >>> match(buyers, sellers)
# ([(23, 3), (7, 5), (6, 7)], 6.5)
# >>>