Tag: juego

El reto de la rana

Kaeru Jump, del japonés kaeru (蛙, rana), es un pequeño juego en flash de inteligencia (o también de probar, probar y probar). El objetivo del juego es que la rana protagonista llegue a cada una de las piedras del escenario. A cada salto, la piedra anterior se hunde en el agua. Los saltos son sólo en ángulos rectos y no se puede saltar hacia atrás.

El reto son diez niveles generados aleatoriamente, a cada cual más difícil. Os reto a ver cuánto tiempo tardáis en acabarlos todos, sin hacer trampas claro.

Solución

Si no consiguieseis acabar todos los niveles, no os desesperéis ni lancéis el teclado por la ventana. Existe un método para resolver este tipo de problemas. En programación se le llama backtracking. Aunque por el nombre parezca algo guapo, no es más que ir probando combinaciones hasta encontrar las que resuelvan el problema (en nuestro caso paramos al encontrar la primera que lo resuelva). Son muchas combinaciones, pero mientras las haga el ordenador a nosotros nos da igual, ¿no?

Para hacerlo funcionar, sólo tenéis que decir la posición inicial, la dirección a la que mira la rana y marcar los checkbox del mapa del nivel, si está marcado es que en el mapa hay una piedra en esa posición. ¡Si leéis desde el lector RSS es probable que no veáis nada!

Fila inicial: Columna inicial: Dirección inicial:

El código

Os pongo la función para calcular la solución en javascript. Se puede comprimir más el código, pero así se entiende mejor. Para llamarla, necesitáis la fila y la columna inicial(f y c), una matriz de booleanos para el tablero donde un true indica que hay una piedra en esa posición, un Array vacío para guardar el camino en la recursividad y un string direccion para la dirección inicial, que puede ser “arriba”, “derecha”, “abajo” o “izquierda”. El resultado es un Array con dos posiciones: la primera indica si hay solución y la segunda indica el camino.

function resolver(f, c, tablero, restantes, camino, direccion) {
    if(restantes == 1) return new Array(true, camino);
    var resuelto = false;
   
    // Miro todas las direcciones desde la posición actual
    // Arriba
    if(direccion != "abajo") {
        var hay = false;
        for(fila = f - 1; !hay && fila >= 0; --fila) {
            if(tablero[fila][c]) {
                hay = true;
                tablero[f][c] = false;
                --restantes;
                camino.push("Arriba");
                resultado = resolver(fila, c, tablero, restantes, camino, "arriba");
                if(resultado[0]) return new Array(true, camino);
                else {
                    ++restantes;
                    tablero[f][c] = true;
                    camino.pop();
                }
            }
        }
    }
   
    // Derecha
    if(direccion != "izquierda") {
        var hay = false;
        for(columna= c + 1; !hay && columna < columnas; ++columna) {
            if(tablero[f][columna]) {
                hay = true;
                tablero[f][c] = false;
                --restantes;
                camino.push("Derecha");
                resultado = resolver(f, columna, tablero, restantes, camino, "derecha");
                if(resultado[0]) return new Array(true, camino);
                else {
                    ++restantes;
                    tablero[f][c] = true;
                    camino.pop();
                }
            }
        }
    }
   
    // Abajo
    if(direccion != "arriba") {
        var hay = false;;
        for(fila = f + 1; !hay && fila < filas; ++fila) {
            if(tablero[fila][c]) {
                hay = true;
                tablero[f][c] = false;
                --restantes;
                camino.push("Abajo");
                resultado = resolver(fila, c, tablero, restantes, camino, "abajo");
                if(resultado[0]) return new Array(true, camino);
                else {
                    ++restantes;
                    tablero[f][c] = true;
                    camino.pop();
                }
            }
        }
    }
   
    // Izquierda
    if(direccion != "derecha") {
        var hay = false;;
        for(columna= c - 1; !hay && columna >= 0; --columna) {
            if(tablero[f][columna]) {
                hay = true;
                tablero[f][c] = false;
                --restantes;
                camino.push("Izquierda");
                resultado = resolver(f, columna, tablero, restantes, camino, "izquierda");
                if(resultado[0]) return new Array(true, camino);
                else {
                    ++restantes;
                    tablero[f][c] = true;
                    camino.pop();
                }
            }
        }
    }
    return new Array(false);
}

También te puede interesar...

Tags , , , ,

El problema de la balsa


Fatal error: Maximum execution time of 1 second exceeded in /home/kamugo/public_html/wp-content/plugins/jetpack/modules/sharedaddy/sharing-sources.php on line 71