catsvsdogs.py

import operator

class Cell(object):

    def __init__(self, name, child, primary, secondary):
        self.name = name
        self.primary = primary
        self.secondary = secondary
        self.children = []
        self.children.append(child)

    def add_child(self, req):
        self.children.append(req)

    def size(self):
        return len(self.children)

    def delete_from_votes(self, primary_tracker, secondary_tracker):
        # if we can still make some sort of pair
        # we remove ourselves form the opposite list
        if self.size():
            if self.name in self.secondary:
                self.secondary.pop(self.name)

        #if you are child of any other element you need to be removed
        clean_up_primary = []
        for k in self.primary:
            item = self.primary[k]
            while self.name in item.children:
                item.children.remove(self.name)
            if not item.children:
                clean_up_primary.append(k)

        clean_up_secondary = []
        for k in self.secondary:
            item = self.secondary[k]
            while self.name in item.children:
                item.children.remove(self.name)
            if not item.children:
                clean_up_secondary.append(k)

        #For the primary cells remove the ones that need to be cleaned up
        for vote in clean_up_primary:
            self.primary.pop(vote)

        #For the secondary cells remove the one that needs to be cleaned up
        #additionally, since this cell has no more children it means that all
        #its higher priority children have had their places (kept/remove) set
        #this means we must add this vote to list that keeps track of items
        #choses from the secondary column if it no longer exists in primary column
        #orhas already been chosen for the primary category
        for cell in clean_up_secondary:
            self.secondary.pop(cell)
            if not cell in primary_tracker and not cell in self.primary:
                secondary_tracker.append(cell)

        #Finally remove yourself from this list
        self.primary.pop(self.name)
        return True if self.size() else False

    def __str__(self):
        return str(self.children)

    def __repr__(self):
        return self.__str__()

def happy_voters(votes, debug=True):

    votes_to_keep = {}
    votes_to_remove = {}
    num_happy = 0

    for keep, remove in votes:
        if not keep in votes_to_keep:
            votes_to_keep[keep] = Cell(keep, remove, votes_to_keep, votes_to_remove)
        else:
            votes_to_keep[keep].add_child(remove)
        if not remove in votes_to_remove:
            votes_to_remove[remove] = Cell(remove, keep, votes_to_remove, votes_to_keep)
        else:
            votes_to_remove[remove].add_child(keep)

    #Use these lists to keep track of what is unambiguously kept
    #and those which are unabiguously removed
    kept = []
    removed = []

    while len(votes_to_keep) > 0 and len(votes_to_remove) > 0:
        #Sort by length of children
        #this is essential a greedy-ish algorithm
        most_liked = sorted(votes_to_keep.iteritems(), key=operator.itemgetter(1),
            cmp=lambda x,y: cmp(x.size(), y.size()), reverse=True)[0][0]
        most_hated = sorted(votes_to_remove.iteritems(), key=operator.itemgetter(1),
            cmp=lambda x,y: cmp(x.size(), y.size()), reverse=True)[0][0]
        if debug: print 'kept: ', kept
        if debug: print 'removed: ', removed

        #if we can satisfy more voters by keeping, then we keep the most liked
        #otherwise we remove the most hated
        if votes_to_keep[most_liked].size() >= votes_to_remove[most_hated].size():
            if votes_to_keep[most_liked].delete_from_votes(kept, removed):
                if debug: print 'added to kept: ', most_liked
                kept.append(most_liked)
        else:
            if votes_to_remove[most_hated].delete_from_votes(removed, kept):
                if debug: print 'added to remove: ', most_hated
                removed.append(most_hated)
    if debug: print 'final kept: ', kept
    if debug: print 'final removed: ', removed
    for keep, remove in votes:
        if keep not in removed and remove not in kept:
            if debug: print 'happy: ', (keep, remove)
            num_happy += 1
        else:
            if debug: print 'unhappy: ', (keep, remove)
    return num_happy

if __name__ == '__main__':
    num_tests = int(raw_input())
    results = []
    debug = True
    for i in range(num_tests):
        votes = []
        num_cats, num_dogs, num_votes = raw_input().strip().split(' ')
        for j in range(int(num_votes)):
            votes.append(tuple(raw_input().strip().split(' ')))
        if debug: print "*******NEW*********"
        results.append(happy_voters(votes, debug))
    for result in results:
        print result