DS Info pour Tou(te)s

################################################"
#            X/ENS/ESPCI   2013
################################################
 
t0 = [1,3,5,7,9,1,3,5,7,9]
t1 = [5,5,2,2,0,2,2]
 
# QUESTION 1
def admet_point_fixe(t):
    for i in range(len(t)):
        if (t[i] == i):
            return True
    return False
 
# QUESTION 2
def nb_points_fixes(t):
    cpt = 0
    for i in range(len(t)):
        cpt = cpt + (1 if t[i] == i else 0)
    return cpt
 
# QUESTION 3
def itere(t,x,k):
    if k == 0:
        return x
    return itere(t,t[x],k - 1)
 
# QUESTION 4
def itere_tab(t,k):
    taille = len(t)
    tmp = [i for i in range(taille)]
    for j in range(k):
       tmp = [t[i] for i in tmp]
    return tmp
 
def nb_points_fixes_iteres(t,k):
    return nb_points_fixes(itere_tab(t,k))
 
# QUESTIOΝ 5
def liste_points_fixes(t):
    taille = len(t)
    return [i for i in range(taille) if i == t[i]]
 
def admet_attracteur_principal(t):
    # k <= taille(t) car f : En -> En
    taille = len(t)
    ps = liste_points_fixes(t)
    if len(ps) != 1:
        return False
    p = ps[0]
    for x in range(taille):
       k, xx = 0, x
       while (xx != p and k <= taille):
            # on évite itere qui recommence depuis k = 0 à chaque appel
            k += 1
            xx = t[xx] 
       if k > taille:
            return False
    return True
 
# QUESTION 6
def temps_de_convergence(t,x):
    tps = 0
    xx = x
    while (t[xx] != xx):
        tps += 1
        xx = t[xx]
    return tps
 
# QUESTION 7
# Mémoïsation
def temps_de_convergence_max(t):
    assert admet_attracteur_principal(t), "N'admet pas d'attracteur principal"
    ps = liste_points_fixes(t)
    dic_tps = {x:1  for x in ps}
    def calcule_temps(xx):
        if xx in dic_tps:
            return dic_tps[xx]
        dic_tps[xx] = 1 + calcule_temps(t[xx])
        return dic_tps[xx]
    return max([calcule_temps(x) for x in t if x not in ps])
 
 
# QUESTION 8
def est_croissante(t):
    for i in range(len(t) - 1):
        if t[i] > t[i + 1]:
            return False
    return True
 
# QUESTION 9
def point_fixe(t):
    assert est_croissante(t), "fonction non croissante"
    def recherche_dicho(deb,fin):
        m = (deb + fin) // 2
        if t[m] == m:
            return m
        elif m > t[m]:
            return recherche_dicho(deb, m - 1)
        else:
            return recherche_dicho(m + 1, fin)
    return recherche_dicho(0,len(t) - 1)
 
 
# QUESTION 13
def pgcd_points_fixes(t):
    cand = 1
    while cand != t[cand]:
        cand = t[cand]
    return cand

# question 1
 
#def nombreZeros(t,i):
#    n   = len(t)
#    j   = i
#    cpt = 0
#    while (j < n) and (t[j] == 0):
#        cpt += 1
#        j   += 1
#    return cpt
 
def nombreZeros(t,i):
    cpt = 0
    for el in t[i:]:
        if el == 0:
            cpt +=1
        else:
            return cpt
    return cpt
 
# from itertools import takewhiel
# def nombreZeros2(t,i):
#     return sum(1 for _ in takewhile(lambda x: x == 0, t[i:]))
 
#def nombreZeros3(t, i):
#    return 0 if t[i] == 1 else 1 + nombreZeros(t, i + 1)
 
#def nombreZeros4(t, i):
#    cpt, j = 0, i
#    while j < len(t) and t[j] == 0:
#        cpt += 1
#        j   += 1
#    return cpt
 
t1 = [0,1,1,1,0,0,0,1,0,1,1,0,0,0,0]
 
def nombreZerosMax(t):
    #return max([nombreZeros(t,i) for i in range(len(t))])
    n = len(t)
    m = 0
    for i in range(n):
        m = max( m, nombreZeros(t,i) )
    return m
 
def nombreZerosMax2(t):
    i, n, cpt = 0, len(t), 0
    saut = nombreZeros(t,i)
    maxi = saut
    while (i < n):
        i    = i + saut + 1
        saut = nombreZeros(t,i) 
        maxi = max(saut, maxi)
        cpt += 1
    return maxi,cpt
 
def nombreZerosMax3(t):
    return max([nombreZeros(t,i) for i in range(len(t)) if t[i] == 0 and (t[i - 1] == 1 or i == 0)])
 
 
# question 2
from numpy.random import randint
 
def comptage(L,N):
    P = [0 for k in range(N)]
    for el in L:
        P[el] += 1
    return P
 
def tri(L,N):
    P = comptage(L,N)
    return [x for x in range(N) for _ in range(P[x])]
 
 
def test(n,N):
    return [randint(N) for k in range(n)]
 
# question 3
from numpy.random import random
 
def calcul_n(h):
        if h > 1:
            return int((h + 2.0)/2 * random()) + 1
        else:
            return 0
 
def initialisation(P):
    return [0]*P # ou [0 for k in range(P)]
 
def actualise(piles,perdus):
    P = len(piles)
    for k in range(1,P):
        diff = calcul_n(piles[k-1] - piles[k])
        piles[k]     += diff
        piles[k - 1] -= diff
    perdus_cette_fois =  calcul_n(piles[P-1])
    perdus += perdus_cette_fois
    piles[P - 1] -= perdus_cette_fois
    return piles, perdus
 
def principal():
    print("Combien de piles ?")
    P = int(input())
    piles  = initialisation(P)
    perdus = 0
    while perdus < 1000:
        piles[0] += 1
        for k in range(10):
            piles, perdus = actualise(piles,perdus)