# FUNCIONES
from random import sample, seed
seed()

# la función da True si ponemos lista_ordenada([4,3,2,1], orden_inverso=True)
def lista_ordenada(lis, orden_inverso=False):
    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

# PROCEDIMIENTO MEJORADO SEGUNDO
# dividiendo los n=100 valores aleatorios en s=5 grupos de n/s=20 números cada uno
# si no es divisible se toma un ancho=int(n/s) y se ajusta el último para que finalice en n
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
        # buscamos el máximo y vamos haciendo ra o rra hasta que quede el primero
        while max(b) != b[0]:
            #print("max(b):", max(b))
            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]:
            #print("max(b):", max(b))
            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__":
    # Generación de la pila A
    n = 100   # número de elementos de la pila
    #a = sample(range(1, n+1), n)
    a = [82, 14, 53, 81, 34, 40, 25, 52, 22, 91, 93, 80, 79, 5, 8, 17, 99, 96, 16, 65, 72, 18, 94, 66, 43, 44, 2, 3, 97, 86, 6, 32, 77, 35, 68, 61, 45, 63, 24, 83, 37, 48, 28, 95, 39, 60, 64, 85, 56, 12, 89, 92, 26, 70, 78, 55, 19, 98, 29, 88, 1, 69, 47, 71, 4, 10, 30, 59, 11, 15, 31, 75, 33, 7, 90, 27, 62, 36, 42, 58, 13, 41, 50, 23, 20, 38, 49, 76, 73, 57, 84, 100, 54, 21, 51, 87, 9, 46, 67, 74]
    #a = [14,3,15,12,16,13,2,5,11,18,17,4,8,1,6,20,10,7,19,9]
    a_original = a[:]
    n = len(a)
    b = []
    s = 4   # número de grupos
    ### PROCEDIMIENTO
    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
        #print("ordenado:", a, b, contador)
    # 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("="*60)
    print("Al final:", a, b)
    print("contador: ", contador)