professor_rando_redux.py

from collections import defaultdict
from copy import deepcopy
from functools import partial


def pre_solve(key_funcs, N):
    kfl = len(key_funcs)
    players = [defaultdict(set) for _ in xrange(kfl)]
    rplayers = [{} for _ in xrange(kfl)]
    
    for i in xrange(1, N + 1):
        for j in xrange(i, N + 1):
            val = (i, j)
            for k, key_func in enumerate(key_funcs):
                players[k][key_func(*val)].add(val)
                rplayers[k][val] = key_func(*val)
    
    scores = [0 for _ in xrange(kfl)]
    
    for i in xrange(1, N + 1):
        for j in xrange(i, N + 1):
            val = (i, j)
            cplayers = deepcopy(players)
            while True:
                found = False
                need_neg = -kfl
                for k in xrange(kfl):
                    cp = cplayers[k]
                    rp = rplayers[k]
                    l = len(cp[rp[val]])
                    if l == 1:
                        scores[k] += 1 if i == j else 2
                        found = True
                        break
                    else:
                        to_remove = []
                        for key in cp.keys():
                            if len(cp[key]) == 1:
                                to_remove.append([el for el in cp[key]][0])
                        if to_remove == []:
                            need_neg += 1
                        for l in xrange(kfl):
                            for el in to_remove:
                                cplayers[l][rplayers[l][el]].remove(el)
                if found:
                    break
                elif need_neg == 0:
                    return None
    
    return scores

key_funcs = [
    lambda i, j: abs(i - j), # Daphne
    lambda i, j: max(i, j), # Max
    lambda i, j: min(i, j), # Mindy
    lambda i, j: i + j, # Sam
    lambda i, j: i * j # Tim
]
solve = partial(pre_solve, key_funcs)


N = 2
while solve(N) is not None:
    N *= 2

low, high = N/2, N

while (high - low) > 1:
    mid = (high + low) / 2
    if solve(mid) is not None:
        low = mid
    else:
        high = mid

print high