###Scrutin à un tour

def creer_dico_resultats(votes):
    D = {}
    for bulletin in votes:
        if bulletin in D:
            D[bulletin] += 1
        else:
            D[bulletin] = 1
    return D

def cle_de_valeur_max(D):
    max = 0
    for cle in D:
        valeur = D[cle]
        if valeur > max:
            max = valeur
            cle_max = cle
    return cle_max


def scrutin_un_tour(votes):
    D = creer_dico_resultats(votes)
    return cle_de_valeur_max(D)

###Scrutin à deux tours

preferences = [['Alice', 'Charlie', 'Dave', 'Bob'], ['Bob', 'Charlie', 'Dave', 'Alice'], ['Alice', 'Dave', 'Charlie', 'Bob'], ['Dave', 'Charlie', 'Bob', 'Alice'], ['Alice', 'Bob', 'Charlie', 'Dave'], ['Charlie', 'Dave', 'Bob', 'Alice'], ['Bob', 'Dave', 'Charlie', 'Alice']]

#C'est Bob qui gagne au second tour contre Alice.

def candidats_second_tour(D):
    premier = cle_de_valeur_max(D)
    max = 0
    for cle in D:
        if cle != premier and D[cle] > max:
            max = D[cle]
            second = cle
    return premier, second

def vote_second_tour(bulletin, p, s):
    for c in bulletin:
        if c==p or c==s:
            return c


def scrutin_deux_tours(votes):
    votes_premier_tour = []
    for bulletin in votes:
        votes_premier_tour.append(bulletin[0])
    resultats_premier_tour = creer_dico_resultats(votes_premier_tour)
    p, s = candidats_second_tour(resultats_premier_tour)
    votes_second_tour = []
    for bulletin in votes:
        report = vote_second_tour(bulletin,p,s)
        votes_second_tour.append(report)
    return scrutin_un_tour(votes_second_tour)

#Version plus concise avec des listes par compréhension :
def scrutin_deux_tours(votes):
    votes_premier_tour = [bulletin[0] for bulletin in votes]
    resultats_premier_tour = creer_dico_resultats(votes_premier_tour)
    p,s = candidats_second_tour(resultats_premier_tour)
    votes_second_tour = [vote_second_tour(bulletin,p,s) for bulletin in votes]
    return scrutin_un_tour(votes_second_tour)

#On considère les listes de préférences de l'exemple.
#Pour le scrutin à un tour, si le votant 4 vote Bob plutôt qu'Alice, et le votant 6 vote Bob plutôt que Charlie,  alors c'est Bob qui est élu au scrutin à un tour, candidat préféré à Alice pour ces deux votants.
#Pour le scrutin à deux tours,  si au premier tour les votants 1 et 3 votent Charlie plutôt qu'Alice,  alors Bob perd les élections et Charlie gagne.  Pour ces deux votants,  c'est bien Charlie qu'ils préfèrent à Bob.
#Ces deux scrutins sont donc sujets au vote utile.

### Dictature aléatoire
from random import *

def dictature_aleatoire(T):
    n = len(T)
    k = randint(0,n-1)
    return T[k]

#Ce système de vote n'est pas sujet au vote utile, on a toujours intérêt à voter pour son candidat préféré pour qu'il soit élu si notre bulletin est tiré.

### Scrutin par élimination

#C'est Dave qui est élu

def liste_sans(L,a):
    R=[]
    for x in l:
        if x!=a:
            R.append(x)
    return R

def enlever_candidat(T,p):
    R=[]
    for L in T:
        L2 = liste_sans(L,p)
        R.append(L2)
    return R

def cle_de_valeur_min(D):
    min = float('inf')
    for cle in D:
        if D[cle] < min or (D[cle] == min and cle < cle_min) :
            min = D[cle]
            cle_min = cle
    return cle_min

def dernier(votes):
    votes_tour_courant = [bulletin[0] for bulletin in votes]
    resultats = creer_dico_resultats(votes_tour_courant)
    for bulletin in votes:
        for c in bulletin:
            if c not in resultats:
                resultats[c] = 0
    return cle_de_valeur_min(resultats)

def scrutin_elimination(votes):
    R=votes
    while len(R[0]) > 1:
        p = dernier(R)
        R = enlever_candidat(R,p)
    return R[0][0]

#Si le votant 1 vote Charlie plutôt que Alice et le votant 2 Charlie plutôt que Bob, alors c'est Charlie qui est élu, et il est placé avant Dave dans leur liste de préférence.  Ce système de scrutin est donc sujet au vote utile.


###Scrutin de Condorcet

#Oui, Charlie est le vainqueur de Condorcet.

#Exemple de préférences sans vainqueur de Condorcet : Alice > Bob > Charlie,  Bob > Charlie > Alice,  Charlie > Alice > Bob.

def duel(votes,c1,c2):
    votes_duel = [vote_second_tour(bulletin,c1,c2) for bulletin in votes]
    return scrutin_un_tour(votes_duel)

def liste_candidats(votes):
    L = []
    for bulletin in votes:
        for candidat in bulletin:
            if candidat not in L:
                L.append(candidat)
    return L

def est_vainqueur_condorcet(votes,L,c):
    for x in L:
        if x!=c and duel(votes,x,c)==x:
            return False
    return True


def scrutin_condorcet(votes):
    L = liste_candidats(votes)
    for c in L:
        if est_vainqueur_condorcet(votes,L,c):
            return c
    return None