application_vnd.jupyter.stderr_output_2.png text_plain_output_1.png
import numpy as np

import pandas as pd

INPUT_PATH = '../input/'
childPref = pd.read_csv(INPUT_PATH + 'child_wishlist.csv', header=None).as_matrix()[:, 1:]
santaPref = pd.read_csv(INPUT_PATH + 'gift_goodkids.csv', header=None).as_matrix()[:, 1:]

numChildren = childPref.shape[0]
numGifts = santaPref.shape[0]
numGiftsPerChild = numChildren / numGifts
numTwins = 4000

childPreferenceMatrix = -1 * np.ones((numChildren, numGifts), np.float32)
for childID in range(numChildren):
    for giftOrder, giftID in enumerate(childPref[childID, :]):
        childPreferenceMatrix[childID, giftID] = 2 * (10 - giftOrder)
santaPreferenceMatrix = -1 * np.ones((numChildren, numGifts), np.float32)
for giftID in range(numGifts):
    for childOrder, childID in enumerate(santaPref[giftID, :]):
        santaPreferenceMatrix[childID, giftID] = 2 * (1000 - childOrder)
child_vs_gift_matrix = childPreferenceMatrix / (20.0 * numChildren)
child_vs_gift_matrix += santaPreferenceMatrix / (2000000.0 * numGifts)
child_vs_gift_matrix = child_vs_gift_matrix.astype(np.float32)
del childPreferenceMatrix
del santaPreferenceMatrix

def calculateTotalHapiness(pred):
    totalHapiness = 0
    for i in range(0, numTwins, 2):
        child_id = i
        gift_id = pred[i]
        totalHapiness += child_vs_gift_matrix[child_id, gift_id]
    for i in range(numTwins, numChildren):
        child_id = i
        gift_id = pred[i]
        totalHapiness += child_vs_gift_matrix[child_id, gift_id]
    return totalHapiness
def AssignGifts_GreedyChildren_Adaptive(child_vs_gift_selection_matrix=child_vs_gift_matrix, numPasses=15):
    child_vs_gift_selection_matrix = child_vs_gift_selection_matrix.copy()
    giftAssignment = -np.ones(numChildren, dtype=np.int32)
    giftCount = np.zeros(numGifts, dtype=np.int32)
    startTime = time.time()
    sortedTwins = 2 * child_vs_gift_selection_matrix[0:numTwins:2].max(axis=1).argsort()
    for childInd in sortedTwins:
        selectedGift = child_vs_gift_selection_matrix[childInd, :].argmax()
        if giftCount[selectedGift] < numGiftsPerChild and giftAssignment[childInd] == -1:
            giftAssignment[childInd] = selectedGift
            giftAssignment[childInd + 1] = selectedGift
            giftCount[selectedGift] += 2
    childrenPerPass = int(1 + (numChildren - numTwins) / (numPasses + 1.0))
    for k in range(numPasses + 1):
        maxValuePerChild = child_vs_gift_selection_matrix.max(axis=1)
        sortedChildren = (numTwins + maxValuePerChild[numTwins:].argsort())[::-1]
        thresholdChildInd = min(numChildren - numTwins - 1, int(numTwins + (k + 1) * childrenPerPass))
        assignmentThreshold = maxValuePerChild[thresholdChildInd]
        numAssignedSoFar = (giftAssignment > -1).sum()
        if numAssignedSoFar > 0.99 * numChildren or k >= numPasses:
            assignmentThreshold = child_vs_gift_selection_matrix.min() - 1.0
            thresholdChildInd = len(sortedChildren)
        if numAssignedSoFar >= numChildren:
            break
        for childInd in sortedChildren[:thresholdChildInd]:
            if giftAssignment[childInd] == -1 and child_vs_gift_selection_matrix[childInd, :].max() >= assignmentThreshold:
                selectedGift = child_vs_gift_selection_matrix[childInd, :].argmax()
                giftAssignment[childInd] = selectedGift
                giftCount[selectedGift] += 1
                if giftCount[selectedGift] >= numGiftsPerChild:
                    child_vs_gift_selection_matrix[:, selectedGift] = -1.0
    assignmentScore = calculateTotalHapiness(giftAssignment)
    return (giftAssignment, assignmentScore)

print('normalizing rows and columns of the value matrix')
startingMatrix = child_vs_gift_matrix.copy()
startingMatrix -= startingMatrix.min()
startingMatrix /= startingMatrix.max()
print('heuristic #1: boost unpopular gifts before greedy assignment')
giftVariability = startingMatrix.std(axis=0)
for giftInd, giftVar in enumerate(giftVariability):
    startingMatrix[:, giftInd] /= giftVar
print('heuristic #2: penalize good kids before greedy assignment')
childFavorability = startingMatrix.mean(axis=1)
for childInd, childFavor in enumerate(childFavorability):
    startingMatrix[childInd, :] /= childFavor
print('assign gifts to children in a child centered greedy fashion')
pred, score = AssignGifts_GreedyChildren_Adaptive(startingMatrix, numPasses=16)
print('predicted score = %.8f' % score)