Informática geek, matemáticas, pensamiento crítico y alguna otra cosa de vez en cuando.

2010-01-30

Aplicando efectos de forma radial

Hay un filtro para GIMP que puede dar buen resultado aplicado a logos u otros propósitos espectaculares, pero cuya utilidad se ve limitada por la forma en que es aplicado. Estoy hablando de Viento.

El filtro Viento sólo se puede aplicar horizontalmente, hacia la izquierda o hacia la derecha. Esto limita mucho su campo de aplicación, pese a que si pudiera aplicarse de forma radial desde un punto de la imagen hacia los bordes, se podrían conseguir efectos interesantes.

Aquí vamos a ver cómo esquivar esa limitación y aplicar el filtro radialmente. Para ello nos ayudaremos de otro filtro presente en ese mismo menú: Coord. polares.

Hace nada compilé un paquete de Gimp 2.6.8 para Debian Lenny, así que es la versión que vamos a usar en este tutorial. En este caso apenas hay diferencias respecto a la 2.4, pero trataré de explicar las que recuerde.

Primero, dejemos claro el objetivo que perseguimos mediante un par de ejemplos:

Logotipo creado con Archivo/Crear/Logotipos/Calor resplandeciente
Logotipo creado con Archivo > Crear > Logotipos > Calor resplandeciente... (en Gimp 2.4 los logotipos están en el menú Xtns de la ventana de herramientas).
Logotipo con el efecto Viento aplicado de forma radial
Resultado de aplicar el efecto Viento de forma radial
Peluso
Peluso
Peluso con efecto viento radial
Peluso con efecto viento radial

En el caso del logotipo, para que aparezca el texto bien perfilado he aplicado el efecto solamente a la capa central, ya que la superpuesta ayuda a perfilar; he hecho la prueba de aplanar primero la imagen para aplicar el efecto a todo, pero se emborronaba mucho.

Para ver si el efecto queda aceptable o no, a modo de quickie, bastará con aplicar los pasos cuarto, quinto, sexto, séptimo y noveno (transformación, giro, aplicar efecto, deshacer giro, deshacer transformación), que son los que comprenden la esencia del método. Nos quedará un círculo en pequeño en el centro, pero con suerte bastará para que podamos decidir si vale la pena intentar el método completo o no.

Paso cero: ¿Tiene nuestra capa canal alfa? ¿Lo necesita? ¿Hay que ajustar el color de fondo? ¿Hay que duplicar la capa?

Este tutorial puede aplicarse tanto a capas con canal alfa, como a capas sin él. Al final del proceso, se nos puede haber contaminado la imagen con píxels que no pertenecen a ella, que serán transparentes si hay canal alfa, o del color del fondo si no lo hay. Si tiene alfa, después se puede colocar la imagen original debajo para disimular, pero si se trata de un color plano, basta con asignárselo al color de fondo y nos ahorraremos algún paso. Así que, si no tiene canal alfa, decidamos primero si lo añadimos o no y, en caso de que no, ajustemos el color de fondo. Por ejemplo, si es una capa que contiene un logo en blanco sobre fondo verde homogéneo, se puede ajustar el color de fondo a ese verde y trabajar sin canal alfa. Si lo vamos a hacer con una fotografía, como la de Peluso, lo que mejor resultado proporcione será probablemente duplicar la capa y añadir alfa si no tiene, de manera que la imagen original quede debajo, para que así las partes contaminadas por transparencia dejen a la vista dicha imagen. En cualquier caso, es una buena idea tener una copia de la capa original como referencia, para facilitar el último paso de recorte.

Primer paso: Recentrar

Nuestro primer paso será escoger cuál va a ser el punto central del que van a salir todos los «rayos». En el caso de Peluso, he escogido el punto (284, 276). El filtro Coord. polares toma como centro el de la capa con la que trabaja, así que vamos a ampliar el tamaño de manera que dichos puntos queden en el centro. Si queremos que el centro coincida con el de la imagen, este paso no será necesario. En el caso del logo, he optado por ello y me lo he saltado.

La forma de conseguir el nuevo centro es: averiguar las distancias desde el centro escogido (en coordenadas relativas a la capa) hasta ambos lados de la capa, averiguar la mayor de las dos, y agrandar la capa al doble de dicha distancia, recolocándola de forma que nuestro centro elegido caiga en el centro de la versión agrandada. Esto se hace tanto para la coordenada horizontal como para la vertical. Aquí, «agrandar» no se refiere a escalar, sino a cambiar el tamaño extendiendo el borde. Es la operación que en el Gimp se llama «Tamaño del borde de capa...».

La imagen de Peluso tiene 640×480 píxels. La distancia del centro elegido al borde izquierdo es 284; al borde derecho, es 640-284=356. Por tanto, tenemos que expandir la capa por su lado izquierdo dejando una imagen de 356·2=712 píxels de ancho. Repetimos lo mismo con las coordenadas verticales: la distancia al borde superior es 276 y al borde inferior es 480-276=204 píxels, por lo tanto está más cerca del inferior, luego habrá que expandirlo por debajo hasta que la imagen llegue a 276·2=552 píxels de alto. Es decir, tras redimensionar la capa, ésta ha de quedar pegada a la esquina superior derecha. Así que vamos a Capa > Tamaño del borde de capa, quitamos la cadenita que liga el tamaño vertical y el horizontal e introducimos en Anchura, 712, y en Altura, 552 (píxels, claro). En Desplazamiento, como queremos llevarla a la esquina superior derecha, subimos X al máximo, que es 72, e Y la dejamos a 0. Pulsamos Redimensionar. Ahora el centro de la capa ya es el que queremos.

Segundo paso: Agrandar

Dada la manera en que vamos a usar el filtro Coord. polares, vamos a tropezar con el problema de que la imagen final va a ser más pequeña que la inicial. Concretamente, con forma de un círculo cuyo diámetro es la menor de las dimensiones de la capa. Para compensar este efecto, hemos de agrandarla de antemano de forma que la parte original quede inscrita dentro de dicho círculo.

Resultado de aplicar el filtro Coord. polares y su inverso. Arriba, sin agrandar la capa primero; abajo, agrandándola.
Resultado de aplicar el filtro Coord. polares y su inverso. Arriba, sin agrandar la capa primero; abajo, agrandándola. Obsérvese que en la de abajo la imagen original queda completa.

Este tamaño extra se aplica incluso si ya la hemos agrandado en el primer paso, y después de hacerlo; así el botón Centrar hará lo que esperamos.

Para saber el radio del círculo dentro del cual estará nuestra capa inscrita, hemos de echar mano del teorema de Pitágoras. Primero, hay que hallar el centro; esto lo hacemos dividiendo los tamaños horizontal y vertical por 2. Con la imagen de Peluso, el horizontal es 356 y el vertical, 276. El punto más alejado de dicho centro es la esquina (todas ellas), así que hay que calcular la distancia a la misma. Aplicamos Pitágoras: (356²+276²)½ ~= 450,45. Al final del proceso, debido a errores de precisión acumulados se colarán unos pocos píxels indeseados; para compensarlo, añadimos un 1% (el error máximo que he observado no llega a 0,4% pero más vale estar seguros, ya que va a ser una diferencia pequeña). Redondeamos por lo alto para estar más seguros aún. Buscaremos, pues, un círculo de 455 píxels de radio, o sea, 455·2=910 píxels de diámetro, así que agrandamos la capa para que sea un cuadrado capaz de circunscribir dicho círculo, es decir, le damos un tamaño de 910×910. Para ello, vamos de nuevo a Capa > Tamaño del borde de capa, quitamos la cadenita, introducimos Anchura = 910, Altura = 910 y pulsamos el botón Centrar para que nos centre el contenido actual. Si hemos escogido un centro distinto, podemos ver el resultado un poco descentrado al pulsar el botón; eso es normal y no debe preocuparnos, pero nuestro centro sí debe estar en el centro del cuadrado resultante; si no es así, quizá hemos colocado la capa en el cuadrante incorrecto en el paso anterior y hay que volver atrás. Si todo ha ido bien, pulsamos Redimensionar.

Para el logo, de 526×238, los valores son (263²+119²)½ ~= 288,67, que multiplicado por 2,02 (el doble más el 1%) y redondeado al alza nos da que la capa debe ser de 584×584.

Tercer paso: Extender los bordes

La capa del logo con la que vamos a trabajar no llega hasta los bordes, así que si se contamina un borde con transparencia a causa de los errores de precisión, no pasa nada; en ese caso podemos pasar al paso siguiente. El caso de Peluso es distinto, porque la fotografía sí que llega hasta los bordes. Si no nos preocupa que se haga un poco transparente en los bordes, podemos saltar este paso. Si estamos aplicando el truco descrito en el Paso Cero, dejando una copia de la imagen en la capa inferior, no lo necesitaremos. Si el borde queda mal incluso al usar esa estratagema, podemos probar con el truco aquí descrito.

La intención es extender cada borde a su correspondiente espacio vacío. No conozco ninguna forma que no sea tediosa. La idea es seleccionar la fila de píxels superior (una selección de Ancho×1), copiarla y pegarla en el espacio vacío superior, escalándola sólo verticalmente y moviéndola para cubrir la totalidad del mismo. Para ver lo que hacemos, es preferible haber hecho primero Imagen > Ajustar lienzo a las capas. Cuando hayamos terminado, hacemos lo mismo con la fila de píxels inferior. Después, con la fila de píxels izquierda (una selección de 1×Alto) y por último, con la derecha. Al hacer la izquierda y la derecha, cogeremos también lo que ya hemos extendido al hacer la parte de arriba y la de abajo.

Por ejemplo, así queda Peluso tras este paso:

Peluso con los bordes extendidos
Peluso con los bordes extendidos de la forma recién descrita.

Cuarto paso: Polares a Cartesianas(*)

