Laboratorios

Laboratorio 14: Maratón de Grafos

posted May 3, 2013, 10:10 AM by Camilo Rocha

El objetivo de este laboratorio es implementar algunos algorítmos de grafos estudiados en el curso.

Este laboratorio usará como enunciado el documento adjunto, en donde se encontrarán 3 problemas de maratón de programación. La reglas del laboratorio son las siguientes:
  1. Cada solución debe usar la implementación del tipo abstracto de datos Graph, bien sea la implementación hecha por cada uno de Ustedes o la publicada en la página del curso.
  2. Cada estudiante deberá resolver, al menos, los problemas A y B.
  3. El problema C es un bono.
Se entiende que cada problema debe resolverse bajo las condiciones y restricciones establecidas en el enunciado.

El laboratorio es individual y cada estudiante debe entregar:
  • El código impreso de las soluciones, SIN incluír el código de la clase Graph
  • El encabezado del archivo debe indicar, usando comentarios de Python,
    • Su nombre en la primera línea
    • Su código de estudiante en la segunda línea

Laboratorio 13: El problema de las 8 reinas

posted Apr 26, 2013, 11:04 AM by Camilo Rocha

El objetivo de este laboratorio es implementar soluciones por reintento al problema de las 8 reinas (ver Wikipedia).

En este laboratorio, un tablero de ajedréz se entenderá como una matriz con 8 filas y 8 columnas (indexadas desde 0). La ubicación de las reinas en un tablero se codificará con un arraglo de enteros de 8 posiciones, cuyos valores están en el conjunto {0,1,2,3,4,5,6,7} u {-1}, de tal manera que si un arreglo b es una codificación de la ubicación de las reinas, tenenmos que para cualquier 0 <= i < 8:
  • si b[i] es -1, entonces no hay reina en la fila i
  • si b[i] no es -1, entonces hay una reina en la fila i y en la columna b[i]
  1. Dibuje los tableros correspondientes a
    • [5, 3, 6, 0, 2, 4, 1, 7]
    • [1, -1, 2, -1, 7, -1, 0, 3]
    • [-1,-1,-1,-1,-1,-1,-1,-1]
El laboratorio es individual y, con base en la plantilla suministrada, cada estudiante debe entregar:
  • El código impreso del archivo queens.py completo, con la implementación de los métodos
    • find_one_solution
    • find_all_solutions
  • El encabezado del archivo debe indicar, usando comentarios de Python,
    • Su nombre en la primera línea
    • Su código de estudiante en la segunda línea

Laboratorio 12: Grafos con listas de adyacencia

posted Apr 19, 2013, 6:17 AM by Camilo Rocha   [ updated Apr 19, 2013, 6:43 AM ]

El objetivo de este laboratorio es implementar, finalmente, la estructura de datos Graph para representar grafos dirigidos. La implementción usa una lista de listas como representación interna, en donde cada lista que representa arcos está ordenada ascendentemente. Para implementar la estructura de datos Graph, cada estudiante deberá completar una plantilla con la implementación de algunas funciones que serán probadas con algunos casos de prueba.

A continuación encuentran la especificación de la clase Graph que deben completar:

NAME
    Graph

