# FUNCIONES
def sa(a, b, result):   # result es un array que va acumulando los pasos dados. Ejemplo: result = ['pb','ra','sa','rra']
    if len(a) > 1: a[0],a[1] = a[1],a[0]; result.append('sa')
    return a, b, result
def sb(a, b, result):
    if len(b) > 1: b[0],b[1] = b[1],b[0]; result.append('sb')
    return a, b, result
def ss(a, b, result):   # ss no llama a sa y sb ya que en result quedarían anotadas las tres funciones: ss, sa y sb
    if len(a) > 1 or len(b) > 1:
        result.append('ss')
        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, result
def pa(a, b, result):
    if len(b) > 0:
        a.insert(0, b[0])
        b.pop(0); result.append('pa')
    return a, b, result
def pb(a, b, result):
    if len(a) > 0:
        b.insert(0, a[0])
        a.pop(0); result.append('pb')
    return a, b, result
def ra(a, b, result):
    if len(a) > 1: a.append(a.pop(0)); result.append('ra')
    return a, b, result
def rb(a, b, result):
    if len(b) > 1: b.append(b.pop(0)); result.append('rb')
    return a, b, result
def rr(a, b, result):
    if len(a) > 1 or len(b) > 1:
        result.append('rr')
    if len(a) > 1: a.append(a.pop(0))
    if len(b) > 1: b.append(b.pop(0))
    return a, b, result
def rra(a, b, result):
    if len(a) > 1: a.insert(0, a.pop()); result.append('rra')
    return a, b, result
def rrb(a, b, result):
    if len(b) > 1: b.insert(0, b.pop()); result.append('rrb')
    return a, b, result
def rrr(a, b, result):
    if len(a) > 1 or len(b) > 1:
        result.append('rrr')
    if len(a) > 1: a.insert(0, a.pop())
    if len(b) > 1: b.insert(0, b.pop())
    return a, b, result

# 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("pila A:", a)
    print("pila B:", b)
    return pasosA

def necesariosB(a, b):    # código nuevo: buscando el hueco
    arr_target = [None] * len(a)
    for i in range(len(a)):
        if a[i] < min(b) or a[i] > max(b):
            target = max(b); arr_target[i] = target
        else:
            for j in range(len(b)-1):
                if a[i] < b[j] and a[i] > b[j+1]:
                    target = b[j+1]; arr_target[i] = target
                elif a[i] < b[-1] and a[i] > b[0]:
                    target = b[0]; arr_target[i] = target
        # en este momento ya tenermos el target completamente calculado
        # ahora toca calcular pasosB
        if b.index(target) < len(b)/2:
            pasosB.append(b.index(target))
        else:
            pasosB.append(-(len(b)- b.index(target)))
    return pasosB, arr_target


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
    return 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 = []
    pasosA = necesariosA(a, b)
    pasosoB, arr_target = necesariosB(a, b)
    total = totaliza(a, b)
    print("target:", arr_target)
    print("pasosA:", pasosA)
    print("pasosB:", pasosB)
    print("total: ", total)
    print()
    return total.index(min(total))   # retorna el índice del elemento de la pila A que menos pasos totales necesita

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

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

# girando pilas A y B
def giraPilas(a, b, indice, result):   # 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. Estoy en el caso de que pasosA y pasosB tienen el mimso signo
        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, result)
            elif pasosA[indice] < 0: # si el signo de ambos es negativo
                rrr(a, b, result)
        exceso_pasosA = abs(pasosA[indice]) - pasos_comunes
        exceso_pasosB = abs(pasosB[indice]) - pasos_comunes
        giraA(a, b, ((pasosA[indice] > 0) - (pasosA[indice] < 0)) * exceso_pasosA, result)    # (a > 0) - (a < 0) da el signo de a
        giraB(a, b, ((pasosB[indice] > 0) - (pasosB[indice] < 0)) * exceso_pasosB, result)   # Python no tiene función sign
    else:   # No existe sinergia
        giraA(a ,b, pasosA[indice], result)   # gira A
        giraB(a, b, pasosB[indice], result)   # gira B

def situarMax_en_B(a, b, result):   # situa el valor máximo de B en la primera posición de B
    indice = b.index(max(b))
    if indice < len(a)/2:
        steps = indice
    else:
        steps = -(len(b)- indice)
    giraB(a, b, steps, result)

