Fuga en la tubería

1. Descripción general

En 1989 la compañía británica The Assembly Line desarrolló el video juego Pipe Mania para la plataforma Amiga. Posteriormente fue distribuido a otras plataformas con el nombre de Pipe Dream. El juego inspiró a otros desarrolladores y se ha producido una cantidad numerosa de adaptaciones. Todas ellas comparten el mismo principio. El jugador debe construir o reconstruir una tubería por donde pasará un fluido, usualmente agua. La tubería se construye sobre un área matricial, donde el fluido surge de una o más fuentes y debe llegar a uno o más destinos. El jugador pasará al siguiente nivel si el camino construido logra transportar el fluido desde las fuentes hasta los destinos sin fugas.

Figura 1. Sesión en progreso del juego (nivel 001)

Por ejemplo, arriba se puede ver un nivel en progreso, donde el fluido surgirá de las válvulas al norte de la celda (1,1) y al este de la celda (1,4), y deberá llegar a través de la tubería al desagüe al sur de la celda (2,4). Sin embargo, el camino construido en la figura producirá dos fugas, una al sur de la celda (1,2) y otra al sur de la celda (2,2).

Por su estructura matricial, las celdas sólo pueden tener conectores en sus cuatro bordes, que en sentido antihorario son: superior (N=norte), izquierdo (W=oeste), inferior (S=sur), y derecho (E=este). Esta restricción limita la cantidad de piezas que el jugador dispone para construir las 16 tuberías listadas en la Tabla 1.

Tabla 1. Los 16 tipos de tubos
Dec	Hex	Fig
0	0
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
10	A
11	B
12	C
13	D
14	E
15	F

Supóngase que un cliente suyo necesita un eficiente software de computadora que trabaje con niveles en progreso del juego Fuga en la tubería. Se requiere un programa validador que reciba el estado de un juego en progreso por la entrada estándar o en archivos e indique si hay o no fugas en él.

El contenido en la entrada estandar o en los archivos podría ser de texto o binario, por eso además de validar, se quiere que también sea capaz de convertir el nivel que recibe de acuerdo a la elección del usuario entre los formatos de texto y binario.

El software debe tener claramente separada su funcionalidad, de tal forma que será usada en el futuro por una implementación del videojuego con interfaz gráfica. Por esto entregue a su cliente la funcionalidad reutilizable en una biblioteca de software, separada del programa validador en línea de comandos.

2. Validar un nivel

Validar un nivel consiste en reportar adónde se encuentran las fugas dentro de una tubería dada. El programa debe validar cuando la acción validate es indicada en el primer argumento en la línea de comandos, como es el caso del ejemplo de invocación 1.

Ejemplo de invocación 1:

pipeleak validate -it

Ejemplo de entrada 1:

Ejemplo de salida 1:

leak 1 2 S
leak 2 2 S

El ejemplo de entrada 1 corresponde al nivel de la Figura 1. Este ejemplo usa una entrada de texto (más adelante se provee una entrada binaria de ejemplo). El programa debe interpretar la entrada como textual si se le provee el argumento -it. Este argumento se considera por defecto, y por tanto, el usuario podría omitirlo. Si en los argumentos de línea de comandos no se provee un nombre de archivo, el programa debe suponer que el estado del juego será provisto en la entrada estándar, como ocurre en el ejemplo de entrada 1.

La primera línea de la entrada textual recibirá cuatro números. Los dos primeros indican las dimensiones de la matriz en filas y columnas. El tercer y cuarto número indican la cantidad de fuentes de agua (hidrantes) y de destinos (desagües) respectivamente que tiene el nivel.

Tras la primera línea de la entrada textual, vendrá una línea en blanco, seguida por las ubicaciones de cada una de las fuentes de agua (hidrantes) y los destinos (desagües). La ubicación se indica con el número de fila y columna de una celda (iniciando en 1) y el punto cardinal hacia el que se encuentra el hidrante o desagüe. En el ejemplo anterior se tienen:

dos fuentes de agua: al norte de la celda (1,1) y al este de la celda (1,4)
un destino al sur de la celda (2,4).

Suponga que las fuentes y destinos siempre se encuentran en el borde del nivel (el borde de la matriz). En caso de que esto no ocurra, se debe imprimir un mensaje error: invalid hydrant (row, col) o error: invalid drain (row, col) en el error estándar para advertir al equipo de desarrollo de que el nivel debe corregirse.

Finalmente, después de otra línea en blanco, la entrada tendrá el estado de la matriz que se quiere evaluar. Por cada celda se indica el código hexadecimal correspondiente al estado de la celda de acuerdo a la tabla Tabla 1.

El programa debe evaluar la tubería e indicar en el archivo de salida escogido si hay fugas o no. Por cada fuga detectada se debe reportar una línea en formato leak R C D, donde R es la fila, C la columna, y D la dirección o punto cardinal de la celda donde se produce la fuga. Esta información es útil para que el futuro videojuego realice animaciones de fuga o llame la atención del jugador. Si el archivo de salida es binario, se debe reportar cada fuga como dos enteros de 4 bytes sin signo, uno para la fila y otro para la columna, seguido de un byte con la dirección (ver más adelante).

En caso de que no hayan fugas, el programa debe reportar el mensaje solved que indica que la tubería logra transportar el fluido desde las fuentes a los destinos sin fugas. En caso de que la salida sea binaria y no hayan fugas, esta será vacía.

Su programa debe defenderse de entradas incorrectas o mal intencionadas reportando el mensaje error: invalid data en el error estándar y terminar su ejecución, sin producir datos en la salida estándar o archivos de texto o binarios.

3. Conversión texto/binario

Para el futuro videojuego, los niveles se representarán en binario, ya que ahorra memoria, hace al videojuego más rápido incluso con niveles muy grandes, y sobre todo, dificulta a jugadores(as) escudriñar los niveles para adulterarlos o resolverlos haciendo trampa. Sin embargo, los niveles textuales también son útiles para facilitar al equipo de desarrollo la creación y el prueba de los niveles para el juego final. Por esto, se requiere que su software pueda convertir niveles de binario a texto y viceversa.

El programa debe convertir cuando se provee la acción convert en el primer argumento de línea de comandos. El formato de los niveles se controla con los argumentos -i[b|t] [file] para la entrada y -o[b|t] [file] para la salida, donde los corchetes indican opcional, y las barras verticales indican alternancia (uno o el otro, pero no ambos). Se explica a continuación las posibles combinaciones:

Para la entrada:

Si se provee el argumento -it file.txt, el nivel debe leer del archivo de texto indicado por file.txt. Si se provee el argumento -it pero se omite file.txt, se cargará el nivel textual de la entrada estándar.
Si se provee el argumento -ib file.bin, el nivel debe leerse del archivo binario indicado por file.bin. Si se provee el argumento -ib pero se omite file.bin, se leerá el nivel binario de la entrada estándar.
Si se provee el argumento -i filename, el nivel debe leerse del archivo indicado por filename y se inferirá el formato a partir de la extensión del archivo: bin para binario, cualquier otra para texto. Si se provee el argumento -i pero se omite filename, se leerá el nivel textual de la entrada estándar.
Si no se provee ninguno de los anteriores, el nivel se leerá en forma textual de la entrada estándar.

Para la salida:

Si se provee el argumento -ot file.txt, el nivel debe imprimirse en el archivo de texto indicado por file.txt, indiferentemente del formato de la entrada. Si se provee el argumento -ot pero se omite file.txt, se imprimirá el nivel textual en la salida estándar.
Si se provee el argumento -ob file.bin, el nivel debe imprimirse en el archivo binario indicado por file.bin, indiferentemente del formato de la entrada. Si se provee el argumento -ob pero se omite file.bin, se imprimirá el nivel binario en la salida estándar.
Si se provee el argumento -o filename, el nivel debe imprimirse en el archivo indicado por filename que tendrá el mismo formato (textual o binario) que tiene la entrada. Si se provee el argumento -o pero se omite filename, se imprimirá el nivel textual o binaria en la salida estándar.
Si no se provee ninguno de los anteriores, el nivel debe imprimirse en forma textual en la salida estándar.