Vamos al meollo del asunto. Abrimos el filtro Coord. polares y desmarcamos la casilla «A polares», dejando todo lo demás por defecto (profundidad circular 100%, ángulo de desfase 0, no mapear al revés, sí mapear desde arriba). Obtenemos una versión deformada de la imagen de partida. La transformación interpreta la imagen original como si estuviera en coordenadas polares y representa en el eje X, el ángulo, y en el Y, el radio relativo a la menor de las dos dimensiones de la imagen(*). Es decir, todos los efectos que apliquemos verticalmente se harán sobre el radio. Mmmm, eso se parece a lo que queremos.

Animación que reproduce el efecto de aplicar el filtro Polares a Cartesianas
Actualización 2-2-2010. Esta animación muestra qué transformación realiza el filtro Coord. Polares al aplicarlo a una imagen habiendo marcado las casillas «Mapear al revés» y «Mapear desde arriba» y con la casilla «A polares» desactivada.

Quinto paso: Rotación de 90° a la izquierda

Pero el efecto Viento no opera en dirección vertical, sino únicamente horizontal, así que antes de aplicarlo, primero rotamos la imagen 90° hacia la izquierda con Capa > Transformar > Rotar 90° en sentido antihorario.

Sexto paso: Aplicar el efecto

Ahora es cuando aplicamos el filtro Viento. Hemos de jugar con los ajustes hasta que consigamos lo que buscamos. En el caso de Peluso, he usado Borde Trasero, Umbral 12 y Fuerza 30, dejando Estilo y Dirección intactos. Con el logo, he usado Borde Delantero, Umbral 10 y Fuerza 100.

Séptimo paso: Rotación de 90° a la derecha

Para poder devolver la imagen a su estado inicial con el efecto aplicado, tenemos que deshacer las transformaciones que hemos acumulado. Primero, la giramos a la derecha 90° con Capa > Transformar > Rotar 90° en sentido horario.

Octavo paso: Ampliar (Antialias primera parte)

El filtro Viento produce unas líneas muy finas, de un píxel de ancho, lo cual causa problemas de aliasing al convertir la imagen de nuevo a polares(*), que sería el paso siguiente si no fuera por ese problema. Según la imagen, podemos tener suerte o no, y no he encontrado otra forma de averiguarlo que el ensayo y error. Con Peluso no lo he necesitado; con el logo, sí.

Para conseguir un antialiasing que palie esa pega, el truco que empleamos es ampliar la imagen en este momento, de tal forma que las líneas que se convertirán de cartesianas a polares(*) sean más gruesas, para que después, al reducir con Sinc una vez convertido, sea la propia interpolación la que consiga el antialias. Así que, si hemos tenido en un intento anterior problemas de aliasing, ahora es el momento de ampliar la capa usando Capa > Escalar capa. Recomiendo un valor que no sea un múltiplo exacto como 200%, porque lo he probado y ha sido un fracaso; en cambio, usando un 121% de ampliación he tenido éxito.

Aquí se ve la diferencia sin antialias y con él:

Sin antialias Con antialias
Comparación entre no usar antialias y usarlo

Noveno paso: Cartesianas a Polares(*)

Abrimos de nuevo Coord. polares y marcamos la casilla «A polares» sin tocar nada más. En la previsualización, veremos ya un anticipo del resultado final. Aceptamos.

Animación que reproduce el efecto de aplicar el filtro Polares a Cartesianas
Actualización 2-2-2010. Esta animación muestra qué transformación realiza el filtro Coord. Polares al aplicarlo a una imagen habiendo marcado las casillas «Mapear al revés» y «Mapear desde arriba» y con la casilla «A polares» activada.

Décimo paso: Reducción (Antialias segunda parte)

Ahora hay que deshacer la ampliación realizada en el octavo paso, si la hemos hecho. Para ello, podemos usar como tamaño destino el tamaño de la imagen en píxels obtenido en el segundo paso (910×910 para Peluso).

Undécimo y último paso: Recortar

Ya solo falta recortar la capa. Esto puede ser complicado si no tenemos una capa de referencia con el tamaño y la posición originales. Si contamos con ella, podemos seleccionarla, usar Capa > Transparencia > Alfa a selección, y luego elegir la capa procesada y usar Capa > Recortar a la selección. Esta última opción no recuerdo que estuviera en Gimp 2.4, así que a quien lo tenga puede que le toque hacer el recorte artesanalmente.

(*): Yo diría que la caja de selección «A polares» está al revés: que cuando está desmarcada es cuando convierte a coordenadas polares y viceversa, representando en un eje el ángulo y en el otro el radio. Por tanto, la primera transformación sería de cartesianas a polares y la transformación inversa convertiría de polares a cartesianas, y no al revés como indica la casilla. Agradecería opiniones al respecto.

Variaciones

El efecto Viento no es el único que se beneficia de esta técnica, así que hay otras opciones para los pasos quinto a séptimo. Otro efecto que no se puede aplicar radialmente es Desplazamiento, aunque en este caso tiene la opción de aplicarlo tanto horizontal como verticalmente, por lo cual si queremos probarlo podemos omitir el paso de la rotación de 90°. No he encontrado aún una utilidad al resultado. Otro posible uso es el Desenfoque gaussiano, ajustando el radio X a cero. Más efectos curiosos: Pixelizar, Mosaico de cristal, Ondular, Borrar las otras filas... Lo que se le ocurra a cada uno.

Nota final

Después de escribir este tutorial, me he dado cuenta de que alguien ya había escrito uno similar: http://www.gimpusers.com/tutorials/rays-of-light-behind-text.html. Sin embargo, he preferido publicarlo porque proporciona valor añadido al explicar cómo recentrar y cómo ampliar la capa en caso de que no sea un logo sino otro tipo de imagen, y explica un método de antialiasing más sofisticado que el que sugiere el autor de ese otro tutorial. El hecho de que ambos tutoriales consten de once pasos es mera coincidencia.

2010-01-28

Solución al problema de la probabilidad de cada longitud

(English version available)

En la entrada sobre IMAP se preguntaba por la probabilidad de cada posible longitud de la cadena resultante en el generador de palabas al azar. El bucle tenía esta forma:

  for ($i = 0; $i < 7 + mt_rand(0, 4); $i++) /* añadir un carácter */ ;

La clave está en que el número extraído que sirve como condición de final de bucle puede variar en cada iteración. Es diferente de un bucle similar que fijara el número de antemano, porque entra en juego la intersección de sucesos. Veamos por qué y cómo.

En el momento en que $i alcanza el valor 7, si el valor de mt_rand es 0 entonces el bucle termina; si es cualquier otro valor, continúa. Es evidente que la probabilidad de que la longitud sea 7 es 1/5 = 20%.

Cuando el valor de $i es 8, hace falta que mt_rand devuelva 0 ó 1 para que el bucle termine, lo cual ocurrirá dos de cada cinco veces. Sin embargo, para que la longitud alcance el valor 8 es condición que primero mt_rand haya devuelto un valor entre 1 y 4, lo cual ocurrirá 4 de cada 5 veces. No son sucesos independientes. Por tanto, la probabilidad combinada es 4/5 · 2/5 = 8/25 = 32%.

Para que $i llegue a 9, se tienen que dar a la vez que mt_rand devuelva un valor entre 1 y 4 la primera vez, y un valor entre 2 y 4 la segunda vez. Además, el bucle parará cuando mt_rand esté entre 0 y 2, lo cual ocurrirá 3 de cada 5 veces. Combinando las probabilidades, tenemos P(longitud 9) = 4/5 · 3/5 · 3/5 = 36/125 = 28,8%.

Con el mismo razonamiento, la probabilidad de que llegue a 10 es 4/5 · 3/5 · 2/5 · 4/5 = 96/625 = 15,36%.

La que queda podemos calcularla bien siguiendo el mismo razonamiento, ahora que le hemos cogido carrerilla, o bien restando de 1 todas las anteriores: 4/5 · 3/5 · 2/5 · 1/5 · 5/5 = 24/625 = 3,84% = 100% - 20% - 32% - 28,8% - 15,36%.

Resumiendo:

  • P(longitud 7) = 20%
  • P(longitud 8) = 32%
  • P(longitud 9) = 28,8%
  • P(longitud 10) = 15,36%
  • P(longitud 11) = 3,84%

O sea, será 8 casi una de cada tres veces, seguido de cerca por 9, luego 7, luego 10, y unas pocas veces llegará a longitud 11. Como siempre he dicho, la probabilidad no es intuitiva.

Este programa ayuda a verificar la corrección de los números:

<?php

  $MAX = 10000000;

  $arr = array(0, 0, 0, 0, 0);

  for ($n = 0; $n < $MAX; $n++)
  {
     for ($i = 0; $i < mt_rand(0, 4); $i++)
       ;
     $arr[$i]++;
  }

  $l = strlen($MAX);
  for ($i = 0; $i < 5; $i++)
  {
    printf("%2d -> %{$l}d/$MAX = %f%%\n", $i+7, $arr[$i], $arr[$i]/$MAX*100);
  }

?>

Aquí el resultado de una ejecución de muestra:

 7 ->  2000626/10000000 = 20.006260%
 8 ->  3198181/10000000 = 31.981810%
 9 ->  2879481/10000000 = 28.794810%
10 ->  1538148/10000000 = 15.381480%
11 ->   383564/10000000 = 3.835640%

Solution to the probability of lengths problem

In the previous IMAP upload post, I asked about the probability of each possible length of the resulting string in the random words generator. The loop had this structure:

  for ($i = 0; $i < 7 + mt_rand(0, 4); $i++) /* add one character */ ;

The key is that the loop exit condition is checked against (probably) different values each time. It's different from a similar loop in which the random number is fixed beforehand, because here the intersection of events comes into play, Let's see why and how.

As soon as $i reaches 7, if the value of mt_rand is 0 then the loop finishes; if it's any other value, it goes on. It's obvious that the probability of the length being 7 is 1/5 = 20%.