def crecientesA(a, b, result):   # situa los tres valores de A en forma creciente estricta: Ejemplo: 17, 45, 82
    if a[0] < a[1] > a[2] and a[0] < a[2]:        # caso: 1 3 2
        ra(a, b, result)
        sa(a, b, result)
        rra(a, b, result)
    elif a[0] > a[1] < a[2] and a[0] < a[2]:        # caso: 2 1 3
        sa(a, b, result)
    elif a[0] < a[1] > a[2] and a[0] > a[2]:        # caso: 2 3 1
        rra(a, b, result)
    elif a[0] > a[1] < a[2] and a[0] > a[2]:        # caso: 3 1 2
        ra(a, b, result)
    elif a[0] > a[1] > a[2]:                        # caso: 3 2 1
        sa(a, b, result)
        rra(a, b, result)
    return                                          # caso: 1 2 3 en este caso no se hace nada pq ya están ordenados

# Después de ordenar los tres elementos de A en orden creciente estricto con la función crecientesA

def cremallera(a, b, result):   # función que va pasando los números de B a A en forma de cremallera, intercalándolos con los que ya hay en A
    aux = [a[-3], a[-2], a[-1]] # creamos un array aux con los tres últimos valores de A
    while len(aux) > 0:         # Mientras aux tenga elementos
        maximo = max(b + aux)   # calcula el maximo entre b y aux
        if maximo in b:         # si el maximo está en B hacer pa
            pa(a, b, result)
        if maximo in aux:       # si el máximo está en aux hacer rra y aux.pop
            print("pila A:", a)
            print("pila B:", b)
            print()
            rra(a, b, result)
            aux.pop()
            print("pila A:", a)
            print("pila B:", b)
            print()
    while len(b) > 0:           # ahora aux está vacío y solo queda hacer pa todo el rato
        pa(a, b, result)

if __name__ == "__main__":
    from random import seed, shuffle
    seed()
    n = 20                             # número de elementos de la pila
    for muestra in range(1):
        a = list(range(1, n+1)); shuffle(a) # generación aleatoria de la pila A
        a = [2, 3, 6, 1, 4, 5]
        a = "47 14 50 68 95 38 87 25 26 62 66 99 8 4 39 16 22 82 18 100 74 41 64 88 45 31 15 92 97 29 76 7 61 42 34 71 9 94 20 98 83 19 1 67 37 12 84 17 44 75 54 23 10 30 52 73 86 70 55 90 80 57 28 27 33 48 24 56 79 96 43 59 32 77 5 11 60 81 46 21 69 13 6 85 51 49 58 2 65 53 40 91 63 3 72 93 35 36 89 78"
        a = [int(num) for num in a.split()]
        b = []
        a_original = a[:]
        print("a_original:", a_original, "\n")
        a_srt = ' '.join(map(str, a_original))
        result = []                         # recoje los pasos dados. Ejemplo: result = ['pb','ra','sa','rra']
        pb(a, b, result); pb(a, b, result)  # pasa de A a B la pareja de elementos de A elegidos a[0], a[1]
        while len(a) > 3:
            index_minimosPasos = calculaIndexPasosMinimos()
            giraPilas(a, b, index_minimosPasos, result)
            pb(a, b, result)         # lo pasa de A a B haciendo pb
        print("Ha finalizado el bucle while\n")
        print("pila A:", a)
        print("pila B:", b)
        print()
        situarMax_en_B(a, b, result) # situa el valor máximo de B en la primera posición de B
        print("Situamos el máximo de B el primero\n")
        print("pila A:", a)
        print("pila B:", b)
        print()
        crecientesA(a, b, result)    # situa los tres últimos valores de A en forma creciente estricta: Ejemplo: 17, 45, 82
        print("Odenamos A de forma creciente\n")
        print("pila A:", a)
        print("pila B:", b)
        print()
        cremallera(a, b, result)     # función que va pasando los números de B a A en forma de cremallera, intercalándolos con los que ya hay en A
        print("Ejecutamos el cremallera\n")
        print("pila A:", a)
        print("pila B:", b)
        print()
        print(len(result))
        print(result)
        largo = len(result)
        #if largo <= 4900 or largo >= 5600:
        print("a_original:", a_srt)
        print(largo, a == sorted(a_original))