5 - Varios problemas de ejemplo

Otra vez a reparar la calle

En la sección anterior propusimos el siguiente programa para resolver el problema de llenar los agujeros de la calle:

> # ------------ Definición de funciones auxiliares-----------
> 
> # Función: llenar_agujero
> llenar_agujero <- function() {
+   girar_derecha()
+   avanzar()
+   if (no_hay_cosos()) {
+     poner_coso()
+   }
+   darse_vuelta()
+   avanzar()
+   girar_derecha()
+ }
> 
> # ------------------- Programa principal -------------------
> 
> generar_mundo("mundo003")
> while (frente_abierto()) {
+   avanzar()
+   llenar_agujero()
+   avanzar()
+ }
> ejecutar_acciones()

Este programa sirve para mundos con calles de cualquier largo, sin embargo no serviría si los agujeros no estuviesen equiespaciados como asumimos inicialmente. Sería mejor tener un programa más general que funcione bajo estas condiciones:

• El mundo puede tener calles de cualquier largo.
• Los agujeros pueden estar en cualquier posición a lo largo de la calle, sin restricciones en cuanto a la cantidad o su espaciado.
• Algunos agujeros podrían estar ya reparados, de modo que Karel no debe poner un coso en ellos.

Un ejemplo de este tipo de mundo es este:

> generar_mundo("mundo006")

Para solucionar este problema, en vez de comenzar cada iteración con un avance, deberíamos primero chequear si donde Karel está parada hay un agujero, si es así llenarlo en el caso de que no estuviese reparado y luego avanzar. Por lo tanto se debe modificar el bloque que se itera:

> # ------------------- Programa principal -------------------
> 
> generar_mundo("mundo106")
> while (frente_abierto()) {
+   if (derecha_abierto()) {
+       llenar_agujero()
+   }
+   avanzar()
+ }
> ejecutar_acciones()

Sin embargo, este programa tiene una falla, porque si bien anda en esta situación…

…no funciona en esta:

> # ------------------- Programa principal -------------------
> 
> generar_mundo("mundo007")
> while (frente_abierto()) {
+   if (derecha_abierto()) {
+       llenar_agujero()
+   }
+   avanzar()
+ }
> ejecutar_acciones()

Karel se detiene sin llenar el último agujero. De hecho, Karel ni siquiera desciende para ver si hay que llenarlo o no. El problema está en que apenas Karel rellena el agujero de la avenida 6, ejecuta la acción de avanzar, quedando enfrente de una pared, lo cual hace que el loop while se detenga antes de evaluar esa última posición. Este es un error lógico bastante frecuente cuando se trabaja con estructuras iterativas, pero su solución es sencilla. Lo único que tenemos que hacer es agregar un chequeo adicional después de haber finalizado el while:

> # ------------------- Programa principal -------------------
> 
> generar_mundo("mundo007")
> while (frente_abierto()) {
+   if (derecha_abierto()) {
+       llenar_agujero()
+   }
+   avanzar()
+ }
> if (derecha_abierto()) {
+   llenar_agujero()
+ }
> ejecutar_acciones()

Crear otras funciones que hagan de Karel aún más poderosa

Karel ya sabe girar, avanzar, poner y juntar cosos. Sin embargo, podemos imaginar que para desempeñarse en su mundo, seguramente hay algunas actividades que debe repetir a menudo. Por ejemplo, avanzar derechito hasta que se encuentre con una pared, juntar todos los cosos que se pueda encontrar a lo largo de una calle o avenida o vaciar su mochila poniendo cosos en un lugar hasta que ya no le quede ninguno. Vamos a crear funciones que se encarguen de estas tareas, de modo que Karel pueda implementarlas en cualquier momento.

1. Avanzar hasta encontrarse con una pared

> # Función: avanzar_hasta_pared()
> # Descripción: permite que Karel avance hasta que encuentre una pared
> # Condición inicial: ninguna
> # Condición final: Karel queda enfrentada a una pared
> avanzar_hasta_pared <- function() {
+   while (frente_abierto()) {
+     avanzar()
+   }
+ }

2. Recolectar una línea de cosos

> # Función: recolectar_linea()
> # Descripción: permite recolectar una línea consecutiva de cosos. La línea
> # termina en la primera celda que no tiene cosos.
> # Condición inicial: ninguna
> # Condición final: Karel está en el final de la línea con la misma dirección que
> # al inicio
> recolectar_linea <- function() {
+   while (hay_cosos()) {
+     juntar_coso()
+     if (frente_abierto()) {
+       avanzar()
+     }
+   }
+ }

3. Poner todos los cosos que tiene en la mochila en un lugar

> # Función: colocar_todo()
> # Descripción: Karel coloca todos los cosos que tiene en su mochila en su
> # posición actual
> # Condición inicial: ninguna
> # Condición final: ninguna
> colocar_todo <- function() {
+   while (karel_tiene_cosos()) {
+     poner_coso()
+   }
+ }

Recoger columnas de cosos

En este ejemplo, no hay paredes en el mundo de Karel pero en algunas avenidas hay columnas de cosos de cualquier altura, mientras que otras avenidas están vacías. El trabajo de Karel es recolectarlas a todas, dejarlas en la posición de abajo a la derecha como muestra el diagrama y volver a su posición inicial:

Como ya hemos dicho, un buen consejo para encarar cualquier problema es tratar de descomponerlo en partes más pequeñas. Siguiendo esta idea, podemos imaginarnos que el programa principal puede estar compuesto por tres partes: recolectar todos los cosos y guardarlos en su mochila que inicialmente estará vacía, depositarlos en la esquina y volver a la posición inicial. Algo como esto:

> generar_mundo("mundo008")
> recolectar_todo()
> colocar_todo()
> volver_inicio()
> ejecutar_acciones()

Así como está, es muy sencillo entender qué es lo que hay que hacer. Además, hace uso de una función que ya tenemos definida de antes, colocar_todo(). Lo único que falta, que no es poco, es escribir los otros dos subalgoritmos, que a su vez pueden descomponerse en otros problemas menores.

En primer instancia, hay que recolectar todas las columnas de cosos, sin saber cuántas pueden ser, esto nos hace pensar en que será necesario un while. Tenemos que recolectar columna por columna hasta que nos encontremos con la pared:

> recolectar_todo <- function() {
+   while (frente_abierto()) {
+     recolectar_una_columna()
+     avanzar()
+   }
+   recolectar_una_columna()
+ }

Notar que después del while hemos repetido recolectar_una_columna(), por la razón expuesta en el ejemplo anterior. Además, le estamos diciendo que recolecte la columna sin haber chequeado si había una… ¿qué pasa si no hay ninguna? Respondé a esta pregunta cuando leas el programa completo más abajo, pero te aseguramos que está bien hacerlo así.

Claro que entonces necesitamos crear esta nueva función recolectar_una_columna(), que tiene que encargarse de que Karel:

1. Gire para mirar hacia el norte.
2. Recolecte todos los cosos deteniéndose cuando ya no haya más (¿te suena este problema?.
3. Se dé vuelta para emprender el descenso.
4. Baje hasta la pared que representa al piso (¿te suena este problema?).
5. Vuelva a girar para estar lista para avanzar a la siguiente columna.

Entonces, la función tiene que ser algo así:

> recolectar_una_columna <- function() {
+   girar_izquierda()
+   recolectar_linea()
+   darse_vuelta()
+   avanzar_hasta_pared()
+   girar_izquierda()
+ }

Aparecieron por ahí dos funciones que definimos en el ejercicio anterior, que como anticipamos son actividades bastante comunes que nos viene muy bien tenerlas ya programadas. El programa completo se muestra a continuación. Recordar que en R necesitamos ejecutar primero las funciones que hemos inventado y luego el programa principal que las utiliza.

> # ------------ Definición de otras funciones auxiliares-----------
> 
> # Función: recolectar_todo()
> # Descripción: permite recolectar todos los cosos de cada columna moviéndose a
> # lo largo de la primera calle.
> # Condición inicial: Karel está mirando al este en la posición (1, 1)
> # Condición final: Karel está mirando al este en la posición del extremo derecho
> # de la primera fila
> recolectar_todo <- function() {
+   while (frente_abierto()) {
+     recolectar_una_columna()
+     avanzar()
+   }
+   recolectar_una_columna()
+ }
> 
> # Función: recolectar_una_columna()
> # Descripción: permite recolectar todos los cosos en una única columna
> # Condición inicial: Karel debe estar en la base de la columna mirando al este
> # Condición final: Karel está en la misma posición y dirección que al inicio
> recolectar_una_columna <- function() {
+   girar_izquierda()
+   recolectar_linea()
+   darse_vuelta()
+   avanzar_hasta_pared()
+   girar_izquierda()
+ }
> 
> # Función: volver_inicio()
> # Descripción: permite que Karel regrese a la posición (1, 1)
> # Condición inicial: Karel mira al este en algún lugar de la primera fila
> # Condición final: Karel está en la posición (1, 1) mirando al este
> volver_inicio <- function() {
+   darse_vuelta()
+   avanzar_hasta_pared()
+   darse_vuelta()
+ }
> 
> # ------------------- Programa principal -------------------
> generar_mundo("mundo008")
> recolectar_todo()
> colocar_todo()
> volver_inicio()
> ejecutar_acciones()

El laberinto

Ahora nos vamos a imaginar que Karel está en un laberinto como el siguiente, donde el coso indica la salida:

Tenemos que crear un programa para que Karel pueda llegar hasta ahí, sin embargo tiene que ser general para que sirva para este y cualquier otro laberinto. Hay una estrategia para resolver cualquier laberinto: si cuando entrás tocás con tu mano la pared a tu derecha y caminás sin dejar de tocarla nunca, eventualmente llegarás a la salida. Esto se conoce como la regla de la mano derecha y se traduce en doblar siempre a la derecha, en toda selección de caminos que se te presente (por supuesto, también serviría si se hiciera siempre con la izquierda).

El breve programa que se presenta a continuación implementa el algoritmo de la mano derecha. Muchas veces, los programas que resuelven problemas muy interesantes no son ni largos ni rebuscados. Miralo con atención hasta que estés convencido de entender la lógica de este algoritmo:

> # ------------------- Programa principal -------------------
> 
> generar_mundo("mundo009")
> while (no_hay_cosos()) {
+   girar_derecha()
+   while (frente_cerrado()) {
+     girar_izquierda()
+   }
+   avanzar()
+ }
> ejecutar_acciones()

Más problemas

A continuación se dejan propuestos algunos ejercicios para seguir repasando lo aprendido junto a Karel.

> # Programa principal
> generar_mundo("mundo021")
> avanzar()
> duplicar_cosos()
> avanzar()
> ejecutar_acciones()