#!/usr/bin/python3

from generation import generate_uniform
from fairdiv import Instance, Allocation
import numpy as np


##############################################################################
# Quelques constantes (que vous pouvez modifier si vous voulez...)

NB_AGENTS = 4
NB_OBJECTS = 8

AGENT_NAMES = ["Tokio", "Rio", "Berlin", "Nairobi", "Stockholm",
               "Moscou", "Helsinki", "Lisbon"]

AGENTS = AGENT_NAMES[:NB_AGENTS]
OBJECTS = ["o{}".format(x+1) for x in range(8)]

MAX_WEIGHT = 20

##############################################################################

# Ici, on crée l'instance demandée

matrix = np.array(
    [[8, 4, 6, 7, 5, 2, 0, 1],
     [8, 2, 0, 3, 13, 4, 5, 6],
     [20, 7, 0, 6, 1, 5, 2, 9],
     [0, 9, 6, 1, 13, 4, 15, 2]]
)
instance = Instance(matrix, AGENTS, OBJECTS)

# Question : Affichez l'instance (utilisez la fonction print)
# BEGIN CORRECTION
print("-----------------------------------")
print(instance)
# END CORRECTION

# Ici, on crée une allocation vide
allocation = Allocation(instance)

# Question : Allouez les objets de la manière suivante :
# - Tokio reçoit {o1, o2}
# - Rio reçoit {o3, o4}
# - Berlin reçoit {o5, o6}
# - Nairobi reçoit {o7, o8}
# NB : pour allouer un objet, utilisez la fonction allocation.give(agent, objet)
# Par exemple : allocation.give("Tokio", "o1")

# BEGIN CORRECTION
print("-----------------------------------")
allocation.give("Tokio", "o1")
allocation.give("Tokio", "o2")
allocation.give("Rio", "o3")
allocation.give("Rio", "o4")
allocation.give("Berlin", "o5")
allocation.give("Berlin", "o6")
allocation.give("Nairobi", "o7")
allocation.give("Nairobi", "o8")
# END CORRECTION

# Question : Calculez et affichez les utilités de chaque agent
# NB : Pour récupérer le poids que donne un agent à un objet, utilisez
# la fonction instance.weight(agent, objet)
# Par exemple : instance.weight("Tokio", "o1")
# NB2 : Pour récupérer la liste des objets d'un agent, utilisez
# la fonction allocation.objects(agent)
# Par exemple : allocation.objects("Tokio")

# BEGIN CORRECTION
print("-----------------------------------")
for agent in AGENTS:
    utility = 0
    for object in allocation.objects(agent):
        utility += instance.weight(agent, object)
    print("u(" + agent + ") = " + str(utility))
# Ou alors directement avec une compréhension de liste
print("\n".join("u({}) = {}".format(
    agent,
    sum(instance.weight(agent, object) for object in allocation.objects(agent))
    ) for agent in AGENTS))
# END CORRECTION

# Question : Quelle est l'utilité collective utilitariste de cette
# allocation ? Et l'utilité collective égalitariste ?

# BEGIN CORRECTION
from itertools import combinations

print("-----------------------------------")

somme = 0
minimum = NB_AGENTS * MAX_WEIGHT
for agent in AGENTS:
    utility = 0
    for object in allocation.objects(agent):
        utility += instance.weight(agent, object)
    somme += utility
    minimum = utility if utility < minimum else minimum
print("util. = " + str(somme))
print("egal. = " + str(minimum))

# Ou alors directement avec une compréhension de liste
utilities = [sum(instance.weight(agent, object)
                 for object in allocation.objects(agent))
             for agent in AGENTS]
print("util. = " + str(sum(utilities)))
print("egal. = " + str(min(utilities)))
# END CORRECTION

# Question : Cette allocation est-elle sans envie ? Si ce n'est pas le
# cas, qui envie qui ?

# BEGIN CORRECTION
print("-----------------------------------")
ef = True
for ag1, ag2 in combinations(AGENTS, 2):
    ut1, ut2 = 0, 0
    for object in allocation.objects(ag1):
        ut1 += instance.weight(ag1, object)
        ut2 -= instance.weight(ag2, object)
    for object in allocation.objects(ag2):
        ut2 += instance.weight(ag2, object)
        ut1 -= instance.weight(ag1, object)
    if ut1 < 0:
        print("{} envie {} !".format(ag1, ag2))
        ef = False
    if ut2 < 0:
        print("{} envie {} !".format(ag2, ag1))
        ef = False
print("L'allocation " + ("est" if ef else "n'est pas")
      + " sans envie.")
# END CORRECTION


