Push Swap método "Modern Times"¶

# FUNCIONES
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

# Generación de la pila A
from random import sample, seed
seed()

def generaPilaA(n):
    return sample(range(1, n+1), n)

def algoritmo_LIS(arr):
    n = len(arr)
    lis = [1]*n
    prev = list(range(n))  # una lista con los index
    
    # Compute optimized LIS values in bottom up manner
    for i in range (1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j]+1
                prev[i] = j

    # Initialize maximum to 0 to get the maximum of all
    # LIS
    maximum = 0
    idx = 0

    # Pick maximum of all LIS values
    for i in range(n):
        if maximum < lis[i]:
            maximum = lis[i]
            idx = i

    seq = [arr[idx]]
    while idx != prev[idx]:
        idx = prev[idx]
        seq.append(arr[idx])

    return list(reversed(seq))

# Llevamos de la pila A hacia la pila B los elementos de la LIS

def rotateLIS(lis):
    global a
    global b
    global contador
    for vlis in lis:
        if a.index(vlis) < len(a)/2:
            for i in range(a.index(vlis)):
                ra(a,b); contador += 1
        else:
            for i in range(len(a)- a.index(vlis)):
                rra(a,b); contador += 1
        pb(a,b); contador += 1

# PASOS NECESARIOS PARA COLOCAR CADA ELEMENTO DE A EN SU SITIO EN B
# PASOS NECESARIOS = Pasos necesarios A + Pasos necesarios B

# Pasos necesarios para situarse como el primer elemento de la pila A

def necesariosA(a, b):   # rellena el array pasosA con todos los pasos necesarios para la pila A
    for i in a:
        if a.index(i) < len(a)/2:
            pasosA.append(a.index(i))
        else:
            pasosA.append(-(len(a)- a.index(i)))

def necesariosB(a,b):   # rellena el array pasosB con todos los pasos necesarios para la pila B
    for v in a:
        try:
            objetivo_primero = max([x for x in b if x<v])
        except:
            objetivo_primero = max(b)   # objetivo_primero calcula el número que se ha de poner en la primera posición de B

        if b.index(objetivo_primero) < len(b)/2:
            pasosB.append(b.index(objetivo_primero))
        else:
            pasosB.append(-(len(b)- b.index(objetivo_primero)))

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
            total.append(abs(pasosA[i]) + abs(pasosB[i]))
        else:
            total.append(max(abs(pasosA[i]), abs(pasosB[i])))

def calculaIndexPasosMinimos():
    global pasosA
    global pasosB
    global 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):
    global contador
    for i in range(abs(pasos)):
        if pasos > 0:
            ra(a,b); contador += 1
        elif pasos < 0:
            rra(a,b); contador += 1

def giraB(a, b, indice, pasos):
    global contador
    for i in range(abs(pasos)):
        if pasos > 0:
            rb(a,b); contador += 1
        elif pasos < 0:
            rrb(a,b); contador += 1

# 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
    global contador
    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); contador += 1
            elif pasosA[indice] < 0: # si el signo de ambos es negativo
                rrr(a,b); contador += 1
        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():
    global contador
    for _ in range(len(b)):
        pa(a,b); contador += 1