When the value of $i is 8, it's necessary for mt_rand to return either 0 or 1 for the loop to end, which will happen one two out of five times. However, for the length to reach the value 8 it's a condition that first mt_rand returns a value between 1 and 4, which will happen 4 out of 5 times. They are not independent events. Therefore, the combined probability is 4/5 · 2/5 = 8/25 = 32%.

For $i to reach 9, it must happen simultaneously that mt_rand returns a value between 1 and 4 the first time, and a value between 2 and 4 the second time. Furthermore, the loop will end when mt_rand is between 0 and 2, which wil happen 3 out of 5 times. Combining the probabilities, we have P(length 9) = 4/5 · 3/5 · 3/5 = 36/125 = 28.8%.

By the same reasoning, the probability for it to reach 10 is 4/5 · 3/5 · 2/5 · 4/5 = 96/625 = 15.36%.

The remaining one can be calculated either following the same reasoning, now that we got the trick, or by subtracting all the previous probabilities from 1: 4/5 · 3/5 · 2/5 · 1/5 · 5/5 = 24/625 = 3.84% = 100% - 20% - 32% - 28.8% - 15.36%.

To sum up:

  • P(length 7) = 20%
  • P(length 8) = 32%
  • P(length 9) = 28.8%
  • P(length 10) = 15.36%
  • P(length 11) = 3.84%

That is, it will be 8 almost one out of three times, closely followed by 9, then 7, then 10, and a few times it will reach 11. As I have always said, probability is not intuitive.

This program helps verifying the correctness of the numbers:

<?php

  $MAX = 10000000;

  $arr = array(0, 0, 0, 0, 0);

  for ($n = 0; $n < $MAX; $n++)
  {
     for ($i = 0; $i < mt_rand(0, 4); $i++)
       ;
     $arr[$i]++;
  }

  $l = strlen($MAX);
  for ($i = 0; $i < 5; $i++)
  {
    printf("%2d -> %{$l}d/$MAX = %f%%\n", $i+7, $arr[$i], $arr[$i]/$MAX*100);
  }

?>

Sample output:

 7 ->  2000626/10000000 = 20.006260%
 8 ->  3198181/10000000 = 31.981810%
 9 ->  2879481/10000000 = 28.794810%
10 ->  1538148/10000000 = 15.381480%
11 ->   383564/10000000 = 3.835640%

2010-01-26

Subida automática de archivos a GMail mediante IMAP

(English version available)

Hace un tiempo había una librería llamada libgmail capaz de comunicarse con GMail usando su protocolo propietario. Sin embargo, los protocolos propietarios tienen un problema muy grave: pueden cambiar en cualquier momento sin previo aviso, y cuando eso ocurre, los que han hecho la ingeniería inversa tienen que averiguar qué cambios se han producido para adaptarlos. Además, hay una norma expresa en los términos de servicio de Google prohibiendo el acceso «por ningún otro medio distinto de la interfaz facilitada por Google». Si se combina eso con el hecho de que libgmail está abandonado desde hace tiempo, puede uno imaginarse el resultado: libgmail ya no se puede utilizar.

Sin embargo, hay otras maneras de usar GMail para subir archivos adjuntos de forma automática. La que probablemente proporcione mayor flexibilidad es usar el protocolo IMAP para realizar las transferencias. El acceso IMAP es proporcionado explícitamente por GMail para que los usuarios no necesiten usar la interfaz web y puedan usar un cliente de email que soporte IMAP para manejar el correo, por lo tanto se puede argumentar que el uso de IMAP es acorde a los términos de servicio. No soy abogado, sin embargo, así que pregunte a uno si quiere una garantía legal.

Por desgracia, no hay actualmente ninguna librería similar a libgmail con soporte IMAP en vez del protocolo propietario de GMail. [Actualización 2011-03-09: Me acabo de enterar de que hay una nueva versión de GMailFS que utiliza el protocolo IMAP. Sin embargo, es un sistema de archivos para Linux, no una utilidad de línea de comandos compatible entre sistemas. No conozco aún una herramienta de línea de comandos que esté disponible para varios sistemas, aparte de la aquí presentada.] He escrito un programa en PHP a modo de prueba de concepto de una herramienta así. Es un ejemplo completo que crea en una cuenta de GMail un mensaje con la etiqueta «ftp» y un archivo adjunto, cuyo tipo MIME es «application/octet-stream». El programa requiere que la extensión IMAP esté instalada en PHP. En Debian Lenny, eso significa instalar el paquete php5-imap.

El acceso IMAP debe estar habilitado en la cuenta destino antes de empezar. La etiqueta 'ftp' debe existir previamente, así que debe ser creada antes de intentar subir ningún archivo. Después de la subida, se puede recuperar el archivo mediante la interfaz web de GMail.

Un inconveniente de este sistema comparado con libgmail es que, puesto que se usa la codificación Base64 para los archivos, el tiempo de subida es cerca de un 33% más. Sería posible en teoría subir archivos usando la codificación Base85, que reduce el tiempo extra a un 25%. Sin embargo, en ese caso la recuperación del archivo requeriría un decodificador Base85 y probablemente no sería posible simplemente hacer clic para descargarlo.

He aquí el código PHP, diseñado para usarse con la versión de línea de comandos. La forma de uso es:
php imap-upload.php <archivo_a_subir>

<?php

/**********************************
 *
 * Configuration section
 *
 */

// User name (full email address)
$usr = 'user@gmail.com';

// Password. Leave unset for being asked (sorry, with echo - yuck!)
unset($pwd);

// IMAP server
$svr = 'imap.gmail.com';

// IMAP port
$prt = 993;

// Folder / Tag (must exist prior to running this)
//$folder = '[Gmail]/Drafts'; // This one would use the actual GMail drafts folder.
                              // NOTE: must be localized, e.g. in spanish the name
                              // is '[Gmail]/Borradores'
$folder = 'ftp';  // Same tag used by gmailftpd.py

// Encoding for the filename string we are passing from the command line
$filename_enc = 'UTF-8';

/*
 *
 * End of configuration section
 *
 ***********************************/


// Encode the subject in MIME quoted-printable format as per RFC 2047
function encode_subject($title, $encoding)
{
  $ret = "=?$encoding?Q?";
  $linelength = 9; // length of "Subject: "

  for ($i = 0; $i < strlen($title); $i++)
  {
    if ($linelength >= 65)
    {
      $ret .= "?=\r\n =?$encoding?Q?";
      $linelength = 1; // length of initial space
    }

    if ($title[$i] >= ' ' and $title[$i] <= '~'
        and $title[$i] != '=' and $title[$i] != '?'
        and $title[$i] != '_')
    {
      if ($title[$i] == ' ')
        $ret .= '_';
      else
        $ret .= $title[$i];
      $linelength++;
    }
    else
    {
      $ret .= '=' . strtoupper(bin2hex($title[$i]));
      $linelength += 3;
    }
  }
  return $ret . '?=';
}

// quoted-string for parameters as per RFC 822
function quoted_string($string)
{
  return '"' . strtr($string, array("\\"=>"\\\\",
                                    "\""=>"\\\"",
                                    "\r"=>"\\\r",
                                    "\n"=>"\\\n")) . '"';
}

// grab 7-11 random lowercase letters
function randword()
{
  $result = '';
  for ($i = 0; $i < 7 + mt_rand(0, 4); $i++)
    $result .= chr(mt_rand(0, 25) + 97);
  return $result;
}

$filepath = $argv[1];

if (! isset($filepath))
  die("No filename specified to upload\n");

$filename = basename($filepath);

if ($prt == 993) $prt = ''; else $prt = ':' . $prt;

if (! isset($pwd))
{
  echo "pwd: ";
  $pwd = substr(fgets(STDIN), 0, -1); // remove extra \n
}

// Open the imap stream
$stream = imap_open("\x7B$svr$prt/ssl}$folder", $usr, $pwd);

// Report all possible errors
print_r(imap_errors());

// Exit on trouble
if ($stream === false) die("\nStopping\n");

$rnd1 = randword();
$rnd2 = randword();
$bndr = "------------" . randword() . randword();

$result = imap_append(
            $stream
            , "\x7B$svr$prt/ssl}$folder"
            , "From: $usr"
              . "\r\nTo: $rnd1@$rnd2.com"
              . "\r\nSubject: " . encode_subject($filename, $filename_enc)
              . "\r\nMIME-Version: 1.0"
              . "\r\nContent-type: multipart/mixed;"
              . "\r\n boundary=\"$bndr\""
              . "\r\n"
              . "\r\nThis is a multi-part message in MIME format."
              . "\r\n--$bndr"
              . "\r\nContent-Type: text/plain; charset=$filename_enc; format=flowed"
              . "\r\nContent-Transfer-Encoding: quoted-printable"
              . "\r\n"
              . "\r\n" . imap_8bit($filename)
              . "\r\n"
              . "\r\n--$bndr"
              . "\r\nContent-Type: application/octet-stream;"
              . "\r\n name=" . quoted_string($filename)
              . "\r\nContent-Transfer-Encoding: base64"
              . "\r\nContent-Disposition: attachment;"
              . "\r\n filename=" . quoted_string($filename)
              . "\r\n"
              . "\r\n" . imap_binary(file_get_contents($filepath))
              . "--$bndr--"
              . "\r\n"
              . "\r\n"
            );

if ($result)
  echo "Succeeded adding file\n";
else
  print_r(imap_errors());

$check = imap_check($stream);
echo "There are now ". $check->Nmsgs . " messages in the $folder folder\n";

print_r(imap_errors());

print_r(imap_alerts());

imap_close($stream);

?>

Y de regalo un pequeño rompecabezas. El generador de letras al azar puede generar entre 7 y 11 caracteres. Suponiendo que el generador genera números enteros uniformemente distribuidos entre 0 y 4 inclusive, ¿cuál es la probabilidad de cada una de las longitudes? Una pista: no es 1/5.