# Question : Nous allons maintenant chercher à améliorer cette allocation
# de manière *distribuée*. C'est-à-dire que les agents vont négocier entre
# eux pour s'échanger des objets. Nous nous limitons ici aux types les plus
# simples d'échanges : chaque échange implique 2 agents (a1, a2) ; a1 donne
# objet o1 à a2, en échange de quoi a2 donne à o1 un objet o2. L'échange doit
# être bénéfique pour les deux agents.
#
# Écrivez un code qui parcourt l'ensemble des couples d'agents, parcourt
# l'ensemble des échanges possibles entre ces agents jusqu'à trouver
# un échange mutuellement bénéfique. Les agents s'échangeront alors ces objets.
# NB : pour retirer un objet à un agent, vous pouvez utiliser
# allocation.take_back(agent, objet)
#
# Modifiez ensuite votre code pour que ces échanges aient lieu jusqu'à ce qu'il
# ne soit plus possible d'en trouver. À chaque échange réalisé, votre programme
# devra afficher les utilités utilitariste et égalitariste courantes.
# Affichez également le nombre d'échanges réalisés. Est-on sûr que ce nombre
# est borné ? En d'autres termes, le programme terminera-t-il dans tous les
# cas ?

# BEGIN CORRECTION
print("-----------------------------------")
def utilities(allocation):
    utilities = [sum(allocation.instance.weight(agent, object)
                 for object in allocation.objects(agent))
                 for agent in AGENTS]
    return sum(utilities), min(utilities)


flag = True
count = 0
ut = utilities(allocation)
print("{} : util. = {} / egal. = {}".format(count, ut[0], ut[1]))
while flag:
    flag = False
    for ag1, ag2 in combinations(AGENTS, 2):
        if flag:
            break
        for ob1, ob2 in zip(allocation.objects(ag1), allocation.objects(ag2)):
            if instance.weight(ag2, ob1) > instance.weight(ag2, ob2)\
               and instance.weight(ag1, ob2) > instance.weight(ag1, ob1):
                allocation.take_back(ag1, ob1)
                allocation.take_back(ag2, ob2)
                allocation.give(ag1, ob2)
                allocation.give(ag2, ob1)
                flag = True
                ut = utilities(allocation)
                count += 1
                print("{} : util. = {} / egal. = {}".format(
                    count, ut[0], ut[1]))
                break
# END CORRECTION


# Question : affichez la nouvelle allocation. Cette allocation est-elle
# sans envie ? Si ce n'est pas le cas, qui envie qui ?

# BEGIN CORRECTION
print("-----------------------------------")
print(allocation)
ef = True
for ag1, ag2 in combinations(AGENTS, 2):
    ut1, ut2 = 0, 0
    for object in allocation.objects(ag1):
        ut1 += instance.weight(ag1, object)
        ut2 -= instance.weight(ag2, object)
    for object in allocation.objects(ag2):
        ut2 += instance.weight(ag2, object)
        ut1 -= instance.weight(ag1, object)
    if ut1 < 0:
        print("{} envie {} !".format(ag1, ag2))
        ef = False
    if ut2 < 0:
        print("{} envie {} !".format(ag2, ag1))
        ef = False
print("L'allocation " + ("est" if ef else "n'est pas")
      + " sans envie.")
# END CORRECTION

# Question : Recommencez le processus de négociation depuis le départ
# en choisissant un ordre différent sur les agents (par exemple, utilisez
# sorted(AGENTS) pour les trier selon l'ordre alphabétique). Cela change-t-il
# quelque chose sur les utilités et l'envie ?

# BEGIN CORRECTION
# Oui, potentiellement cela changera, à la fois pour l'utilité collective
# utilitariste et l'utilité collective égalitariste.
# END CORRECTION


# Nous allons maintenant passer à une autre méthode d'allocation :
# l'allocation séquentielle. Commençons par remettre notre allocation
# à zéro et à définir une séquence d'agents...
allocation = Allocation(instance)
sequence = ["Tokio", "Rio", "Berlin", "Nairobi",
            "Tokio", "Rio", "Berlin", "Nairobi"]
objets_restants = set(OBJECTS)

# Question : Calculez l'allocation résultant de l'exécution de cette
# séquence. Vous pouvez afficher toutes les étapes de l'allocation
# (qui prend quoi à quel moment) si vous voulez.
# NB : voici quelques indications pour vous aider :
# - pour enlever l'objet o1 de l'ensemble des objets restants :
#   objets_restants.remove("o1")
# - pour récupérer le meilleur objet de l'ensemble des objets restants
#   selon Tokio : instance.best_obj("Tokio", objets_restants)

# BEGIN CORRECTION
print("-----------------------------------")
for agent in sequence:
    best = instance.best_obj(agent, objets_restants)
    allocation.give(agent, best)
    objets_restants.remove(best)
    print("{} prend {}. Objets restants après : {}".format(
        agent, best, objets_restants))
