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

def bajar_tres(a,b):   # se usa en la función tres_decrecientes para el caso habitual en el que hacemos pb pb pb
    pb(a,b)
    pb(a,b)
    pb(a,b)
    
def tres_decrecientes(a,b):   # bajamos los tres primeros números de A a B, y los hacemos decrecientes de forma circular
    if a[0] < a[1] < a[2]:                          # caso: 1 2 3
        bajar_tres(a,b)
    elif a[0] < a[1] > a[2] and a[0] < a[2]:        # caso: 1 3 2
        pb(a,b)
        sa(a,b)
        pb(a,b)
        pb(a,b)
    elif a[0] > a[1] < a[2] and a[0] < a[2]:        # caso: 2 1 3
        sa(a,b)
        bajar_tres(a,b)
    elif a[0] < a[1] > a[2] and a[0] > a[2]:        # caso: 2 3 1
        bajar_tres(a,b)
    elif a[0] > a[1] < a[2] and a[0] > a[2]:        # caso: 3 1 2
        bajar_tres(a,b)
    elif a[0] > a[1] > a[2]:                        # caso: 3 2 1
        bajar_tres(a,b)
        sb(a,b)

# PASOS NECESARIOS PARA COLOCAR CADA ELEMENTO DE A EN SU SITIO EN B      total = pasosA + pasosB (esta suma es solo una idea, se ha de sumar de una forma peculiar)

def necesariosA(a, b):   # array pasosA calcula los pasos necesarios para colocar cada elemento de A como el primero de su pila
    for v in a:
        if a.index(v) < len(a)/2:
            pasosA.append(a.index(v))
        else:
            pasosA.append(-(len(a)- a.index(v)))
    #print("pasosA: ", pasosA)

def necesariosB(a,b):   # array pasosB calcula los pasos de B necesarios para colocar cada elemento de A dentro de su sitio en B
    for i in range(len(a)):    # objetivo_primero es el número que se ha de poner en la primera posición de la pila B
        if a[i] < min(b):      # si el elemento de A considerado es menor que el mayor de B entonces
            objetivo_primero = max(b)   # el objetivo_primero será el mayor de B
        else:   # objetivo_primero en este caso será el maximo de los inferiores en B al valor iésimo de A
            objetivo_primero = min(b)   #se inicializa en el valor mínimo de la pila B
            for j in range(len(b)):
                if b[j] < a[i] and b[j] > objetivo_primero:
                        objetivo_primero = b[j]
        # el objetivo_primero se ha de situar el primero de la pila B            
        if b.index(objetivo_primero) < len(b)/2:
            pasosB.append(b.index(objetivo_primero))
        else:
            pasosB.append(-(len(b)- b.index(objetivo_primero)))
    #print("pasosB: ", pasosB)

def totaliza(a,b):   # totalizar pasos
    global total
    for i in range(len(pasosA)):
        if pasosA[i] * pasosB[i] < 0:   # si son de distinto signo, uno positivo y otro negativo
            total.append(abs(pasosA[i]) + abs(pasosB[i]))   # no hay sinergia
        else:   # si son de igual signo o alguno cero
            total.append(max(abs(pasosA[i]), abs(pasosB[i])))  # si son de igual signo hay sinergia
    #print("total:  ", total)

def calculaIndexPasosMinimos():
    global pasosA, pasosB, total
    pasosA = []   # [0,1,2, ...,41,-41,... , -2,-1]  vector donde cada index está asociado con el valor del mismo index en A
    pasosB = []   # [-3,2,-5, ..., -5,0]   estos dos arrays se han de recalcular cada vez que realmente se mueva algún elemento de A a B
    total = []
    necesariosA(a, b)
    necesariosB(a, b)
    totaliza(a,b)
    return total.index(min(total))   # retorna el índice del elemento de la pila A que menos pasos totales necesita

def giraA(a, b, indice, pasos):
    for i in range(abs(pasos)):
        if pasos > 0:
            ra(a,b)
        elif pasos < 0:
            rra(a,b)

def giraB(a, b, indice, pasos):
    for i in range(abs(pasos)):
        if pasos > 0:
            rb(a,b)
        elif pasos < 0:
            rrb(a,b)

# girando pilas A y B
def giraPilas(a,b,indice):   # indice es el index del valor en la pila A que deseamos poner el primero
    if pasosA[indice] * pasosB[indice] > 0:   # Existe sinergia, nos podemos ahorrar pasos
        pasos_comunes = min(abs(pasosA[indice]), abs(pasosB[indice]))
        for i in range(pasos_comunes):
            if pasosA[indice] > 0:   # si el signo de ambos es positivo, ya que ambos tienen el mismo signo
                rr(a,b)
            elif pasosA[indice] < 0: # si el signo de ambos es negativo
                rrr(a,b)
        exceso_pasosA = abs(pasosA[indice]) - pasos_comunes
        exceso_pasosB = abs(pasosB[indice]) - pasos_comunes
        giraA(a, b, indice, ((pasosA[indice] > 0) - (pasosA[indice] < 0)) * exceso_pasosA)    # (a > 0) - (a < 0) da el signo de a
        giraB(a, b, indice, ((pasosB[indice] > 0) - (pasosB[indice] < 0)) * exceso_pasosB)   # Python no tiene función sign
    else:   # No existe sinergia
        giraA(a ,b, indice, pasosA[indice])   # gira A
        giraB(a, b, indice, pasosB[indice])   # gira B

def situarMax_en_B():
    indice = b.index(max(b))
    if indice < len(a)/2:
        pasos = indice
    else:
        pasos = -(len(b)- indice)
    giraB(a, b, indice, pasos)

def subirTodo_a_A():
    for _ in range(len(b)):
        pa(a,b)

if __name__ == "__main__":
    from random import seed, shuffle
    seed()
    for intento in range(10000):
        contador = 0
        n = 500   # número de elementos de la pila
        a = list(range(1, n+1)); shuffle(a)   # generación aleatoria de la pila A
        b = []
        a_original = a[:]
        tres_decrecientes(a,b)
        while len(a) > 0:
            index_minimosPasos = calculaIndexPasosMinimos()
            giraPilas(a,b,index_minimosPasos)
            pb(a,b) # lo pasa de A a B haciendo pb
        situarMax_en_B()
        subirTodo_a_A()
        if a != sorted(a_original):
            print(f"ERROR: no se ha ordenado\n {a_original}\n{a}")
        if contador >= 5500:
            print(f"{intento+1} contador: \t{contador} {a_original}")