Automated upload to GMail via IMAP

Some time ago, there was a Python library called libgmail which was able to communicate with GMail using their proprietary protocol. However, proprietary protocols have a serious drawback: they can be changed at any time without prior notice, and when that happens, those who have reverse-engineered them have to figure out the changes. Furthermore, there's an explicit rule in Google's ToS forbidding access «by any means other than through the interface that is provided by Google». Combine it with the fact that libgmail has now been abandoned for a while, and you can figure out the result: libgmail is no longer usable.

There are, however, other ways of using GMail to do automated attachment uploads. The one that probably provides the most flexibility is to use the IMAP protocol to do the transfers. IMAP access is explicitly provided by GMail so that users do not need to use the web interface and can use an email client that supports IMAP to handle mail, thus it's arguable that using IMAP is in accordance with the ToS. I am not a lawyer, though, so ask one if you want to be sure.

Unfortunately, there's currently no library similar to libgmail which supports IMAP instead of the proprietary GMail protocol. [Update 2011-03-09: I just learned that there's a new version of GMailFS which uses the IMAP protocol. However, it is a filesystem for Linux, not a cross-platform command line utility. I don't know yet of a command line tool that is compatible across systems, besides the one presented here.] I've written a PHP program as a proof-of-concept of such a tool. It's a complete example that creates a message with the tag 'ftp', having an attached file with MIME type 'application/octet-stream', in a GMail account. The program requires the IMAP extension to be installed in PHP. In Debian Lenny, that means to install the package php5-imap.

IMAP access must be enabled in the target GMail account before starting. The files are tagged with the label 'ftp' which must already exist, so create it before trying to upload. After uploading, you can retrieve the file via the GMail web interface.

A drawback when compared to libgmail is that, as it uses Base64 encoding for files, the upload time is about 33% greater. It would be theoretically possible to upload files using Base85 encoding, which reduces the overhead to 25%. However, in that case the retrieval of the file would need a Base85 decoder and it would probably not be possible to just click on the file to download it.

Here's the PHP code, intended for being used with the PHP command line interface. Usage is:
php imap-upload.php <file_to_upload>

<?php

/**********************************
 *
 * Configuration section
 *
 */

// User name (full email address)
$usr = 'user@gmail.com';

// Password. Leave unset for being asked (sorry, with echo - yuck!)
unset($pwd);

// IMAP server
$svr = 'imap.gmail.com';

// IMAP port
$prt = 993;

// Folder / Tag (must exist prior to running this)
//$folder = '[Gmail]/Drafts'; // This one would use the actual GMail drafts folder.
                              // NOTE: must be localized, e.g. in spanish the name
                              // is '[Gmail]/Borradores'
$folder = 'ftp';  // Same tag used by gmailftpd.py

// Encoding for the filename string we are passing from the command line
$filename_enc = 'UTF-8';

/*
 *
 * End of configuration section
 *
 ***********************************/


// Encode the subject in MIME quoted-printable format as per RFC 2047
function encode_subject($title, $encoding)
{
  $ret = "=?$encoding?Q?";
  $linelength = 9; // length of "Subject: "

  for ($i = 0; $i < strlen($title); $i++)
  {
    if ($linelength >= 65)
    {
      $ret .= "?=\r\n =?$encoding?Q?";
      $linelength = 1; // length of initial space
    }

    if ($title[$i] >= ' ' and $title[$i] <= '~'
        and $title[$i] != '=' and $title[$i] != '?'
        and $title[$i] != '_')
    {
      if ($title[$i] == ' ')
        $ret .= '_';
      else
        $ret .= $title[$i];
      $linelength++;
    }
    else
    {
      $ret .= '=' . strtoupper(bin2hex($title[$i]));
      $linelength += 3;
    }
  }
  return $ret . '?=';
}

// quoted-string for parameters as per RFC 822
function quoted_string($string)
{
  return '"' . strtr($string, array("\\"=>"\\\\",
                                    "\""=>"\\\"",
                                    "\r"=>"\\\r",
                                    "\n"=>"\\\n")) . '"';
}

// grab 7-11 random lowercase letters
function randword()
{
  $result = '';
  for ($i = 0; $i < 7 + mt_rand(0, 4); $i++)
    $result .= chr(mt_rand(0, 25) + 97);
  return $result;
}

$filepath = $argv[1];

if (! isset($filepath))
  die("No filename specified to upload\n");

$filename = basename($filepath);

if ($prt == 993) $prt = ''; else $prt = ':' . $prt;

if (! isset($pwd))
{
  echo "pwd: ";
  $pwd = substr(fgets(STDIN), 0, -1); // remove extra \n
}

// Open the imap stream
$stream = imap_open("\x7B$svr$prt/ssl}$folder", $usr, $pwd);

// Report all possible errors
print_r(imap_errors());

// Exit on trouble
if ($stream === false) die("\nStopping\n");

$rnd1 = randword();
$rnd2 = randword();
$bndr = "------------" . randword() . randword();

$result = imap_append(
            $stream
            , "\x7B$svr$prt/ssl}$folder"
            , "From: $usr"
              . "\r\nTo: $rnd1@$rnd2.com"
              . "\r\nSubject: " . encode_subject($filename, $filename_enc)
              . "\r\nMIME-Version: 1.0"
              . "\r\nContent-type: multipart/mixed;"
              . "\r\n boundary=\"$bndr\""
              . "\r\n"
              . "\r\nThis is a multi-part message in MIME format."
              . "\r\n--$bndr"
              . "\r\nContent-Type: text/plain; charset=$filename_enc; format=flowed"
              . "\r\nContent-Transfer-Encoding: quoted-printable"
              . "\r\n"
              . "\r\n" . imap_8bit($filename)
              . "\r\n"
              . "\r\n--$bndr"
              . "\r\nContent-Type: application/octet-stream;"
              . "\r\n name=" . quoted_string($filename)
              . "\r\nContent-Transfer-Encoding: base64"
              . "\r\nContent-Disposition: attachment;"
              . "\r\n filename=" . quoted_string($filename)
              . "\r\n"
              . "\r\n" . imap_binary(file_get_contents($filepath))
              . "--$bndr--"
              . "\r\n"
              . "\r\n"
            );

if ($result)
  echo "Succeeded adding file\n";
else
  print_r(imap_errors());

$check = imap_check($stream);
echo "There are now ". $check->Nmsgs . " messages in the $folder folder\n";

print_r(imap_errors());

print_r(imap_alerts());

imap_close($stream);

?>

Here's a little bonus brainteaser. The generator of random lowercase letters can generate 7 to 11 characters. What's the probability of each length? Hint: it's not 1/5.

2010-01-23

Génera y sexa

¿A ustedes no les asombra
que diciendo rico y rica,
majo y maja, chico y chica,
no digamos hombre y hombra?
Y la frase tan oída
del marido y la mujer,
¿por qué no tiene que ser
el marido y la marida?
[...]
El sexo a hablar nos obliga
a cada cual como digo:
si es hombre, me voy contigo;
si es mujer, me voy contiga.
Melitón González (Pablo Perellada), El idioma castellano (fragmento)

Ya hace mucho que, en el esfuerzo por compensar el machismo tradicional en nuestra sociedad, ciertos grupos están intentando imponer el hembrismo como doctrina. Y no digo feminismo, porque feminismo es otra cosa. El objetivo parece ser la venganza a través del cambio de papeles, así que se trata de sustituir una dominación por la contraria.

En ese empeño de sobrecompensarla hasta el punto de llevarla al polo opuesto, uno de los más equivocados objetivos es la hembrización del lenguaje. Típicamente, se confunde género con sexo y las palabras de género masculino se fuerzan de forma artificial a una versión femenina inexistente. No digo que ello esté siempre mal; la lengua se rige por la tradición y la inexistencia de ciertas palabras puede deberse a la falta de uso previo, por lo que si surge la necesidad, es lógico que aparezcan.

Veamos unos ejemplos. El que maneja una bomba hidráulica para apagar incendios es un bombero; por tanto, si es ella, es bombera. Sí, puede sonarnos extraño, pero dudo que sea por otra razón que la falta de costumbre, pues es el mismo caso que con cajero y cajera, por decir uno. Otro ejemplo más sencillo: el que aboga es abogado y la que aboga, abogada. Aquí, además, contamos con un verbo cuyo participio ya pertenece a nuestro idioma, de modo que la palabra ya existía; por ejemplo, «la reforma abogada por los grupos...» vendría a significar «la reforma por la que los grupos abogan...». No es preciso agregar un vocablo inexistente para referirse a las que ejercen la abogacía.

El problema del hembrismo está en que arrambla con todo tipo de palabras, pese a los absurdos a los que conduce tal política (como con miembra*). Hasta tal punto llega el empeño, que también se han convertido al femenino palabras neutras. ¿Qué me dicen de jueza? Juez es una palabra de género común que no tiene siquiera una terminación clásicamente asociada al género masculino. ¿De quién fue la feliza* idea de apalear así a nuestro idioma? No me lo digan: de las hembristas.

Otro tanto ocurre con presidenta. Si el o la que preside es presidente, ¿a qué tanto empeño en amplificar las diferencias entre sexos, si lo que persigue el feminismo es la igualdad? ¿Está acaso calienta* la que tiene calores? Lo mismo con capitana, edila, concejala, tenienta, bedela... ¿Qué será lo próximo? ¿Caba*, alféreza*, albañila*? ¿Por qué no otros adjetivos menos agradables? ¿Qué tal incordianta*, atroza*, inútila*, gilipóllasa* o, ya puestos, gilicoños*?

