Sesión 2: Estructuras de datos lineales

Esta sesión presenta el tipo list de Python que implementa listas indexadas de tamaño dinámico y cuyo contenido puede cambiar (es decir, son mutables). También presenta el tipo tuple que implementa una colección lineal de valores, indexada, pero inmutable. Una ventaja de las listas de Python es que automáticamente ofrecen una implementación del tipo abstracto de datos pila (en inglés stack), una estructura de datos lineal lifo (del inglés last-in first-out). Usando el módulo deque, Python ofrece colas (en inglés queue), una estructura de datos lineal fifo (del inglés first-in first-out). A modo de ejemplo, un provedor de una pistola es lifo mientras que una cola de banco (donde no hay colados ni preferidos) es fifo. Esta sesión también usa una de las características más llamativas de Python: la posibilidad de definir listas por comprensión.

El problema

El problema se encuentra en la arena de programación competitiva UVa y es el siguiente:

514 - Rails

Este problema puede ser formalizado de la siguiente manera:

  • Entrada: una lista de enteros b[0..n) con una permutación del conjunto {1,2,..., n}, con n>0
  • Salida: determinar, bajo las reglas del enunciado, si es posible reorganizar la lista de trenes 1,2,..,n como b.

La notación b[0..n) la usamos para indicar que b es una variable que corresponde a una lista de n elementos indexada desde 0 hasta n-1 (es decir, el primer elemento es b[0] y el último elemento es b[n-1]).

Estrategia de solución

La estrategia de solución es hacer una simulación de la situación descrita en el problema. Identificamos los siguientes tres elementos como parte de la solución:

  • la lista con el orden actual de los vagones en el punto A del riel, la cual llamaremos a (note que esta lista corresponde a los valores 1,2,...,n en ese orden)
  • la lista con el estado actual de los vagones en la estación, la cual llamaremos station; dado que el comportamiento de la estación es lifo, esta lista en realidad será una pila
  • la lista con el orden esperado en B, la cual llamaremos b

La simulación entonces consiste en mover, uno por uno, los trenes de A a la estación. Cada vez que un tren sea ubicado en la estación (recuerden que es una pila), trataremos de moverlo a B. Si el movimiento es posible (es decir, si el tope de la pila es igual al elemento que se espera en b), entonces lo movemos y hacemos lo mismo con cada uno de los elementos al tope de la pila hasta que sea imposible (es decir, cuando la pila sea vacía o su tope no coincida con el siguiente elemento esperado en b). Dado que hemos todos los movimientos posibles cada vez que se mueve un tren de A a la estación, cuando no haya más trenes en A una de dos cosas sucederá: o la estación está vacía o tiene al menos un tren. Si la estación está vacía, entonces fue posible ordenar los trenes como deseábamos; de lo contrario no.

Tutoriales y documentación

En Python, la estructura de datos lineal por defecto son las listas y no los arreglos. Comúnmente, los arreglos son tipos de datos básicos en cualquier lenguaje de programación: permiten almacenar una colección arbitraria de valores, es decir, se comportan como una variable multidimensional (o como un vector en álgebra lineal en un espacio de dimensión arbitraria). Para aquellas personas que alguna vez han programado, no contar con arreglos como un tipo básico suena algo raro. Sin embargo, como veremos en esta sesión, las listas en Python puede usarse como arreglos y, además, su tamaño es dinámico (en contraste con los arreglos que son de tamaño fijo), lo cual es una ventaja.

  1. Visite las secciones 4.1-4.3 de The Python Standard Library para familiarizarse con el tipo Booleano y algunos operadores de comparación lógica.
  2. Visite la documentación del método split en la sección 4.7.1 de The Python Standard Library para familiarizarse con la tokenización de cadenas.
  3. Visite la sección 3.1.3 de The Python Tutorial para familiarizarse con algunos conceptos básicos de listas y la sección 5.1 de The Python Standard Library para profundizar más en ellas.
  4. Visite la sección 5.3 de The Python Standard Library para familirizarse con tuplas y secuencias.
  5. Visite la sección 5.6 de The Python Standard Library para conocer algunas técnicas de iteración sobre listas y estructuras de datos lineales.
  6. Visite la sección 8.3 de The Python Standard Library para conocer una implementación eficiente de colas con la clase deque.

En el modo interactivo de Python, siempre es posible consultar la documentación de los módulos o clases disponibles en el ambiente. Esto se hace ejecutando el comando help(...) con parámetro correspondiente al nombre del módulo o clase de interés. Por ejemplo, para averigüar sobre la documentación del tipo list, basta con ejecutar el siguiente comando en la consola de Python:

>>> help(list)
Help on class list in module builtins:
class list(object)
 |  list() -> new empty list
 |  list(iterable) -> new list initialized from iterable's items
 | 
 |  Methods defined here:
...

Solución

Al igual que con la sesión 1, primero nos ocupamos de cómo capturar los datos de la entrada estándar y cómo los imprimimos a la salida estándar. Es justo decir que la entrada de este problema tiene un formato más elaborada que la del problema anterior.

El algoritmo para leer los datos de entrdada es el siguiente:

  1. capturar en una variable n la cantidad vagones del caso de prueba
  2. mientras que n sea diferente de 0, es decir, mientras no lleguemos al fin de los casos de prueba
    1. construir una tupla a con los valores a=(1,2,...,n)
    2. capturar en una variable l la lista de valores del siguiente renglón (esto lo hacemos tokenizando por espacios la línea de texto leída)
    3. si el primer valor de l no es la cadena '0' es decir, mientras no se acaben las posibles permutaciones sobre las que se quiere averigüar
      1. se convierte l en b
      2. se resuelve el problema para a y b usando la función solve y se imprime de acuerdo al enunciado
      3. capturar en una variable l la lista de valores del siguiente renglón (como en 2.2)
    4. capturar en una variable n la cantidad vagones del caso de prueba (igual que en 1)

Dado que a es una tupla, estamos optando por no modificar nunca el valor del contenido de a. Por el gusto de variar, usaremos a y b como variables globales. Esto nos permite llamar la función solve sin parámetros. Dado que se debe imprimir una línea en blanco entre cada bloque de casos de prueba, se usa una variable Booleana first (es decir, first es una variable cuyos valores son True o False) para determinar si el bloque actual es el primero o no. Si no es el primero, entonces se imprime una línea en blanco; esta variable inicialmente vale True y es asignada el valor False en cada iteración del ciclo.

El código resultante para leer e imprimir es el siguiente:

from sys import stdin
a,b = None,None
def solve():
  global a, b
  ...
def main():
  global a, b
  n = int(stdin.readline())
  first = True
  while n!=0:
    if not(first):
      print()
    first = False
    l = stdin.readline().strip().split()
    a = tuple(i+1 for i in range(n))
    while l[0]!='0':
      b = [ int(x) for x in l ]
      if solve():
        print('Yes')
      else:
        print('No')
      l = stdin.readline().strip().split()
    n = int(stdin.readline())
main()

A mode de sugerencia, no avance de este punto hasta no entender la función main. Recuerde que algunos casos de prueba están en archivos al final de la página. De ser necesario, anote el código con instrucciones print para entender paso a paso cómo se ejecuta.

La solución algorítmica del problema está en la función solve. Además de las variables globales a y b, y de la pila station hay una variable entera idxb. Esta última variable será un índice sobre la lista b. El problema se resuelve en un ciclo de acuerdo con la estrategia descrita inicialmente. Inicialmente idxb es 0 y el ciclo cumple con el siguiente invariante:

ha sido posible organizar los trenes en orden b[0], b[1], ..., b[idxb-1]

Nótese que una vez terminen todas las iteraciones, si idxb es igual a n (es decir, al tamaño de a), entonces se han podido ordenar todos los vagones del tren; de lo contrario no. Esto es equivalente a decir que la estación esté vacía o no, dado que todos los vagones en A pasan a la estación y de la estación a B.

El código resultante para la función solve es el siguiente:

def solve():
  global a, b
  station, idxb = list(),0
  for t in a:
    station.append(t)
    while len(station)>0 and station[-1]==b[idxb]:
      station.pop()
      idxb += 1
  return idxb==len(a) 

Tarea

  1. Para practicar entrada y salida, y listas por compresión, implemente una solución para el problema 11764 - Jumping Mario. Use los archivos mario_test1.in y mario_test1.out para validar su implementación.
  2. En la solución presentada en esta sección, la variable a corresponde a una estructura de datos lineal, en particular, corresponde a una tupla. Sin embargo, para resolver el problema, basta con que a sea una variable de número entero. Modifique la solución del problema presentado en esta sección para que la variable a sea un número entero y no una estructura de datos lineal. Para validar su solución use los archivos rails_test1.in y rails_test1.out.
  3. Usando listas como pilas, implemente una solución para el problema 127 - "Accordian" Patience. Para validar su solución use los archivos patience_test1.in y patience_test1.out.
  4. Usando la estructura de datos deque, implemente una solución para el problema 10935 - Throwing Cards Away I. Para validar su solución use los archivos cards_test1.in y cards_test1.out.