# END CORRECTION

# Question : Affichez l'allocation résultante. Cette allocation est-elle
# sans envie ? Si ce n'est pas le cas, qui envie qui ? Affichez également les
# utilités collectives utilitariste et égalitariste.

# BEGIN CORRECTION
print("-----------------------------------")
print(allocation)
ef = True
for ag1, ag2 in combinations(AGENTS, 2):
    ut1, ut2 = 0, 0
    for object in allocation.objects(ag1):
        ut1 += instance.weight(ag1, object)
        ut2 -= instance.weight(ag2, object)
    for object in allocation.objects(ag2):
        ut2 += instance.weight(ag2, object)
        ut1 -= instance.weight(ag1, object)
    if ut1 < 0:
        print("{} envie {} !".format(ag1, ag2))
        ef = False
    if ut2 < 0:
        print("{} envie {} !".format(ag2, ag1))
        ef = False
print("L'allocation " + ("est" if ef else "n'est pas")
      + " sans envie.")
ut = utilities(allocation)
print("util. = {} / egal. = {}".format(ut[0], ut[1]))
# END CORRECTION

# Question : Essayez avec d'autres séquences et observez les différences.

# BEGIN CORRECTION
# Exemple avec la séquence renversée

allocation = Allocation(instance)
sequence = ["Tokio", "Rio", "Berlin", "Nairobi",
            "Nairobi", "Berlin", "Rio", "Tokio"]
objets_restants = set(OBJECTS)

print("-----------------------------------")
for agent in sequence:
    best = instance.best_obj(agent, objets_restants)
    allocation.give(agent, best)
    objets_restants.remove(best)
    print("{} prend {}. Objets restants après : {}".format(
        agent, best, objets_restants))
print("-----------------------------------")
print(allocation)
ef = True
for ag1, ag2 in combinations(AGENTS, 2):
    ut1, ut2 = 0, 0
    for object in allocation.objects(ag1):
        ut1 += instance.weight(ag1, object)
        ut2 -= instance.weight(ag2, object)
    for object in allocation.objects(ag2):
        ut2 += instance.weight(ag2, object)
        ut1 -= instance.weight(ag1, object)
    if ut1 < 0:
        print("{} envie {} !".format(ag1, ag2))
        ef = False
    if ut2 < 0:
        print("{} envie {} !".format(ag2, ag1))
        ef = False
print("L'allocation " + ("est" if ef else "n'est pas")
      + " sans envie.")
ut = utilities(allocation)
print("util. = {} / egal. = {}".format(ut[0], ut[1]))
# END CORRECTION

# Essayons maintenant quelque chose de plus systématique. Nous allons
# tester, parmi les trois séquences suivantes, de déterminer en moyenne
# laquelle est la meilleure

sequence1 = ["Tokio", "Tokio", "Rio", "Rio",
             "Berlin", "Berlin", "Nairobi", "Nairobi"]
sequence2 = ["Tokio", "Rio", "Berlin", "Nairobi",
             "Tokio", "Rio", "Berlin", "Nairobi"]
sequence3 = ["Tokio", "Rio", "Berlin", "Nairobi",
             "Nairobi", "Berlin", "Rio", "Tokio"]

# Générez n instances aléatoires (n = 1000 par exemple). Pour chaque
# instance aléatoire, calculez le résultat de l'allocation séquentielle
# pour chacune des trois séquences. Ensuite calculez pour chacune des trois
# séquences :
# - la moyenne des utilités utilitariste et égalitariste
# - le nombre de fois que ces séquences résultent en des allocations sans envie
# Laquelle vous semble la meilleure ?
# NB : pour générer une instance aléatoire :
# instance = Instance(generate_uniform(NB_AGENTS, NB_OBJECTS, MAX_WEIGHT),
#                     AGENTS, OBJECTS)

# BEGIN CORRECTION
print("-----------------------------------")
N = 100
util = [0, 0, 0]
egal = [0, 0, 0]
nb_ef = [0, 0, 0]
sequences = [sequence1, sequence2, sequence3]


def executer_sequence(instance, sequence):
    allocation = Allocation(instance)
    objets_restants = set(instance.objects)
    for agent in sequence:
        best = instance.best_obj(agent, objets_restants)
        allocation.give(agent, best)
        objets_restants.remove(best)
    return allocation


def is_ef(allocation):
    for ag1, ag2 in combinations(AGENTS, 2):
        ut1, ut2 = 0, 0
        for object in allocation.objects(ag1):
            ut1 += instance.weight(ag1, object)
            ut2 -= instance.weight(ag2, object)
        for object in allocation.objects(ag2):
            ut2 += instance.weight(ag2, object)
            ut1 -= instance.weight(ag1, object)
        if ut1 < 0 or ut2 < 0:
            return False
    return True


