import math, random
n_people = 6
edges = []
for i in range(n_people): edges.extend((i,j) for j in range(n_people) if j != i)
# Ugly hack: enforce conjectured shape of solution
# (to not do this, remove next 3 non-comment lines and see
# single change below; note also that this needs changing if n_people
# changes)
edges0 = [(1,0), None, (2,1), (1,2), (0,1), (2,0), (0,2), (3,0), (0,3), (4,0), (0,4), (5,0), (0,5)] # adjust if n_people changes
edges1 = [e for e in edges if e not in edges0]
edges = edges0[:1] + edges1 + edges0[2:]
n_edges = len(edges)
def score(edges):
    money = n_people*[1]
    for (i,j) in edges:
        money[i] += money[j]
    #return sum(money) # use this to optimize total money (older problem)
    return money[0] # use this to optimize your own money (newer problem)
def mutate(edges):
    edges = edges[:]
    # The -11 version is for the "restricted" optimization
    #i,j = random.sample(range(n_edges),2)
    i,j = random.sample(range(1, n_edges-11),2)
    edges[i],edges[j] = edges[j],edges[i]
    return edges
curr = score(edges)
best = (curr, edges)
print(best)
temp = 8000
while True:
    candidate = mutate(edges)
    cscore = score(candidate)
    if cscore > curr or random.random() < math.exp((cscore-curr)/temp):
        edges = candidate
        curr = cscore
        if curr > best[0]:
            best = (curr, edges)
            print("new best", curr, edges)
    temp = 0.999993 * temp
    if temp < 1:
        print("resetting", curr, edges)
        temp = 8000