No digo que al revés no haya ocurrido; así, hay casos como modisto, que viene de moda, siendo que ya contamos con la palabra neutra modista, que describe lo mismo. Pocos, muy pocos ejemplos similares se podrán encontrar. Puedo comprenderlo (aunque no compartirlo), pues la profesión de modista ha sido siempre asociada a la mujer y la palabra debió de surgir de que alguien, no necesariamente siquiera un varón (quizá incluso la esposa del interfecto), quería recalcar para evitar confusiones que el modista era de sexo masculino, muy machote él. Déjenme recalcar esto: me parece tan aberrante jueza o presidenta como modisto y tan correcto abogada o bombera como prostituto (y hablo únicamente de la corrección del lenguaje, no de las condiciones laborales).

En general, en cambio, al varón no le importa lo más mínimo que sea adjetivado con una palabra acabada en -a: no hay transportistos* ni ordenanzos* ni guíos* ni falta que hace, porque ni la terminación ni el género determinan el sexo. Nadie presiona por que se use idioto* en vez de idiota para los varones. Son, por tanto, las ganas de marcar las diferencias entre sexos por parte de las talibanas de la lengua las que nos llevan a aberraciones como estas. Es hora de detener esta sinrazón.

2010-01-18

Estreno de foro en 11-s.eu.org

En nuestra página web del 11-S no teníamos sección de comentarios. Con este propósito estábamos parasitando el foro de Psicopanadero, porque el soft de wiki usado para la web no soporta comentarios. Es un soft a medida que yo desarrollé usando la idea del Giki pero escribiendo el código desde cero. Sin embargo, la adición de una sección de comentarios con todo lo que ello conlleva parecía demasiado trabajo.

Ahora hemos abierto un foro para discutir sobre el 11-S; dentro de él, uno de los subforos hace de sección de comentarios para que se puedan discutir los artículos individualmente, con lo que queda por fin paliada esa falta.

2010-01-17

Y más puzles

La colección de Simon Tatham está echando humo. Ahora son tres nuevos juegos más: Towers, Singles y Magnets.

Towers es un poco raro. Se trata de determinar la altura de unas torres (que son números enteros dispuestos en forma de cuadrado latino, de nuevo), una torre por casilla. Las pistas con las que contamos son unos enteros dispuestos alrededor del cuadrado, que indican el número de torres visibles horizontalmente desde el lado en el que se encuentra la pista en cuestión. Las torres más altas ocultan a las más bajas. Por ejemplo, en un casillero de 5×5, si en el lado izquierdo una de las filas tiene un 5 como pista, eso quiere decir que esa fila están los números del 1 al 5 en escala ascendente. Si pone un 3, hay muchas posibilidades y tendremos que valernos de más información para averiguarlo. Si pone un 1, entonces esa fila empieza por un 5, porque es el único que oculta a todos los demás. No me ha parecido interesante; me parece muy artificioso y poco intuitivo. Aunque eso mismo pensaba de Tents y al final sí que le vi la gracia.

Singles es algo más normal. Se nos muestra un cuadrado de n×n (no latino, esta vez) relleno con enteros de 1 a n, algunos repetidos en ciertas filas y columnas. Se trata de tachar todos los repetidos menos uno y dejar únicamente los no repetidos. Como condiciones adicionales, los números tachados no pueden estar adyacentes (arriba/abajo/izquierda/derecha, pero pueden estar en diagonal) y no puede haber grupos aislados de números sin tachar, es decir, se debe poder ir de cualquier número sin tachar a cualquier otro número mediante repetidos movimientos de una casilla cada uno hacia arriba, abajo, a la izquierda o a la derecha, o lo que es también lo mismo, los números no tachados tienen que formar un área conexa. Tiene su encanto.

Por último, en Magnets nos dan un tablero no necesariamente cuadrado, en el que se han dispuesto de antemano una serie de fichas rectangulares de 2×1. Cada una puede ser bien un imán, bien una ficha neutra. Se trata de colocar todos los imanes con su polaridad, respetando dos reglas básicas: una, que el número de signos positivos y el número de signos negativos de una fila o columna coincidan con las pistas que se nos dan (sin embargo, en algunas variantes no se nos dan todas: los que no tienen número no son cero, sino desconocidos), y otra, que no puede haber dos signos + juntos ni dos signos - juntos. Este es el más entretenido de los tres, a mi gusto.

Están todos disponibles para descarga para varias plataformas (Linux, OS X, Android, Windows, Palm) en el sitio de costumbre: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/.

2010-01-15

Mapa del RGB

Una imagen de 4.096×4.096 tiene 16.777.216 píxels. El número de colores RGB representables con 8 bits por componente (24 bits por color) es de 16.777.216. Esto quiere decir que en una imagen de 4.096×4.096 caben exactamente todos los colores posibles RGB de 24 bits.

Hay muchas maneras de distribuir los colores en la imagen. Esta es una, aunque está reducida y por tanto le faltan colores, pero enlaza a la verdadera de 4096×4096:

Imagen de 4096×4096 con todos los colores del RGB (versión reducida)

Aquí el programa PHP que la genera en formato TGA (la que hay para descarga ha sido convertida después a PNG con GIMP):

<?php
  $tgahdr = "\0\0\2\0\0\0\0\0\0\0\0\0\x00\x10\x00\x10\x18\40";
  $f = fopen($argv[1], "wb");
  fwrite($f, $tgahdr);

  for ($gl = 0; $gl < 16; $gl++)
    for ($r = 0; $r < 256; $r++)
    {
      $r2 = ($gl & 1) == 0 ? $r : 255-$r;
      $line = "";
      for ($gh = 0; $gh < 256; $gh += 16)
        for ($b = 0; $b < 256; $b++)
        {
          $b2 = ($gh & 16) == 0 ? $b : 255-$b;
          $line .= chr($b2) . chr($gh+$gl) . chr($r2);
        }
      fwrite($f, $line);
    }

  fclose($f);
?>

2010-01-14

Respuesta de la FUB sobre las imágenes del Hale

Al poco de publicar la entrada relativa al cráter Hale, envié un email al Dr. Gerhard Neukum para tratar de confirmar la precisión de mis deducciones. Creía que lo más probable era que no recibiera contestación pero, para mi sorpresa, en esa me equivoqué. Hace unas horas tenía en mi programa de correo la respuesta. Este es el mensaje que escribí:

Dear sir,

Sorry to take your time in this matter that will probably sound so frivolous. Maybe you are already aware of the fact that some JPEG compression artifacts are being interpreted by some UFO enthusiasts as signs of civilization on the surface of Crater Hale. They argue that there can't be any JPEG compression in a TIFF image. As ignorant as the argument may sound about the transmission process and the bandwidth restrictions, it's always good in my opinion to debunk those arguments with full detail to avoid them to spread in our society.

I'm friend of skeptic organizations in Spain and I've already written an article in spanish debunking this myth. I'm also considering to translate it into English. The link is here:

http://orden-y-concierto.blogspot.com/2009/12/civilizacion-en-el-crater-hale.html

While working on this article, I noticed that for ellaborating the Hale crater images used as textures for the 3D renders, your team took the images from orbit 533, but only the green and blue channels, as the red channel was basically so dark that the JPEG compression destroyed virtually all detail. However, the image used as texture is showing a red channel with a detail that is obviously not seen in the original orbit 533's red channel.

The reason for writing to you is to ask whether that red channel was recomposed by scaling the nadir view, as I suspect.

I'd also like to ask how other images such as that of Echus Chasma are processed, since they exhibit JPEG artifacts with a size much greater than the image's resolution, and only when looking at the color information. I suspect that the original image was translated to YCbCr or similar, and then the luminance channel substituted with the data from the nadir view and the chrominance channels scaled appropriately. Is that correct?

Finally, I'd like to ask you for your permission to publish your response, in case you decide to reply.

Thanks in advance,

Pedro Gimeno

Me ha respondido Björn Schreiner, miembro del Departamento de Ciencias Planetarias y Teledetección que encabezan los Drs. Neukum y Jaumann. Para consternación mía, pese a que pido expresamente permiso para publicar el mensaje, no me ha dicho ni que sí ni que no, con lo cual no puedo asumir que me otorga permiso para hacerlo, así que únicamente puedo contar lo que me dice.

En su amable respuesta, en primer lugar confirma algo que ya sabíamos gracias a la página que describía la cámara: que los datos son enviados por la sonda a la Tierra comprimidos, debido a limitaciones en el ancho de banda de la transmisión. Dice de la compresión que es similar al JPEG, de lo que deduzco que no es necesariamente el mismo algoritmo exacto pero sí que se basa en la transformada discreta del coseno al igual que éste, y menciona que efectivamente se producen artefactos a consecuencia de dicha compresión. Habla de las imágenes que están disponibles en la página web de la ESA como «productos para la prensa», lo cual debería dejar definitivamente claro que están postprocesadas, y añade que son ofrecidas en formato TIFF para que estén disponibles con la mayor calidad posible, pese a que ya contienen artefactos debidos a la compresión para su transmisión a la Tierra.

Cuando descubrí esos artefactos de tamaño gigantesco en los canales de color del Echus Chasma, ya dije:

Esto nos indica que en esta imagen o se ha hecho un downsampling de crominancia enorme, probablemente de 6×6 u 8×8, o más probablemente, la ESA ha empleado la vista nadir para aportar datos de luminancia, ya que la resolución de dicha vista es sustancialmente mayor.

Schreiner confirma mi sospecha, aunque con un matiz menor. Efectivamente, utilizan la vista nadir para dar datos de iluminación y las vistas en tres colores para dar información de color, pero no usan el espacio de color YCbCr como yo creía, sino el IHS (que es otra forma de decir HSL). Puesto que hay diversas formulaciones incompatibles entre sí de este espacio de color y no me ha especificado la variante exacta que emplean (tampoco se lo he preguntado), no puedo deshacer su transformación para confirmarlo. Me ha intrigado un poco por qué no usan un modelo más ligado a la percepción lumínica del ojo humano como el YCbCr que usa el JPEG; la respuesta probablemente sea la velocidad de proceso. El propio visor de la superficie marciana hace eso mismo en tiempo real, así que parece una buena justificación.

