Universidad de Costa Rica. Escuela de Ciencias de la Computación e Informática.
CI-0113 Programación II. 2024a. Examen 01 [25-May-2024] Gr02. Prof.: Jeisson Hidalgo-Céspedes

Una organización quiere crear un pequeño robot capaz de dibujar en un lienzo. Entre otros propósitos, se quiere que el robot ayude a personas a aprender a programar en el ensamblador de sistemas computacionales como éste. Su propósito es crear un intérprete del ensamblador propuesto del robot, de tal forma que permita ejecutar programas y ver su efecto sobre los lienzos.

Su intérprete recibirá en la primera línea las dimensiones del lienzo en filas y columnas, seguido por un carácter de relleno. Después de una línea en blanco vendrán las instrucciones del programa en el ensamblador del robot. Se sabe que el segmento de código del robot está limitado a 4096 instrucciones de máximo 16 caracteres cada una.

Ejemplo de entrada 1:

8 10 .

fly 2 4
down 3
ink O
fly 4 7
up 3
fly 7 8
ink #
left 6
ink *
_draw
fly 6 2
right 1
fly 6 9
right 1
_draw

Ejemplo de salida 1:

. . . . . . . . . .
. . . # . . O . . .
. . . # . . O . . .
. . . # . . O . . .
. . . . . . . . . .
. . . . . . . . . .
. . # # # # # # . .
. . . . . . . . . .

. . . . . . . . . .
. . . # . . O . . .
. . . # . . O . . .
. . . # . . O . . .
. . . . . . . . . .
. * . . . . . . * .
. . # # # # # # . .
. . . . . . . . . .

Ejemplo de entrada 2:

5 8 :

ink >
right 100
_draw

ink v
fly 50 50
down 100
_draw

ink <
left 100
ink ^
up 100

_draw

Ejemplo de salida 2:

> > > > > > > >
: : : : : : : :
: : : : : : : :
: : : : : : : :
: : : : : : : :

> > > > > > > v
: : : : : : : v
: : : : : : : v
: : : : : : : v
: : : : : : : v

^ > > > > > > v
^ : : : : : : v
^ : : : : : : v
^ : : : : : : v
^ < < < < < < <

El robot funciona similar a la tortuga del lenguaje Logo, que puede desplazarse y dibujar sobre el lienzo, pero con capacidades nuevas que la tecnología moderna permite, como poder volar. Al iniciar la ejecución de un programa el robot se encuentra en la fila 1 y columna 1 del lienzo. Si el robot se desplaza (camina) sobre el lienzo, deja un rastro de tinta. Naturalmente, este rastro no queda si el robot vuela sobre el lienzo. El conjunto de instrucciones que el robot comprende son las siguientes (en orden alfabético).

# Instrucción Efecto

1

down f

El robot camina la cantidad f de filas hacia abajo dejando rastro de tinta sobre el lienzo. Si llega al borde del lienzo se detiene sin salir de él aunque le falten filas por desplazarse.

2

_draw

El intérprete dibuja el lienzo completo en la salida estándar. Las celdas que no tienen tinta se imprimirán con el carácter de relleno indicado en la primera línea. Si ya previamente había dibujado otro lienzo en la salida estándar, los separa por una línea vacía. Esta es una instrucción para el intérprete de computadora que no es necesaria para el robot físico, por lo que se decidió iniciarla con guión bajo para indicarlo.

3

fly r c

El robot usa sus capacidades de dron para elevarse y dirigirse a la celda ubicada en la fila f y columna c. Si la celda no existe, no tiene ningún efecto sobre el estado del robot.

4

ink c

