unmatched_trades.py

"""
A trade is defined as a string containing the 4 properties given below separated by commas:
- Symbol (4 alphabetical characters, left-padded by spaces)
- Side (either "B" or "S" for buy or sell)
- Quantity (4 digits, left-padded by zeros)
- ID (6 alphanumeric characters)
e.g. "AAPL,B,0100,ABC123" represents a trade of a buy of 100 shares of AAPL with ID "ABC123"
Given two lists of trades - called "house" and "street" trades, write code to create groups 
of matches between trades and return a list of unmatched house and street trades sorted 
alphabetically. Without any matching, the output list would contain all elements of both house
and street trades. There are many ways to match trades, the first and most important way is an
exact match:
    An exact match is a pair of trades containing exactly one house trade and exactly one street
    trade with identical symbol, side, quantity, and ID
    NOTE: Trades are distinct but not unique
Example:
INPUT:
house_trades: ["AAPL,B,0100,ABC123", "AAPL,B,0100,ABC123", "GOOG,S,0050,CDC333"]
street_trades:["FB,B,0100,GBGGGG", "AAPL,B,0100,ABC123"]
OUTPUT:
["FB,B,0100,GBGGGG","AAPL,B,0100,ABC123","GOOG,S,0050,CDC333"]
Because the first (or second) house trade and second street trade form an exact match, leaving 
behind three unmatched trades.
"""

from collections import Counter, defaultdict
def get_unmatched(house_trades, street_trades):
    house = Counter(house_trades)
    unmatched_house = []
    unmatched_street = []
    for st in street_trades:
        house[st] -= 1
    for trade in house:
        # == 0 means everything matched
        unmatched = [trade]*abs(house[trade])
        if house[trade] > 0: #unmatched house
            unmatched_house.extend(unmatched)
        elif house[trade] < 0: #unmatched street
            unmatched_street.extend(unmatched)
    house = defaultdict(lambda: defaultdict(int))
    street = defaultdict(lambda: defaultdict(int))
    for ht in unmatched_house:
        sym, side, qty, tid = ht
        house[sym,side,qty][tid] += 1
    for st in unmatched_street:
        sym, side, qty, tid = st
        street[sym,side,qty][tid] += 1
    for attr in house:
        for tid in house[attr]:
            count = min(house[attr][tid], street[attr][tid])
            house[attr][tid] -= count
            street[attr][tid] -= count
    unmatched_house = []
    unmatched_street = []
    for attr in house:
        for tid in house[attr]:
            if house[attr][tid]:
                trade = '{},{}'.format(''.join(attr),tid)
                unmatched_house.extend([trade]*house[attr][tid])
    for attr in street:
        for tid in street[attr]:
            if street[attr][tid]:
                trade = '{},{}'.format(''.join(attr),tid)
                unmatched_house.extend([trade]*street[attr][tid])
    BUY, SELL = 'buy', 'sell'
    house = defaultdict(lambda: defaultdict({BUY: defaultdict(int),SELL: defaultdict(int)}))
    street = defaultdict(lambda: defaultdict({BUY: defaultdict(int),SELL: defaultdict(int)}))
    for ht in unmatched_house:
        sym, side, qty, tid = ht
        house[sym,qty][side][tid] += 1
    for st in unmatched_street:
        sym, side, qty, tid = st
        street[sym,qty][side][tid] += 1
    for offset in unmatched_house:
        for tid in unmatched_house[offset][BUY]:
            count = min(unmatched_house[offset][BUY][tid], unmatched_house[offset][SELL][tid])
            unmatched_house[offset][BUY][tid] -= count
            unmatched_house[offset][SELL][tid] -= count
    for offset in unmatched_street:
        for tid in unmatched_street[offset][BUY]:
            count = min(unmatched_street[offset][BUY][tid], unmatched_street[offset][SELL][tid])
            unmatched_street[offset][BUY][tid] -= count
            unmatched_street[offset][SELL][tid] -= count
    unmatched_house = []
    unmatched_street = []
    for offset in unmatched_house:
        for side in unmatched_house[offset]:
            for tid in unmatched_house[offset][side]:
                if unmatched_house[offset][side][tid]:
                    sym, qty = offset
                    trade = '{},{},{},{}'.format(sym,side,qty,tid)
                    unmatched_house.extend([trade]*unmatched_house[offset][side][tid])
    for offset in unmatched_street:
        for side in unmatched_street[offset]:
            for tid in unmatched_street[offset][side]:
                if unmatched_street[offset][side][tid]:
                    sym, qty = offset
                    trade = '{},{},{},{}'.format(sym,side,qty,tid)
                    unmatched_street.extend([trade]*unmatched_street[offset][side][tid])
    return unmatched_house+unmatched_street