Tag: programación

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 conjunto de Mandelbrot

Un fractal, como muchos sabréis, es una estructura que se repite a diferentes escalas. El fractal más conocido es el de Mandelbrot, estudiado por el matemático polaco, ya fallecido, Benoît Mandelbrot, recientemente fallecido, en la década de los 70 del siglo pasado. Mandelbrot pensaba que lo que él estaba estudiando no interesaba a nadie, ya que todos los demás matemáticos se centraban en estructuras “suaves y regulares”. Para definir estas nuevas estructuras acudió a un diccionario de latín, hasta encontrar un adjetivo que describía las piezas irregulares de una piedra que ha sido lanzada: «fractus, fracta, fractum».

Los fractales no son sólo cosa de las matemáticas, sino que aparecen en muchos lugares de la naturaleza, como en las hojas de los helechos, en las ramas de los árboles, en el brécol, etc. Un caso extraordinario de fractal lo podemos encontrar en el Romanescu, una mezcla de brécol y coliflor.

Romanescu, un fractal en la naturaleza Matemáticamente, el conjunto de Mandelbrot se define como:
  • Tenemos c, un número complejo cualquiera.
  • Tenemos la sucesión por inducción siguiente \left \{  \begin{matrix}  z_0 & = & 0 \qquad \ & \qquad \\  z_{n+1} & = & z_n^2 + c &  \end{matrix} \right.

Si la sucesión queda acotada, podemos decir que el punto c es parte del conjunto.

Pero dejemos las matemáticas y vamos a ver como se ve el conjunto gráficamente. Lo he generado utilizando jQuery y HTML5. Podéis aumentarlo para ver la autosimilitud haciendo clic encima. Es probable que no lo podáis leer desde el lector RSS o utilizando un navegador antiguo.

Tu navegador no es compatible con Canvas, deberías utilizar uno más moderno.

Para acabar, la entrevista de Benoît en el programa Redes

Como siempre, dejo el código para los programadores curiosos

// Clase timer para contar el tiempo de ejecucion
var timer = {
   time: 0,
   now: function(){ return (new Date()).getTime(); },
   start: function(){ this.time = this.now(); },
   since: function(){ return this.now()-this.time; }
}

// Variables globales
// Variables del tamaño de Canvas
var width = 500;
var height = 500;
// Precisión de los pixels (1 es lo más preciso)
var pixels = 1;

// Coordenadas iniciales
var xmin = -2;
var xmax = 1;
var ymin = -1.5;
var ymax = 1.5;

// Stride
var stridex = ((xmax - xmin) / height) * pixels;
var stridey = ((ymax - ymin) / width) * pixels;

// Aumentos
var zoom = 4;
var aumentos = 0;

// Iteraciones
var maxIt = 200;

function render() {
   
    timer.start();
   
    // Cargamos canvas
    // Obtenemos el objeto Canvas
    var canvas = document.getElementById('canvas');
    var context = false;
    // Obtenemos el contexto 2d
    if(canvas && canvas.getContext('2d')) {
        context = canvas.getContext('2d');
    }
    if(context){
        // Si existe empezamos a dibujar
        // Cambiamos el tamaño, por si este ha cambiado
        canvas.width = width;
        canvas.height = height;

        for(var x0 = xmin, i = 0; i < height; i += pixels, x0 += stridex){
            for(var y0 = ymin, j = 0; j < width; j += pixels, y0 += stridey) {
                var x = 0;
                var y = 0;
                var it;
                for(it = 0; x*x + y*y < 4 && it < maxIt; ++it) {
                    var xtemp = x*x - y*y + x0;
                    y = 2*x*y + y0;
                    x = xtemp;
                }
                if(it >= maxIt) {
                    context.fillStyle = "rgba(0,0,0,1)";
                    context.fillRect(i,j,pixels,pixels);
                }
                else {                 
                    context.fillStyle = "rgba(0,0,0," + it / maxIt + ")";
                    context.fillRect(i,j,pixels,pixels);
                }
            }
        }
    }

    return timer.since();
}

$(document).ready(function() {
   
    var since = render();
    $("#mandInfo").append("Renderizado en " + since + " ms</br>");
   
    $("#canvas").click(function(e){
        // Obtengo las coordenadas del clic dentro de canvas
        var x = Math.floor((e.pageX-$("#canvas").offset().left));
        var y = Math.floor((e.pageY-$("#canvas").offset().top));
        // Las transformo a las coordenadas actuales
        var realx = xmin + x * stridex;
        var realy = ymin + y * stridey;
       
        // Pongo los nuevos límites de las coordenadas
        var temp_xmin = xmin;
        var temp_xmax = xmax;
        var temp_ymin = ymin;
        var temp_ymax = ymax;
        xmin = realx - (temp_xmax - temp_xmin) / zoom;
        xmax = realx + (temp_xmax - temp_xmin) / zoom;
        ymin = realy - (temp_ymax - temp_ymin) / zoom;
        ymax = realy + (temp_ymax - temp_ymin) / zoom;
       
        // Recalculo los Strides
        stridex = ((xmax - xmin) / height) * pixels;
        stridey = ((ymax - ymin) / width) * pixels;
        ++aumentos;
        since = render();
        $("#mandInfo").append("Aumentado en " + since + " ms</br>");
    });
});
Para que funcione, en el HTML hay que importar la librería jQuery. Después necesitamos el canvas de HTML5: <canvas id="canvas" width="500" height="500"></canvas> (tiene que tener identificador canvas). Por último y opcionalmente, un div donde se muestra el tiempo de renderizado: <div id = "mandInfo"></div>.

También te puede interesar...

Tags , , , , ,

Tu uso de cada letra

Ya os hablé una vez de cuanto se usaba cada letra de media en Español, pero eso solo eran datos. Hoy os traigo algo más entretenido para que comprobéis que porcentaje de letras utilizáis vosotros mismos. Solo tenéis que escribir lo que queráis en el cuadro de texto y podréis ver un gráfico con los porcentajes de cada letra. Si el texto es muy largo seguramente se parezca a la media que os conté la otra vez.

¿Se parece a los porcentajes del otro post? ¿Cuál es la letra que más utilizas?

El programa no cuenta caracteres extraños como á, é, ñ, ç, … ¡viva el inglés! Recordad que necesitáis estar en el navegador y no en el lector RSS para poder probarlo.

Escribe el texto que quieras

Para los que quieran saber como funciona el programa en Javascript, os lo dejo aquí el código, he utilizado jQuery y JSCharts para generar los gráficos. El script principal es el siguiente:

$(document).ready(function() {
    var v = new Array(26);
    var abecedario = new Array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z');
    // Cada vez que dejemos de pulsar una tecla
    $("#texto_letras_j").keyup(function() {
        $("#contador_letras_j").text("");
        for(i = 0; i &lt; v.length; ++i) v[i] = 0;
        var arr = $("#texto_letras_j").val();
        var cont = 0;
        // Recorremos todo el texto para analizar cada letra
        for(i = 0; i &lt; arr.length; ++i) {
            // Comprobamos que sea una letra y la añadimos
            if(/[a-z]/.test(arr.charAt(i))){
                ++cont;
                ++v[arr.charCodeAt(i)-'a'.charCodeAt(0)];
            }
            else if(/[A-Z]/.test(arr.charAt(i))) {
                ++cont;
                ++v[arr.charCodeAt(i)-'A'.charCodeAt(0)];
            }
        }
        if(cont != 0) {
            var myData = new Array(26);
            // Escribimos los resultados
            for(i = 0; i &lt; v.length; ++i) {
                var res = 100*v[i]/cont;
                myData[i] = [abecedario[i], res];
                $("#contador_letras_j").append("&lt;li&gt;"+abecedario[i]+": "+res.toFixed(3)+"%&lt;/li&gt;");
            }
            // Generamos el gráfico de JSCharts
            var myChart = new JSChart('grafico_letras_j', 'bar');
            myChart.setTitle('Uso letras');
            myChart.setAxisNameY('%');
            myChart.setAxisNameX('Letras');
            myChart.setDataArray(myData);
            myChart.setBarColor('#42aBdB');
            myChart.setBarOpacity(0.8);
            myChart.setBarBorderColor('#D9EDF7');
            myChart.setBarValues(false);
            myChart.setTitleColor('#8C8383');
            myChart.setAxisColor('#777E81');
            myChart.setAxisValuesColor('#777E81');
            myChart.setSize(616, 321);
            myChart.draw();
    }
    else {
        $("#grafico_letras_j").text("");
    }
    });
});

Además, para que funcione, debemos añadir lo siguiente al HTML

El resultado final del HTML será el siguiente:

<script src="/jquery.js" type="text/javascript"></script>
<script src="/jscharts.js" type="text/javascript"</script>
<script src="/cuenta_letras.js" type="text/javascript"></script>
<textarea id="texto_letras_j"></textarea>
<div id="grafico_letras_j>Escribe el texto que quieras</div>
<ul id="contador_letras_j"></ul>
  • Los scripts Javascript.
  • El cuadro de texto (texto_letras_j).
  • Un div para colocar el gráfico (grafico_letras_j).
  • Una lista y un párrafo (contador_letras_j) para guardar los resultados.

También te puede interesar...

Tags , ,

Programadores maltratados

Hoy os traigo un vídeo sobre el inferno de los programadores. Están en la calle, con carteles de cartón como si estuvieran pidiendo.
Por si no sabéis ingles, os traduzco los carteles, por orden.

  • Estoy dolido.
  • Llevamos 4 meses en un programa de 5 y he recibido los requisitos finales ayer (y han vuelto a cambiar!)
  • Gasto la mitad de mi día en reuniones de como trabajar mejor (en vez de trabajar).
  • Mi jefe leyó en una revista que los programadores usando (otro) lenguaje de programación eran dos veces más productivos, así que compró una copia y cortó por la mitad el programa (lo destrozó).
  • Cada día mi jefe cambia de opinión sobre lo que estamos programando.
  • La gente no para de decirme que les arregle el correo, así que no tengo tiempo para programar-
  • Mi padre no tiene más tiempo para mi.
  • Le dijeron a mi jefe que podían hacer nuestra siguiente versión en la mitad de tiempo y por la mitad de dinero, él les creyó, pero ahora han gastando todo su presupuesto y todo el tiempo y…
  • Está aun a la mitad. Ahora se han ido y su código es un desastre, tenemos que arreglarlo y acabar lo que empezaron.

También te puede interesar...

Tags , ,