################################################################################
#           DS 1 d'informatique commune de l'année 2025/2026 - MPSI            #
#                                  Correction                                  #
################################################################################

import random

################
### Question 1
################

# Il s'agit de l'expression len(C).

################
### Question 2.a
################

def appartient(L, x, i0):
    assert 0 <= i0
    for i in range(i0, len(L)):
        if x == L[i]:
            return True
    return False

################
### Question 2.b
################

def tousDiff(C):
    for i in range(len(C)-1):
        if appartient(C, C[i], i+1):
            return False
    return True

################
### Question 3.a
################

def nbOcc(V,s):
    res = 0
    for e in V:
        if e == s:
            res += 1
    return res

################
### Question 3.b
################

def makeR1(C,V):
    R = []
    for s in C:
        R.append(nbOcc(V, s))
    return R

################
### Question 4.a
################

def nomToNum(C, s):
    for i in range(len(C)):
        if C[i] == s:
            return i
    return None

################
### Question 4.b
################

def makeR2(C,V):
    R = [0]*len(C)
    for s in V:
        i = nomToNum(C, s)
        if i is not None:  # OU i != None
            R[i] += 1
    return R

################
### Question 5.a
################

def nbVotes(R):
    res = 0
    for e in R:
        res += e
    return res

################
### Question 5.b
################

def majAbs(R):
    return nbVotes(R)//2 + 1

################
### Question 5.c
################

# Les signatures de ces fonctions sont:
# nbVotes(R: list[int]) -> int
# majAbs(R: list[int]) -> int

################
### Question 6.a
################

def tour1(R):
    seuil = majAbs(R)
    for i in range(len(R)):
        if R[i] >= seuil:
            return i
    return None

################
### Question 6.b
################

def max2(R):
    if R[0] >= R[1]:
        i1 = 0
        i2 = 1
    else:
        i1 = 1
        i2 = 0
    for i in range(2,len(R)):
        if R[i] > R[i1]:
            i2 = i1
            i1 = i
        elif R[i] > R[i2]:
            i2 = i
    return (i1,i2)

################
### Question 7.a
################

def valAbs(a):
    if a >= 0:
        return a
    else:
        return -a

################
### Question 7.b
################

# nv1 = Nombre de voix qu'obtient i1 au 2nd tour
# nv2 = Nombre de voix qu'obtient i2 au 2nd tour
# La fonction nb_voix calcule nv1 et nv2
def nb_voix(R, i1, i2):
    nv1 = 0
    nv2 = 0
    for i in range(len(R)):
        if valAbs(i - i1) <= valAbs(i - i2):
            nv1 += R[i]
        else:
            nv2 += R[i]
    return nv1, nv2

def tour2(R, i1, i2):
    nv1, nv2 = nb_voix(R, i1, i2)
    if nv1 > nv2:
        return i1
    elif nv1 < nv2:
        return i2
    else:
        if i1 < i2:
            return i1
        else:
            return i2

################
### Question 8
################

def elu(C, V):
    if not tousDiff(C):
        return None
    R = makeR1(C,V)
    elu_tour1 = tour1(R)
    if elu_tour1 is not None:  # OU elu_tour1 != None
        return C[elu_tour1]
    (i1,i2) = max2(R)
    return C[tour2(R, i1, i2)]

################
### Question 9
################

# Il faut d'abord importer le module random en écrivant "import random" au début
# du fichier. On peut alors utiliser la fonction en écrivant random.randint.

################
### Question 10
################

def f(m):
    s = ""
    i1 = ord('a')
    i2 = ord('z')
    for _ in range(m):
        c = chr(random.randint(i1,i2))
        s = s + c
    return s

def g(n):
    C = []
    while len(C) < n:
        m = random.randint(4, 10)
        s = f(m)
        if not appartient(C, s, 0):
            C.append(s)
    return C

################
### Question 10.a
################

# La signature de la fonction f est
#      f(m: int) -> str
# Cette fonction renvoie une chaîne de caractères s de taille m où chaque
# caractère a été choisi aléatoirement parmi les 26 lettres minuscules de
# l'alphabet.

################
### Question 10.b
################

# La signature de la fonction g est :
#      g(n: int) -> list[str]
# Cette fonction renvoie une liste C contenant n chaînes de caractères toutes
# différentes. Chaque élément de C est généré par la fonction f (voir question
# précédente) et sa longueur est choisie aléatoirement dans l'intervalle [|4,
# 10|].

