Our solver for Google Hash Code qualifier 2022 - 67th place

solver.py

import json
import random

# Takes a dataset variable and returns a solution variable
def solve(dataset):
    for contributor in dataset['contributors'].values():
        contributor['availableAt'] = 0

        # Since we levelup only in skillsByName, avoid discrepancies
        del contributor['skills']

    totalScore = 0
    lastDay = max(proj['bestBefore'] + proj['score'] for proj in dataset['projects'].values())
    
    solution = {'projects': []}
    selectedProjectNames = set()
    currentTime = 0
    while True:
        projectScores = []
        projectOrder = []
        for project in dataset['projects'].values():
            if project['name'] in selectedProjectNames:
                continue # don't select a project twice

            penalty = max(0, currentTime + project['days'] - project['bestBefore'])
            manpower = project['days'] * len(project['roles'])
            score = max(0, project['score'] - penalty) / manpower
            projectOrder.append((score, project['name']))

        projectOrder.sort(reverse=True)
        for _, projectName in projectOrder:
            project = dataset['projects'][projectName]
            if project['name'] in selectedProjectNames:
                continue # don't select a project twice
            
            penalty = max(0, currentTime + project['days'] - project['bestBefore'])
            manpower = project['days'] * len(project['roles'])
            score = max(0, project['score'] - penalty) / manpower
            realScore = max(0, project['score'] - penalty)
            
            selectedPpl = []
            selectedContribs = set()
            rolesCanBeMentored = set()
            for roleDict in project['roles']:
                roleName = roleDict['name']
                roleLevel = roleDict['levelRequired']
                contribselect = []
                ordr = list(dataset['contributors'].values())
                random.shuffle(ordr)
                for contributor in ordr:
                    # TODO : include mentorship
                    # TODO : shuffle iter order
                    
                    if (contributor['availableAt'] <= currentTime and
                        contributor['name'] not in selectedContribs):
                        if (any(dataset['contributors'][nnn]['skillsByName'].get(roleName, 0) >= roleLevel for nnn in selectedPpl) 
                            and contributor['skillsByName'].get(roleName, 0) == roleLevel - 1):
                            contribselect.append((1000, contributor['name']))
                            break
                        elif contributor['skillsByName'].get(roleName, 0) == roleLevel:
                            contribselect.append((500, contributor['name']))
                        elif contributor['skillsByName'].get(roleName, 0) > roleLevel:
                            contribselect.append((-sum(contributor['skillsByName'].values()), contributor['name']))
                        
                if len(contribselect) == 0:
                    # Did not find a suitable contributor at this date
                    score = -1
                    break
                else:
                    bestContribScore, bestContribName = max(contribselect)
                    selectedPpl.append(bestContribName)
                    selectedContribs.add(bestContribName)
                    
                    for role in project['roles']:
                        roleName = role['name']
                        roleLevel = role['levelRequired']
                        if dataset['contributors'][bestContribName]['skillsByName'].get(roleName,0) >= roleLevel:
                            rolesCanBeMentored.add(roleName)
                    
            projectScores.append((score, realScore, project['name'], selectedPpl))
            if score > 0:
                # Found a valid score
                # Since we're checking by decreasing expected score, we can break now
                break 

        bestScore, bestRealScore, bestProjectName, bestAlloc = max(projectScores)
        
        print(f'Best project score: {bestScore:.2f} / {bestRealScore}. Total {totalScore}')
        if bestScore > 0:
            totalScore += bestRealScore
            print(f"{len(dataset['projects']) - len(selectedProjectNames)} projects remaining.")
            bestProject = dataset['projects'][bestProjectName]
            for name, role in zip(bestAlloc, bestProject['roles'], strict=True):
                contributor = dataset['contributors'][name]
                contributor['availableAt'] = currentTime + bestProject['days']
                
                # Level up
                contributorSkill = contributor['skillsByName'].get(role['name'], 0)
                if contributorSkill <= role['levelRequired']:
                    assert contributorSkill >= role['levelRequired'] - 1
                    contributor['skillsByName'][role['name']] = contributorSkill + 1
                
            projectSol = {
                'name': bestProjectName,
                'roles': bestAlloc,
                'startTime': currentTime
            }
            solution['projects'].append(projectSol)
            selectedProjectNames.add(bestProjectName)
            
        if bestScore <= 0: # TODO: <= 0 for datasets other than E
            # Step forward in time
            
            earliestStep = 99**99
            for contributor in dataset['contributors'].values():
                if contributor['availableAt'] > currentTime:
                    earliestStep = min(earliestStep, contributor['availableAt'])
            currentTime = earliestStep
            print(f'Advancing time to {currentTime}/{lastDay}')
            if currentTime >= lastDay:
                break
        """
        if random.random() < 0.05:
            print('Saving')
            # 5% chance to save progress
            with open(f'debug/save_{lastDay}.json', 'w') as fo:
                json.dump(solution, fo)
        """

    print(totalScore)
    return solution


if __name__ == '__main__':
    test_dataset = {'contributors': {'Anna': {'name': 'Anna', 'skills': [{'name': 'C++', 'level': 2}], 'skillsByName': {'C++': 2}}, 'Bob': {'name': 'Bob', 'skills': [{'name': 'HTML', 'level': 5}, {'name': 'CSS', 'level': 5}], 'skillsByName': {'HTML': 5, 'CSS': 5}}, 'Maria': {'name': 'Maria', 'skills': [{'name': 'Python', 'level': 3}], 'skillsByName': {'Python': 3}}}, 'projects': {'Logging': {'name': 'Logging', 'days': 5, 'score': 10, 'bestBefore': 5, 'roles': [{'name': 'C++', 'levelRequired': 3}], 'rolesByName': {'C++': 3}}, 'WebServer': {'name': 'WebServer', 'days': 7, 'score': 10, 'bestBefore': 7, 'roles': [{'name': 'HTML', 'levelRequired': 3}, {'name': 'C++', 'levelRequired': 2}], 'rolesByName': {'HTML': 3, 'C++': 2}}, 'WebChat': {'name': 'WebChat', 'days': 10, 'score': 20, 'bestBefore': 20, 'roles': [{'name': 'Python', 'levelRequired': 3}, {'name': 'HTML', 'levelRequired': 3}], 'rolesByName': {'Python': 3, 'HTML': 3}}}, 'projectsL': [{'name': 'Logging', 'days': 5, 'score': 10, 'bestBefore': 5, 'roles': [{'name': 'C++', 'levelRequired': 3}], 'rolesByName': {'C++': 3}}, {'name': 'WebServer', 'days': 7, 'score': 10, 'bestBefore': 7, 'roles': [{'name': 'HTML', 'levelRequired': 3}, {'name': 'C++', 'levelRequired': 2}], 'rolesByName': {'HTML': 3, 'C++': 2}}, {'name': 'WebChat', 'days': 10, 'score': 20, 'bestBefore': 20, 'roles': [{'name': 'Python', 'levelRequired': 3}, {'name': 'HTML', 'levelRequired': 3}], 'rolesByName': {'Python': 3, 'HTML': 3}}], 'contributorsL': [{'name': 'Anna', 'skills': [{'name': 'C++', 'level': 2}], 'skillsByName': {'C++': 2}}, {'name': 'Bob', 'skills': [{'name': 'HTML', 'level': 5}, {'name': 'CSS', 'level': 5}], 'skillsByName': {'HTML': 5, 'CSS': 5}}, {'name': 'Maria', 'skills': [{'name': 'Python', 'level': 3}], 'skillsByName': {'Python': 3}}]}
    print(solve(test_dataset))