Actualización: En este enlace se menciona precisamente la transformación IHS como herramienta para combinar imágenes pancromáticas de alta resolución con imágenes RGB de menor resolución, es decir, exactamente el proceso realizado por el equipo de la FUB: http://ij.ms3d.de/plugins/ihs_image_fusion.php (fin actualización).

También me comenta que a menudo, sustituyen el canal rojo, que es en realidad cercano al infrarrojo, por el canal nadir. Yo pensaba que eso haría que el color fuera más irreal, pero me aclara que este canal está pasado por un filtro con un color bastante cercano al rojo, con lo cual la pérdida no es muy grande. No me dice que este proceso haya sido aplicado a la imagen del cráter Hale específicamente, probablemente no lo recuerde (la imagen fue tomada en 2004 y supongo que procesada no mucho tiempo después) o no se haya preocupado en comprobarlo. En cualquier caso, sí que confirma que el proceso exacto que conjeturo que fue seguido para obtener esa imagen, sí ha sido utilizado en ocasiones. Sumen ustedes.

Termina con una frase que no creo que le importe que reproduzca aquí: «Certainly the artefacts mentioned above are no sign of civilization», o sea, «ciertamente los artefactos mencionados más arriba no son ningún signo de civilización».

2010-01-13

El Wall Hugger de Robot Odyssey

Robot Odyssey es un juego educativo para adultos, sumamente interesante. Fue creado en 1984 por una compañía llamada The Learning Company e hicieron versiones para Apple II, TRS-80 e IBM PC.

La idea del juego es cablear unos robots utilizando circuitos lógicos para resolver rompecabezas. El juego se desarrolla en la ciudad imaginaria futurista de Robotropolis. El objetivo es abrirnos camino a través de las múltiples pantallas con ayuda de tres robots, que más adelante pueden ser cuatro si resolvemos un puzle extra. Los robots cuentan con cuatro detectores de paredes o bumpers, uno en cada dirección, que activan entradas cuando están en contacto con una pared; cuatro propulsores, también uno por dirección, que son activados por salidas; una pinza que tiene una entrada indicadora de que ha cogido algo y una salida con la que le damos la orden de activarse o no, y una antena para comunicarse con los otros robots, con su entrada y su salida. Además hay un interruptor de encendido/apagado, una batería que se va gastando mientras el robot está conectado y un «periscopio» por si queremos ver el exterior mientras el robot se mueve con el jugador en su interior. Las puertas lógicas con que programamos nuestros robots tienen un retardo de propagación de una unidad de tiempo, lo cual tiene que ser tenido en cuenta en algunos diseños.

Pantalla inicial de Robot Odyssey
Pantalla inicial de Robot Odyssey, donde nos encontramos por primera vez a los tres robots que nos ayudarán en la aventura (aquí vemos la versión para Apple II).

Para superar ciertas pantallas, por ejemplo, hay que conseguir que los robots activen sus pinzas en ciertos momentos, para coger un objeto al que no podemos acceder porque un robot centinela impide el paso a humanos. En otras, la estructura de la pantalla es lo bastante sencilla como para que, con un poco de imaginación, podamos diseñar un circuito sencillo para resolverla. Por supuesto, a medida que avanzamos pantallas aumenta la dificultad y pronto necesitamos más de un robot actuando coordinadamente para resolver ciertos puzles.

A. K. Dewdney ya habló de este juego en su sección Juegos de Ordenador de la revista Investigación y ciencia. Cuando leí el artículo, se me caía la baba y me quedé con unas ganas tremendas de verlo. Hoy, gracias a las maravillas del software libre e internet, existe una versión rehecha en Java llamada DroidQuest, disponible para descarga, escrita por Thomas Foote, en http://www.droidquest.com/. Por añadidura, el autor también ofrece la versión original de Apple II para descarga, así que quien disponga de un emulador puede también experimentar la sensación de jugar al juego original tal y como Dewdney lo mostró en su sección. Huelga decir que no lo solté hasta completarlo, superando así esa «cuenta pendiente».

Una característica interesante del juego es que hay unos chips disponibles, unos circuitos integrados que podemos programar para combinar varias operaciones en un solo circuito, simplificando con ello los diseños y ahorrando así puertas lógicas, lo cual es más interesante si tenemos en cuenta que hay un número limitado de ellas disponible. Algunos de los chips vienen ya preprogramados.

Interior de uno de los robots, con el chip Wallhugger preprogramado conectado.
Interior de uno de los robots, con un cableado predefinido que incluye un chip preprogramado, en este caso el chip Wallhugger. También está a la vista uno de los objetos del juego, una llave.

El Wallhugger en particular es un chip que, al cablearlo como se ve en la figura, consigue que el robot vaya pegado a las paredes de una habitación, recorriéndolas en sentido antihorario. Tiene algunas limitaciones y, debido a ellas, en el juego tenemos pocas ocasiones para usarlo, pero su interés radica en la dificultad de su elaboración. De acuerdo con la documentación, el chip contiene 16 puertas lógicas y un chip más en su interior. El autor de DroidQuest dice en una página dedicada al chip:

El chip Wallhugger parece ser el Santo Grial del Robot Odyssey. De acuerdo con el juego original, fue diseñado con «16 puertas lógicas y un chip anidado». No tengo ni idea de cómo el Wallhugger fue creado solo con eso. Me encantaría averiguar cómo funciona. [1]

A mí también me dejó con el gusanillo, pero como siempre he sido de naturaleza curiosa, finalmente agarré el original de la versión de Apple y me puse a destriparlo.

El proceso requirió bastantes pasos. Primero, tenía que averiguar en qué posiciones del archivo .dsk se guardaban los datos de los chips. En esta parte encontré tanto facilidades como dificultades que lo hicieron laborioso, pero básicamente rutinario. Lo siguiente era realizar la ingeniería inversa del formato con el que se almacenan los circuitos del chip.

Esta parte fue, por supuesto, la más interesante. Mediante la creación de diversos chips, averigüé cómo se codificaban las entradas y salidas del chip, así como las puertas empleadas. Cuando alcancé una comprensión aceptable del formato, me lancé en pos del Wallhugger.

De esa manera, constaté que lo que decía la documentación era perfectamente correcto: efectivamente, en su interior contenía 16 puertas lógicas y un chip anidado. Aquí está el circuito principal, dibujado con el programa libre de diseño y simulación de circuitos TkGate (sí, ya sé que pronunciado en español suena muy mal), concretamente con la versión 1.8:

Esquema del circuito principal del chip Wallhugger
Esquema del circuito principal del chip Wallhugger (clic para ampliar)

Y a continuación, el esquema del chip anidado:

Esquema del chip anidado dentro del chip Wallhugger
Esquema del chip anidado dentro del chip Wallhugger (clic para ampliar). En los flip-flops (FF) no está dibujada la salida derecha. Los LEDs a la salida de los flip-flops están solo como referencia.

Para poder realizar la simulación y probar el diseño en funcionamiento, tuve que crear un flip-flop R-S en TkGate que fuera compatible con el de Robot Odyssey. La idea era que cuando ambas entradas tuvieran un 1 lógico simultáneamente, el estado no variara, pues es la forma en que se comporta el RO. Aquí está el diseño que empleé:

Esquema del flip-flop usado para la simulación con TkGate
Esquema del flip-flop usado para la simulación con TkGate (clic para ampliar)

¿Cuál es el principio de funcionamiento de este curioso chip? Lo primero que hay que observar es que, si conectamos el bumper izquierdo al propulsor superior, el bumper superior al propulsor derecho, el bumper derecho al propulsor inferior, y el bumper inferior al propulsor izquierdo, tendremos un robot que casi funciona, pues al menos es capaz de moverse en círculos en habitaciones con paredes convexas. El problema radica en que cuando nuestro robot recorre una pared con un ángulo cóncavo (de 270°), al terminarse ésta pierde el contacto y deja de propulsarse, quedándose parado. El chip incorpora la circuitería necesaria para actuar en ese caso y resolver el inconveniente.

Efectivamente, los cuatro bumpers están conectados a los cuatro propulsores a través de sendas puertas OR, es decir, que mientras la otra entrada de cada una de las puertas OR sea cero, nuestro robot se comportará igual que el robot seguidor de paredes convexas recién descrito.

Ahora, ¿cuándo ha de actuar y qué ha de hacer para poder salvar también ángulos cóncavos? Si el problema es que se queda parado, lógicamente lo que tendrá que hacer es moverse. La condición es simplemente que no haya ningún bumper activo, que es lo que provoca que nuestro seguidor de paredes convexas se pare. Esa condición es detectada por las tres puertas OR en cascada de la parte superior que van seguidas de un inversor. Cuando la salida del inversor se activa, quiere decir que no hay ningún bumper tocando una pared. Con esto se activan cuatro puertas AND que dan paso a la señal que moverá el robot. Veamos cómo.

Ahora que sabemos que en ese caso hay que moverse, queda la duda de hacia adónde. Puesto que se trata de continuar siguiendo la pared de la esquina que acabamos de dejar, habrá que moverse hacia ella. Nos interesa que el siguiente bumper entre en contacto con la siguiente pared, para que la parte seguidora de paredes convexas pueda seguir actuando. Por suerte, gracias a los retardos de propagación de las puertas, tras perderse el contacto con la pared anterior el propulsor habrá estado en marcha el tiempo suficiente como para que el robot haya sobrepasado la esquina, habiendo recorrido la distancia suficiente como para que, si vamos directamente 45° en diagonal en dirección a la esquina que acabamos de dejar, acabemos tocando la nueva pared y no la antigua de la que venimos.

Por tanto, se trata de moverse en diagonal hacia la esquina que acabamos de dejar. ¿Cómo conseguimos eso? Ahí es donde entra en juego el chip anidado.