for _ in range(N):
    matrix = generate_uniform(NB_AGENTS, NB_OBJECTS, MAX_WEIGHT)
    instance = Instance(matrix, AGENTS, OBJECTS)
    allocations = [executer_sequence(instance, sequence)
                   for sequence in sequences]
    ut = [utilities(allocation) for allocation in allocations]
    ef = [is_ef(allocation) for allocation in allocations]
    for k in range(len(util)):
        util[k] += ut[k][0]
        egal[k] += ut[k][1]
        nb_ef[k] += int(ef[k])
for seq, ut, eg, ef in zip(sequences, util, egal, nb_ef):
    print("{} → util. = {}, egal. = {}, nb_ef = {} / {}".format(
        seq, ut / N, eg / N, ef, N))
# END CORRECTION


# Question : enfin, nous allons nous intéresser à une méthode d'allocation
# encore plus centralisée. Reprenez l'instance du début du TP et utilisez
# un algorithme de recherche pour calculer une allocation sans envie
# s'il en existe une. Affichez l'allocation, et affichez également
# ses utilités utilitariste et égalitariste.

# BEGIN CORRECTION
print("-----------------------------------")
matrix = np.array(
    [[8, 4, 6, 7, 5, 2, 0, 1],
     [8, 2, 0, 3, 13, 4, 5, 6],
     [20, 7, 0, 6, 1, 5, 2, 9],
     [0, 9, 6, 1, 13, 4, 15, 2]]
)
instance = Instance(matrix, AGENTS, OBJECTS)

# On utilise la méthode qui est décrite dans le module
# solving (regardez le code pour savoir comment fonctionne
# l'algorithme)
from solving import find_solution
allocation = find_solution(instance,
                           lambda allocation: allocation.is_envy_free(),
                           cut=lambda allocation: False)
print(allocation)
ut = utilities(allocation)
print("util. = {} / egal. = {}".format(ut[0], ut[1]))
# END CORRECTION


# Question : Mêmes questions en tâchant cette fois-ci de renvoyer
# l'allocation qui maximise l'utilité utilitariste puis celle qui maximise
# l'utilité égalitariste.


# BEGIN CORRECTION
print("-----------------------------------")
from solving import find_optimal_solution

allocation = find_optimal_solution(instance,
                                   lambda allocation: utilities(allocation)[0],
                                   maximize=True,
                                   cut=lambda allocation: False)
print(allocation)
ut = utilities(allocation)
print("util. = {} / egal. = {}".format(ut[0], ut[1]))

allocation = find_optimal_solution(instance,
                                   lambda allocation: utilities(allocation)[1],
                                   maximize=True,
                                   cut=lambda allocation: False)
print(allocation)
ut = utilities(allocation)
print("util. = {} / egal. = {}".format(ut[0], ut[1]))
# END CORRECTION


# Question : reprenez enfin les trois séquences d'agents testées ci-dessus.
# Pour chaque séquence et chaque instance générée aléatoirement, comparez
# les utilités obtenues avec la séquence aux utilités optimales.
# L'utilisation d'une séquence engendre-t-elle une grosse perte d'utilité
# en comparaison de l'utilité optimale ?

# BEGIN CORRECTION
print("-----------------------------------")
N = 10
util = [0, 0, 0]
egal = [0, 0, 0]
nb_ef = [0, 0, 0]
sequences = [sequence1, sequence2, sequence3]

for k in range(N):
    print("\r{} / {}".format(k, N), end='')
    matrix = generate_uniform(NB_AGENTS, NB_OBJECTS, MAX_WEIGHT)
    instance = Instance(matrix, AGENTS, OBJECTS)
    allocations = [executer_sequence(instance, sequence)
                   for sequence in sequences]
    ut = [utilities(allocation) for allocation in allocations]
    ef = [is_ef(allocation) for allocation in allocations]

    opt_ut = [utilities(
        find_optimal_solution(instance,
                              lambda allocation: utilities(allocation)[0],
                              maximize=True,
                              cut=lambda allocation: False))[0]
              for allocation in allocations]
    opt_eg = [utilities(
        find_optimal_solution(instance,
                              lambda allocation: utilities(allocation)[1],
                              maximize=True,
                              cut=lambda allocation: False))[1]
              for allocation in allocations]

    for k in range(len(util)):
        util[k] += ut[k][0] * 100 / opt_ut[k]
        egal[k] += ut[k][1] * 100 / opt_eg[k]
        nb_ef[k] += int(ef[k])
print()
for seq, ut, eg, ef in zip(sequences, util, egal, nb_ef):
    print("{} → util. = {}, egal. = {}, nb_ef = {} / {}".format(
        seq, ut / N, eg / N, ef, N))
# END CORRECTION