################
### Question 11
################

def alea1(m, s):
    A = []
    for _ in range(m-1):
        r = random.randint(0, s)
        A.append(r)
        s = s-r
    A.append(s)
    return A

################
### Question 12 - Solution 1
################

# Solution 1 : on construit une liste de booléens représentant le tableau de
# l'énoncé.

# On appelle T le tableau décrit dans l'énoncé.
# T[i] vaut False si la case est vide et True si elle contient une croix.
# F est la liste des indices i tels que T[i] = False.
def getT(m, s):
    T = [False]*(s+m-1)
    F = [i for i in range(len(T))]
    for _ in range(m-1):
        k = random.randint(0, len(F)-1)
        i0 = F[k]
        T[i0] = True
        F = [i for i in F if i != i0]
    return T

def alea2(m, s):
    T = getT(m, s)
    A = [0] * m
    k = 0
    for b in T:
        if b:
            k = k+1
        else:
            A[k] = A[k] + 1
    return A

################
### Question 12 - Solution 2
################

# Solution 2 : on construit une liste (triée !) contenant les indices des croix
# dans le tableau.

def mini(L):
    i_min = 0
    for i in range(1, len(L)):
        if L[i] < L[i_min]:
            i_min = i
    return i_min

def tri(L):
    M = []
    for _ in range(len(L)):
        i_min = mini(L)
        M.append(L[i_min])
        L = L[:i_min] + L[i_min+1:]
    return M

# L est la liste des cases qui ne contiennent pas de croix
def pos_croix(m, s):
    pos = []
    L = [i for i in range(s+m-1)]
    for _ in range(m-1):
        k = random.randint(0, len(L)-1)
        i0 = L[k]
        pos.append(i0)
        L = [i for i in L if i != i0]
    return tri(pos)

def alea2(m, s):
    if m == 1:
        return [s]
    pos = pos_croix(m, s)
    A = [pos[0]]
    for i in range(len(pos)-1):
        A.append(pos[i+1] - pos[i] - 1)
    A.append(s+m-2-pos[-1])
    return A

################
### Question 13
################

def aleaR(n, s):
    m = n+2
    L = alea2(m, s)
    R = L[:-2]
    v1 = L[-2]
    v2 = L[-1]
    return (R, v1, v2)

################
### Question 14
################

# On fait en sorte de ne pas modifier la liste donnée en entrée.
def melange(L0):
    L = L0[:]
    n = len(L)
    for i in range(n-1, 0, -1):
        j = random.randint(0,i)
        tmp = L[i]
        L[i] = L[j]
        L[j] = tmp
    return L

################
### Question 15
################

def aleaV(C, R, v1, v2):
    V0 = []
    for i in range(len(C)):
        L = [C[i]] * R[i]
        V0 = V0 + L
    V0 = V0 + [""]*v1
    for _ in range(v2):
        V0.append(f(11))
    return melange(V0)

################
### Question 16
################

def test(n, s):
    C = g(n)
    (R, v1, v2) = aleaR(n, s)
    V = aleaV(C, R, v1, v2)
    return makeR1(C,V) == R and makeR2(C,V) == R

################
### Question 17.a
################

# 's0' est le nom de la personne dont le score est maximal.
# 'x0' est le score de 's0'.
def premM(P, A):
    s0 = None
    x0 = None
    for (s,x) in P:
        if not appartient(A, s, 0):
            if x0 is None or x > x0:
                s0 = s
                x0 = x
    return s0

################
### Question 17.b
################

def triP(P):
    A = []
    for _ in range(len(P)):
        s = premM(P, A)
        A.append(s)
    return A

################
### Question 18
################

# On utilise une variable "L: list[list[str], list[str]]".
# Les éléments de L sont des couples (M1, M2) où "M2: list[str]" est la liste
# des personnes choisies pour être ministres et "M1: list[str]" est la liste des
# personnes restantes.
# Initialement M2 est vide, puis on y ajoute de nouvelles personnes choisies
# dans M1 jusqu'à ce que M2 soit de taille n.

def tousGouv(M, n):
    L = [(M, [])]
    for _ in range(n):
        L2 = []
        for (M1, M2) in L:
            for s in M1:
                M3 = [t for t in M1 if t != s]
                M4 = M2 + [s]
                L2.append((M3,M4))
        L = L2
    for (_,M0) in L:
        print(M0)