{
* Solución para el Concurso internacional de programación en lenguaje Karel,
* organizado por retroAcción.
* https://www.retroaccion.org/concurso-internacional-de-programacion-en-lenguaje-karel
*
* Autor: Abel Naya
* Fecha de entrega: 2021/11/25
* 
* Nota: Aunque el programa es relativamente corto, el número de comentarios es
* muy alto. Si se desea, se puede ejecutar el siguiente regexp para eliminarlos
*     \r?\n *\{.*?\}
}
iniciar-programa

    {
    * Prototipos
    * (siempre es más agradable leer el resto de funciones en orden,
    * además tenemos dependencia cíclica)
    }
    define-prototipo-instrucción recorrer-salida;
    define-prototipo-instrucción recorrer-laberinto;



    {
    * Se encarga de recorrer un laberinto desde la posición actual,
    * asumiendo que está mirando hacia la entrada.
    * Al terminar, Karel queda girada exactamente 180º y con el laberinto
    * al que estaba mirando (que ahora queda detrás) recorrido,
    * es decir, con un zumbador en cada una de sus casillas
    *
    *     o   o   o   o        o   o   o   o
    *         |   |                | 1 |
    *     o---o   o---o        o---o   o---o
    *                     =>     1   1   1
    *     o---o   o---o        o---o   o---o
    *           ^                    v
    *     o   o   o   o        o   o   o   o
    }
    define-nueva-instrucción recorrer-salida como inicio
        { Entramos en el laberinto }
        avanza;
        { Si no estaba recorrido, lo recorremos }
        si no-junto-a-zumbador entonces recorrer-laberinto
        { Si ya lo estaba, pues damos media vuelta }
        si-no repetir 2 veces gira-izquierda;
        { Y salimos }
        avanza;
    fin;


    {
    * Equivalente a recorrer-salida, pero con Karel empezando dentro del
    * laberinto, que no debe haber sido recorrido, teniendo la salida detrás.
    * Termina también tras 180º, mirando hacia la salida, dentro todavía.
    *
    *     o   o   o   o        o   o   o   o
    *         |   |                | 1 |
    *     o---o   o---o        o---o   o---o
    *           ^         =>     1  \1/  1
    *     o---o   o---o        o---o   o---o
    *
    *     o   o   o   o        o   o   o   o
    }
    define-nueva-instrucción recorrer-laberinto como inicio
        { Lo primero es dejar un zumbador para marcar que hemos estado aquí }
        deja-zumbador;
        { Si ya no nos quedan mas zumbadores, podemos terminar             }
        { (aunque no es necesario, pero así nos ahorramos ciclos inútiles) }
        si ningún-zumbador-en-la-mochila entonces apágate;
        { Y ahora recorremos las 3 salidas de la casilla actual (la cuarta es }
        { la casilla por la que hemos entrado                                 }

        { Esta es sin duda la parte mas compleja del algoritmo y requiere   }
        { explicación adicional:                                            }

        {
        * Lo más fácil sería recorrer cada salida en orden (lado izquierdo,
        * enfrente, lado derecho), cosa que podemos realizar en una pocas
        * instrucciones:
        }
        (*
        { Nos ponemos mirando a la izquierda }
        gira-izquierda;
        { Y ahora repetimos 3 veces, una para cada salida: }
        repetir 3 veces inicio
            { Si está libre la recorremos }
            si frente-libre entonces recorrer-salida
            { Si no lo está, giramos 180º }
            si-no repetir 2 veces gira-izquierda;
            { Y ahora pasamos a la siguiente salida a comprobar }
            gira-izquierda;
        fin;
        *)
        {
        * Este proceso, aunque muy eficiente en líneas de código, es
        * tremendamente ineficiente en instrucciones ejecutadas. Por ejemplo: si
        * sólo la salida de enfrente estuviera libre, bastaría recorrerla y
        * habríamos acabado sin giros adicionales, pero este código realiza 8
        * giros! De media se realizan unos 4 giros y medio adicionales por cada
        * casilla que tiene el laberinto. Para optimizar este procedimiento hay
        * que ver que tenemos 8 situaciones posibles:
        *
        *   o--o    o--o    o  o    o  o
        *   |/\|    |/\     |/\|    |/\
        *   o  o    o  o    o  o    o  o
        *
        *   giro    giro    sal     sal
        *   giro    giro            giro
        *           giro            sal
        *           sal             giro
        *           giro
        *
        *
        *   o--o    o--o    o  o    o  o
        *    /\|     /\      /\|     /\
        *   o  o    o  o    o  o    o  o
        *
        *   giro    giro    giro    giro
        *   sal     sal     sal     sal
        *   giro    sal     giro    giro
        *   giro    giro    sal     sal
        *   giro                    giro
        *                           sal
        *                           giro
        *
        *  Donde se muestra una de las soluciones óptimas siendo:
        *   'giro' corresponde a girar a la izquierda.
        *   'sal'  corresponde a tomar la salida que tiene enfrente, recorrerla,
        *          y volver, con lo que equivale a girar 180º.
        *
        * Se pueden programar las 8 ramas por separado, o buscar un método
        * recursivo que lo realice. Curiosamente, el método recursivo (aunque
        * interesante) acaba siendo menos eficiente que realizar un simple árbol
        * de decisión (ver anexo al final del fichero).
        * A continuación se describe el árbol de decisiones implementado, al que
        * se han aplicado micro-optimizaciones específicas (juntar ramas
        * equivalentes y realizar salidas prematuras para permitir juntar aún
        * más ramas ).
        * Nota: Para simplificar las explicaciones se asume que Karel empieza
        * mirando al norte, sin pérdida de generalidad:
        }
        { Primero comprobamos la salida del oeste, a nuestra izquierda }
        {
        *    o ? o
        *    ! ^ ?
        *    o   o
        }
        si izquierda-libre entonces inicio
            { Si está libre, la recorremos }
            {
            *    o ? o
            *      ^ ?
            *    o   o
            }
            gira-izquierda;
            {
            *    o ? o
            *      < ?
            *    o   o
            }
            recorrer-salida;
            {
            *    o ? o
            *  1   > ?
            *    o   o
            }
            { Estamos ahora orientados al este                   }
            { (recordar que recorrer-salida te deja girado 180º) }

            { Comprobamos ahora la salida del norte, a nuestra izquierda }
            {
            *    o ! o
            *  1   > ?
            *    o   o
            }
            si izquierda-libre entonces inicio
                { Si lo está, la recorremos }
                {
                *    o   o
                *  1   > ?
                *    o   o
                }
                gira-izquierda;
                {
                *    o   o
                *  1   ^ ?
                *    o   o
                }
                recorrer-salida;
                {      1
                *    o   o
                *  1   v ?
                *    o   o
                }
                { Nos quedamos mirando al sur }

                { Por último miramos la última salida, el este, que está a }
                { nuestra izquierda                                        }
                {      1
                *    o   o
                *  1   v !
                *    o   o
                }
                si izquierda-bloqueada entonces
                    { Si está bloqueada, hemos terminado }
                    {      1
                    *    o   o
                    *  1   v |
                    *    o   o
                    }
                    sal-de-instrucción;
                { En caso contrario, la recorremos }
                {      1
                *    o   o
                *  1   v
                *    o   o
                }
                gira-izquierda;
                {      1
                *    o   o
                *  1   >
                *    o   o
                }
                recorrer-salida;
                {      1
                *    o   o
                *  1   <   1
                *    o   o
                }
                { Terminamos mirando al oeste }

            fin si-no
                { Si la salida del norte no estaba libre, miramos la de }
                { enfrente que nos queda                                }
                {
                *    o---o
                *  1   > !
                *    o   o
                }
                si frente-libre entonces
                    { Si lo está la recorremos }
                    {
                    *    o---o
                    *  1   >
                    *    o   o
                    }
                    recorrer-salida
                    {
                    *    o---o
                    *  1   <   1
                    *    o   o
                    }
                si-no
                    { En caso contrario hacemos un giro de 180º }
                    {
                    *    o---o
                    *  1   > |
                    *    o   o
                    }
                    repetir 2 veces gira-izquierda;
                    {
                    *    o---o
                    *  1   < |
                    *    o   o
                    }
                { En cualquiera de los casos estamos ahora mirando al oeste }

        fin si-no inicio
            { Si la salida del oeste no estaba libre, entonces comprobamos la }
            { de enfrente, el norte                                           }
            {
            *    o ! o
            *    | ^ ?
            *    o   o
            }
            si frente-libre entonces
                { Si esta sí que está libre, la recorremos }
                {
                *    o   o
                *    | ^ ?
                *    o   o
                }
                recorrer-salida
                {      1
                *    o   o
                *    | v ?
                *    o   o
                }
            si-no
                { Si no, damos media vuelta }
                {
                *    o---o
                *    | ^ ?
                *    o   o
                }
                repetir 2 veces gira-izquierda;
                {
                *    o---o
                *    | v ?
                *    o   o
                }
            { En ambos casos estamos ahora mirando al sur }

            { Con lo cual comprobamos la ultima salida, la del este }
            {
            *    o * o
            *    | v !
            *    o   o
            }
            si izquierda-bloqueada entonces
                { Si está bloqueada, hemos terminado ya }
                {
                *    o * o
                *    | v |
                *    o   o
                }
                sal-de-instrucción;
            { En caso contrario la realizamos }
            {
            *    o * o
            *    | v
            *    o   o
            }
            gira-izquierda;
            {
            *    o * o
            *    | >
            *    o   o
            }
            recorrer-salida;
            {
            *    o * o
            *    | <   1
            *    o   o
            }
        fin;

        { Para cualquiera de las variantes anteriores, si no hemos realizado }
        { una salida prematura entonces estamos mirando al oeste             }
        {
        *    o * o
        *    * < *
        *    o   o
        }
        { Con lo que basta girar una última vez, y hemos terminado }
        gira-izquierda;
        {
        *    o * o
        *    * v *
        *    o   o
        }
    fin;



    {
    * main(): función principal
    }
    inicia-ejecución
        { Recorrer el laberinto, empezamos dentro }
        recorrer-laberinto;
        { En el enunciado no se especifica hacia donde empieza mirando Karel, }
        { y recorrer-laberinto solo evalúa la salida de enfrente y los lados. }
        { Por si acaso, evaluamos ahora la que nos queda.                     }
        { Esto también hace que nuestra solución sirva incluso si Karel       }
        { empieza en una casilla cualesquiera de dentro.                      }
        si frente-libre entonces recorrer-salida;
        { No sería necesario apagarla, el programa ya ha terminado (y además  }
        { ya debería haberse apagado tras soltar todos sus zumbadores).       }
        { Aun así somos ahorradores, no hay que dejar los aparatos conectados }
        apágate;
    termina-ejecución
finalizar-programa







{*********************************** ANEXO ************************************}
{ Tal y como se describe en recorrer-laberinto, esta es una solución en la que }
{ dicha función se sustituye por una subfunción que realiza el mismo           }
{ procedimiento mediante un algoritmo recursivo. Se han omitido los            }
{ comentarios ya explicados                                                    }
(*
iniciar-programa

    define-prototipo-instrucción recorrer-salida;
    define-prototipo-instrucción recorrer-laberinto;
    define-prototipo-instrucción comprobar-salidas(n);



    define-nueva-instrucción recorrer-salida como inicio
        avanza;
        si no-junto-a-zumbador entonces recorrer-laberinto
        si-no repetir 2 veces gira-izquierda;
        avanza;
    fin;


    define-nueva-instrucción recorrer-laberinto como inicio
        deja-zumbador;
        si ningún-zumbador-en-la-mochila entonces apágate;

        { Ahora recorremos las 3 salidas de la casilla actual }
        comprobar-salidas(3);
    fin;


    {
    * Función de recorrido de casilla, comprobando las n salidas que quedan,
    * mediante recursividad.
    * Para ello es necesario tener un contador de cuantas salidas nos
    * quedan por revisar, 'n', y usar recursividad terminando al llegar a 0.
    * No podemos terminar al intentar 'salir' por la cuarta salida, ya que si
    * Karel empieza el programa dentro del laberinto, esto no se cumple y
    * solucionarlo requeriría una condición extra específica. Pensar por ejemplo
    * en un laberinto 1x1, sin salidas.
    *
    * Tenemos entonces 5 situaciones/ramas a comprobar:
    * 'Gastar' 1 comprobación para la salida de la izquierda:
    *   1) Si no nos queden salidas por comprobar -> girar y terminar
    *   2) Está libre -> girar y recorrerla
    * 'Gastar' otra comprobación en la salida de enfrente:
    *   3) Si no nos quedan salidas por comprobar -> terminar
    *   4) Está libre -> girar y recorrerla
    * Si no se ha dado ningún caso:
    *   5) Girar 180º
    *
    * Esta es la lista de las 8 situaciones posibles y una posible solución
    * óptima (algunas tienen otras soluciones con mismo número de instrucciones)
    * El número de la izquierda corresponde al valor de n en esa iteración.
    * El número siguiente corresponde a la rama tomada
    * y luego vienen las instrucciones que la componen:
    *     'giro' corresponde a girar a la izquierda.
    *     'sal'  corresponde a tomar la salida que tiene enfrente, recorrerla,
    *            y volver, con lo que equivale a girar 180º.
    *
    *       o--o          o--o          o  o          o  o
    *       |/\|          |/\           |/\|          |/\
    *       o  o          o  o          o  o          o  o
    *
    *   3 > 5 giro    3 > 5 giro    3 > 4 sal     3 > 4 sal
    *         giro          giro    1 > 3 -       1 > 2 giro
    *   1 > 3 -       1 > 2 giro                        sal
    *                       sal                   0 > 1 giro
    *                 0 > 1 giro
    *
    *
    *       o--o          o--o          o  o          o  o
    *        /\|           /\            /\|           /\
    *       o  o          o  o          o  o          o  o
    *
    *   3 > 2 giro    3 > 2 giro    3 > 2 giro    3 > 2 giro
    *         sal           sal           sal           sal
    *   2 > 5 giro    1 > 4 sal     2 > 2 giro    2 > 2 giro
    *         giro    0 > 1 giro          sal           sal
    *   0 > 1 giro                  1 > 3 -       1 > 2 giro
    *                                                   sal
    *                                             0 > 1 giro
    }
    define-nueva-instrucción comprobar-salidas(n) como inicio
        { (1) Primero miramos si ya no hay salidas que comprobar, }
        {     en ese caso estamos mirando a la izquierda          }
        {     (porque hemos terminado de hacer el lado derecho, el último)   }
        {     con lo cual giramos y ya no hacemos nada mas        }
        si si-es-cero(n) entonces gira-izquierda

        { (2) Si no, miramos si la salida de la izquierda está libre }
        si-no si izquierda-libre entonces inicio
            { Si lo está, giramos }
            gira-izquierda;
            { Y la recorremos }
            recorrer-salida;
            { Para por ultimo comprobar las n-1 salidas restantes }
            comprobar-salidas(precede(n));
        fin

        { Si hemos llegado hasta aquí, es porque la salida de la izquierda    }
        { ya está revisada, podemos restar n-- (aunque eso aquí no existe así }
        { que ahora tratamos con n-1, o en sintaxis de Karel: precede(n); )   }

        { (3) De nuevo miramos si ya no nos quedan más salidas que comprobar }
        {     (n-1==0), en ese caso estamos mirando hacia abajo (acabamos de }
        {     terminar la penúltima salida, la de arriba) y no hay que hacer }
        {     nada más                                                       }
        si-no si si-es-cero(precede(n)) entonces inicio {-} fin

        { (4) Si no, miramos si la salida de enfrente es la que está libre }
        si-no si frente-libre entonces inicio
            { Si lo está la recorremos }
            recorrer-salida;
            { Y por último comprobamos las n-2 ((n-1)-1) salidas restantes }
            comprobar-salidas(precede(precede(n)));
        fin

        { Si hemos llegado hasta aquí, es porque tanto la salida de la }
        { izquierda como la de enfrente están revisadas,               }
        { de nuevo hacemos n-- (ya vamos por n-2)                      }

        { (5) Lo último que nos queda es }
        si-no inicio
            { Dar media vuelta }
            repetir 2 veces gira-izquierda;
            { Y comprobar esas n-2 salidas que nos quedan }
            comprobar-salidas(precede(precede(n)));
        fin;
    fin;


    inicia-ejecución
        recorrer-laberinto;
        si frente-libre entonces recorrer-salida;
        apágate;
    termina-ejecución
finalizar-programa
*)