El siguiente ejemplo muestra una conversión binaria a textual:

Ejemplo de invocación 2:

pipeleak convert -ib level001.bin

Ejemplo de salida 2:

En el ejemplo de invocación 2 se invocó el programa con los argumentos -ib level001.bin que indica al programar cargar el nivel del archivo binario level001.bin y no de la entrada estándar. Cabe indicar que level001/input.bin corresponde al nivel de la Figura 1. Dado que no se puede mostrar el contenido binario original dentro de este enunciado, se incluye a continuación un "volcado" hexadecimal obtenido con el comando od -t x1 level001/input.bin o xxd level001/input.bin.

Volcado de level001/input.bin en hexadecimal:

02 00 00 00 04 00 00 00 02 00 00 00 01 00 00 00
01 00 00 00 01 00 00 00 4e 01 00 00 00 04 00 00
00 45 02 00 00 00 04 00 00 00 53 c7 75 06 d3

En el despliegue hexadecimal, cada dos dígitos corresponden a 1 byte. Un nivel binario es un archivo en little endian cuyos campos corresponden en orden a:

Cantidad de filas (R): entero de 4 bytes sin signo (ej.: 0x02000000 = 2).
Cantidad de columnas (C): entero de 4 bytes sin signo (ej.: 0x04000000 = 4).
Cantidad de fuentes de fluido (S): entero de 4 bytes sin signo (ej.: 0x02000000 = 2).
Cantidad de destinos de fluido (T): entero de 4 bytes sin signo (ej.: 0x01000000 = 1).
S fuentes de fluido, cada uno de 9 bytes (ej.: 01 00 00 00 01 00 00 00 4e y 01 00 00 00 04 00 00 00 45):
1. Fila: entero de 4 bytes sin signo para la fila (ej.: 0x01000000 = 1)
2. Columna: entero de 4 bytes sin signo para la columna (ej.: 0x01000000 = 1)
3. Dirección: punto cardinal, carácter ASCII de 1 byte, con N=norte, W=oeste, S=sur, y E=este (ej.: 0x4e = 78 = 'N').
T destinos de fluido, cada uno de 9 bytes (ej.: 02 00 00 00 04 00 00 00 53):
1. Fila: entero de 4 bytes sin signo para la fila (ej.: 0x02000000 = 2)
2. Columna: entero de 4 bytes sin signo para la columna (ej.: 0x04000000 = 4)
3. Dirección: punto cardinal, carácter ASCII de 1 byte, con N=norte, W=oeste, S=sur, y E=este (ej.: 0x53 = 83 = 'S').
Estados de la matriz: \((R \cdot C + 1) \div 2\) bytes, donde \(\div\) es división entera. Cada byte contiene dos celdas de la matriz. Si la cantidad de celdas es impar, el último byte contendrá en sus 4 bits más significativos el valor de la última celda, y sus 4 bits menos significativos serán bits cero. (ej.: c7 75 06 d3 que corresponden a ocho celdas de la matriz con sus equivalentes piezas en hexadecimal de la Tabla 1).

4. Evaluación

4.1. [5%] Control de versiones

El proyecto será realizado de forma individual en un repositorio de control de versiones. Realice todas las fases del proceso (diseño, programación, documentación, pruebas) y deje evidencia de ellas en el historial de commits.

Por ninguna razón debe agregar archivos binarios a control de cambios o que hayan sido generados a través de un proceso automatizado, por ejemplo, archivos objeto (.o), ejecutables, bibliotecas (.so), documentación generada por Doxygen. En su lugar, provea en la raíz de su repositorio un archivo .gitignore adecuado.