El esquema de este chip está diseñado de la siguiente forma. Hay cuatro flip-flops, cuatro entradas y cuatro salidas. Las cuatro entradas vienen directamente de los bumpers. Cada bumper activa un flip-flop y pone a cero los otros tres (si no hay conflictos, claro). Es decir, el set del primer flip-flop viene del primer bumper y el reset es el OR de los otros tres, y lo mismo con los demás. En resumen, el chip está diseñado para recordar cuál fue el último bumper activo. Cuando estamos tratando de doblar una esquina de 270° y perdemos el contacto, tenemos la garantía (o eso presumimos) de que en el último instante justo antes de perderse el contacto solo había un bumper activo, por lo tanto no hay que preocuparse de los conflictos. (Cuando hay paredes muy próximas, esto podría no cumplirse, y esa es una de las limitaciones de Wallhugger: debe tener suficiente espacio para moverse sin que, por ejemplo, dos bumpers opuestos toquen dos paredes a la vez).

La línea de puesta a uno de cada flip-flop es retardada mediante tres puertas OR, por un motivo que no he llegado a entender. Quizá sea porque de lo contrario, pulsos muy cortos del bumper podrían perderse antes de que la señal de puesta a cero de otro bumper la desactive, aunque no le acabo de ver el sentido. Parece, en cualquier caso, que el número de retardos es uno más que los que se producen en la señal reset, por lo que la intención parece en todo caso que el set llegue siempre en último lugar.

Tenemos entonces un chip que recuerda el último bumper activo antes de perderse el contacto y queremos usarlo para, cuando se pierde el contacto, movernos hacia la esquina que queremos doblar. Veamos cómo. Si el bumper derecho era el último activo cuando se perdió el contacto, entonces estaba en marcha el propulsor inferior, por tanto la esquina que acabamos de dejar queda debajo y a la derecha del robot, y es hacia ahí donde queremos movernos, por lo cual tendremos que activar los propulsores izquierdo y superior. Extendiendo el razonamiento a las cuatro direcciones, el bumper superior activará los propulsores inferior e izquierdo, el izquierdo los propulsores inferior y derecho, y el inferior los propulsores derecho y superior.

Visto desde el lado de los propulsores, en ausencia de señal de bumpers, el izquierdo se activará cuando el último bumper activo fue el superior OR el derecho, etcétera. Esto justifica las cuatro puertas OR restantes, lo que concluye la totalidad del chip.

Si alguien quiere conocer el formato de los chips del Robot Odyssey y la forma de almacenarse en los archivos .dsk, aquí hay un enlace donde pueden consultarlo (en inglés): [2]. Está en inglés porque lo escribí para los miembros del grupo de Yahoo de DroidQuest. También incluye una explicación del funcionamiento, aunque más somera que la dada aquí, y el archivo TkGate con los esquemas aquí presentados listos para usar en la simulación. Aviso de que el enlace está en un directorio temporal, que puede ser movido cuando actualice mi página personal y lo coloque en la que será su ubicación definitiva. Cuando así lo haga, procuraré recordar actualizar esta entrada en consonancia, pero si alguien enlaza a ese directorio temporal directamente, debe tenerlo en cuenta.

Referencias

[1] http://mysite.verizon.net/thomasfoote/DQ/id60.htm
[2] http://www.formauri.es/personal/pgimeno/temp/RO/wallhugger.php

2010-01-06

Unequal Adjacent y Keen agregados a la colección de Simon Tatham

Han salido hace muy pocos días dos nuevos juegos de la colección de puzzles de Simon Tatham. Ambos están basados en la misma idea de los cuadrados latinos en que se basan el Sudoku y el Futoshiki. Uno de ellos es un nuevo programa: se llama Keen y es un clónico de un juego conocido como KenKen, en el que además de cumplir la restricción de que se ha de componer un cuadrado latino, hay que cumplir que la operación aritmética indicada realizada entre los números contenidos en los rectángulos coincida con el número indicado; por ejemplo, 3- quiere decir que la diferencia de los números de ese rectángulo debe ser 3, y 24× que el producto debe ser 24. He jugado, pero no me ha enganchado mucho. El otro es una variante que se ha añadido a uno ya existente, el Unequal, clónico del Futoshiki. La variante consiste en que en vez de signos de desigualdad, hay unas barras entre algunos de los números, que indican que la diferencia entre las casillas es una unidad. A diferencia del Unequal convencional, las casillas que no tienen barra no son desconocidas, sino que se sabe que tienen una diferencia mayor que una unidad. Este sí que engancha, aviso.

Para quien no conozca la colección, advierto de que es peligrosa. Vicia demasiado. En particular, contiene un buscaminas cuyos tableros son siempre resolubles (no dependemos sólo de la suerte, como sucede en el convencional). Es el único buscaminas donde he visto un 8. Hay otras joyas que invito a descubrir, como el frustrante y divertido Inertia, el Net con sus conexiones, el Untangle con sus nudos o el Map, basado en el teorema del mapa de cuatro colores. La colección se caracteriza por una propiedad: todos los juegos generados son resolubles y en muchos (digamos en los que es posible) la solución es única.

Ya no me siento tan solo. Bueno, corrijo, me siento más solo. http://www.perspicalia.com/post/admito-mi-derrota. Todavía resisto a ambas cosas: móvil y féisbuc. Y también a tuíter.

2010-01-03

Autómatas celulares

Es un tema tan fascinante como inevitable. Como siempre habrá lectores que no hayan oído hablar del tema, este artículo será la preceptiva introducción.

Un autómata celular consiste en un casillero en el que cada casilla (también llamada celda o célula) puede estar en un estado determinado, y una regla de transición que determina cuál será el próximo estado de cada casilla en función de su estado actual y del estado de las casillas vecinas. No está limitado a retículas cuadriculadas ni bidimensionales, pero son las más comunes. Así, los píxels de una pantalla pueden servir para representar un autómata celular, representando el estado de cada casilla como el color de un píxel (o varios, si hacemos zoom). Normalmente se parte de un casillero previamente relleno de alguna forma, ya que los casilleros en que todas las casillas tienen el mismo estado suelen ser muy monótonos.

En los autómatas celulares, es importante que toda la transición del estado suceda «de golpe», esto es, para programarlo debemos tener en cuenta que no podemos modificar el estado de una celda y después usar la versión modificada como vecina de la siguiente para calcular su estado, sino que la vecina debe tomar el estado original. Una forma sencilla de implementar esta regla es usar una matriz con el mismo tamaño que la matriz donde guardamos los estados e ir depositando los nuevos estados en esa otra matriz. Cuando acabamos de calcularlos todos, trasladamos los nuevos estados a la matriz original y/o a la pantalla. A cada transición de estados se le suele llamar «tick» o «tic», porque es como el tic-tac de un reloj figurado. También se emplea el término «generación» en el mismo sentido, como si las casillas o células fueran organismos que van teniendo descendencia.

Los autómatas celulares lineales (de una dimensión) se suelen dibujar en dos dimensiones, usando la segunda de histórico. Esto es, en cada línea se dibuja el estado completo de todas las casillas, en la inmediatamente inferior se dibuja el tick siguiente, y así sucesivamente.

Las reglas de transición pueden ser cualesquiera que tengan en cuenta las casillas vecinas. Hay quien no considera autómatas celulares los que tienen reglas asimétricas, es decir, las que producen resultados diferentes según la orientación en la que esté el dibujo original. Lo sean o no, hay conjuntos de reglas asimétricas interesantes, aunque no las vamos a tratar aquí, al menos por ahora. Hay algunos casos de autómatas en los que se analizan bloques completos de varias casillas a la vez, produciendo cambios simultáneos en varias casillas a la vez. De nuevo, hay quien no los considera autómatas per se, pero también son interesantes.

Los casos más comunes de reglas de transición son los que se rigen por el estado de las cuatro (arriba, abajo, izquierda, derecha) u ocho (incluyendo diagonales) casillas vecinas a una dada, a veces incluyendo a la casilla misma, en una retícula cuadriculada. Entre los autómatas de dos estados, es común contar el número de casillas vecinas que hay en uno de dichos estados y determinar el siguiente en función de dicho número.

Veamos un par de ejemplos. El autómata de Edward Fredkin considera un entorno de nueve casillas y la regla de transición es la siguiente: el nuevo estado será un 1 si el estado actual es 1 y el número de casillas que rodean a la actual que están en estado 1 es par, o bien si está a 0 y el número de casillas que estan a 1 es impar; será 0 en caso contrario. La regla equivale a sumar los valores de las nueve casillas incluyendo la central, asignando un 1 si la suma es impar y 0 si no lo es. Curiosamente, con esta regla, cada figura acaba multiplicada por 9 al cabo de unos cuantos ticks. Aquí vemos el estado inicial y 32 estados posteriores del autómata de Fredkin:

Autómata de Fredkin en movimiento
Autómata de Fredkin en acción, tomando como estado inicial un rótulo con la palabra Fredkin. Al cabo de 32 iteraciones, se ha multiplicado por 9.

El otro ejemplo que vamos a considerar es el llamado Juego de la vida de J.H. Conway. La regla de transición es: si una célula está «muerta» (estado 0), estará «viva» (estado 1) en la generación siguiente si tiene a su alrededor (sin contarse a sí misma) exactamente tres casillas «vivas». Si está «viva», entonces estará «viva» en la próxima generación únicamente si tiene dos o tres vecinas «vivas». En otro caso, «morirá». Esto se suele indicar con la notación B3/S23 (la B, de Born, indica el número de vecinos necesario para que la casilla pase a estado 1 cuando es 0, en este caso 3, y la S, de Survive, el número de vecinos necesario para que la casilla pase a estado 1 cuando es 1, en este caso 2 y 3).

Con esas sencillas reglas basta para que se plantee todo un abanico de cuestiones con respuestas complicadas. Típicamente, a partir de una configuración cualquiera al azar no muy grande, la población fluctúa durante bastantes generaciones y termina en un estado estable en el que se ven patrones estáticos y otros oscilantes con periodo 2, y ocasionalmente algún otro. Por ejemplo, la siguiente configuración:

Palabra «Conway» que se someterá al Juego de la Vida

que tiene inicialmente 58 celdas «vivas», tras 1.235 generaciones evoluciona a la siguiente figura (clic para versión completa):

Estado final estable del desarrollo de la palabra «Conway»

con una «población» de 228 celdas que ya permanece constante durante el resto de generaciones. En el curso de esas 1.235 generaciones, ha liberado cuatro «deslizadores». Un deslizador es una configuración cíclica que va cambiando de manera que tras cierto número de generaciones, se repite la misma forma pero está desplazada. El más común, en cuanto a que aparece espontáneamente con facilidad, es este de cuatro estados y que en todo momento tiene cinco células «vivas»:

Deslizador típico en el Juego de la Vida

Por supuesto, puede aparecer en cualquier posición, ya que el Juego de la Vida es simétrico. Obsérvese cómo tras cuatro generaciones, tiene la misma forma original pero está una casilla desplazado, hacia arriba y hacia la derecha en este caso.

Esta tendencia de las configuraciones al azar a alcanzar la estabilidad poblacional con el tiempo, le hizo a Conway conjeturar que no existía ninguna configuración que creciera indefinidamente, y ofreció un premio de 50 dólares a quien encontrara una que lo hiciera. El premio fue ganado por Bill Gosper, quien encontró una configuración cíclica que emitía un deslizador cada 30 generaciones y, por tanto, la población del conjunto siempre crecía, demostrando así falsa la conjetura de Conway. El cañón lanza-deslizadores, como se le conoció, tenía este aspecto:

Cañón lanza-deslizadores de Bill Gosper
Cañón lanza-deslizadores de Bill Gosper, en pleno proceso (se muestran dos deslizadores ya generados).

Hoy en día se conocen muchas configuraciones que crecen siempre. También se sabe que el Juego de la Vida es Turing-completo, es decir, que es posible crear una configuración tal que emule cualquier cálculo que un ordenador es capaz de realizar (otra cosa es la velocidad). El Juego de la Vida ha sido profusamente estudiado y hay muchas webs recomendables a quien quiera profundizar sobre él; valgan como ejemplo [1] (un léxico) y [2] (la entrada de la Wikipedia inglesa sobre este autómata).

Hay otro tipo de regla que tiene como caso particular el Juego de la Vida. Se trata de Generations. La idea es la misma, pero en lugar de morir inmediatamente, las células se hacen «viejas». Para definir la regla hace falta especificar, además de los supervivientes y neonatos, el número total de estados del autómata. Por ejemplo, 345/2/4 indica que hay cuatro estados. Si una célula está en el estado 1 y el número de células vecinas de una dada, sin contar ella misma, en el estado 1 es de 3, 4 ó 5, entonces esa celda continuará en el estado 1 en el siguiente tick. Si está en el estado 0 y está rodeada exactamente de dos células en el estado 1, entonces pasará al estado 1. En cualquier otro caso, si su estado es 1 pasará a ser 2 (envejecerá). Si es 2, independientemente de las células que la rodeen, pasará a 3 en el tick siguiente, y si es 3, pasará a 0 (muerte final). Si ya era 0, se quedará igual. La regla recién descrita recibe el nombre de Star Wars y fue creada por Mirek Wojtowicz. Obviamente, el Juego de la Vida se escribiría 23/3/2 en notación Generations. El autómata de Fredkin se escribiría 02468/1357/2 en esta notación.

La regla /2/3 de Generations es digna de mención. Tiene tres estados; toda célula en el estado 1 pasará a 2 en la generación siguiente, ya que no hay indicación de ningún número de estados con el que sobrevivir (mantenerse en 1), y después a 0. Si una célula muerta está rodeada de dos células en estado 1, pasará al estado 1 en la próxima generación. Al autómata recién descrito se le llama Brian's Brain, descubierto por Brian Silverman, y es muy entretenido contemplarlo cual si se tratara de una pecera. Aquí hay una versión animada, cortesía de Wikipedia: [3].

Por supuesto, Generations no es la única familia de reglas existente. Hay un autómata celular llamado Wireworld, descubierto también por Silverman, que modela el comportamiento de los circuitos electrónicos. Sus reglas, aun siendo muy parecidas a las de Generations, contienen un estado extra que permanece siempre inmutable. Digamos que es un Generations con máscara.

Así, Wireworld es un conjunto de reglas con cuatro estados. El primer estado, el 0, permanece siempre inalterado. Al estado 1 se le llama «cable». Al estado 2 se le llama «cabeza de electrón», y al 3 «cola de electrón». Las reglas son las siguientes: si una célula cable tiene a su alrededor exactamente 1 ó 2 cabezas de electrón, entonces pasará a ser cabeza de electrón en la generación siguiente; de lo contrario permanecerá cable. La cabeza de electrón pasará siempre a ser cola de electrón, y la cola de electrón pasará siempre a ser cable. Es, por tanto, el equivalente a la regla /12/3 en Generations, con la adición de un estado inmutable.

Hay otros juegos de reglas en los que se realizan operaciones aritméticas con los estados. Uno de los más llamativos es la máquina Hodge Podge (que fue traducida por la revista Investigación y Ciencia como «máquina batiburrillo»), diseñada por M. Gerhard y H. Schuster. Pese a que se le llame máquina, es un autómata celular. En realidad, es toda una familia de reglas, ya que se rigen por cuatro parámetros: el número de estados y varios «niveles de infección». Si n es el número de estados, se define una célula como «sana» si está en el estado 0, como «enferma» si está en el estado n-1, y como «infectada» si está en cualquiera de los estados intermedios. La regla para una célula «sana» es pasar a un estado dado por ⌊E/re⌋ + ⌊I/ri⌋, donde ⌊x⌋ indica la parte entera de x, E es el número de células enfermas que rodean a la actual, e I es el número de células infectadas. re y ri son dos de los parámetros que definen el autómata.

Para una célula «infectada», la regla es la siguiente: su próximo estado será la parte entera de la media de los estados de las células infectadas que la rodean incluyéndose a sí misma, más un parámetro de infección g. El valor se trunca para que no exceda de n-1. La regla para una célula «enferma» es la más sencilla: pasará siempre al estado «sana» en la siguiente generación. Los cuatro parámetros son, pues, n (número de estados), re (relación de infección para células enfermas), ri (relación de infección para células infectadas) y g (velocidad de progreso de la enfermedad). Esos parámetros, junto con el tipo de entorno, que no necesariamente es de ocho células, determinan una máquina concreta.

Pese a lo complicado de las reglas, es todo un placer verlas actuar, generando unos bellos patrones en espiral característicos de una reacción catalítica heterogénea (el autómata fue diseñado con el fin de emular dicha reacción). Aquí hay una versión en Flash: [4]. Hace falta algo de paciencia para ver las espirales formarse; a veces se desvanecen antes de cobrar fuerza. Aquí se ilustran versiones ya desarrolladas de patrones al azar usando diferentes entornos: [5]

Hay muchos otros conjuntos de reglas posibles, pero no vamos a detenernos en más. En vez de eso, vamos a presentar dos programas que reconocen muchos juegos de reglas y nos permiten dibujar patrones iniciales o probar patrones al azar. Uno de ellos es Mirek's Java Cellebration, MJCell (versión 1.51 a fecha de escritura de este artículo), escrito en Java, como su nombre indica, que es una versión del Mirek's Cellebration (MCell) para Windows. Una ventaja de la versión Java es que se puede ejecutar en línea; otra, que el código fuente está disponible, aunque la licencia es incierta. El otro programa es Golly, con unos pocos algoritmos y patrones menos que MJCell, pero con una velocidad realmente pasmosa. Golly hace uso de un algoritmo que utiliza tablas «hash» para reconocer patrones ya visitados, y hacerlos evolucionar a muchas veces la velocidad normal. Las tablas requieren gran cantidad de memoria para conseguir su velocidad; he llegado a llenar los 3 Gb de memoria que permiten las aplicaciones de 32 bits en Linux (algún día antes de 2038 migraré mi Debian a 64 bits, ¡lo prometo!). Esa memoria sólo hace falta para conseguir la velocidad máxima, pero no hace falta tanta para ver los patrones a una velocidad de vértigo, pudiendo ver pasar literalmente trillones de generaciones en segundos para autómatas simples, o miles de millones en minutos para otros no tan simples. Por ejemplo, podemos ver recrearse la Esfinge de William R. Buckley, una máquina autorreplicante basada en el complejo autómata original de 29 estados de John von Neumann, al que lleva unos 40 minutos completar las 261.903.042.739 generaciones que requiere construir una copia e insuflarle vida. O podemos ver la computadora de primos diseñada en Wireworld de Mark Owen, mostrando primo tras primo en su flamante display. O podemos ver en funcionamiento la máquina de Turing de tres estados de Paul Rendell, implementada mediante un patrón del Juego de la Vida.

Otra ventaja de Golly en comparación con MJCell es su universo virtualmente ilimitado. En MJCell hemos de definir de antemano el tamaño de la cuadrícula y no se le dan bien las cuadrículas muy grandes, pero en Golly, los patrones se extienden «hasta el infinito y más allá», por lo que no tenemos que sufrir por si el patrón llega al borde. La licencia es GPL y está también disponible en versión binaria para Linux, Mac y Windows.

Referencias

[1] http://www.bitstorm.org/gameoflife/lexicon/
[2] http://en.wikipedia.org/wiki/Conway's_Game_of_Life
[3] http://upload.wikimedia.org/wikipedia/en/a/a7/Brian's_brain.gif
[4] http://www.galaxygoo.org/blogs/2006/07/hodgepodge_machine.html
[5] http://www.vbaccelerator.com/home/VB/Code/vbMedia/Algorithmic_Images/Hodge_Podge/article.asp