Cambia la tinta del robot al carácter c, de tal forma que los desplazamientos subsecuentes dejarán rastro de tinta c hasta que se vuelva a cambiar la tinta con otra instrucción ink. La tinta por defecto es el carácter numeral (#).

5

left c

El robot camina la cantidad c de columnas hacia la izquierda dejando rastro de tinta sobre el lienzo. Si llega al borde del lienzo se detiene sin salir de él aunque le falten columnas por desplazarse.

6

right c

El robot camina la cantidad c de columnas hacia la derecha dejando rastro de tinta sobre el lienzo. Si llega al borde del lienzo se detiene sin salir de él aunque le falten columnas por desplazarse.

7

up r

El robot camina la cantidad f de filas hacia arriba dejando rastro de tinta sobre el lienzo. Si llega al borde del lienzo se detiene sin salir de él aunque le falten filas por desplazarse.

Si se pide desplazar al robot 0 celdas en una dirección, la acción no tendrá efecto, el robot seguirá en su misma celda sin dejar rastro de tinta. Si el robot está en una celda (a,b) y se solicita desplazarlo 1 unidad en alguna dirección, el robot marcará la celda (a,b) con tinta y luego tratará de moverse a la celda vecina (x,y). Si la celda vecina (x,y) existe en el lienzo, el robot se moverá a (x,y) sin marcarla con tinta y se quedará en (x,y). Si la celda vecina (x,y) no existe (está fuera de los bordes), el robot permanecerá en la celda original (a,b). Si se pide mover el robot n unidades en alguna dirección, se aplicará el este mismo comportamiento n veces, una celda a la vez.

Para efectos de este enunciado puede considerar las siguientes simplificaciones y restricciones:

  1. No hay instrucciones de salto hacia atrás ni subrutinas, por lo que su intérprete puede ejecutar las instrucciones en una pasada conforme las lee de la entrada estándar.

  2. Si una instrucción es desconocida, su programa debe imprimir un mensaje error: n: unknown instruction w donde n es el número de línea (iniciando en 1) y w es la instrucción escrita en el programa de usuario, y detenerse de interpretar más instrucciones.

  3. Si una instrucción tiene sintaxis incorrecta en sus argumentos, su programa imprimir un mensaje error: n: invalid syntax donde n es el número de línea y detenerse también. Para efectos de la prueba en papel, puede suponer que toda instrucción provista en la entrada estándar tiene siempre sus argumentos correctos. Es decir, no requiere realizar esta validación en su solución en papel, pero sí en digital.

  4. La instrucción vacía, indicada por una línea en blanco, es válida y no produce efecto en el estado de la máquina computacional (robot), simplemente se ignora.

Sugerencias:

  1. Puede usar los procedimientos de entrada con formato (ej.: scanf) para obtener las partes de cada instrucción.

  2. Puede almacenar el estado de la máquina (del intérprete) en uno o varios registros de memoria (struct), y pasar direcciones a estos en lugar de muchos parámetros en sus subrutinas.

  3. Utilice enteros con signo (ej.: long) en lugar de size_t para facilitar la aritmética que debe evitar que el robot se salga hacia la izquierda o arriba en el lienzo.

  4. Para efectos del programa en papel no es necesario: hacer inclusión de encabezados, declarar subrutinas antes de invocarlas, ni documentar interfaces con Doxygen.

  5. Puede considerar su hoja de anotaciones como una biblioteca reutilizable. Si en ella tiene definida una subrutina, no es necesario que la transcriba a su cuaderno de examen, puede invocarla directamente.

Evaluación

En cada uno de los rubros siguientes se evalúan las buenas prácticas de programación que influyen en la calidad, eficiencia, y reutilización del código. Nota: no es necesario que documente con Doxygen.

  1. [30%] Diseña un algoritmo solución usando los 8 tipos de instrucciones (pseudocódigo).

  2. [10%] Hace buen uso de la memoria. Crea y destruye matrices en memoria dinámica.

  3. [20%] Interpreta (ejecuta) las instrucciones ensamblador en la entrada estándar o se detiene si hay desconocidas.

  4. [10%] Imprime el estado del lienzo (_draw) separada de impresiones previas.

  5. [10%] Cambia el robot de lugar (fly) a una celda existente. Cambia el tipo de tinta (ink).

  6. [20%] Mueve el robot en las cuatro direcciones (top, down, right, left) dejando rastro de tinta sobre el lienzo sin salirse de él.

  7. [10% extra] Transcribe y corrige su solución en HackerRank para que pase los casos de prueba.