4.2. [5%] Estructura de proyecto

Los archivos del proyecto deben aparecer en una carpeta dentro de su repositorio individual de control de versiones (abreviado con R), a la cual se le llamará la carpeta del proyecto (y abreviada con P). Dentro de la carpeta del proyecto habrá cuatro módulos (subcarpetas):

libpipeleak/: Biblioteca que contiene el código reutilizable (L).
pipeleak/: Comando que usa la biblioteca para validar y convertir niveles del juego (C).
testpipeleak/: Programa de pruebas de la biblioteca de caja blanca (unit testing) (T).
common/: Archivos comunes/compartidos entre los tres módulos anteriores (S).

El contenido de cada uno de los cuatro módulos es la de un proyecto característico en Unix, descrito en la Tabla 2. La columna Módulo indica para cuáles módulos aplica el recurso, usando las letras de los cuatro módulos anteriores.

Tabla 2. Estructura de archivos y directorios por módulo
Recurso	Descripción	Versionado	Módulo
`bin/`	Ejecutables del comando y del programa de pruebas	No	`CT`
`build/`	Código objeto (.o) temporal	No	`CTL`
`doc/`	Documentación generada por Doxygen en formato html	No	`L`
`design/`	Diseño en pseudocódigo	Sí	`CL`
`lib/`	Biblioteca estática (`.a`) o dinámica (`.so`), compartida por el comando y el programa de pruebas	No	`L`
`include/`	Archivos de encabezado (.h) reutilizables de la biblioteca	Sí	`L`
`src/`	Código fuente (.c)	Sí	`CLT`
`tests/`	Casos de prueba propios, creados manualmente	Sí	`C`
`Makefile`	Automatiza compilación, pruebas, extracción de documentación, y limpieza	Sí	`CTLP`
`Doxyfile`	Configura Doxygen para extraer documentación del código fuente	Sí	`L`
`readme.ext`	Documento de análisis, incluye el manual de usuario y de desarrollador	Sí	`P`
`.gitignore`	Ignora los recursos que NO deben estar en control de versiones (columna Versionado)	Sí	`R`

La columna "Versionado" indica si los recursos deben estar o no en control de versiones. Note que NO puede haber redundancia de código entre el comando y el programa de pruebas. El código común debe estar alojado en la biblioteca estática o dinámica de acuerdo a los lineamientos de su docente.

Para crear la estructura de archivos y directorios de este proyecto, puede descargar el script mkproj.sh a la raíz de su repositorio de control de versiones, ejecutarlo, agregar los archivos iniciales a control de versiones, verificar que no se agreguen las carpetas que deben ignorarse a control de versiones, hacer un commit con los archivos iniciales, y finalmente eliminar el script. Los siguientes comandos realizan esta tarea, donde los valores entre <angulares> deben ser reemplazados por sus respectivos valores.

cd <path/to/your/repo>
wget <url/to/mkproj.sh>
bash mkproj.sh
tree project01
git add project01 .gitignore
git status
git commit -m "Project01 directory and file structure"
rm mkproj.sh

Nota: el comando wget permite descargar archivos de internet. El comando tree muestra la estructura de archivos y directorios en forma gráfica. Si no tiene instalados estos comandos, puede usar su administrador de paquetes, por ejemplo, en distribuciones basadas en Debian con con la orden sudo apt install tree wget.

4.3. [10%] Análisis del problema

El producto del análisis del problema es un documento readme.ext en la carpeta del proyecto. Puede estar redactado en inglés o español. Puede usar notación Markdown (extensión .md) o AsciiDoc (extensión .adoc). Resuma en dos a tres párrafos el problema a resolver y enlazar este enunciado. Debe indicar su nombre, un manual de usuario, y finalmente un manual de desarrollo.

