######   FUNCIONES   ######
from random import sample, seed
seed()

def lista_ordenada(lis, orden_inverso=False): # la función da True si ponemos lista_ordenada([4,3,2,1], orden_inverso=True)
    ordenada = False
    aux = lis[:]
    aux.sort(reverse=orden_inverso)
    if aux == lis:
        ordenada = True
    return ordenada

def sa(a,b):
    if len(a) > 1: a[0],a[1] = a[1],a[0]
    return a,b
def sb(a,b):
    if len(b) > 1: b[0],b[1] = b[1],b[0]
    return a,b
def ss(a,b):
    sa(a,b)
    sb(a,b)
    return a,b
def pa(a,b):
    if len(b) > 0:
        a.insert(0, b[0])
        b.pop(0)
    return a,b
def pb(a,b):
    if len(a) > 0:
        b.insert(0, a[0])
        a.pop(0)
    return a,b
def ra(a,b):
    if len(a) > 1: a.append(a.pop(0))
    return a,b
def rb(a,b):
    if len(b) > 1: b.append(b.pop(0))
    return a,b
def rr(a,b):
    ra(a,b)
    rb(a,b)
    return a,b
def rra(a,b):
    if len(a) > 1: a.insert(0, a.pop())
    return a,b
def rrb(a,b):
    if len(b) > 1: b.insert(0, b.pop())
    return a,b
def rrr(a,b):
    rra(a,b)
    rrb(a,b)
    return a,b

def separa(tramo, n, s, a, b):   # se llevan de la pila A a la B los números del tramo que toca
    contador = 0
    ancho = int(n/s)
    fin = tramo * ancho          # fin del tramo
    inicio = (tramo-1)*ancho+1   # inicio del tramo
    pasados = 0   # cuenta cuantos números se han pasado de la pila A a la B
    while pasados < fin-inicio+1: # recorremos los elementos de la plia A hasta que pasemos todos los números de este tramo
        if inicio <= a[0] <= fin:
            pb(a,b)
            contador += 1
            pasados += 1
        else:
            ra(a,b)
            contador += 1
    return a, b, contador

def ordena(tramo, n, s, a, b):   # Pasamos de B a A los del tramo que toca, comenzando por el nº mayor, que para el tramo 1 es 5.
    # ordena los números recientemente separados y llevados a B
    # el objetivo es que esos números queden en B ordenados de forma decreciente: 5,4,3,2,1
    contador = 0
    ancho = int(n/s)
    fin = tramo * ancho          # fin del tramo
    inicio = (tramo-1)*ancho+1   # inicio del tramo
    while not lista_ordenada(b, orden_inverso=True): # se repite hasta que B quede ordenada decrecientemente. Si solo queda un elemento en B es que está ordenada
        while max(b) != b[0]:   # buscamos el máximo y vamos haciendo ra o rra hasta que quede el primero
            if b.index(max(b)) <= int(len(b)/2):
                rb(a,b)
            else:
                rrb(a,b)
            contador += 1
        if not lista_ordenada(b, orden_inverso=True):
            pa(a,b); contador += 1
    while len(a) > n-fin:   # llevamos de A a B los números del tramo que toca
        pb(a,b); contador += 1
    return a, b, contador

def ordena_final(tramo, n, s, a, b):    # ordena los números del úlitmo tramo que están en "A" y el objetivo es que queden crecientes: ...,18,19,20.
    contador = 0
    ancho = int(n/s)
    fin = n           # en el último tramo se ajusta para que el último nº sea igual a n
    inicio = (tramo-1)*ancho+1   # inicio del tramo
    while not lista_ordenada(a): # se repite hasta que A quede ordenada en orden creciente. Si solo queda un elemento en A es que está ordenada
        while min(a) != a[0]:
            if a.index(min(a)) <= int(len(a)/2):
                ra(a,b)
            else:
                rra(a,b)
            contador += 1
        if not lista_ordenada(a):
            pb(a,b); contador += 1
    while len(b) > 0:   # llevamos de B a A todos los números que hay en B
        pa(a,b); contador += 1
    return a, b, contador

if __name__ == "__main__":
    for n in [10,50,100,500,1000]:
        for generada in range(200): # nº de pilas A generadas por cada n
            # Generación de la pila a
            #n = 500   # número de elementos de la pila
            a = sample(range(1, n+1), n)
            a_original = a[:]
            b = []
            ######   PROCEDIMIENTO PRIMERO   ######
            contador = 0
            while not lista_ordenada(a):   # se repite hasta que A quede ordenada. Si solo queda un elemento en A es que está ordenada
                while min(a) != a[0]:   # buscamos el mínimo y vamos haciendo ra o rra hasta que quede el primero
                    if a.index(min(a)) <= int(len(a)/2):
                        ra(a,b)
                    else:
                        rra(a,b)
                    contador += 1
                if not lista_ordenada(a):
                    pb(a,b); contador += 1 #print(a,b) # luego hacemos pb
            while len(b) > 0:   # luego se hace pa pa pa pa hasta que no quede nadie en la pila b
                pa(a,b); contador += 1
            #print("PROCEDIMIENTO PRIMERO contador:", contador)
            primero = contador
            for s in range(max(2,int(-0.000003*n**2+0.0155*n+1.6253)-1), int(-0.000002*n**2+0.01544*n+6.8537)+3):
                ######   PROCEDIMIENTO SEGUNDO   ######
                a = a_original[:]
                n = len(a)
                b = []
                #s = 20   # número de grupos
                contador = 0
                for tramo in range(1, s):   # tramo=1,2,...,s-1. El último tramo se trata de forma diferente
                    a, b, contador_separa = separa(tramo,n,s,a,b)   # lleva de A a B los números correspondientes a ese tramo
                    contador += contador_separa
                    a, b, contador_ordena = ordena(tramo,n,s,a,b)   # ordena los números recientemente separados y llevados a B
                    contador += contador_ordena
                # tramo final donde los números de A ya se ordenan en A, ya no se usa la función separa
                # la pila de trabajo es "A" y el objetivo es que sea creciente: ...,18,19,20.
                a, b, contador_ordena_final = ordena_final(tramo,n,s,a,b)
                contador += contador_ordena_final
                #print("Al final:", a, b)
                #print("PROCEDIMIENTO SEGUNDO contador: ", contador)
                segundo=contador
                #print(f"n: {n}, primero: {primero}, s: {s}, segundo: {segundo}")
                print(n, primero, s, segundo)