CLASSES
    builtins.object
        Graph
   
    class Graph(builtins.object)
     |  This class models a graph with a bounded number of vertexes, where
     |  each vertex is represented as a natural number indexed from 0 and
     |  where edges are represented by tuples of arbitrary length. The
     |  convention for edges is that, given a source vertex, the first
     |  component of the tuple representing such an edge corresponds to the
     |  target of the vertex. The remaining components of such a tuple can
     |  be used to store, for instance, the weight of the edge, a label, etc.
     | 
     |  Methods defined here:
     | 
     |  __eq__(self, other)
     |      Return if another object is equal to this object.
     | 
     |  __init__(self, v_count)
     |      This is the constructor of the class. Initially, a graph
     |      has no edges.
     | 
     |  __str__(self)
     |      Return the string representation of the graph.
     | 
     |  add_edge(self, s, t)
     |      Add an edge with source s and target t[0], if not such an edge exists.
     |      Otherwise a ValueError exception is thrown. The argument t must be a tuple.
     |      The values s and t are such that 0 <= s,t[0] < get_vertex_count().
     | 
     |  get_adj_count(self, s)
     |      Return the number of edges with source s, where 0 <= s < get_vertex_count().
     | 
     |  get_edge_at_index(self, s, i)
     |      Return the edge with source s at position i, if any; otherwise throw
     |      a ValueError exception. The values s and i is such that 0 <= s < get_vertex_count()
     |      and 0 <= i < get_adj_count(s).
     | 
     |  get_edge_count(self)
     |      Return the number of edges in the graph.
     | 
     |  get_vertex_count(self)
     |      Return the number of vertexes in the graph.
     | 
     |  has_edge(self, s, t)
     |      Return True if there is an edge from source s to target t; False otherwise.
     |      The values s and t are such that 0 <= s,t < get_vertex_count().
     | 
     |  remove_edge(self, s, t)
     |      Remove the edge with source s and target t if it exists, otherwise
     |      a ValueError exception is thrown.  The values s and t are such
     |      that 0 <= s,t[0] < get_vertex_count().
     | 
     |  update_edge(self, s, t)
     |      Update the edge with source s and target t[0], if such an edge exists.
     |      Otherwise a ValueError exception is thrown. The argument t must be a tuple.
     |      The values s and t are such that 0 <= s,t[0] < get_vertex_count().

Para la implementación, tengan especial cuidado al trabajar con los arcos: identifiquen cuándo un método recibe/retorna un vértice o una tupla (al referirse a un arco).

A continuación encuentran una sesión interactiva con una implementación de la clase Graph:

>>> a = Graph(5)
>>> print(a)
0 -> []
1 -> []
2 -> []
3 -> []
4 -> []
>>> a.add_edge(1,(3,4))
>>> a.add_edge(1,(2,5))
>>> a.add_edge(1,(4,2))
>>> print(a)
0 -> []
1 -> [(2, 5), (3, 4), (4, 2)]
2 -> []
3 -> []
4 -> []
>>> a.has_edge(1,2)
True
>>> a.has_edge(1,0)
False
>>> a.get_vertex_count()
5
>>> a.get_edge_count()
3
>>> a.get_adj_count(1)
3
>>> a.get_adj_count(3)
0
>>> a.get_edge_at_index(1,1)
(3, 4)
>>> a.get_edge_at_index(3,1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "pimo/Graph.py", line 170, in get_edge_at_index
    assert 0 <= i < self.get_adj_count(s)
AssertionError
>>> a.add_edge(3,(5,1))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "pimo/Graph.py", line 104, in add_edge
    assert 0 <= t[0] < self.get_vertex_count()
AssertionError
>>> a.remove_edge(1,2)
>>> a.get_edge_count()
2
>>> print(a)
0 -> []
1 -> [(3, 4), (4, 2)]
2 -> []
3 -> []
4 -> []
>>> a.update_edge(1,(4,6))
>>> print(a)
0 -> []
1 -> [(3, 4), (4, 6)]
2 -> []
3 -> []
4 -> []
>>> a.update_edge(1,(2,4))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "pimo/Graph.py", line 152, in update_edge
    raise ValueError("There is no edge from {0} to {1} to update.".format(str(s),str(t[0])))
ValueError: There is no edge from 1 to 2 to update.
>>>

El laboratorio es individual y cada estudiante debe entregar:
  • El código impreso del archivo pimo/Graph.py completo, con la implementación de todos los métodos.
  • El código impreso del archivo Graph.test.py que implementa al menos 5 pruebas para cada método público de la clase Graph. Además, se debe adjuntar el código impreso de la ejecución de las pruebas.
  • El encabezado de cada archivo debe indicar, usando comentarios de Python,
    • Su nombre en la primera línea
    • Su código de estudiante en la segunda línea

Laboratorio 11: Árboles binarios balanceados (opcional)

posted Apr 19, 2013, 6:06 AM by Camilo Rocha

Pedir cita.

Laboratorio 10: Árboles binarios etiquetados

posted Apr 6, 2013, 3:24 PM by Camilo Rocha

Un árbol binario es una estructura de datos jerárquica. En este laboratorio se explorará una implementación de árboles binarios en Python y se implementarán tres recorridos sobre ellos: preorden, inorden y posorden. Para ello, cada estudiante debe examinar los archivos adjuntos:
  • pimo/BinTree.py: implementación incompleta de los árboles binarios
  • BinTree.test.py: cascarón con las pruebas para los árboles binarios
El laboratorio es individual y cada estudiante debe entregar:
  • El código impreso de las versiones completas de
    • 'pimo/BinTree.py' con todos los métodos implementados (los métodos que deben implementar tienen como cuerpo la instrucción pass)
    • 'BinTree.test.py' con pruebas para cada uno de los métodos del árbol binario
      • Para cada método son necesarias al menos 5 pruebas diferentes
    • El encabezado de cada uno de los archivos debe indicar, usando comentarios de Python,
      • Su nombre en la primera línea
      • Su código de estudiante en la segunda línea
  • El resultado impreso de ejectuar las pruebas para cada uno de los métodos de la estructura de datos.

Laboratorio 8: Listas de adyacencia

posted Mar 15, 2013, 10:02 AM by Camilo Rocha   [ updated Mar 19, 2013, 6:11 PM ]

Una lista de adyacencia es una estructura de datos bidimensional que permite búsquedas e inserciones eficientes y, a su vez, es óptima en el uso de memoria. Uno de sus principales usos es en la representación de relaciones binarias (o grafos) y la representación de listas con prioridad.

En particular, la estructura de datos lista de adyacencia ofrece las siguientes operaciones:
  • init(): crea una lista de adyacencia vacia (complejidad temporal O(1))
  • eq(other): determina si la lista de adyacencia es igual a other (complejidad temporal O(n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • str(): representación en cadena de la lista de adyacencia (complejidad temporal O(n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • insert(x,y): inserta el elemento y con prioridad x (complejidad temporal O(log2 n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • contains(x,y): retorna True si el elemento y con prioridad x está en la lista de adyacencia; False de lo contrario (complejidad temporal O(log2 n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • remove(x,y): elimina el elemento y con prioridad x de la lista de adyacencia, si este existe (complejidad temporal O(log2 n), en donde n es la cantidad de elementos en la lista de adyacencia)
Dadas las restricciones en la complejidad temporal para las funciones insert, contains y remove, es imperativo utilizar estructuras de datos ordenadas para poder efectuar búsquedas binarias sobre la lista de adyacencia. En particular, representaremos internamente una lista de adyacencia como una lista encadenada lista de Python (list()) de listas encadenadas listas de Python, en donde cada una de las listas está ordenada ascendentemente. Asumiremos que los elementos almacenados en una lista de adyacencia serán números enteros y que la prioridad también es un número entero.

Por ejemplo, el siguiente esquema brinda una representación gráfica de una lista de adyacencia que contiene los elementos (1,2),(3,5),(1,0),(8,7),(6,4),(6,100),(1,0):

1 -> [0,2]
|
v
3 -> [5]
|
v
6 -> [4,100]
|
v
8 -> [7]

Note que tanto las prioridades (1,3,6,8) como los valores asociados a cada una de ellas están ordenados ascendentemente. Además note que ninguna pareja está repetida!

En internet existen muchas fuentes de información sobre el algorítmo de búsqueda binaria para para estructuras lineales y ordenadas (es más, este algoritmo fue parte del primer quiz del semestre ... recuerdan?). En particular, pueden consultar las siguientes páginas para repasar el tema:
El laboratorio es individual y cada estudiante debe entregar:
  • El código impreso del laboratorio en un archivo llamado 'AdjList.py'; siga las convenciones de Python para la definición e implementación de los métodos init, eq y str.
    • El encabezado del archivo debe indicar, usando comentarios de Python,
      • Su nombre en la primera línea
      • Su código de estudiante en la segunda línea
  • La estructura de datos debe estar debidamente documentada. Para ello, debe entregar impreso el texto que se obtiene al ejecutar el comando pydoc sobre la estructura de datos definida en AdjList.py.
  • El código impreso de las pruebas hechas para validar la estructura de datos lista de adyacencia; cada método de la estructura de datos debe probarse con al menos 5 casos de prueba diferentes.
  • El resultado impreso de ejectuar las pruebas para cada uno de los métodos de la estructura de datos lista de adyacencia.

Laboratorio 7: Listas Ordenadas

posted Mar 8, 2013, 4:52 AM by Camilo Rocha   [ updated Mar 8, 2013, 4:54 AM ]

El objetivo de este laboratorio es implementar la estructura de datos OrdList para representar listas ordenadas de números. Para ello, cada estudiante deberá completar una plantilla con la implementación de algunas funciones que serán probadas con algunos casos de prueba.

El archivo 2013-1-pimo-lab7.tar.gz contiene los archivos y plantillas del laboratorio. Una vez bajado y estando en el directorio en donde se encuentra este archivo, este archivo se puede descomprimir con el siguiente comando, que generará el directorio lab7:

tar zxvf 2013-1-pimo-lab7.tar.gz

El directorio lab7 contiene los siguientes archivos:
  • OrdList.test.py: conjunto de pruebas para la implementación de listas ordenadas
  • pimo/OrdList.py: plantilla para la implementación de listas ordenadas
  • pimo/__init__.py: descriptor del paquete pimo (ver acá para más detalles)
Cada estudiante debe modificar únicamente el contenido del archivo pimo/OrdList.py con la implementación de las funciones que no han sido implementadas aún (aquellas con la instrucción pass).

El conjunto de pruebas en el archivo OrdList.test.py se suministra para validar que la implementación de las listas ordenadas es potencialmente correcta. Para ejecutar las pruebas, basta con estar en el directorio lab7 y ejecutar el siguiente comando:

python3 OrdList.test.py

Inicialmente, ejecutar el comando anterior genera los siguientes resultados, que indican que algunas pruebas son satisfactorias (True) mientras que otras no lo son (False):

Test init(01): True
Test insert(01): True
Test insert(02): False
Test empty(01): None
Test empty(02): True
Test empty(03): True
Test empty(04): None
Test count(01): False
Test count(02): False
Test count(03): False
Test count(04): False
Test count(05): False
Test remove(01): False
Test remove(02): True
Test remove(03): True
Test remove(04): True
Test remove(05): False
Test pop(01): True
Test pop(02): False
Test pop(03): False
Test pop(04): True
Test index(01): False
Test index(02): False
Test index(03): False
Test index(04): False
Test extend(01): True
Test extend(02): False
Test purge(01): True
Test purge(02): False
Test purge(03): True
Test purge(04): False

Una vez implementadas las funciones de la lista ordenada, ejectuar el comando anterior debería arrojar los siguientes resultados, indicando que todas las pruebas son satisfactorias:

Test init(01): True
Test insert(01): True
Test insert(02): True
Test empty(01): True
Test empty(02): True
Test empty(03): True
Test empty(04): True
Test count(01): True
Test count(02): True
Test count(03): True
Test count(04): True
Test count(05): True
Test remove(01): True
Test remove(02): True
Test remove(03): True
Test remove(04): True
Test remove(05): True
Test pop(01): True
Test pop(02): True
Test pop(03): True
Test pop(04): True
Test index(01): True
Test index(02): True
Test index(03): True
Test index(04): True
Test extend(01): True
Test extend(02): True
Test purge(01): True
Test purge(02): True
Test purge(03): True
Test purge(04): True

Es importante que cada estudiante se familiarice con las pruebas de las funciones, especialmente con el manejo de errores y excepciones (ver acá). Note que el manejo de errores y/o excepciones es fundamental para probar funciones, como pop y remove, que pueden arrojar errores en algunos casos.

El laboratorio es individual y cada estudiante debe entregar:
  • El código impreso del archivo pimo/OrdList.py
    • El archivo debe ser compatible con Python 3
    • El archivo debe contener una implementación de listas ordenadas para la cual las pruebas son todas satisfactorias.
    • El encabezado del archivo debe indicar, usando comentarios de Python,
      • Su nombre en la primera línea
      • Su código de estudiante en la segunda línea

Laboratorio 6: "Paint Me and Reverse Nonogram"

posted Mar 1, 2013, 10:14 AM by Camilo Rocha   [ updated Mar 6, 2013, 8:25 PM ]

El objetivo de este laboratorio es implementar en el lenguaje de programación Python 3 una solución a dos problemas de maratón de programación. Para ello, el estudiante deberá modificar unas plantillas dadas que implementan la entrada de los problemas en cada uno de sus formatos, y entregar una solución para cada uno de los problemas asignados.

Siguiendo la plantilla, identifique:
  1. La función main(); esta función se encarga de leer la entrada del problema y procesarla; para cada instancia del problema llama la función init() con los parámetros dados
  2. La función solve(...); esta función se invoca para cada instancia del problema definida por los casos de prueba y sus parámetros dependen de cada problema. Inicialmente esta función está vacia.
Una vez familiarizados con el código de la plantilla :
  1. Implemente la función solve(...) con los parámetros dados en cada una de las plantillas, para cada uno de los siguientes problemas:
    • E - Paint Me
    • G - Reverse Nonogram
  2. Pruebe que su solución funciona con los datos de prueba suministrados en el enunciado.
El laboratorio es individual y la instrucciones para la entrega son las siguientes:
  1. Para cada problema se ha suministrado un archivo de pruebas (con extensión .in)
  2. Para cada solución (es decir, para paintme.py y nonogram.py) genere un archivo con las respuestas a los casos de prueba. Por ejemplo, para el problema E - Paint Me, ejecute el siguiente comando suponiendo que la solución paintme.py y los casos de prueba paintme.in están en el mismo directorio:
    • (python3 paintme.py < paintme.in) > paintme.out
  3. Calcule la suma md5 para cada uno de los dos archivos .out generados con las instrucciones anteriores. Por ejemplo, para el problema E - Paint Me, ejecute el siguiente comando:
    • md5sum paintme.out
Ejecutar el último comando, genera una número hexagesimal de 32 dígitos que corresponde a la suma md5 de cada una de las soluciones.

Cada estudiante debe entregar:
  • El código impreso de las dos soluciones
    • El encabezado del archivo debe indicar, usando comentarios de Python,
      • Su nombre en la primera línea
      • Su código de estudiante en la segunda línea
      • La suma md5 de los archivos con las respuestas generadas por las soluciones

Laboratorio 5: "Memory"

posted Feb 15, 2013, 10:13 AM by Camilo Rocha

El objetivo de este laboratorio de final de tercio es evaluar características del lenguaje de programación Python y el ambiente CodeSkulptor. Para ello, el estudiante deberá modificar una versión del juego "Memory" en CodeSkulptor y entregar una versión "más interesante" de este juego.

"Memory" es uno de tantos juegos de cartas. Puede ver sus reglas y algunas variaciones en Wikipedia.

El taller se desarrollará en CodeSkulptor utilizando esta plantilla. Es importante que siga las convenciones e instrucciones allí expuestas.

Siguiendo la plantilla, identifique:
  1. Las constantes y variables globales que allí se encuentran definidas.
  2. La función init(); esta función se invoca cada vez que se inicia una partida del juego.
  3. La función draw(canvas); esta función se invoca aproximadamente 60 veces por segundo y su objetivo es actualizar el estado del juego y de la interfaz gráfica.
  4. Las función keymouseclick(pos); esta función se encargan de registrar los eventos asociados al ratón.
Una vez familiarizados con el código de la plantilla, lleve a cabo los siguientes cambios en la plantilla:
  1. (10 pts) Invertir el uso de los colores azul y naranja.
  2. (10 pts) Actualmente el se juega con 8 pares de cartas, representadas por pares de valores entre 0 y 7, inclusive. Aumente el número de parejas a 10, representando los pares de valores con los números entre 0 y 9, y ajustando coherentemente el tamaño de la ventana en donde se muestra el juego.
  3. (10 pts) Indicar al usuario por medio de un mensaje de advertencia en la consola cada vez que se escoje una carta que ya ha sido 'destapada'.
  4. (10 pts) Registrar la cantidad de escogencias erróneas (es decir, escogencia de cartas ya destapadas) mostrando esa información de una forma similar a como se muestra la información de 'Moves'. Cada vez que se re-inicia el juego, la información de errores inicia a contar desde 0.
  5. (10 pts) Cambiar el tamaño de las cartas de 50x100 pixeles a 60x90 pixeles, ajustando coherentemente el tamaño de la ventana en donde se muestra el juego.
El laboratorio es individual y la instrucciones de entrega se darán durante la sesión.

Laboratorio 4: "The Pong Game"

posted Feb 8, 2013, 12:34 AM by Camilo Rocha   [ updated Feb 8, 2013, 9:57 AM ]

El objetivo de este laboratorio es repasar algunas de las características del lenguaje de programación Python y aprender sobre librerias del lenguaje disponibles a través de CodeSkulptor. Para ello, el estudiante deberá modificar una versión del juego "Pong" en CodeSkulptor y entregar una versión "más interesante" de este juego.

"The Pong Game" es uno de los juegos clásicos de Atari. Puede revisar parte de su historia y también jugar en linea visitando http://www.ponggame.org/.

El taller se desarrollará en CodeSkulptor utilizando esta plantilla. Es importante que siga las convenciones e instrucciones allí expuestas.

Siguiendo la plantilla, identifique:
  1. Las constantes y variables globales que allí se encuentran definidas.
  2. La función init(); esta función se invoca cada vez que se inicia una partida del juego.
  3. La función draw(c); esta función se invoca aproximadamente 60 veces por segundo y su objetivo es actualizar el estado del juego y de la interfaz gráfica. La mayoría de cambios se harán en el cuerpo de esta función.
  4. Las funciones keydown(key) y keyup(key); estas funciones se encargan de registrar los eventos asociados al teclado. En la versión actual del juego las teclas 'w' y 's' controlan la paleta izquierda, mientras que las teclas 'arriba' y 'abajo' la paleta derecha.
Una vez familiarizados con el código de la plantilla, lleve a cabo las siguientes tareas sobre el código en la plantilla:
  1. Cambiar el color de la 'bola' de blanco a amarillo.
  2. Aumentar el tamaño del texto que muestra el marcador del juego a 28 unidades; actualmente el tamaño es 18.
  3. Cada vez que la 'bola' rebota en una pared o en una paleta, su velocidad aumenta un 10%; modifique esta proporción para que aumente 15% en lugar de 10%.
  4. Cambiar los controles de la paleta izquierda para que usen las teclas 'a' (arriba) y 'z' (abajo).
  5. Aumentar la velocidad de las paletas, al menos en un 100%; actualmente son lentas y esto hace el juego algo aburridor.
  6. Actualmente cada vez que se inicia un punto, la bola inicia hacia arriba y en contra de quien ganó el último punto. Cambie esto para que la bola aleatoreamente inicie hacie arriba o hacia abajo, pero manteniendo la regla de que se moverá en contra de quien ganó el último punto.
  7. (Bono) Las paletas no tienen ningún color de relleno. Modifique el código de tal manera que el borde de las paletas sea gris y su relleno blanco.
El laboratorio es individual y cada estudiante debe entregar:
  • El código impreso del laboratorio
    • El código debe ser ejecutable en CodeSkulptor
    • El encabezado del archivo debe indicar, usando comentarios de Python,
      • Su nombre en la primera línea
      • Su código de estudiante en la segunda línea
  • Suministrar, junto con el código impreso, un vínculo a su solución del laboratorio

1-10 of 13