El manual de usuario debe explicar cómo invocar el programa, qué significa cada opción, proveer varios ejemplos de ejecución, y explicar la entrada y salida en cada caso. Debe incluir un ejemplo de invocación de las ocho posibles combinaciones de: acción (validar|convertir) × entrada (textual|binaria) × salida (textual|binaria).

Para las salidas binarias provea un volcado hexadecimal del resultado, como se hizo en el ejemplo de ejecución 2. El manual de usuario debe incluir ejemplos de errores y advertencias que el programa puede reportar.

El manual de desarrollador debe explicar cómo compilar la solución, probarla, agregar casos de prueba, e instalar el ejecutable. Debe explicar cómo está estructurado el código fuente en el proyecto, en especial, cuáles archivos pertenecen a la biblioteca, al comando, y al programa de pruebas.

4.4. [25%] Comando

Se debe desarrollar un comando que permita al usuario validar y convertir niveles del juego con la siguiente funcionalidad, expresada tanto en diseño algorítmico (archivos .pseudo) como código fuente en el lenguaje de programación C (archivos .h y .c).

Análisis de argumentos en línea de comandos. El manejo de argumentos debe hacerse en su propio módulo (archivos .h, .c) y no en el main.c del comando. El comando debe satisfacer los requerimientos ya planteados en el enunciado del problema y las siguientes consideraciones:

El comando debe invocarse con una acción en el primer argumento. En caso contrario, o si se provee una acción desconocida, debe terminar con un mensaje de error y sugerir el argumento --help.
Si el usuario pide ayuda con el argumento --help, el comando la provee indiferentemente de otros argumentos que se hayan provisto.
Las opciones (que inician con guión) pueden combinarse en cualquier orden, por ejemplo bin/pipeleak convert -ob file1.bin -it file1.txt tiene el mismo efecto que bin/pipeleak convert -it file1.txt -ob file1.bin.
Si el usuario especifica una opción desconocida, el comando debe reportar error en el error estándar y terminar su ejecución.
Si un archivo de entrada no existe, se debe reportar en el error estándar y terminar la ejecución.

Funcionalidad y reutilización. El comando debe reutilizar el código la biblioteca, el cual debe enlazarse de forma estática o dinámica (ver adelante). Si se usa una biblioteca dinámica, puede corroborar que si realiza un cambio (ej. una corrección de una pulga) en la biblioteca, el comando se verá beneficiado sin tener que recompilarlo.

Pruebas de caja negra. Provea casos de prueba de caja negra en la subcarpeta pipeleak/tests/. Automatice la ejecución de su comando contra los casos de prueba en su archivo pipleak/Makefile. Puede descargar y adaptar los casos de prueba provistos en la siguiente carpeta: tests/. Sin embargo, usted deberá crear al menos tres casos de prueba propios, siguiendo estas instrucciones:

En la carpeta pipeleak/tests/ cree tres subcarpetas con la notación tests/levelNNN/ donde NNN es un número arbitrario de tres dígitos (mayor a 100). En cada subcarpeta agregue un archivo de texto test/levelNNN/input.txt y escriba un caso de prueba en modo texto. Cree al menos dos niveles resolubles, y al menos uno irresoluble. Al menos uno de los niveles resolubles debe ser "realista" (como los que se encontrarían en un videojuego de la temática), y tener dimensiones arbitrarias mayores a 5x5. Agregue estos archivos a control de versiones.

Para crear los demás archivos del caso de prueba (entrada binaria, solución textual, solución binaria y resultado de la validación), puede usar editores de texto y hexadecimales, o su comando conversor de niveles.

4.5. [45%] Biblioteca

Mientras desarrolla el comando propuesto, identifique el código que puede ser reutilizable, por ejemplo, para un futuro videojuego de escritorio o web. El código reutilizable debe separarlo a una biblioteca estática o dinámica (de acuerdo a los lineamientos de su docente). Los siguientes tres módulos se evaluarán y cada uno debe tener sus propios archivos .pseudo, .h, y .c:

[15%] Módulo de validación. Provee subrutinas que validan un nivel del juego y generan un reporte (en memoria) de fugas. Debe usar alguna estructura de datos y no imprimir en salida o archivo. Recuerde que todo módulo debe tener al menos una tripleta de archivos .alg, .h, .c.

[15%] Módulo de conversión. Provee funcionalidad de conversión de formato textual y binario. Provee subrutinas para leer y escribir niveles textuales y binarios, tanto de la entrada estándar como archivos nombrados.
[15%] Módulo común. Provee estructuras de datos y subrutinas comunes que necesitan los dos módulos anteriores. Provea una página principal de Doxygen (@mainpage) para la biblioteca y algunos ejemplos de uso.

Documentación de interfaces y diseño por contratos. Todas las subrutinas y registros de memoria de los tres módulos anteriores deben tener su interfaz documentada usando Doxygen: qué hace, qué recibe, qué retorna, y cualquier otro detalle necesario para usarla adecuadamente. Todo supuesto (invariante) o contrato debe estar resaltado (remark). Para cada subrutina realice un análisis de qué entradas (argumentos o estado de la máquina) la harían fallar y documéntelo. Recuerde, no se trata de escribir texto por cumplir diciendo lo que es trivial o ya se puede leer del código fuente (como suelen hacer las herramientas de inteligencia artificial). Se trata de escribir la mínima información que sería crucial para que los clientes humanos de su biblioteca puedan usarla efectivamente, y en especial, ante situaciones especiales.

Documentación de implementaciones y programación defensiva. Toda subrutina de la biblioteca debe defenderse de entradas inválidas, sea a través de condicionales o supuestos (asserts) dependiendo de si el error es provocado por usuario/a o programador/a respectivamente. Las implementaciones (cuerpos) de las subrutinas deben estar documentadas (con comentarios sencillos y no de Doxygen) de tal manera que un programador/a pueda entender cómo funciona sin necesidad de leer el código fuente. De nuevo, no se trata de replicar en comentarios lo que hace el código fuente, sino explicar a otra persona en alto nivel lo que hace la subrutina, en especial, las decisiones que le llevaron a implementar la subrutina de esa forma, y que de no escribir el comentario, ese conocimiento se perdería.

4.6. [10%] Pruebas unitarias

Mientras analiza y documenta cada subrutina de la biblioteca, cree casos de prueba de caja blanca que las invoquen con entradas correctas y mal intencionadas. Puede utilizar un framework casero (hecho a la medida) que simplifique la definición de los casos de prueba y evite la redundancia de código. Al compilar el programa de pruebas unitarias debe generar un ejecutable. Al ejecutarlo, probará todas las subrutinas públicas de la biblioteca. Si alguna de las pruebas falla, debe reportarlo en el error estándar. En caso de no producir salida, se interpretará como que la biblioteca pasó todas las pruebas unitarias definidas.

4.7. Características comunes

Buenas prácticas de programación. En todos los rubros que involucren código fuente se evaluarán las buenas prácticas de programación, entre las que se incluyen:

Apego a una convención de estilo (cpplint).
Buen uso de la memoria (Valgrind Memcheck, Google Address Sanitizer).
Indentación.
Identificadores significativos.
Inicialización de variables.
Programación defensiva.
Diseño por contratos.

Construcción automática (build automation). El proyecto debe incluir varios archivos Makefile que faciliten la construcción del comando verificador/convertidor, la biblioteca, y el programa de pruebas unitarias. El archivo Makefile en la carpeta del proyecto debe permitir construir a los demás automáticamente. El archivo Makefile de la biblioteca debe permitir compilarla como estática o dinámica (de acuerdo a los lineamientos de su docente). El archivo Makefile del comando debe permitir ejecutar el comando con los casos de prueba de caja negra.