Clase 12 de febrero

Este dia se hizo un problema mas complicado:

Autopista

10a OMI, Durango 2005

Descripción

En Beeperópolis han construido su primera autopista. La autopista esta delimitada por paredes y atraviesa la ciudad de norte a sur, debido a las irregularidades del terreno, el ancho de la autopista varía a lo largo de la misma.
Sin embargo, los habitantes tienen un grave problema ya que no cuentan con la línea central que divide los carriles de ida y de vuelta. Afortunadamente Karel es jefe de tránsito y siempre esta dispuesto a resolver los problemas de Beeperopolis, por lo que se ha dado a la tarea de dibujar dicha línea.

Problema

Ayuda a Karel a poner la línea divisoria en la autopista, esta será formada por zumbadores y deberá dividir por la mitad la autopista desde el norte hasta el sur.
No debe de quedar ningún zumbador en una posición que no pertenezca a la línea divisoria. En cada posición de la línea divisoria, deberá haber únicamente un zumbador.

Consideraciones

• Karel lleva un número INFINITO de zumbadores en su mochila.
• Karel inicia en cualquier lugar del extremo norte de la autopista con dirección al sur.
• No hay paredes ni zumbadores dentro de la autopista.
• En cualquier fila de la autopista, el espacio entre ambas paredes es un número impar desconocido.
• La línea deberá estar formada por montones de 1 zumbador y deberá ser de ancho 1 y no deberá haber zumbadores en ningún otro lugar de la autopista.
• No importa la posición ni orientación final de Karel.

Ejemplo mundo inicial

Mundo final

Solucion

iniciar-programa
    define-nueva-instruccion inicia como inicio
        gira-izquierda;
        gira-izquierda;
        gira-izquierda;
        mientras frente-libre hacer inicio
            avanza;
        fin;
        gira-izquierda;
        gira-izquierda;
    fin;
    define-nueva-instruccion mide-mitad como inicio
        si frente-libre entonces inicio
            avanza;
            avanza;
            mide-mitad;
            avanza;
        fin sino inicio
            gira-izquierda;
            gira-izquierda;
        fin;
    fin;
    define-nueva-instruccion busca-abajo como inicio
        mientras derecha-bloqueada y frente-libre hacer inicio
            avanza;
        fin;
        si derecha-bloqueada entonces inicio
           gira-izquierda;
        fin sino inicio
            gira-izquierda;
            gira-izquierda;
            gira-izquierda;
            avanza;
        fin;
    fin;
    inicia-ejecucion
        mientras no-orientado-al-norte hacer inicio
            inicia;
            mide-mitad;
            deja-zumbador;
            mientras frente-libre hacer inicio
                avanza;
            fin;
            gira-izquierda;
            gira-izquierda;
            busca-abajo;
        fin;
        apagate;
    termina-ejecucion
finalizar-programa