# Correction

#1a
# Pour chaque case, il y a 2 choix (0 ou 1). Donc il y a 2^n listes possibles. 

# 1b
def nombre2tableau(n : int, k : int) -> list :
   # on suppose que 0 <= k < 2**n
   tab = n*[0]
   for i in range( n-1, -1, -1 ) :
      tab[i] = k % 2
      k //= 2
   return tab

# 1c
def ensemble_tableaux(n : int) -> list :
   ens = []
   for i in range(2**n) :
      ens += [ nombre2tableau(n, i) ]
   return ens

#2
def comptage(T : list) -> tuple :
   n0 = 0
   for i in range( len(T) ) :
      if T[i]==0 :
         n0 += 1
   return(n0, len(T)-n0) # on suppose que T ne contient que des 0 ou des 1

#3
def plageMax0(T : list) -> int :
   pmax = 0 # longueur maximal d'une plage de 0
   plage0 = 0 # compteur d'une plage de 0 
   for i in range( len(T) ) :
      if T[i] == 0 :
         plage0 += 1
      else : # si la plage de 0 s'arrête 
         if pmax < plage0 : # si la plage de 0 actuelle est la plus longue, on la conserve 
            pmax = plage0 
         plage0 = 0 # on réinitialise le compteur de la taille d'une plage de 0 
   if pmax < plage0 :   # vérification si la dernière plage est la plus grande
      pmax = plage0
   return pmax

#4a
def listeMin0(n : int) -> int :
   ensemble = ensemble_tableaux(n)
   nb = 0 # compteur du nombres de listes acceptables 
   for tab in ensemble :
      if plageMax0( tab ) < 3 :
         nb += 1
   return nb

# 4b
def plageMax(T : list, b : int) -> int :
   pmax = 0 # longueur maximale des plages de b 
   plage = 0
   for i in range( len(T) ) :
      if T[i] == b :
         plage += 1
      else : 
         if pmax < plage :
            pmax = plage
         plage = 0
   if pmax < plage :
      pmax = plage
   return pmax

def listeMin(n : int) -> int :
   ensemble = ensemble_tableaux(n)
   nb = 0
   for tab in ensemble :
      if plageMax( tab, 0 ) < 3 and plageMax( tab, 1 ) < 3 :
         nb += 1
   return nb

# 5
def frise3(n : int) -> list :
   ensemble = ensemble_tableaux(n)
   ensOK = []
   for tab in ensemble :
      if plageMax( tab, 0 ) < 3 and plageMax( tab, 1 ) < 3 : # si la liste est acceptable 
         ensOK += [ tab ]
   return ensOK
#>>> frise3( 20 )
#21892

# 6a
def guirlande2tuple(T : list) -> tuple :
   n = len(T)
   nb = 0
   for i in range( n ) :
      nb += T[i] * 2**(n-1-i)
   return n, nb

# 6b
def frise3bis(n : int) -> list :
   ensOK = frise3( n )
   tupOK = []
   for tab in ensOK :
      tupOK += [ guirlande2tuple(tab) ]
   return tupOK

# 6c
# Les nombres étant scané dans l'ordre croissant, les listes correspondent à des nombres dans l'ordre croissant. Donc : 
#>>> nbAccept20 = frise3bis( 20 )
#>>> nbAccept20[0], nbAccept20[-1]
#(20, 149796), (20, 898779)

# 6d
# La longueur des listes est constante. Donc il ne sert à rien de renvoyer le tuple (n,L) à chaque fois. On peut gagner de la place sur le
# dique en ne renvoyant qu'une seule fois la longueur, puis toutes les listes. Par exemple, on pourrait renvoyer un tuple (n,T) où n est
# la longueur communes de toutes les gurilandes, et T est une liste de listes contenant toutes les gurilandes acceptables par le Père Noël.