Universidad Técnica Federico Santa María Departamento de Informática Campus Santiago San Joaquín

Tarea 2: Salvando la Navidad. Estructura de Datos, Segundo semestre 2011 20 de Diciembre de 2011 al 4 de Enero de 2012

Profesor:

Diego Arroyuelo ([email protected])

Ayudantes: Alex Arenas ([email protected]) Ignacio Ureta ([email protected])

Objetivos Implementar en C los TAD Pila, Cola y Cola de Prioridad para la resolución de un problema.

Introducción En el polo norte, se encuentra la fábrica de regalos del viejito pascuero, en ella trabajan muchos duendes organizando y clasificando los regalos para que todo salga bien en la próxima navidad. Antiguamente, la selección y clasificación de los regalos se hacía de forma manual, pero ahora poseen un moderno sistema de cintas transportadoras que son operadas por los duendes. El sistema actual consiste de dos cintas transportadoras (colas), una de juguetes y la otra de paquetes. El sistema envuelve cada tipo de regalo con un color de paquete diferente. Actualmente se tienen 3 tipos de regalos muy populares que serán los que se van a distribuir. Además para los niños que se han portado mal y no han hecho correctamente sus tareas, se les ha destinado un pedazo de carbón. Las muñecas deben envolverse en paquetes de color rojo, las pelotas deben envolverse en paquetes de color azul y las tablets en paquetes de color verde. Los pedazos de carbón pueden envolverse con cualquier color.

Tarea 2: Salvando la Navidad (TAD Pila, Cola y Cola de Prioridad) Estructura de Datos, Segundo Semestre 2011

Luego de tener los regalos envueltos, estos pasan por una cinta transportadora central (cola de prioridad) por la que circulan los paquetes ya envueltos. Estos paquetes poseen un código QR el cual indica su contenido. Ahora los paquetes deben ser verificados por uno o más duendes, el cual verifica que el color del paquete corresponda con el juguete que se encuentra dentro de él. La prioridad de verificación es primero los paquetes rojos, luego los azules y por último los verdes. Si el regalo está correctamente envuelto pasa a una de las cinco cintas transportadoras correspondientes a los cinco continentes y luego a sacos (pilas) para su posterior distribución. Si el regalo no está correctamente envuelto es llevado a uno de los 3 sacos de error y posteriormente se vuelven a encolar el paquete y el juguete en su respectiva cinta transportadora. Si el paquete erróneamente envuelto es azul pasa al saco azul, si el paquete erróneamente envuelto es verde pasa al saco verde y si el paquete erróneamente envuelto es rojo pasa al saco rojo. El sistema de selección, empaquetado y clasificación se muestra en la siguiente figura:

En la fábrica trabajan 6 duendes realizando las tareas de verificación de regalos y faltando solo cinco días para navidad el duende más conflictivo de todos, el duende Nachito, decide renunciar porque no está contento con su labor. Sin embargo antes de retirarse empuja accidentalmente a 4 de sus compañeros por el ducto de ventilación, quedando estos envueltos en algunos paquetes, poniendo en peligro la Navidad.

Página 2 de 6

Tarea 2: Salvando la Navidad (TAD Pila, Cola y Cola de Prioridad) Estructura de Datos, Segundo Semestre 2011

Tareas a Realizar 1. Se deben programar en C (en Linux, se compilará en los computadores del LDS con S.O. Fedora 16) las principales funciones para los TAD Pila, Cola y Cola de Prioridad (como mínimo para pilas: apilar, desapilar, esVacio; como mínimo para colas: encolar, desencolar, esVacio). 2. Se deberán usar las funciones programadas en el punto anterior para simular la fábrica en donde trabajan los duendes. El programa deberá recibir un archivo llamado Entrada.txt con el Nombre, Continente y Regalo de cada niño que será visitado esta navidad. El formato del archivo Entrada.txt es el siguiente: Juanito Perez America Carbon Akira Tanaka Asia Tablet … Pepe Gonzalez America Tablet Cada 3 líneas aparece un niño con su respectivo nombre, continente y regalo. El programa deberá leer el archivo Entrada.txt y cargar su contenido en la cola de juguetes. Además deberá contabilizar cuantos paquetes de cada color se necesitarán para envolver los regalos. La cola de paquetes vacíos deberá ser llenada aleatoriamente con la cantidad exacta de paquetes según los contadores obtenidos. Además, se deben incluir aleatoriamente en la cola de juguetes los 4 duendes que cayeron por el ducto de ventilación. 3. Una vez que se tengan las colas de juguetes y regalos llenas según el punto anterior, se desencolarán uno a uno los elementos de ambas colas y se procederá a envolver los regalos con un elemento de cada cola. Por ejemplo, si de la cola de juguetes sale un duende, y de la cola de paquetes sale un paquete rojo, el resultado será un duende envuelto en un paquete rojo. Cada vez que un paquete sea envuelto deberá ser enviado a la cinta transportadora central (cola de prioridad). Este proceso deberá repetirse hasta que se acaben los paquetes vacíos (recordar que hay 4 elementos de más en la cola de juguetes).

Página 3 de 6

Tarea 2: Salvando la Navidad (TAD Pila, Cola y Cola de Prioridad) Estructura de Datos, Segundo Semestre 2011

