Estructuras de datos no lineales

Esta sesión presenta los tipos abstractos de datos set y dict, que están disponibles con cualquier distribución de Python. El primero de ellos sirve para modelar conjuntos, es decir, colecciones en donde el orden y la cantidad de repeticiones de un elemento son ignorados. El segundo sirve para modelar multiconjuntos, es decir, colecciones en donde el orden es ignorado por no la cantidad de repeticiones de un elemento. Si la cantidad de ocurrencias de un elemento dado es 0, entonces en cualquiera de estas colecciones el elemento no está contenido en ellas. Desde el punto de vista de orden y ocurrencias, una lista modela secuencias de datos en donde el órden y las repeticiones son imporantes. De ninguna manera las únicas estructuras de datos no lineales disponibles en Python son estas dos. Por ejemplo, Python ofrece montones (en inglés heap) con el módulo heapq. Sin embargo, el estudio de otras estructuras no será parte del curso.

El problema

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

11849 - CD

Este problema puede ser formalizado de la siguiente manera:

• Entrada: dos conjuntos de números a y b
• Salida: determinar la cantidad de elementos en la intersección de a y b

Un CD es representado por un número. Las colecciones de CDs son modeladas como conjuntos porque, de acuerdo con el enunciado del problema, ninguno entre Jack o Jill tiene más de una copia por CD.

Estrategia de solución

La estrategia de solución es la siguiente:

• crear un conjunto a con los números de CDs pertenecientes a Jack
• crear un conjunto b con los números de CDs pertenecientes a Jill
• imprimir el tamaño de la intersección de a y b

Cada uno de los conjuntos será creado a medida que se lea la entrada del problema. El tipo set en Python permite determinar la intersección de dos conjuntos; por eso este problema es relativamente sencillo de resolver. A su vez, uno puede pensar que una lista de Booleanos, suficientemente grande, sirviría en lugar de los conjuntos: por ejemplo, si la lista tiene nombre a, podriamos usar la convención a[i]==True si y solo si Jack es dueño del CD i. Sin embargo, esto no es factible dado el tamaño de los datos del problema: ¿qué sucede si un número de CD es 100000000? Es prácticamente imposible, por limitaciones de memoria, que una lista de ese tamaño sea útil (pueda que ni siquiera se pueda crear). Aún si se puede crear, habría que recorrer esta lista para inicializarla a False antes de cada caso de prueba. Entonces no es buena idea.

Tutoriales y documentación

En esta sección usaremos documentación externa para revisar los elementos del lenguaje necesarios para resolver el problema. En particular, visitaremos parte de la sección 3 de The Python Tutorial y practicaremos con material para aprender Python del sitio After Hours Programming.

1. Visite la sección 5.4 de The Python Tutorial para familiarizarse con algunos conceptos básicos de set.
2. Visite la sección 5.5 de The Python Tutorial para familiarizarse con algunos conceptos básicos de dict.
3. Lleve a cabo el tutorial sobre dict en el sitio After Hours Programming (no es necesario registrarse).

Solución

A diferencia de las sesiones anteriores, modelaremos la solución al problema en una sola función. Esto se debe a que, aparte de hacer la entrada de datos, no hay mucho más que hacer.

La solución algorítmica del problema está en la función main presentada a continuación:

from sys import stdin

def main():

  lena,lenb = [ int(x) for x in stdin.readline().strip().split() ]

  while lena>0 or lenb>0:

    a,b = set(),set()

    for i in range(lena):

      a.add(int(stdin.readline()))

    for i in range(lenb):

      b.add(int(stdin.readline()))

    print(len(a.intersection(a, b)))

    lena,lenb = [ int(x) for x in stdin.readline().strip().split() ]

main()