4. Una vez que se haya terminado con el proceso anterior, se deberá procesar la cinta transportadora central (cola de prioridad) teniendo en cuenta que la prioridad de verificación es paquetes rojos por sobre paquetes azules y paquetes azules por sobre paquetes verdes. Para la verificación se cuenta inicialmente con un solo duende (eran seis al principio, pero Nachito renunció y empujó a otros cuatro duendes a la máquina empaquetadora). La tarea de este duende es leer el código del paquete para investigar su contenido: a) Si el contenido del regalo corresponde con el color del paquete, deberá llevar el regalo a una de las siguientes cintas según el continente de destino. b) Si el contenido del regalo no corresponde con el color del paquete, deberá apilarlo en uno de los sacos destinados para errores de envoltura. c) Si el contenido del regalo es un duende, deberá liberarlo inmediatamente para que lo ayude a trabajar y el paquete deberá ser reencolado en la cinta transportadora de paquetes vacíos. Los tiempos promedio de verificación según cantidad de duendes que se encuentren trabajando son Cantidad de Duendes

Tiempo

1 2 3 4 5

10 segundos en verificar 1 regalo 10 segundos en verificar 2 regalos 10 segundos en verificar 3 regalos 10 segundos en verificar 4 regalos 10 segundos en verificar 5 regalos

5. Cuando se acaben los regalos de la cinta transportadora central, se deberán reencolar los paquetes erróneamente envueltos en las cintas transportadoras de juguetes y paquetes vacíos separando el contenido de la envoltura. Luego se deberá repetir desde el punto 3 en adelante. 6. Cuando se terminen de clasificar todos los regalos por continente (esto significa que todos los juguetes han sido envueltos adecuadamente y además que los cinco duendes fueron liberados de su prisión de papel de regalo) se deberá dar inicio al procesamiento de las cintas transportadoras continentales, las cuales deberán apilar los regalos en las bolsas para prepararlas para su distribución por todo el mundo.

Página 4 de 6

Tarea 2: Salvando la Navidad (TAD Pila, Cola y Cola de Prioridad) Estructura de Datos, Segundo Semestre 2011

7. Finalmente, el programa deberá generar 6 archivos. El archivo Registro.txt con la información de la verificación de los regalos. Se deberá indicar cada verificación y su situación final y además debe contener el tiempo total que demoró el proceso de empaque en minutos y segundos. El formato del archivo Registro.txt es el siguiente: Duendes trabajando: 1 Tiempo: 0 segundos. Verificando regalo… Muñeca en Verificando regalo… Duende en Duendes trabajando: 2 Tiempo: 20 segundos. Verificando regalo… Carbon en … Operacion terminada! Tiempo empleado: 20 minutos y

paquete verde... Incorrecto. paquete azul… Liberar!

paquete rojo… Correcto.

50 segundos.

Además se deberán generar 5 archivos correspondientes a los 5 sacos de los distintos continentes con los nombres de los niños que serán visitados. Los archivos deberán llamarse America.txt, Europa.txt, Asia.txt, Africa.txt y Oceania.txt. El formato de los archivos es el siguiente (ejemplo America.txt): AMERICA Juanito Perez Pepe Gonzalez Para el resto de los archivos solo cambia el titulo. Los nombres deben obtenerse desapilando el contenido de los sacos.

Página 5 de 6

Tarea 2: Salvando la Navidad (TAD Pila, Cola y Cola de Prioridad) Estructura de Datos, Segundo Semestre 2011

Entrega La tarea debe entregarse vía correo electrónico al mail del ayudante [email protected] con el asunto “[EDD] Tarea 2 Grupo X” (sin las comillas y reemplazando X por su número de grupo). La tarea debe enviarse comprimida en un archivo TAR.GZ llamado GrupoX.tar.gz (reemplazando X por su número de grupo) que debe contener: -

El archivo compilable. (tarea2.c) Nombre, ROL y que programó cada alumno. (nombres.txt) Indicaciones de compilación de ser necesarias. (README.txt) Archivo de entrada inventado por los integrantes del grupo con al menos veinte niños con su respectivo continente y regalo. (Entrada.txt)

El plazo máximo para la entrega de esta tarea es el día miércoles 4 de enero de 2012 hasta las 23:59:59 hrs. Se descontarán 30 puntos por cada día de retraso o fracción.

Restricciones y Consideraciones Las tareas deben compilar en los computadores que se encuentran en el LDS (Fedora 16). Si la tarea no compila, no será revisada. La tarea será compilada con el comando gcc –Wall tarea2.c –o salida Por cada Warning en la compilación se descontarán 5 puntos. La tarea debe funcionar al menos con el archivo Entrada.txt proporcionado por cada grupo. Se debe respetar la integridad de los TAD Pila, Cola y Cola de prioridad, accesos inmediatos a las estructuras se considerará como una violación grave del TAD y será evaluado con nota cero. Se deben respetar al pie de la letra los formatos de los archivos Entrada.txt, Registro.txt, America.txt, Europa.txt, Asia.txt, Africa.txt y Oceania.txt y formatos de entrega especificados en este enunciado. La tarea debe enviarse desde un correo electrónico institucional, @alumnos.usm.cl o @alumnos.inf.utfsm.cl. Si se detecta Copia, la tarea será evaluada con nota cero. Tareas que no cumplan con alguna de estas restricciones arriesgan descuentos e incluso la no revisión. Página 6 de 6