Orden y concierto

2011-08-23T16:32:00.002+02:00

Si te gusta el té fuerte, he aquí un simple consejo: no le pongas azúcar o leche hasta que el té se haya disuelto por completo. Esto favorecerá que el agua tenga menos soluto, permitiéndole así disolver más cantidad de té.

Nostalgia - Los programadores de verdad no usan Pascal

2011-08-19T14:05:00.000+02:00

Me he reencontrado recientemente con este texto en mis archivos. Releerlo ha sido una experiencia bastante nostálgica. He creído conveniente reproducirlo en versión castellana. La versión inglesa está todavía disponible en línea, así que ofrezco aquí mi traducción. Parece ser que fue publicado en 1983. Helo aquí en toda su gloria:

Los Programadores de Verdad No Usan Pascal

En los buenos tiempos, la "Edad de Oro" de los ordenadores, era fácil separar a los hombres de verdad de los críos (a veces en la literatura se les ha llamado "Hombres de Verdad" y "Comedores de Pastelitos"). Durante ese periodo, los Hombres de Verdad eran los que comprendían la programación de ordenadores y los Comedores de Pastelitos eran los que no. Un auténtico programador de ordenadores decía cosas como:
  DO 10 I = 1, 10
y
  ABEND
Hablaban en mayúsculas, ya me entienden. El resto del mundo decía cosas como "los ordenadores son demasiado complicados para mí", y "no puedo relacionarme con ordenadores: son tan impersonales...". Un escrito anterior (1) puntualiza que los Hombres de Verdad no se relacionan con nada, y no temen ser impersonales. Pero, como suele pasar, los tiempos cambian. Hoy nos enfrentamos a un mundo en el que las señoras tienen ordenadores en su horno de microondas, los niños de 12 años pueden vencer a los Hombres de Verdad jugando al Asteroids o al Pac-Man, y cualquiera puede comprar y comprender su propio ordenador personal. El Programador de Verdad está en peligro de extinción, en peligro de ser reemplazado por estudiantes universitarios con Commodores y Ataris. Hay una clara necesidad de puntualizar las diferencias entre un típico jugador junior de Pac-Man de universidad y el Programador de Verdad. Si se aclara esta diferencia, les dará a esos muchachos algo a lo que aspirar - un modelo, una figura paterna. También ayudará a explicar al que tenga contratado a un Programador de Verdad por qué sería un error reemplazar a los Programadores de Verdad de su plantilla por jugadores-de-PacMan-de-12-años (que le suponen un ahorro considerable).

1.1 Lenguajes

La forma más fácil de distinguir a un Programador de Verdad del resto es por el lenguaje de programación que él o ella usa. Los Programadores de Verdad usan Fortran. Los Comedores de Pastelitos usan Pascal. Nicklaus Wirth, el diseñador del Pascal, dio una conferencia una vez en la que le preguntaron: "¿Cómo pronuncia usted su nombre?" El respondió: "Pueden llamarme por mi nombre, pronunciándolo 'Virt', o pueden llamarme por mi valor, 'Worth'" [valioso, merecedor - N.del T.]. Enseguida se deduce de ese comentario que Nicklaus Wirth es un Comedor de Pastelitos. El único mecanismo de pase de parámetros que usan los Programadores de Verdad es la "llamada por valor - retorno", como se implementa en los compiladores de FORTRAN G y H del IBM/370. Los Programadores de Verdad no necesitan todos esos conceptos abstractos para hacer su trabajo: son perfectamente felices con un teclado perforador, un compilador FORTRAN IV, y una cerveza.

Los Programadores de Verdad realizan Proceso de Listas en FORTRAN.
[N.del T.: Proceso de Listas = List Processing, de donde viene el nombre del lenguaje de programación LISP]

Los Programadores de Verdad realizan Manipulación de Cadenas en FORTRAN.

Los Programadores de Verdad hacen Contabilidad (si es que la hacen) en FORTRAN.

Los Programadores de Verdad hacen programas de Inteligencia Artificial en FORTRAN.

Si no puedes hacerlo en FORTRAN, hazlo en Lenguaje Ensamblador, o no merecerá la pena hacerlo.

1.2 Programación Estructurada

Los académicos de la ciencia de computación se han hecho esclavos de la "Programación Estructurada" durante los últimos años. Afirman que los programas son más fácilmente comprensibles si el programador utiliza ciertas construcciones especiales del lenguaje, por supuesto, y los ejemplos que usan para mostrar su punto de vista caben invariablemente en una sola hoja de alguna que otra oscura publicación, ejemplo claramente insuficiente para convencer a nadie. Cuando salí de la escuela, pensaba que era el mejor programador del mundo. Podía escribir un programa invencible de tres en raya, usar cinco lenguajes de ordenador diferentes, y crear programas de 1000 líneas que funcionaban (¡de verdad!). Entonces salí al Mundo Real. Mi primer trabajo fue leer y comprender un programa en FORTRAN de 20.000 líneas, para acelerarlo al doble de su velocidad. Cualquier Programador de Verdad te dirá que toda la Programación Estructurada del mundo no te ayudará a solucionar un problema como ese: requiere auténtico talento. Algunas observaciones a bote pronto sobre los Programadores de Verdad y la Programación Estructurada:

Los Programadores de Verdad no temen usar GOTO.

Los Programadores de Verdad pueden escribir bucles DO de cinco páginas sin confundirse.

Los Programadores de Verdad disfrutan con las sentencias IF aritméticas: hacen el código más interesante.

Los Programadores de Verdad escriben código automodificable, especialmente si pueden ahorrar 20 nanosegundos en mitad de un bucle crítico.

Los Programadores de verdad no necesitan comentarios: el código es obvio.

Aunque el FORTRAN no tiene sentencias IF, REPEAT...UNTIL ni CASE estructuradas, los Programadores de Verdad no se preocupan por no poder usarlos. Además, todas esas estructuras pueden ser simuladas mediante GOTOs cuando es necesario.

Las estructuras de datos también han recibido mucha atención últimamente. Los Tipos Abstractos, Estructuras, Punteros, Listas y Cadenas se han hecho muy populares en ciertos círculos. Nicklaus Wirth (el antes mencionado Comedor de Pastelitos) ha conseguido escribir todo un libro (2) defendiendo que se puede escribir un programa basándose en Estructuras de Datos en lugar de todo lo habitual. Como todos los Programadores de Verdad saben, la única estructura de datos útil es el ARRAY. Las cadenas, listas, estructuras, conjuntos... son sólo casos especiales de Arrays y pueden ser tratados de esa forma fácilmente sin necesidad de ensuciar el lenguaje de programación con todo tipo de complicaciones. Lo peor sobre los tipos de datos bonitos es que tienes que declararlos, y todos los Lenguajes de Programación de Verdad, como todos sabemos, tienen tipos implícitos basados en la primera letra del nombre (de seis caracteres) de la variable.

1.3 Sistemas Operativos

¿Qué tipo de sistema operativo usa el Programador de Verdad? ¿CP/M? Por favor, el CP/M, después de todo, es básicamente un sistema operativo de juguete. Hasta las señoras respetables y los estudiantes de primaria pueden usar y entender el CP/M. El UNIX es mucho más complicado, por supuesto: el típico hacker de UNIX nunca es capaz de recordar cómo se llama el comando de imprimir esta semana. Cuando se le conoce bien, el UNIX no es sino un video juego glorificado. La gente no hace trabajo serio en sistemas UNIX: envían chistes por el mundo a través de una red UUCP, y escriben juegos de aventuras y artículos de investigación. No, el Programador de Verdad usa OS/370. Un buen programador puede encontrar en el manual del JCL y comprender la descripción de un mensaje de error IJK3051 que acaba de aparecerle. Un gran programador puede escribir JCL sin recurrir al manual del JCL en absoluto. Un programador realmente bueno puede encontrar bugs enterrados en un volcado hexadecimal de seis Megabytes sin usar una calculadora hexadecimal. El OS/370 es un sistema operativo realmente destacable. Es posible destruir días de trabajo con un simple espacio fuera de lugar (nos ocurre hasta a los mejores), así que se favorece la alerta entre el personal de programación. La forma de acercarse más al sistema es mediante un teclado perforador. Hay gente que afirma que hay un sistema de Compartición de Tiempos que funciona en OS/370, pero tras un cuidadoso estudio he llegado a la conclusión de que estaban equivocados.

Referencias:

(1) Fierstein, B., Real Men Don't Eat Quiche, New York, Pocket Books, 1982
(2) Wirth, N., Algorithms+Data Structures=Programs, Prentice Hall, 1976

1.4 Herramientas de Programación

¿Qué tipo de herramientas usa un programador de verdad? En teoría, un programador de verdad podría ejecutar sus programas tecleándolos en el panel frontal de un ordenador. En los tiempos en los que los ordenadores tenían paneles frontales, esto se hacía en alguna ocasión. El típico programador de verdad se conocía de memoria la rutina de arranque en hexadecimal, y la reemplazaba cuando su programa destruía el arranque. Por entonces, la memoria era memoria: no se iba al quitar la alimentación. Hoy, la memoria bien olvida cosas que no quieres, o recuerda demasiado tiempo lo que sería mejor olvidar. Dice la leyenda que Seymour Cray (el inventor del superordenador Cray-1 y la mayoría de los ordenadores de Control Data) tecleó el primer sistema operativo del CDC-7600 en el panel frontal de memoria la primera vez que fue puesto en marcha. Seymour, por supuesto, es un programador de verdad.

Uno de mis programadores de verdad favoritos era un programador de sistemas de Texas Instruments. Un día, recibió una llamada de larga distancia de un usuario cuyo sistema se había venido abajo a mitad de salvar un trabajo importante. Jim fue capaz de reparar el daño por teléfono, consiguiendo que el usuario metiera las instrucciones de E/S de disco en el panel frontal, reparando las tablas del sistema en hexadecimal, leyendo los contenidos de los registros a través del teléfono. La moraleja de la historia: aunque un programador de verdad normalmente incluye un teclado perforador y una impresora de líneas entre sus herramientas, puede desenvolverse bien con sólo un panel frontal y un teléfono en caso de emergencia.

En algunas compañías, la edición de textos ya no consiste en diez ingenieros esperando en fila para usar un teclado perforador 029. De hecho, el edificio en que trabajo no tiene ni un solo teclado perforador. El programador de verdad, al verse en esa situación, tiene que trabajar con un programa de edición de textos. La mayoría de los sistemas proporcionan varios editores de textos entre los que seleccionar, y el programador de verdad debe tener cuidado de elegir el que más refleja su estilo personal. Mucha gente cree que los mejores editores de texto del mundo se escribieron en el Centro de Investigación Xerox de Palo Alto para usarse en sus ordenadores Alto y Dorado (3). Por desgracia, ningún programador de verdad usaría un ordenador con un sistema operativo llamado SmallTalk, y desde luego nunca le hablaría a un ordenador con un ratón.

Algunos de los conceptos de esos editores de Xerox han sido incorporados en editores que funcionan en sistemas más razonables, por ejemplo EMACS y VI. El problema con dichos editores es que los programadores de verdad consideran que "lo que ves es lo que hay" [también llamado WYSIWYG - N.del T.] es un concepto tan malo aplicado a los editores como lo es aplicado a las mujeres. No, el programador de verdad prefiere un editor tipo "tú lo has pedido, ahí lo tienes": complicado, críptico, potente, inolvidable, y peligroso. TECO para ser preciso.

Se ha observado que una secuencia de comandos de TECO se parece más al ruido de transmisión de línea que a texto legible (4). Un entretenido juego que se puede jugar con TECO es escribir tu nombre en la línea de comandos e intentar adivinar lo que hará. Casi cualquier error de escritura durante la comunicación con TECO destruirá probablemente tu programa, o aún peor, introducirá bugs misteriosos y sutiles en una subrutina que antes funcionaba.

Por esta razón, los programadores de verdad se muestran recelosos a la hora de editar un programa que está próximo a funcionar. Encuentran mucho más fácil editar el código objeto en binario directamente, usando un maravilloso programa llamado SUPERZAP. Este sistema funciona tan bien que muchos programas en funcionamiento en sistemas IBM no mantienen relación alguna con su código FORTRAN original. En muchos casos el código fuente original ya no está disponible. Cuando llega el momento de modificar un programa como ese, ningún director pensaría siquiera en enviar a cualquiera que no fuera un programador de verdad para hacer el trabajo. Ningún Programador Estructurado Comedor De Pastelitos sabría siquiera por dónde empezar. A esto se le llama Seguridad del Puesto.

He aquí algunas herramientas de programación que los programadores de verdad no usan:

Preprocesadores de FORTRAN como MORTRAN o RATFOR. Son como las cocinas de la programación: ideales para hacer pastelitos. Ver arriba los comentarios sobre programación estructurada.

Debuggers de Código Fuente. Los Programadores de Verdad pueden leer volcados hexadecimales.

Compiladores con chequeo de límite en arrays. Ahogan la creatividad, destruyen la mayoría de los usos interesantes de la sentencia EQUIVALENCE, y hacen imposible modificar el sistema operativo mediante subíndices negativos. Y lo peor de todo, el chequeo de límite es ineficiente.

Sistemas de mantenimiento de código fuente. Un programador de verdad mantiene su código cerrado con llave en un fichero de tarjetas, porque eso implica que el dueño no puede dejar programas importantes al descubierto (5).

(3) Xerox PARC Editors...
(4) Finseth, C. Theorey and Practice of Text Editors - or A Cookbook for an EMACS, B.S. Thesis, MIT/LCS/TM-165, Massachusetts Institute of Technology, May 1980.
(5) Weinberg, G. The Psychology of Computer Programming, New York, Van Nostrand Reinhold, 1971, p. 110.

1.5 El Programador de Verdad en el trabajo

¿Dónde trabaja el típico programador de verdad? ¿Qué tipo de programas merecen los esfuerzos de un individuo con tanto talento? Puede estar seguro de que no encontrará a ningún programador de verdad escribiendo programas de contabilidad en COBOL, u ordenando listas de correo para la revista People. Un programador de verdad quiere tareas de una importancia que haga temblar la tierra (¡literalmente!).

Hay Programadores de Verdad trabajando para el Laboratorio Nacional de Los Alamos escribiendo simulaciones de bomba atómica para superordenadores CRAY-1. Hay Programadores de Verdad trabajando para la Agencia de Seguridad Nacional, decodificando transmisiones rusas.

Fue gracias sobre todo al esfuerzo de miles de Programadores de Verdad que trabajaban para la NASA que los americanos llegaron a la luna antes que los rusos. Hay Programadores de Verdad trabajando para Boeing, diseñando sistemas operativos para misiles crucero.

Algunos de los más puros Programadores de Verdad de todos trabajan en el Jet Propulsion Laboratory de California. Muchos de ellos se saben el sistema operativo completo de las naves Pioneer y Voyager de memoria. Con la ayuda de grandes programas en FORTRAN desde tierra y pequeños programas en ensamblador desde la nave espacial, son capaces de hacer increíbles hazañas de navegación y de previsión: acertar en ventanas de diez kilómetros de anchura en Saturno tras seis años en el espacio, reparar o prescindir de plataformas sensoras, radios o baterías dañadas. Se cuenta que un programador de verdad consiguió meter un programa de comparación de patrones en unos cuantos cientos de bytes de memoria no usada en una nave espacial Voyager que buscó, localizó y fotografió una nueva luna de Júpiter. Los planes actuales de la nave espacial Galileo son usar una trayectoria asistida por gravedad a través de Marte en su camino hacia Júpiter. Esta trayectoria pasa a 80 más menos 3 kilómetros de la superficie de Marte. Nadie va a confiar en un programa en Pascal (o en un programador de Pascal, para el caso) para navegar con esas tolerancias.

Como puede imaginar, muchos de los Programadores de Verdad del mundo trabajan para el Gobierno americano, sobre todo en el Departamento de Defensa. Así es como debe ser. Desde hace poco, sin embargo, se ha formado una nube negra en el horizonte de los Programadores de Verdad. Parece que algunos Comedores de Pastelitos con un puesto importante en el Departamento de Defensa decidieron que todos los programas de Defensa deberían ser escritos en un gran lenguaje unificado llamado ADA. Durante un tiempo parecía que el ADA estaba destinado a convertirse en un lenguaje que iba contra todos los preceptos de la programación de verdad: un lenguaje con estructura, con tipos de datos, mucho tecleo, y puntos y comas. En definitiva, un lenguaje diseñado para inutilizar la creatividad del típico programador de verdad. Por suerte, el lenguaje que adoptaron tenía las suficientes cualidades como para hacerlo aprovechable: es increíblemente complejo, incluye métodos para cargarse el sistema operativo y reposicionar memoria, y a Edsger Dijkstra no le gusta (6). Dijkstra, como seguramente ya sabrá, es el autor de "el Go To considarado peligroso", que marcó época en la metodología de programación y fue aplaudido por programadores en Pascal y comedores de pastelitos. Y de todas formas, un programador de verdad puede escribir programas FORTRAN en cualquier lenguaje.

Los Programadores de Verdad podrían comprometer sus principios y trabajar en algo ligeramente más trivial que la destrucción o la vida, si hay suficiente dinero implicado. Hay varios programadores de verdad escribiendo video juegos en Atari, por ejemplo (pero no jugando a ellos: un programador de verdad sabe cómo ganar en cualquier momento; eso no es un reto para ellos). Todos los de LucasFilm son programadores de verdad (sería de locos rechazar el dinero de cincuenta millones de fans de Star Trek). La proporción de programadores de verdad en gráficos por ordenador es ligeramente menor de lo normal, sobre todo porque nadie les ha encontrado un uso a los gráficos por ordenador todavía. Por otra parte, toda la programación de gráficos por ordenador está hecha en FORTRAN, así que hay cierto número de ellos dedicados a los gráficos sólo para evitar escribir programas en COBOL.

1.6 El Programador de Verdad Jugando

Generalmente, el programador de verdad juega de la misma forma que trabaja: con ordenadores. El programador de verdad está constantemente asombrado de que su jefe le pague por lo que él haría de todas formas (aunque tiene cuidado de no expresar esta opinión en voz alta). Ocasionalmente, un programador de verdad sale fuera de la oficina a tomar un respiro de aire fresco y una cerveza o dos. He aquí algunas pistas para reconocer a los programadores de verdad fuera de la sala de ordenadores:

En una fiesta, los programadores de verdad son los que están en la esquina hablando sobre seguridad de sistemas y cómo saltársela.

En un partido de fútbol, el programador de verdad es el que compara las jugadas con la simulación impresa en papel continuo de 11 por 14.

En la playa, el programador de verdad es el que está dibujando diagramas de flujo en la arena.

En un funeral, el programador de verdad es el que dice "Pobre George. Y eso que casi había conseguido hacer que su rutina de ordenación funcionara antes de su coronaria".

En la tienda de ultramarinos, el programador de verdad es el que insiste en pasar él mismo las latas por el lector de barras, porque nunca confiaría en que un operador de teclado perforador lo hiciera bien la primera vez.

Piloto automático para naves espaciales

2011-01-13T18:06:00.002+01:00

Algún afortunado lector quizá haya jugado con el sensacional Elite de Ian Bell y David Braben. o sus aún más sensacionales continuaciones, Elite II: The Frontier y Frontier: First Encounters. Los tres son simuladores espaciales. El primero no tiene un motor físico muy realista: en Elite, la velocidad no es relativa. Hay un sistema de referencia universal, y la nave tiene una velocidad máxima dentro de ese sistema de referencia.

En cambio, en los otros dos el motor de física es mucho más realista. La velocidad actual está indicada siempre con respecto a un sistema de referencia dado, que generalmente se corresponde con el astro o planeta más próximo, y puede cambiar cuando éste lo hace. Los motores de las naves pueden acelerar y frenar, lo que impone una aceleración máxima, como es lógico, pero no hay limitación para la velocidad. Como pega en contra de ese realismo, aunque a favor de la jugabilidad, cabe nombrar que la aceleración de la nave no depende de la masa de la misma, lo cual sí que ocurriría si los motores ejercieran una fuerza de empuje máxima (F=ma). Otros detalles, aunque de menos importancia, son la falta de efectos relativistas y la omnidireccionalidad del empuje, así como el hecho de que la aceleración a la que la nave es sometida (típicamente rondando los 20 g) no podría ser soportada por un cuerpo humano. Le concedemos esas licencias de buena gana, porque el producto resultante bien lo vale.

Como los dos títulos comparten la palabra Frontier y no hay diferencias entre ellos en la parte que aquí nos interesa, me referiré a ambos colectivamente usando dicha palabra. Frontier cuenta con un piloto automático, cuyo principio de funcionamiento exacto desconozco, para viajar de un punto a otro del espacio. Sin embargo, yo al menos soy fan de desconectar el piloto automático y volar a mano, porque disfruto haciéndolo, y porque el piloto automático utiliza el motor delantero para frenar, que siempre tiene menos potencia, mientras que yo doy la vuelta a la nave para hacerlo y así puedo alcanzar una velocidad mayor y frenar a tiempo. (Es un error típico de novatos el acelerar continuamente hasta llegar al destino... y pasarse de largo por mucho, porque la potencia de frenado es la misma que la de aceleración y por lo tanto requiere el mismo tiempo acelerar que frenar).

Cuando quiero ir de punto a punto, observo la distancia al objetivo; entonces acelero hasta la mitad del trayecto y decelero hasta llegar. Los resultados suelen ser bastante buenos; en la primera aproximación quizá no me quede lo bastante cerca, pero con una o dos aproximaciones más (cada vez más cortas) el éxito está prácticamente garantizado.

Sin embargo, las batallas suelen aparecer en medio del viaje, y cuando lo hacen, me estropean los planes de navegación, porque debido a la inercia que llevo, voy acercándome al objetivo mientras dura la batalla, lo cual, cuando se va a 12.000 km/s, resulta significativo. Esto me hizo preguntarme: ¿y cómo calcular entonces el punto de frenada, para llegar cuanto antes al objetivo? La respuesta resulta no ser muy fácil para el caso de una dimensión. Cuando se da la eventualidad de una batalla, los movimientos laterales son pequeños, lo que permite considerar el caso 1D como una buena aproximación.

El método entonces sería el siguiente. El espacio necesario para frenar dada la velocidad actual viene dado por la fórmula v²/(2a), donde a es la aceleración máxima con la que podemos frenar y v la velocidad con la que se reanuda el viaje. Por razones que me costaría explicar, el punto de frenada viene dado por (x₀ - v|v|/(2a))/2, donde x₀ es el punto inicial, y el punto destino se asume 0. Puede ser que ya nos hayamos pasado de dicho punto, en cuyo caso es inevitable que nos pasemos de largo y tengamos que frenar hasta pararnos.

Pero, ¿qué pasa si estoy de camino hacia un planeta y de repente cambio de opinión y quiero dirigirme a otro? En ese caso, tengo una velocidad inicial cuya alineación probablemente no coincida para nada con el destino final, por lo cual no podemos usar el truco de 1D. ¿Qué puedo hacer, si quiero llegar cuanto antes?

Anticipo que no sé la respuesta. Si para el caso 1D no era fácil, para 3D es diabólico. Esto es lo que sé. Con un cambio de sistema de referencia, siempre se puede transformar el problema en uno en dos dimensiones. Se formularía así: dados un punto inicial, p₀, una velocidad inicial, v₀, y una aceleración máxima, a_max, determinar la función que da la aceleración a aplicar en cada instante, tal que se alcance el punto (0, 0) a velocidad nula en el menor tiempo posible.

O, alternativamente, partiendo parados desde el punto (0, 0), hallar la función de aceleración necesaria para alcanzar el punto p_F a una velocidad v_F (como vector), en el mínimo tiempo posible. Es lo mismo pero haciendo el camino al revés e invirtiendo la velocidad.

Es un problema frustrante porque, pese a su simple planteamiento y aspecto inocente, resulta bastante esquivo. La aproximación más inmediata, que es resolverlo en 1D para cada eje, no funciona porque al aplicar la aceleración máxima por cada eje, el módulo de la aceleración es mayor que la aceleración máxima. Podemos dividir la aceleración por √2 para compensar, pero es que no es la única pega: nada nos garantiza que el tiempo que se tarda en cada eje coincida. Así que tenemos además que encontrar una aceleración máxima por eje, que cumpla dos requisitos: que el tiempo sea el mismo en cada eje, y que la suma de los cuadrados de las aceleraciones máximas coincida con el cuadrado de la aceleración máxima dada.

¿Es óptima esa solución? Pues una de dos: o no lo es, o hay infinitas soluciones óptimas. Para demostrarlo, basta ver que si rotamos el sistema de referencia en el problema original, deberíamos obtener una versión rotada de la solución, cosa que no ocurre. Los cuatro posibles vectores de la solución forman siempre un rectángulo alineado con los ejes.

En fin, ando quebrándome la cabeza con este problema.

Colección de Simon Tatham: Range

2010-10-08T16:04:00.001+02:00

Un nuevo puzle ha sido añadido a la colección de Simon Tatham. Se llama Range y es interesante. Las reglas pueden recordar un poco al Singles en algunos aspectos, pero en realidad al jugarlo encontramos reminiscencias del Pattern más bien.

Las reglas no están muy bien explicadas en la documentación, así que voy a dar una explicación aquí. Nos presentan un casillero con varios números colocados en varias casillas. Nuestro objetivo es determinar qué casillas hay que rellenar de negro, cumpliendo las siguientes reglas:

Todas las casillas que no son negras tienen que formar una figura conexa, es decir, no se permite aislar una casilla blanca o un grupo conexo de casillas blancas en una «isla». Se entiende que están conectadas por arriba, abajo, izquierda o derecha; las diagonales no cuentan.
No puede haber dos cuadrados negros adyacentes (igualmente, por arriba, abajo, izquierda o derecha).
Las casillas con números no se pueden pintar de negro.
Cada número indica la cantidad de casillas totales, incluida ella misma, que pueden alcanzarse hasta tropezar con una casilla negra, moviéndose hacia arriba, abajo, izquierda o derecha a partir de la casilla donde está el número.

Por ejemplo, en el tablero por defecto de 9×6, si aparece un 14, eso quiere decir que no hay ninguna casilla negra en la fila ni en la columna donde aparece dicho número, pues hay 8 casillas horizontales y 5 casillas verticales además de la propia casilla, en total 14. Si aparece un 13, quiere decir que hay una casilla negra en uno de los cuatro extremos, no sabemos en principio en cuál, y todas las demás son blancas.

En la documentación pone como ejemplo el número 1. Si apareciera un 1, al contarse a sí misma ya estaría el cupo lleno, por lo tanto ese 1 debería estar rodeado de casillas negras. Pero eso formaría una región de una casilla que estaría aislada del resto de casillas blancas, quebrantando otra de las reglas. Por lo tanto, no puede aparecer un 1 en ningún tablero.

Como ayuda para resolver los problemas, podemos marcar casillas con un punto que indica «esta casilla no es negra». Así, por ejemplo, en cuanto colocamos una casilla negra podemos rodearla de puntos para recordarnos que ahí no puden ir otras casillas negras, de acuerdo con las reglas.

Como de costumbre, la solución de cada problema es única. El grado de adicción lo compararía con el del Pattern también. Podría decirse que Range (Kurodoko) es a Pattern (Nonograms, Picross) como Unequal (Futoshiki) es a Solo (Sudoku).

2010-08-14T00:00:00.006+02:00

Enhorabuena, acaban ustedes de sobrevivir a otro fin del mundo.

Batallitas

2010-08-12T19:19:00.000+02:00

2010-08-11T21:00:00.002+02:00

Las psicofonías son el arte de decirte lo que has de oír. Y es que, cuando te dicen lo que has de oír, lo oyes esté o no ahí. Un ejemplo:

(La canción está en Hindi, su título original es Mehboob Mere y pertenece a la película Fiza; la letra real en Hindi —o mejor dicho, una transcripción a nuestro alfabeto— está por ejemplo aquí: http://www.hindilyrix.com/songs/get_song_Mehboob%20mere,%20mehboob%20mere.html).

Frases para el recuerdo

2010-03-12T16:50:00.000+01:00

En los tiempos de los apostóles
los hombres eran muy barbáros:
se subían a los arbóles
y se comían los pajáros.

(Tildes añadidas para enfatizar la pronunciación).

Solución al problema de la cebra

2010-02-24T21:42:00.004+01:00

Vamos con la solución al puzle de la cebra.

Recordemos las pistas:

1=B5
3=E3
A1=D2
A2=B1
A5=E1
B2=E4
B3=D1
B4=C5
C4=D3
D4=E5
A4|B5
C1|D5
C3|D2
A3|A5
A3<A5

Ponemos en un casillero los símbolos, de tal forma que en cada casilla estén todos los símbolos de una fila. Para esto se puede emplear OOCalc, que es lo que he hecho.

	1	2	3	4	5
A	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5
B	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E3E4E5	E1E2E3E4E5	E1E2E3E4E5	E1E2E3E4E5	E1E2E3E4E5

Aplicamos las pistas 1, 2 y 11 para hallar la posición de B5, E3 y A4.

	1	2	3	4	5
A	A1A2A3A4A5	A4	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5
B	B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E3E4E5	E1E2E3E4E5	E3	E1E2E3E4E5	E1E2E3E4E5

Cada vez que consigamos averiguar el símbolo de una casilla, lo tachamos (borramos) de todas las demás casillas de esa fila:

	1	2	3	4	5
A	A1A2A3A5	A4	A1A2A3A5	A1A2A3A5	A1A2A3A5
B	B5	B1B2B3B4	B1B2B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E4E5	E1E2E4E5	E3	E1E2E4E5	E1E2E4E5

Ahora vamos recorriendo las pistas repetidamente. Para cada igualdad, hemos de comprobar si en las columnas donde aparece cada uno de los dos miembros también está el otro; si no es así, debemos tachar el extra. Por ejemplo, aplicando la pista 3 (A1=D2), puesto que en la 2ª columna no hay A1, hemos de quitar D2 de la misma:

	1	2	3	4	5
A	A1A2A3A5	A4	A1A2A3A5	A1A2A3A5	A1A2A3A5
B	B5	B1B2B3B4	B1B2B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E4E5	E1E2E4E5	E3	E1E2E4E5	E1E2E4E5

Repetimos con las pistas 4, 5, 6, 7, 8 y 10:

	1	2	3	4	5
A	A1A3A5	A4	A1A2A3	A1A2A3A5	A1A2A3A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C3C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2D3D4D5	D1D3D4D5	D1D2D3D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E5	E2E4E5	E3	E1E2E4E5	E1E2E4E5

Al examinar la pista 13, observamos que en la columna 2 no hay D2, por lo tanto en la columna 1 no puede haber C3. Al aplicar la pista 14, podemos tachar A3 y A5 de la columna 1. Como se queda solo A1 en la primera fila, lo tachamos de las demás celdas de esa fila (a partir de ahora lo haremos sin avisar). De acuerdo con la pista 15, A3 no puede estar a la derecha del todo, así que lo tachamos también. Después de todos esos cambios, queda esto:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2D3D4D5	D1D3D4D5	D1D2D3D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E5	E2E4E5	E3	E1E2E4E5	E1E2E4E5

Cuando al comprobar una de las igualdades, uno de los miembros está solo, el otro debe estarlo también. Aplicando ese principio a la pista 3 en este punto, hay que dejar solo D2 en la columna 1:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2	D1D3D4D5	D1D3D5	D1D3D4D5	D1D3D4D5
E	E1E2E5	E2E4E5	E3	E1E2E4E5	E1E2E4E5

Aplicamos las pistas 5 y 10, quitando E1 y E5, respectivamente, de la columna 1. Ya sabemos quién bebe E2=agua:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2	D1D3D4D5	D1D3D5	D1D3D4D5	D1D3D4D5
E	E2	E4E5	E3	E1E4E5	E1E4E5

Es B5, el noruego. Aplicamos las pistas 13, 8, 9 y ya no podemos seguir por este método:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2	C3	C1C2C4C5	C1C2C4C5	C1C2C4C5
D	D2	D1D4D5	D1D3D5	D1D3D4D5	D1D3D4D5
E	E2	E4E5	E3	E1E4E5	E1E4E5

Vamos a hacer un ensayo para falsar una hipótesis. Supongamos que en la columna 2 va E5 y no E4. Entonces, por la pista 10, tiene que ir D4 ahí. Por la pista 7, no puede ir B3 en esa columna, luego tiene que ser B2; pero ahora esto se contradice con la pista 6, que dice que donde va B2 tiene que ir E4. La conclusión es que en la columna 2 no puede ir E5. Lo tachamos y continuamos, aplicando las pistas 6, 10 y 7:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2	B1B3B4	B1B3B4	B1B3B4
C	C1C2	C3	C1C2C4C5	C1C2C4C5	C1C2C4C5
D	D2	D5	D1D3	D1D3D4	D1D3D4
E	E2	E4	E3	E1E5	E1E5

Nuevo punto muerto. Este es más complicado. Vamos a ensayar primero poniendo E1 en la columna 4 y viendo si nos conduce a una contradicción. Aplicamos las pistas 5, 10, 9, 15, 4, 8 y llegamos a este resultado provisional:

	1	2	3	4	5
A	A1	A4	A3	A5	A2
B	B5	B2	B3B4	B3B4	B1
C	C1C2	C3	C1C2C4C5	C1C2C4C5	C1C2
D	D2	D5	D1D3	D1D3	D4
E	E2	E4	E3	E1	E5

Ahora, si ponemos B3 en la columna 3, por la pista 7 tiene que ir D1 en la misma columna, luego en la columna 4 tiene que ir D3, y por la pista 9 va C4 en la misma. Pero esto se contradice con la pista 8, ya que en la columna 4 sólo puede ir B4. Y si ponemos B3 en la columna 4 en vez de la 3, tenemos exactamente el mismo problema. Pongamos donde pongamos B3, llegamos a una contradicción. La única conclusión posible es que E1 no puede ir en la columna 4.

Antes de seguir, una nota. En este punto se puede recurrir a una técnica del Sudoku que consiste en lo siguiente. Las columnas 1 y 5 tienen ambas C1 y C2, aunque no sabemos en qué orden. Esto quiere decir que o la 1 tiene C1 y la 5 C2, o viceversa, no hay otra posibilidad. En cualquiera de los dos casos, podemos tachar C1 y C2 de las columnas 3 y 4. Después de hacerlo, podemos recurrir a la pista 12 para asignar C1 a la columna 1, con lo que en la columna 5 iría C2. Esta es la solución parcial errónea a la que aludía al plantear el problema: C2 está en la columna correcta, como veremos, pero B1 no es la respuesta.

Volvemos al punto muerto anterior, ponemos E5 en la columna 4 y continuamos. Aplicamos las pistas 10, 5, 14, 4, 7, 9, 8, 12 y obtenemos la solución:

	1	2	3	4	5
A	A1	A4	A2	A3	A5
B	B5	B2	B1	B4	B3
C	C1	C3	C4	C5	C2
D	D2	D5	D3	D4	D1
E	E2	E4	E3	E5	E1

O sea, el dueño de C2 (la cebra) es B3 (el japonés).

¿Quién es el dueño de la cebra?

2010-02-19T09:39:00.000+01:00

Cuando era niño, vi en una revista un pasatiempo que me resultó muy curioso. Lo copié y lo repartí a mis compañeros y hubo cierto revuelo con el mismo. Se ha divulgado en otras formas, pero aún permanecen en mi memoria las frases del planteamiento y la solución tal y como figuraban en la revista.

Decía así (disculpas por la propaganda de tabacos, que sospecho que estaba detrás de esa publicación, pero he preferido dejar el texto original tal y como lo conocí):

Hay cinco casas de distinto color con individuos de diferentes nacionalidades. También hay distintos animales, cigarrillos y bebidas en cada una de ellas.
El inglés vive en la casa roja.
El español es el propietario del perro.
En la casa verde se bebe café.
El ucraniano bebe té.
La casa verde está contigua y a la derecha (la derecha del lector) de la casa de marfil.
El fumador de Winston tiene caracoles.
En la casa amarilla se fuma Camel.
En la casa del centro se bebe leche.
El noruego vive en la primera casa de la izquierda.
El hombre que fuma Chesterfield vive en la casa contigua a la del dueño del zorro.
En la casa contigua a aquella donde se encuentra el caballo se fuma Camel.
El fumador de Lucky Strike bebe naranjada.
El japonés fuma Philip Morris.
El noruego vive al lado de la casa azul.

Las preguntas eran: ¿quién bebe agua? y ¿quién es el dueño de la cebra?

La respuesta a la primera pregunta es relativamente fácil, pues surge al poco tiempo de ir aplicando pistas. La segunda requiere llegar hasta el final, lo cual requiere bastante más esfuerzo.

Se puede abstraer este problema de la siguiente manera: sea un casillero de 5 filas y 5 columnas, en el que se deben colocar los símbolos A1, A2, A3, A4, A5, B1 a B5, C1 a C5, D1 a D5 y E1 a E5, cada uno en una casilla. Las letras indican la fila en la que colocarlos, pero los dígitos NO indican la columna; en este caso he escogido una permutación al azar de los números del 1 al 5 para cada fila. Para saber en qué columna colocar cada uno, necesitaremos las pistas. Usaremos la siguiente notación:

n=símbolo indica que en la columna n ha de ir el símbolo dado. Por ejemplo, 1=A4 indica que el símbolo A4 se debe colocar en la fila A, columna 1.
símbolo1=símbolo2 indica que ambos están en la misma columna.
símbolo1|símbolo2 indica que están en columnas adyacentes.
símbolo1<símbolo2 indica que símbolo1 está a la izquierda de símbolo2 (no necesariamente adyacentes).

Las pistas equivalentes para este problema (no en el orden original) son:

1=B5
3=E3
A1=D2
A2=B1
A5=E1
B2=E4
B3=D1
B4=C5
C4=D3
D4=E5
A4|B5
C1|D5
C3|D2
A3|A5
A3<A5

Y las preguntas son: ¿qué simbolo hay en la fila B en la misma columna donde está E2? ¿Qué símbolo hay en la fila B en la misma columna donde está C2? Es decir, hallar x e y tales que Bx=E2 y By=C2.

Al principio iba a preguntar en qué columna van E2 y C2, pero después me lo he pensado, dado que hay una solución parcial errónea que tiene C2 en la columna correcta, pero no tiene el símbolo bueno en la fila B de dicha columna. Aquí se busca la solución correcta.

Nótese que las dos últimas pistas juntas equivalen a la Nº. 6 del problema original, pero he querido hacerlo más general por si revisitamos este tipo de acertijos en el futuro.

La equivalencia con el problema anterior es: A1=Amarilla, A2=Roja, A3=Marfil, A4=Azul, A5=Verde; B1=Inglés, B2=Ucraniano, B3=Japonés, B4=Español, B5=Noruego; C1=Zorro, C2=Cebra, C3=Caballo, C4=Caracoles, C5=Perro; D1=Philip Morris, D2=Camel, D3=Winston, D4=Lucky Strike, D5=Chesterfield; E1=Café, E2=Agua, E3=Leche, E4=Té, E5=Naranjada.

No intente hacer esto en su oficina

2010-02-18T21:38:00.000+01:00

2010-02-17T14:17:00.001+01:00

SignPost es otro nuevo juego en la colección de puzles de Simon Tatham. Partiendo de la casilla 1, hay que avanzar un número indeterminado de casillas en cada paso en la dirección de la flecha, hasta acabar en la que tiene una estrella tras haber recorrido el resto del tablero visitando cada casilla una sola vez. A veces se nos indica en qué paso hay que tocar cierta casilla. Durante la resolución, lo normal es que vayamos conectando partes separadas hasta que tengamos todo conectado.

Como de costumbre, genera problemas con solución única.

No me ha enganchado, pero me ha entretenido, que también es importante.

Paintfuck

2010-02-11T12:20:00.000+01:00

Ya hablamos en el artículo Lenguajes esotéricos sobre Brainfuck, un lenguaje de ocho instrucciones sumamente popular. Tanto, que existen multitud de variantes de dicho lenguaje. He aquí unos cuantos:

En COW se representan la mayoría de instrucciones mediante cambios en las mayúsculas de la palabra «Moo». Es una variante de Brainfuck con cinco instrucciones nuevas.
FukYorBrane es un lenguaje diseñado para que dos programas en Brainfuck compitan entre sí.
Brainfork añade una instrucción para convertir el Brainfuck en multitarea.
Boolfuck y Smallfuck son versiones de Brainfuck que operan sobre bits en vez de palabras.
Dimensifuck utiliza un casillero n-dimensional en vez de bidimensional.
Quantum brainfuck opera sobre qubits en vez de sobre enteros. Está basado en la teoría de computación cuántica.
2L es una variante bidimensional que usa dos símbolos (y el espacio en blanco).
Hay muchas más variantes; véase Category: Brainfuck derivatives en la wiki de lenguajes esotéricos.

En particular, el Smallfuck opera sobre un casillero donde cada celda es de un bit. Tiene cinco instrucciones: elimina la entrada y la salida y, como no le hace falta incremento y decremento porque las dos operaciones hacen lo mismo, las sustituye por el comando *, que invierte el bit en la celda actual. Es relativamente sencillo convertir un programa en Brainfuck a Smallfuck (salvo por la entrada/salida), sustituyendo el incremento y decremento por subrutinas que manipulan los bits en bloques de, por ejemplo, 8 bits.

Y del Smallfuck surge el Paintfuck. Es una variante creada por Wouter Visser que utiliza un casillero bidimensional en vez de lineal, lo cual en principio no parece nuevo. Lo que lo hace original es que está pensado para que el casillero sea representado en la pantalla, viendo en tiempo real y de forma animada cómo el programa actúa sobre el mismo.

Las instrucciones < y > son sustituidas por n, s, e, w para los cuatro puntos cardinales respectivos. Las demás instrucciones son idénticas a las de Smallfuck, así que consta de siete instrucciones en total. Todo carácter que no sea una instrucción válida (incluyendo las versiones en mayúsculas de los comandos) se considera un comentario y por tanto no interviene en el programa, pero tampoco causa error. Por ello, es común que los comentarios intercalados se escriban en mayúsculas, para evitar escribir accidentalmente alguna de las letras n, s, e o w que influirían en el comportamiento del programa. El espacio de datos está inicialmente vacío (todo ceros).

Aunque es un lenguaje Turing-completo cuando se aplica a casilleros infinitos en al menos una dimensión, lo cierto es que los casilleros toroidales finitos suelen ser más interesantes. Así, este sencillo programa rellena todo el casillero de unos, aunque no para nunca:

*[e[s]*]

¿Qué hace este programa? Primero, cambia la casilla inicial de 0 a 1. Esto le permite entrar en el bucle. Ya dentro del bucle, se mueve hacia el este y, si da con una casilla que no es cero, se mueve hacia el sur hasta que encuentre la primera que es cero. Si se parte de un casillero vacío, eso debería ocurrir en la línea siguiente, salvo que llegue al punto inicial, en cuyo caso se quedará enganchado indefinidamente en ese bucle. Tanto si va al sur como si no, pone a 1 la casilla actual (era 0 seguro, o de lo contrario no habría salido del bucle anterior) y repite.

Programar en Paintfuck tiene el aliciente de que vemos cómo se desarrolla nuestro programa. Además, trabajar con bits es más simple en general. Entre los programas actualmente escritos en Paintfuck hay, por ejemplo, uno para hacer funcionar el autómata del Juego de la Vida de Conway del que hablamos en la entrada sobre autómatas celulares; también hay otro autómata finito llamado la hormiga de Langton y un contador decimal.

El contador decimal, escrito por un servidor de ustedes, representa cada número dentro de un bloque de 3×5, y se basa en una sugerencia dada en el canal de IRC #esoteric sobre realizar tal contador analizando cada dígito para ver de cuál se trata e incrementarlo. Requirió bastante esfuerzo diseñar la fuente, hallar los píxels distintivos únicos de cada número y analizar los cambios que convertían cada dígito en el siguiente. El programa final es este:

PAINTFUCK PROGRAM BY PEDRO GIMENO 2008-12-01.

swwww*es*ww*s*ee*s*ww*sseeee*wwnw*ww
*[*
  nnee[*ww*s*nee]ww[*ee*ww]s
  *[*ne[*w*n*se]w[*e*w]n
    [*ee*e*s*w*w*s*e*e*s*ww*wnn*n]
    s*[*nnee*s*w*es*s*s*e*ww*wnn]*s]
  n*[*
    nee[*ww*s*nee]ww[*ee*ww]s[*nne*ees*w*w*ess*w*w*n]
    s*[*
      nnnee[*ww*s*nee]ww[*ee*ww]s*[*nee*e*s*s*ss*w*w*wn*nn]
      ss*[*
        seee[*www*n*seee]www[*eee*www]n[*e*ee*s*www*n]
        s*[*
          ee[*ww*n*see]ww[*ee*ww]n*[*nnne*ee*sww*sss*e*en*wwws*n]
          s*[*
            nnne[*w*s*ne]w[*e*w]s*[*nnee*sw*s*ee*ss*w*w*wn*n]
            s*[*
              nnne[*w*s*ne]w[*e*w]s[*ne*sss*s*wnn*n]
              s*[*
                nneee[*www*s*neee]www[*eee*www]s[*ne*ees*ww*s*see*sw*w*wnn*n]
                s*[*
                  se[*w*n*se]w[*e*w]n[*eee*ssww*n*w*n]
                  s*[*
                    ne*e*ws*s*wwwwws*nn]n]]s]s]]n]]n]
  sss*[
    [*e*]*wwwww]n
*]

Bueno, en realidad esa es la versión no comentada. La versión comentada es bastante más larga [1].

Pueden verse este y otros programas en acción gracias al intérprete de Paintfuck en JavaScript, que también puede servir para quien quiera escribir sus propios programas en Paintfuck.

Referencias

[1] http://www.formauri.es/personal/pgimeno/temp/esoteric/paintfuck/decimal-counter.pfk

Dibujando curvas de Bézier cúbicas

2010-02-03T17:49:00.008+01:00

He actualizado el tutorial de GIMP sobre la aplicación de efectos de forma radial para incorporarle una animación que cuando publiqué la entrada no había puesto a punto, aunque pensaba que sería una buena adición para explicar cómo actúa el filtro Coord. polares de GIMP. La animación en cuestión es esta:

Está hecha con un programa que escribí en mi lenguaje favorito para hacer pequeñas utilidades cuya velocidad no es crucial, es decir, en PHP. Cuando me puse a pensarlo, me di cuenta de que para hacer la animación que tenía en mente me iban a ser muy útiles las curvas de Bézier cúbicas. Sin embargo, al mirar el listado de funciones de la librería GD, descubrí que no contaba con funciones de dibujado de estas curvas.

Tenía, pues, unas pocas opciones. Una era buscar algún otro módulo PHP capaz de dibujarlas. Resulta que el módulo de ImageMagick lo hacía. Pero usar GD tenía sus ventajas para mí, porque va muy al grano y se puede trabajar con imágenes indexadas (es decir, con paleta), y el ImagickDraw no estaba muy bien documentado. Otra era buscar si alguien más había implementado lo mismo. Encontré unas pocas implementaciones, sí, una de ellas de PEAR que parecía que precisaba mucho aprendizaje para usarla, y otra que resultó tener una calidad muy pobre. La tercera opción era hacerme yo una función para dibujarlas. Finalmente me decanté por esa, aprovechando la ocasión para acometer un reto que tenía pendiente desde hace años. Con algún sistema simple me habría bastado, pero quería resolver el problema de forma definitiva para tener una función que dibujara curvas aplicable a cualquier campo, y que me sirviera de referencia en caso de necesitar reescribirla en otro lenguaje.

Métodos iterativos

Así que estuve investigando los métodos que pude encontrar, para hacerme una idea de por dónde atacar el problema. Sabía de antemano que los métodos recursivos daban mejor resultado que el método iterativo simple.

El método iterativo simple

La forma más sencilla de dibujar curvas de Bézier es utilizar la fórmula directamente, escogiendo un incremento de t adecuado que nos permita recorrer el intervalo [0, 1] de forma uniforme, trazando líneas rectas entre cada punto y el anterior. Además, podemos calcular sólo los coeficientes hasta la mitad usando la igualdad B(P₀, P₁, P₂, P₃, t) = B(P₃, P₂, P₁, P₀, 1 - t). Ya conocía este sistema. El problema principal es que no existe un incremento de t adecuado. Si dibujamos demasiados segmentos, podemos encontrarnos con que la línea se engrosa en algunas zonas de forma muy antiestética. Si no dibujamos suficientes, quedarán a la vista los trazos angulosos de los segmentos rectos con que se dibuja la curva. Lo malo es que en ciertas curvas es fácil que se vean ambos defectos a la vez: trazos angulosos y líneas engrosadas. Así que hay que buscar alternativas.

El método iterativo variable

El problema del método iterativo simple radica en que la distancia entre puntos consecutivos (al aplicar un incremento de t constante) no es uniforme. Este problema se podría salvar recurriendo a la fórmula de la velocidad de la curva, que nos da un indicador de cuán grande será el desplazamiento para un t dado. Para una curva que va de P₀ a P₃ con puntos de control P₁ y P₂, la fórmula es:

V(t) = 3·(1 - t)²·(P₁ - P₀) + 6·t ·(1 - t)·(P₂ - P₁) + 3·t²·(P₃ - P₂)

No he probado este método. A primera vista, parece que tiene el problema de que, si los incrementos no son lo suficientemente pequeños, podrían verse los polígonos de nuevo, así que habría que hacerlos lo bastante pequeños. Hacerlos de un píxel puede presentar problemas cuando los trazos son diagonales. Quizá haciéndolos de 2^½ (1,414213...) píxels, que es la distancia entre dos píxels diagonales, o ligeramente superior para evitar problemas de redondeos, fuera suficiente. Tendría que experimentar. Otra pega es que no veo inmediatamente cómo trasladar velocidad a píxels.

Métodos recursivos

En general, los métodos recursivos se basan en subdividir la curva en múltiples segmentos, utilizando el algoritmo de De Casteljau: Sea B(P₀, P₁, P₂, P₃) una curva de Bézier definida por los puntos P₀, P₁, P₂, P₃. Esta curva se puede dividir de forma exacta en dos segmentos, B₀(P₀, P₀₁, P₀₁₂, P₀₁₂₃) y B₁(P₀₁₂₃, P₁₂₃, P₂₃, P₃). El punto P₀ y el punto P₃ coinciden con los de la curva original, ya que son los extremos del segmento curvo y lógicamente tienen que estar cada uno en una de las curva subdivididas. El punto de subdivisión, P₀₁₂₃, también forma parte de la curva, pues esa es precisamente la ventaja del método de De Casteljau.

P₀₁ es un punto situado en la recta entre P₀ y P₁, a distancia relativa t. Es decir, P₀₁ = (1 - t)·P₀ + t ·P₁. Análogamente obtenemos P₂₃ = (1 - t)·P₂ + t ·P₃. Para obtener los puntos que faltan es preciso calcular un punto extra, P₁₂ = (1 - t)·P₁ + t ·P₂. Ahora, P₀₁₂ = (1 - t)·P₀₁ + t ·P₁₂ y P₁₂₃ = (1 - t)·P₁₂ + t ·P₂₃. Por último, P₀₁₂₃=(1 - t)·P₀₁₂ + t ·P₁₂₃. La figura siguiente ilustra el proceso. Cuando t = ½, nos basta con calcular medias entre los puntos.

Método de subdivisión de una curva de Bézier cúbica en dos, en el punto t=0,3. La curva B(P₀, P₁, P₂, P₃) puede ser dividida en las dos curvas B(P₀, P₀₁, P₀₁₂, P₀₁₂₃) y B(P₀₁₂₃, P₁₂₃, P₂₃, P₃).

Los algoritmos recursivos realizan esta subdivisión, normalmente en el punto t=½, y continúan haciendo lo mismo recursivamente con cada uno de los subsegmentos obtenidos. Difieren en la elección del caso base de la recursión.

Método de la colinealidad

Las subdivisiones recursivas van aproximando cada vez más el segmento dividido a un segmento de recta. Si conseguimos determinar en qué momento es tan parecido a una recta que no es distinguible a simple vista, podremos trazar una recta en su lugar y obtener así una muy buena aproximación.

La curva es más plana cuanto más próximos estén los dos puntos de control a la recta que une los puntos origen y final, así que el cálculo de esa distancia es una buena forma de determinar si son casi colineales. Para evitar una raíz, se puede calcular el cuadrado de la distancia en lugar de la distancia misma. La fórmula del cuadrado de la distancia es:

d(P₁, P₀P₃)² = ((P_x3-P_x0)·(P_y1-P_y0) - (P_y3-P_y0)·(P_x1-P_x0))²/((P_x3-P_x0)² + (P_y3-P_y0)²)

y lo mismo cambiando P₁ por P₂.

Actualización 2011-03-23: Tengo pendiente examinar otra forma de evaluar el «grado de colinealidad», que se me ha ocurrido al releer esta entrada. La idea sería utilizar la ecuación de la recta que pasa por P₀ y P₃, rotándola 90° si el valor absoluto de la pendiente es > 1, para hallar el valor de y que se correspondería con el valor de x del punto a comprobar, hallando entonces la diferencia con la y de dicho punto. Esto podría ser más rápido que el cálculo de la distancia aquí nombrado y probablemente sería igualmente efectivo.

Que sean casi colineales no es condición suficiente para poder aproximar la curva como un segmento de P₀ a P₃. Hay otra condición adicional, y es que tanto P₁ como P₂ estén comprendidos entre P₀ y P₃. Si no se impone esta condición, tanto P₁ como P₂ pueden estar fuera del segmento P₀P₃ y el resultado teórico sería una curva que desde uno de los extremos va temporalmente en dirección contraria al otro extremo, y ese fragmento no sería dibujado. Por ejemplo, si consideramos la curva B((0,0), (-3,0), (10,0), (10,0)), los puntos P₁ y P₂ son colineales con P₀P₃ y, pese a ello, la curva se extiende un poco hacia el lado de abscisas negativas.

En casos como el indicado, la subdivisión podría requerir infinitos pasos para el subsegmento que contiene el pico. Para evitarlo, se puede dar un margen de error: si P₂ y P₃ están ambos dentro de un ~~cuadrado~~ rectángulo de tamaño (|P_x3-P_x0|+ε, |P_y3-P_y0|+&epsilon), se consideran buenos.

Este es el método que escogí finalmente. Los resultados son muy decentes y el algoritmo es aceptablemente rápido. Como parámetros, la distancia al cuadrado que puse para considerar los puntos colineales es 0,125 píxels y el ε que escogí es 0,25 (un cuarto de píxel).

Método de la longitud

La longitud de una curva de Bézier puede ser calculada numéricamente, no hay una fórmula explícita general para la misma. Además de mediante una integral que requiere métodos numéricos clásicos y complicados, hay una forma recursiva de aproximarla que, además, nos da un método para dibujarla.

Sea L₀ la longitud del segmento P₀P₃ y L₁ la suma de las longitudes de los segmentos restantes, concretamente L₁=|P₀P₁| + |P₁P₂| + |P₂P₃|. Entonces, la media de esos valores, (L₁ + L₀) / 2, da una aproximación a la longitud, y L₁ - L₀ da una medida del error. Dicho error decrece en relación 2^-4m donde m es el número de subdivisiones [1].

Se puede entonces dibujar el segmento de forma que si la longitud del subsegmento actual es lo bastante pequeña, se trace dicho subsegmento como recta.

No he probado este método. En realidad es muy similar al anterior, ya que cuando el error es pequeño, significa que los puntos están próximos a ser colineales, lo cual es casi lo mismo que el método anterior. En este no nos salvamos de calcular al menos cuatro raíces cuadradas, por lo cual lo deseché antes de probarlo.

Otros métodos

Descomposición en cuadráticas

En [2] se da una forma de descomponer una curva cúbica en cuatro segmentos de curva cuadrática. No me ha convencido el resultado, pero al menos he creído oportuno dejar una referencia para quien quiera averiguar más. Con este método, queda abierto el problema de cómo dibujar una curva cuadrática de forma eficiente.

Partición de la derivada por octantes

Para terminar, vamos a considerar un método que ha sido utilizado por METAFONT, el programa de diseño tipográfico de D. E. Knuth. Para leer la documentación del programa METAFONT decentemente, necesitaremos la utilidad Weave, capaz de extraer archivos escritos en TeX (el formato de proceso de texto de Knuth) a partir de archivos WEB (que contienen una mezcla del programa en Pascal y la documentación en TeX). El original está aquí: http://mirror.ctan.org/systems/knuth/dist/mf/mf.web. La explicación, junto con el código correspondiente, comienza en la §384.

La idea del método es similar a la de los círculos de Bresenham: se clasifica la derivada de la curva por octantes y se transforma cada uno de los octantes al primero, de manera que la pendiente (el incremento de y por cada incremento unitario de x) no sea superior a la unidad. Con este método se consigue que cada incremento de x vaya asociado a cero o un incremento de y, con lo cual la curva resultante tiene una fineza superior. El precio a pagar por tanto refinamiento es un programa que cuesta mucho entender, además de que cuesta bastantes cálculos. El beneficio es la curva más perfecta posible, igual que la línea de Bresenham es la recta más perfecta posible.

Referencias

[1] http://steve.hollasch.net/cgindex/curves/cbezarclen.html
[2] http://www.timotheegroleau.com/Flash/articles/cubic_bezier_in_flash.htm

Aplicando efectos de forma radial

2010-01-30T16:59:00.001+01:00

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... (en Gimp 2.4 los logotipos están en el menú Xtns de la ventana de herramientas).

Resultado de aplicar el efecto Viento de forma radial

Peluso

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. 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 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.

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:

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.

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.

Solución al problema de la probabilidad de cada longitud

2010-01-28T12:10:00.015+01:00

(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

2010-01-28T12:10:00.014+01:00

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%

Subida automática de archivos a GMail mediante IMAP

2010-01-26T11:29:00.007+01:00

(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

2010-01-26T11:28:00.006+01:00

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.

Génera y sexa

2010-01-23T11:49:00.003+01:00

¿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.

Estreno de foro en 11-s.eu.org

2010-01-18T23:07:00.002+01:00

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.

Y más puzles

2010-01-17T17:43:00.001+01:00

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/.

Mapa del RGB

2010-01-15T11:13:00.000+01:00

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:

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);
?>

Respuesta de la FUB sobre las imágenes del Hale

2010-01-14T00:30:00.006+01:00

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».

El Wall Hugger de Robot Odyssey

2010-01-13T12:21:00.001+01:00

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, 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 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 (clic para ampliar)

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

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 (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

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

2010-01-06T19:53:00.001+01:00

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.

2010-01-06T18:18:00.001+01:00

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.

Autómatas celulares

2010-01-03T22:07:00.005+01:00

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 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:

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

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»:

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, 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/r_e⌋ + ⌊I/r_i⌋, 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. r_e y r_i 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), r_e (relación de infección para células enfermas), r_i (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.

Queda a criterio del lector decidir si probarlo o no. Si acude a la entrada con JavaScript activo, podrá ver un Brian's Brain en tiempo real a continuación. Si no, tendrá que conformarse con la animación fija obtenida de Wikipedia aquí reproducida. Si le gusta y le pica el gusanillo de ver otros mundos bidimensionales en movimiento, le garantizo que le encantarán los dos programas mencionados. Aquí probablemente hablaremos pronto de algún espécimen de ese zoo.

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

El Hexadecimal ha sido patentado - Quiero más

2010-01-02T13:10:00.003+01:00

(English version below)

Recientemente, la lista de correo de GMP recibió una invitación a los desarrolladores para contribuir en el recientemente creado proyecto Peer-To-Patent Australia, porque Hewlett-Packard ha enviado una solicitud de patente que podría estar relacionada con el proyecto.

Al buscar en Google el título de la patente (Binary representation of number based on processor word size), me he encontrado, para mi sorpresa, con que ya estaba concedida en Europa y EE.UU. Pero mi sorpresa ha sido aún mayor tras leer la patente.

El «invento» cubre el almacenamiento de números que se pretende representar en base B, como números en base Bⁿ, a razón de un dígito por palabra, donde Bⁿ es la mayor potencia entera de B que cabe en una palabra de procesador. Por ejemplo, para almacenar un número que se pretende representar en decimal en un procesador de 16 bits, la idea es guardar el número en base 10.000, ya que 10⁴ es la mayor potencia entera de 10 que puede representarse en una palabra de 16 bits (10⁵=100.000 se sale de rango).

Esa resulta ser la misma idea que usé por simplicidad para el contador de ciclos de mi depurador de BF (brfd 1.0) en 2001, al que le llamé «Petradecimal» (búsquense las apariciones de «Petra» en el código). En realidad, sólo puedo demostrar 2006 como fecha inferior, porque esa es la fecha en la que está archivado en la Wayback Machine, que recientemente fue admitida como prueba por un tribunal de EE.UU. Aquí está el enlace a la Wayback Machine: [1]. En la lista de correo de GMP dije por error que fue en 2005 cuando lo usé, pero esa era en realidad la fecha de una versión posterior, la 1.0.1, presentada en la entrada anterior. El tiempo pasa tan rápido...

Lo peor es que se puede argumentar que la patente cubre la conversión de/a hexadecimal en procesadores de 8, 16, 32 y 64 bits, cuando dicha conversión se realiza en bloques de una palabra de procesador cada uno.

Sin embargo, lo que quiero decir no es que esta patente no debería haber sido concedida.

Lo que está haciendo Peer-To-Patent es evitar que se patenten ciertos inventos que cuentan con precedentes, de manera que la calidad general de las patentes concedidas mejore, pero no protege contra la trivialidad. Sin embargo, el mundo no necesita patentes de software de mejor calidad. Eso es simplemente un paso que disfraza a las patentes como algo marginalmente aceptable, disimulando el verdadero problema. El mundo necesita llenarse de patentes triviales y de baja calidad, para que más y más gente se dé cuenta de cuán ridículo es el sistema de patentes aplicado al software y por qué las patentes y el software necesitan divorciarse, y así todos juntos pidamos ese divorcio a gritos.

El proyecto Peer-To-Patent está ahí para ayudar a los de la oficina de patentes, gente dedicada a tiempo completo a investigar patentes, porque incluso con su dedicación a tiempo completo, fácilmente se les puede escapar identificar algo que ya está inventado. Esto por sí mismo expone una buena parte de lo que está mal con las patentes de software. Si los investigadores dedicados a tiempo completo no pueden saber con seguridad si un invento ya está inventado, ¿cómo puede, digamos, un programador de software libre estar seguro de no pisar una mina en forma de patente mientras está haciendo su trabajo creativo diario? Y al margen de si el programador hace o no un trabajo de investigación todavía más cuidadoso que los de la oficina de patentes, hay una posibilidad de que la idea sea patentada después de todas formas, como ha sido mi caso. Tengo suerte en esta ocasión de ser capaz de demostrar que 2006 es la fecha de mi «invento». ¿Qué pasaría si no pudiera?

La existencia de Peer-To-Patent es, por tanto, un síntoma de que el sistema de patentes no funciona cuando se aplica al software, pero no el único. La existencia de la Open Invention Network para desarrollar una biblioteca de patentes encaminadas a la defensa contra los juicios por patentes, y la propuesta de un seguro contra patentes, significan que estamos en una situación en la que estamos defendiéndonos de la ley en lugar de ser protegidos por ella. Mejorar la calidad de las patentes NO es la solución. Acabar con las patentes de software, por otro lado, sí lo es. Las patentes de software deben ser eliminadas, no mejoradas.

Referencias

[1] http://web.archive.org/web/*/http://www.formauri.es/personal/pgimeno/prog/brfd10.zip

The patent on Hexadecimal - We need more

2010-01-02T13:09:00.000+01:00

Recently the GMP mailing list received an invitation for the developers to contribute to the recently created Peer-To-Patent Australia, because Hewlett-Packard had filed a patent application which could be related to the project.

I googled for the patent title (Binary representation of number based on processor word size) and, to my surprise, the patent was already granted in Europe and U.S.A. My surprise was even bigger after reading the patent.

The 'invention' covers storage of numbers that are to be represented in base B as numbers in base Bⁿ, one digit per word, Bⁿ being the biggest integer power of B which fits in a processor word. For example, to store a decimal number in a 16-bit processor the idea is to store the number in base 10,000, because 10⁴ is the biggest integer power of 10 that can be represented in a 16-bit word (10⁵=100,000 would not fit).

That happens to be the idea I used for simplicity for the cycle counter in my BF Debugger (brfd 1.0) back in 2001, which I called 'Petradecimal' (look for appearances of 'Petra' in the code). Actually I can only prove 2006, because that's the date in which it's filed in the Wayback Machine, recently admitted as proof by an U.S. court. Here's the Wayback Machine link: [1]. In the GMP mailing list I wrongly said it was in 2005 when I used it, but that was actually the date of a later version, 1.0.1. Time passes so fast...

Even worse, arguably the patent covers conversion to/from hexadecimal in processors with 8-, 16-, 32-, and 64-bit word sizes, when that conversion is done in blocks of one processor word each.

However, my point is not that this patent should not have been filed.

What Peer-To-Patent is doing is avoiding some patents with prior art so that the overall quality of the patents granted is enhanced, but it does not protect against triviality. However, the world does not need better-quality software patents. This is merely a step towards concealing the actual cause of concern, disguising the patents as something marginally acceptable. The world actually needs to be full of trivial, low-quality patents, so that more and more people realize just how silly the patent system is when applied to software and how software and patents should get a divorce, and loudly ask for it.

The Peer-To-Patent project is there to help the patent officers who are full-time dedicated to research patents, because even with their full-time dedication they can easily fail to identify what is already invented. This in itself exposes a good part of what's wrong with software patents. If full-time dedicated researchers can't know for sure whether a patent has no merit, how can, say, a free software programmer be sure not to be stepping on a patent mine while doing his everyday creative work? And regardless of whether that programmer did actually do even more careful research than the patent officers, there's the possibility of the idea being patented afterwards anyway, as has been my case. I'm lucky in this case to be able to prove 2006 as prior art date. What if I couldn't?

The existence of Peer-To-Patent is, thus, a symptom that the patent system is broken when applied to software, but not the only one. The existence of the Open Invention Network for building a patent porfolio aiming at the defense against patent suits, and the proposal of a patent insurance, mean that we're in a situation in which we are defending ourselves against the law instead of being protected by it. Improving patent quality is NOT a solution. Terminating patents on software, on the other hand, is. Software patents must be eliminated, not enhanced.

References

[1] http://web.archive.org/web/*/http://www.formauri.es/personal/pgimeno/prog/brfd10.zip

2010-01-01T19:58:00.002+01:00

Francisco Gimeno Garrote. 10 de agosto de 1931 - 31 de diciembre de 2009

Adiós, papá.

Estaremos cerrados unos días.

2009-12-30T21:43:00.000+01:00

Cachis... Se me escapó una entrada. Si alguien la ha visto, que la olvide hasta el próximo domingo por la tarde. Aún no estaba acabada :(

Lenguajes esotéricos

2009-12-29T16:26:00.009+01:00

Este artículo es una reedición, con algunos extras nuevos, del que publiqué en la columna Informática recreativa en la ahora extinta web de Lola Cárdenas El rincón del programador. También fue publicada con mi permiso en programacion.com. Pido disculpas si algunos enlaces no funcionan. También pido disculpas por el uso repetido de la palabra decrementar a lo largo del texto, no reconocida en el DRAE.

Ser aficionado a la informática y no saber programar es algo que no casa bien. Un auténtico aficionado sabrá al menos hacer pinitos en algún lenguaje de programación, sea Java, Basic, Pascal, C o cualquier otro. Entre los lenguajes de programación también hay modas; un cierto lenguaje «se lleva» más que otros en ciertos momentos, lo cual es lógico habida cuenta de que la informática evoluciona y con ella las necesidades.

No muchos conocen, sin embargo, la inmensa variedad de lenguajes de programación que hay disponibles. Los nombres que ahora mismo me vienen a la cabeza sin consultar ninguna fuente de información son COBOL, ALGOL, APL, BASIC, RPG, Forth, Fortran, Lisp, PL/I, Logo, C, Pascal, Perl, Python, TCL, Ada, Java, ensamblador... y he omitido deliberadamente nombrar variantes como Visual Basic, RPG III, Scheme (un derivado de Lisp), C++ o Delphi (un Pascal ampliado).

Cuando llegamos al ensamblador, el tema de las variantes se convierte en locura. Cada modelo de microprocesador tiene su propio ensamblador, y existen miles y miles de modelos: Z80, PIC-16, 8051, 8086, 6809, 68000, 6502... A veces, como en el caso del 80x86 de Intel, hay varios, incluso multitud de dialectos: el dialecto oficial de Intel, el dialecto oficial del proyecto GNU (formato AT&T), el dialecto del ensamblador gratuito NASM...

Para liar aún más la madeja existen personas que inventan su propio lenguaje ensamblador, el de un procesador que no existe. El ejemplo más notable quizá sea el de Donald Ervin Knuth, matemático y escritor de una serie de tratados sobre computación famosos en todo el mundo. Existen simuladores de los dos lenguajes ensambladores que ha inventado, que corresponden a los procesadores imaginarios llamados MIX y MMIX.

Ahí no queda todo. Hay gente que no ve razón en que el lenguaje a inventar sea un lenguaje ensamblador; simplemente inventan un lenguaje nuevo. Las razones son muy variadas; está claro por ejemplo que Sun Microsystems tenía razones poderosas para inventar el Java. Pero no todo el mundo necesita razones poderosas; aquí vamos a tratar precisamente sobre los lenguajes de programación que han sido inventados por puro entretenimiento. ¿Hay gente capaz de eso? Sí, y no pocos. Incluso existen intérpretes de la mayoría de esos lenguajes, y en algunos casos hasta compiladores.

Uno de los primeros lenguajes esotéricos (al menos que yo tenga referencia, pues fue creado en 1972), y quizá de los más extendidos, es el INTERCAL. Su diseño se fundamenta en la pretensión de crear un lenguaje totalmente distinto a cualquier otro en todo, aunque sin olvidar desde luego el sentido del humor. En él, tenemos que pedir por favor la ejecución de ciertas sentencias; en lugar del conocido «go to» (ir a) para saltar a otra instrucción, tenemos que escribir «come from» (venir desde) en el lugar de destino, aunque esto es una extensión posterior a la primera especificación. Podemos pedir que se abstenga de ejecutar ciertas sentencias, por ejemplo: PLEASE ABSTAIN FROM CALCULATING evita que se ejecute la orden CALCULATE. Cuando llegamos al capítulo sobre la precedencia de operadores se nos explica que no la hay, porque precisamente el objetivo en el diseño del lenguaje era que no hubiera ningún precedente. Como resultado de esta regla, cuando necesitamos concatenar dos operaciones juntas hay que agrupar los operandos por pares mediante un equivalente a los paréntesis. El nombre completo del lenguaje, según los autores, es «Lenguaje Compilado Carente de Acrónimo Pronunciable», cuya abreviatura es, «por razones obvias», INTERCAL. Podemos ver el aspecto que tiene un programa escrito en INTERCAL en la figura 1. La función de este programa, extraído del manual de INTERCAL, es leer dos enteros de 32 bits, tratándolos como enteros con signo en formato de complemento a dos, y escribir su valor absoluto.

        DO (5) NEXT
    (5) DO FORGET #1
        PLEASE WRITE IN :1
        DO .1 <- 'V":1~'#32768$#0'"$#1'~#3
        DO (1) NEXT
        DO :1 <- "'V":1~'#65535$#0'"$#65535'
                ~'#0$#65535'"$"'V":1~'#0$#65535'"
                $#65535'~'#0$#65535'"
        DO :2 <- #1
        PLEASE DO (4) NEXT
    (4) DO FORGET #1
        DO .1 <- "'V":1~'#65535$#0'"$":2~'#65535
                $#0'"'~'#0$#65535'"$"'V":1~'#0
                $#65535'"$":2~'#65535$#0'"'~'#0$#65535'"
        DO (1) NEXT
        DO :2 <- ":2~'#0$#65535'"
                $"'":2~'#65535$#0'"$#0'~'#32767$#1'"
        DO (4) NEXT
    (2) DO RESUME .1
    (1) PLEASE DO (2) NEXT
        PLEASE FORGET #1
        DO READ OUT :1
        PLEASE DO .1 <- 'V"':1~:1'~#1"$#1'~#3
        DO (3) NEXT
        PLEASE DO (5) NEXT
    (3) DO (2) NEXT
        PLEASE GIVE UP

Figura 1: Programa en lenguaje INTERCAL

Los programas en INTERCAL, desde luego, no son fáciles de escribir. De todas formas no es el lenguaje esotérico en el que más cuesta escribir un programa. Por ejemplo, en lenguaje Piet es imposible escribir un programa: hay que dibujarlo. Vemos en la figura 2 un ejemplo de un programa en lenguaje Piet.

Figura 2: Programa en lenguaje Piet.

El programa de la figura 2 se limita a escribir la conocida frase «Hello, world!» («¡Hola, mundo!»). Hay que reconocer, sin embargo, que hemos hecho abuso del significado de la palabra escribir en este contexto. Diseñar el programa es algo que en Piet no es una tarea demasiado difícil.

Quien busque algo en lo que sea verdaderamente difícil programar, puede intentar usar Malbolge. El nombre procede del Malebolge (el octavo círculo del infierno de Dante), aunque seguramente el nombre fue recortado a causa de una limitación del sistema operativo para el que fue originariamente escrito (MS-DOS), que limita la longitud de los nombres a ocho caracteres. Esta alusión al infierno puede dar una somera idea de la complicación del lenguaje, aunque obtendremos una idea más aproximada conociendo la dificultad que supuso para Andrew Cooke escribir un programa en Malbolge que simplemente escribiera «Hello, world» (digamos que lo hizo por métodos de tipo «ensayo y error», y ni siquiera consiguió uniformidad en las mayúsculas y minúsculas ni signos de puntuación: el programa escribía «HEllO WORld»). En la figura 3 vemos el programa que consiguió la hazaña.

(=<`$9]7<5YXz7wT.3,+O/o'K%$H"'~D|#z@b=`{^Lx8%$Xmrkpohm-kNi;g
sedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543s+O<oLm

Figura 3: Programa en lenguaje Malbolge.

No hay que desesperarse por no entender nada. Esa es justo la intención que el inventor del lenguaje tenía. De hecho, el cripticismo buscado por el autor le resta cierto interés al lenguaje: está deliberadamente encriptado, razón por la cual Cooke propone un «Malbolge normalizado», que es lo que queda después de la fase de desencriptación. No hay que dejarse llevar por la idea, sin embargo, de que esto le reste dificultad al lenguaje. Se puede (si es que se puede) escribir un programa en Malbolge normalizado y después aplicar la fase final de encriptación para obtener un programa válido en Malbolge. La figura 4 muestra el aspecto del programa «Hello world» en Malbolge normalizado.

jpp<jp<pop<<jo*<popp<o*p<pp<pop<pop<jijoj/o<vvjpopoopo<ojo/o
vooooooooooooooooooooooooooooooooooooooooooooooooooo*p<v*<*

Figura 4: Programa en lenguaje Malbolge normalizado.

Aunque resulta algo más legible que antes, sigue siendo complicado de descifrar sin una descripción de qué significa cada símbolo (y aun con ella). En el fichero de la distribución de Malbolge existe una descripción completa del lenguaje.

Pero de entre todos los lenguajes esotéricos hay uno que llama la atención por su exquisita simplicidad y potencia. Se llama Brainfuck, que en inglés suena tan mal como en español su traducción de Jodecerebros, con perdón. Debido a lo ofensivo del nombre, no es tan fácil buscar referencias en WWW usando buscadores ya que hay muchas variaciones del nombre para ocultar su carácter ofensivo: Brainf*ck, Brainf***, Brainfsck, BF... La intención de su creador, Urban Müller, era la de crear un lenguaje para el cual se pudiera escribir el compilador más corto del mundo.

A pesar del nombre, escribir un programa en Brainfuck no es tan difícil como cabe pensar. Está demostrado que es un lenguaje Turing-completo, lo que expresado de forma simple significa que se puede codificar cualquier algoritmo con él. Existen únicamente ocho instrucciones, cada una de las cuales está asociada a un símbolo. Hay un resumen en la tabla 1. Existe un puntero de programa, que representa la posición en la que se está ejecutando actualmente el código, como en cualquier otro lenguaje imperativo (con algunas salvedades), y un puntero de datos, que es una característica propia de Brainfuck y que sirve precisamente para manipular los datos. El puntero de datos apunta a la posición cero de una zona de memoria, inicialimente rellena de ceros. No se considera correcto un programa si intenta aplicar un decremento al puntero de datos cuando éste está en la posición cero. Usualmente se considera que el contenido de cada posición de memoria es un byte sin signo (un número de 0 a 255). Al incrementar uno de estos bytes cuando su valor era 255, generalmente pasa a valer 0. Al aplicarle un decremento cuando su valor era 0, generalmente pasa a valer 255. Decimos «generalmente» porque según la implementación puede haber versiones del lenguaje que adopten otros convenios.

Instrucción	Descripción	Equivalente C
`-`	Restar 1 al contenido de la celda de memoria actualmente apuntada por el puntero de datos.	`--*p;`
`+`	Sumar 1 al contenido de la celda de memoria actualmente apuntada por el puntero de datos.	`++*p;`
`<`	Decrementar el puntero de datos en una unidad. Es un error ejecutar esta instrucción cuando el puntero de datos tiene el valor 0.	`--p;`
`>`	Incrementar el puntero de datos en una unidad.	`++p;`
`[`	Si el contenido de la celda de memoria a la que apunta el puntero de datos es cero, buscar el correspondiente «`]`» y colocar el puntero de instrucción inmediatamente después. Es posible anidarlos. No se considera un programa válido aquél en el que no hay un balance correcto entre los «`[`» y los «`]`».	`while(*p){`
`]`	Colocar el puntero de programa en el «`[`» anterior correspondiente.	`}`
`,`	Introducir un carácter desde entrada estándar y colocarlo en la celda apuntada por el valor actual del puntero de datos.	`*p=getchar();`
`.`	Escribir el carácter ASCII correspondiente al valor de la celda actual en la salida estándar.	`putchar(*p);`

Tabla 1: Instrucciones del lenguaje Brainfuck.

Aquellos que sepan C pueden valerse de las equivalencias aproximadas que se dan en la tabla para entender un poco mejor las acciones que cada instrucción realiza. Con tal sencillez estructural, mal puede sorprendernos la facilidad con la que se puede escribir un intérprete, y hasta un compilador de Brainfuck. Pero antes de entrar en detalles respecto al intérprete, analizaremos un poco el lenguaje y veremos algunas construcciones comunes.

Por ejemplo, la secuencia de instrucciones [-] se usa a menudo en los programas Brainfuck, y sirve para poner a cero la celda de memoria actual: equivale en C a la instrucción «while(*p){--*p;}», es decir, mientras la celda de memoria actual sea distinta de cero, decrementarla, lo cual obviamente tiene como efecto ponerla a cero.

Si queremos mover el valor actual una posición a la derecha (aquí entendemos que «izquierda» implica disminuir el puntero de datos y «derecha» aumentarlo), utilizaremos el siguiente programa: [>+<-]. Esto va incrementando el byte de la derecha de la posición inicial y decrementando el actual, hasta que éste es cero. Como resultado, al byte situado a la derecha de la posición inicial se le suma lo que hubiera en dicha posición, que acaba siendo cero. Suponiendo que a la derecha hubiera un cero, habremos acabado moviendo el byte de esa posición un lugar a la derecha. Copiar un valor es un problema más complicado; asumiendo que las dos posiciones situadas a la derecha de la actual sean cero, se procederá de la siguiente forma: primero, usaremos [>+>+<<-], que tendrá el efecto de copiar el valor en la posición actual a la posición de su derecha y a la siguiente más a la derecha, y poner a cero la posición actual; después iremos dos posiciones a la derecha usando >>, tras lo cual usaremos una versión modificada del fragmento mover: [<<+>>-], es decir, mover el byte de la posición p (siendo p la posición del puntero de datos) a la posición p-2. Al terminar, retrocederemos otra vez dos posiciones usando <<, aunque dependiendo de la aplicación que queramos darle este último paso puede ser innecesario.

Si no estamos seguros de si están a cero las dos posiciones de la derecha de la actual, siempre podemos asegurarnos usando el siguiente fragmento: >[-]>[-]<<. Normalmente, sin embargo, no necesitaremos ejecutar este código, ya que estará a cero al comenzar.

Juntando todo esto, nos damos cuenta de que si al empezar tenemos en la posición p el valor a, en la posición p+1 el valor 0 y en la posición p+2 el valor 0, tras ejecutar el siguiente fragmento de código acabaremos teniendo en p el valor a, en p+1 el valor a, y en p+2 el valor 0:

[>+>+<<-]>>[<<+>>-]<<

¿Confuso? Considerando cada parte por separado, se ve claramente que simplemente estamos construyendo fragmentos cada vez más grandes mediante los bloques básicos que anteriormente hemos considerado.

Multiplicar un byte por una constante es sencillo: basta con utilizar el programa de mover, pero en lugar de incrementar una vez la variable de la derecha, la incrementamos tantas veces como haga falta. Por ejemplo, para multiplicar el byte actual por 7 podemos utilizar esto: [>+++++++<-], que deja el resultado a la derecha del byte actual, y éste a cero.

Multiplicar dos bytes entre sí requiere algo más de esfuerzo. La idea es sumar el segundo sobre el byte a su derecha tantas veces como diga el primero. Veamos cómo hacemos esto. Primero fijémonos en que la operación de copiar puede ser usada también para sumar, puesto que si el valor en la posición de la derecha de la actual no es cero, se le sumará el contenido del byte actual. Así pues, si llamamos c a la operación copiar, con este código resolveremos el problema: [>c<-], es decir, ir a la derecha, sumar el byte que hay allí al siguiente, ir a la izquierda, decrementar y continuar hasta que éste sea cero. Si se desea que no se pierda el primer multiplicando, habrá que empezar copiándolo a un lugar seguro.

El código completo queda así:

[>
  [>+>+<<-]
  >>
  [<<+>>-]
  <<
<-]

Veamos ahora un programa simple que imprime la «respuesta a la Gran Pregunta de la Vida, el Universo y Todo lo demás» (según Douglas Adams, escritor y humorista británico fallecido hace pocos años). Dicha respuesta es 42. El siguiente programa calcula el código ASCII del número 4 y lo imprime, y a continuación calcula el código ASCII del número 2 y lo imprime: +++++++[>+++++++<-]>+++.--.. El código ASCII del dígito 4 es 52 = 7×7+3, por tanto primero multiplicamos 7×7, y luego sumamos 3 al resultado y lo imprimimos. Después restamos 2 a lo que quedaba, ya que el código ASCII del dígito 2 es 50 = 52-2. Lo imprimimos, y ya lo tenemos.

Dejamos al cuidado del lector el resto del aprendizaje del lenguaje Brainfuck, para centrarnos en una forma de elaborar un intérprete de dicho lenguaje. Esta es una tarea realmente sencilla, como veremos enseguida; la única parte que presenta alguna complicación (poca, realmente) es llevar el balance de qué «]» corresponde con un «[» y viceversa. Precisamos de dos memorias, compuestas por sendos arrays (o arreglos, según algunos traductores): la de programa y la de datos, llamadas respectivamente mp y md. También necesitaremos dos variables: p y d, que serán los punteros de programa y datos, respectivamente.

He aquí un esquema del algoritmo principal del intérprete:

  Leer el programa en la memoria de programa, mp,
    guardando en la variable pfin la posición siguiente
    a la última usada, que indicará fin de programa.
  Poner a cero todos los elementos de la memoria de datos.
  Hacer p = 0, d = 0.
  Comienzo del bucle (1):
    Si p = pfin, fin de programa: ir a la etiqueta (4).
    Si la instrucción mp[p] es «-», hacer md[d] = md[d] - 1.
    Si la instrucción mp[p] es «+», hacer md[d] = md[d] + 1.
    Si la instrucción mp[p] es «<», hacer d = d - 1.
    Si la instrucción mp[p] es «>», hacer d = d + 1.
    Si la instrucción mp[p] es «,», leer un carácter y guardarlo en md[d].
    Si la instrucción mp[p] es «.», escribir el carácter que hay en md[d].
    Si la instrucción mp[p] es «[» y md[d] es cero, hacer lo siguiente:
      Hacer nivel = 0.
      Comienzo del bucle (2):
        Si mp[p] es «[», hacer nivel = nivel + 1.
        Si mp[p] es «]», hacer nivel = nivel - 1.
        Hacer p = p + 1.
        Si nivel = 0, ir al comienzo del bucle (1).
      Ir al comienzo del bucle (2).
    Si la instrucción mp[p] es «]», hacer lo siguiente:
      Hacer nivel = 1.
      Comienzo del bucle (3):
        Hacer p = p - 1.
        Si mp[p] es «]», hacer nivel = nivel + 1.
        Si mp[p] es «[», hacer nivel = nivel - 1.
        Si nivel = 0, ir al comienzo del bucle (1).
      Ir al comienzo del bucle (3).
    Hacer p = p + 1.
  Ir al comienzo del bucle (1).
  Etiqueta (4): fin de programa.

El intérprete recién descrito asume que los programas son sintácticamente correctos, es decir, que tienen un balance correcto de «[» y «]» y que el programa nunca utiliza la instrucción «<» cuando d = 0, ni la instrucción «>» cuando d está en la última posición disponible de md. También asume que el lenguaje efectúa correctamente el «salto» de 255 a 0 al incrementar, y de 0 a 255 en los decrementos. Si esto no fuera así, habrá que poner condiciones adicionales, convirtiéndose la operación de incrementar en la siguiente:

  Si md[d] = 255, hacer md[d] = 0; si no, hacer md[d] = md[d] + 1.

y la de decrementar, similarmente:

  Si md[d] = 0, hacer md[d] = 255; si no, hacer md[d] = md[d] - 1.

Durante el desarrollo de un programa Brainfuck es fácil equivocarse de forma que no cumpla los requisitos arriba expuestos. Para evitar sorpresas es aconsejable incluir en el intérprete comprobaciones en lugares estratégicos: comprobar antes de decrementar d que éste no es cero, y antes de incrementarlo que no está ya en el límite derecho; en los bucles que buscan el «[» y «]» correspondientes a su pareja, hay que comprobar que no llegamos a p = 0 o a p = pfin sin encontrar la pareja correspondiente, o en caso contrario detener la ejecución. Con esas precauciones el intérprete debería ser seguro frente a cualquier programa Brainfuck por mal construido que esté.

Ya para terminar, una pregunta: ¿cuál es la longitud del programa Brainfuck más corto capaz de escribir una o minúscula (código ASCII 111) dejando el resto de la memoria de datos con ceros?

Intérprete en JavaScript

El siguiente intérprete puede servir para probar código en Brainfuck. Incluye entrada y salida, pero no ejecución paso a paso ni visualización de los datos (véase la sección de enlaces para un depurador de Brainfuck más completo en C).

Enlaces

Por ahora la mayoría de las páginas enlazadas desde aquí están en inglés, ya que el tema parece que todavía no es muy conocido en nuestro país. Esperemos que con el tiempo la situación cambie.

Sobre lenguajes esotéricos en general

El lugar por excelencia donde encontrar información y referencias sobre lenguajes esotéricos es sin duda el Esoteric Languages Wiki:
http://www.esolangs.org/wiki/

Hay un índice de páginas apuntadas a un webring sobre lenguajes esotéricos, que también contiene multitud de referencias:
http://b.webring.com/hub?ring=esolang

Una excelente página dedicada a los lenguajes experimentales, mantenida por Chris Pressey:
Cat's Eye, http://catseye.tc/
Es de destacar la sección dedicada a los lenguajes de programación esotéricos:
http://catseye.tc/projects/eso.html

Eric S. Raymond es el autor de un compilador de INTERCAL, el C-INTERCAL. Su página llamada The Retrocomputing Museum contiene una selección de joyas del esoterismo en programación. Brainfuck tiene ocho instrucciones, pero ¿cuál es el mínimo número de instrucciones que debe tener un lenguaje para ser Turing-completo? ¡Una! Hay en esta página dos ejemplos, que llevan el concepto del RISC un paso más lejos: OISC (One Instruction Set Computing) y URISC (Ultimate RISC).
Otra de las joyas presentes en este museo es el kvikkalkul, un lenguaje pretendidamente utilizado en los submarinos nucleares suecos en la década de 1950, aunque más probablemente sea una broma. El lenguaje sólo soporta números en coma flotante sin parte entera, es decir, menores que 1.
También destacamos el MIXAL, que es el lenguaje ensamblador del procesador MIX de Knuth, mencionado en el texto, y un lenguaje de programación Klingon llamado var'aq. Hay muchas otras perlas que invitamos a descubrir.
http://www.catb.org/esr/retro/

La Enciclopedia de Lenguajes Estúpidos contiene una lista bastante exhaustiva de lenguajes esotéricos, sus características, el nombre de su creador, el año de creación y la página principal. Varios de los enlaces disponibles aquí han sido obtenidos gracias a esa página.
http://www.kraml.at/stupid/

Listas de correo relacionados con lenguajes esotéricos:
Archivo de la lista de correo de Cat's Eye

Selección de lenguajes esotéricos concretos

El lenguaje Whenever, cuyas instrucciones no se ejecutan en un orden preestablecido sino aleatorio:
http://www.dangermouse.net/esoteric/whenever.html

Las instrucciones del lenguaje Wierd son cambios de dirección en cadenas de símbolos. Esta es la especificación del lenguaje:
http://catseye.tc/projects/wierd/doc/wierdspec.txt

El lenguaje Piet mencionado en el texto, cuyas instrucciones son colores:
http://www.dangermouse.net/esoteric/piet.html

Descripción del lenguaje nihilista Sartre, creado por J. Colagioia, otro lenguaje pensado con buen humor. Es bastante llamativa la definición de la instrucción condicional IF.
http://catseye.tc/projects/sartre/doc/sartre.html

Sobre Brainfuck

He aquí un intérprete y depurador de Brainfuck escrito por el autor de este artículo (en inglés), suministrado en forma de código fuente en C. El código debería ser sumamente portable; compila perfectamente con gcc tanto en Windows como en Linux. El intérprete, además, realiza primero una pasada de optimización del código para que se ejecute más rápido. El depurador contiene funciones avanzadas que hasta ahora no he encontrado en ningún programa similar.
brfd101.zip (11.077 bytes)

Una completa guía acerca de los bloques con los que construir programas en Brainfuck:
http://home.planet.nl/~faase009/Ha_bf_intro.html

La demostración formal de que Brainfuck es Turing-completo:
http://home.planet.nl/~faase009/Ha_bf_Turing.html

Un intérprete de Brainfuck disponible en línea, escrito en JavaScript:
http://home.planet.nl/~faase009/Ha_bf_online.html

Propuestas de normalización del Brainfuck:
http://www.muppetlabs.com/~breadbox/bf/standards.html
y otra con cierto sentido del humor:
http://esoteric.sange.fi/ENSI/brainfuck-1.0.txt

Existen numerosos programas escritos en lenguaje Brainfuck; entre ellos destacamos un programa para averiguar si un número es primo, varios intérpretes y compiladores de Brainfuck escritos precisamente en Brainfuck, y un programa para calcular PI, aunque éste último requiere una extensión del lenguaje que permita que cada celda pueda almacenar números de 16 bits en vez de 8.

He aquí una biblioteca de programas escritos en Brainfuck. Destacamos el programa SORT.BF, que lee una entrada, la ordena mediante el método de la burbuja e imprime el resultado.
http://esoteric.sange.fi/brainfuck/bf-source/prog/

Otros enlaces indirectamente relacionados con lenguajes esotéricos

Una colección del programa Hello, World escrito en gran variedad de lenguajes, incluyendo muchos esotéricos, entre ellos BrainFuck e INTERCAL:
http://www.latech.edu/~acm/HelloWorld.shtml

99 Bottles of Beer es una canción popular inglesa y estadounidense, al estilo de la canción popular española cuya letra empieza así: Un elefante se balanceaba sobre la tela de una araña... La versión en inglés requiere contar del 99 al cero durante la canción. Escribir su letra es un ejercicio de programación indudablemente más complicado que el de Hello, World, ya que requiere un bucle finito, una cuenta atrás e imprimir números, y por ello los programas tienden a ser más largos pero a la vez más interesantes. He aquí una página dedicada a los programas que imprimen la letra completa de la canción 99 Bottles of Beer en diferentes lenguajes de programación; destacamos el escrito en A+ ya que es capaz de imprimir las versiones europea y americana. Por supuesto no faltan versiones Brainfuck ni INTERCAL del programa, e incluso una en Malbolge.
http://www.99-bottles-of-beer.net/

Los quines son programas capaces de reproducirse a sí mismos. No tienen, sin embargo, nada que ver con los virus: a diferencia de éstos, el requisito que han de cumplir los quines es que la salida del programa sea su propio código fuente, sin utilizar ningún fichero externo. Pensando un poco sobre el tema vemos enseguida que la tarea no es trivial, y que se parece al problema del huevo o la gallina. Hay ejemplos en muchos lenguajes, entre ellos INTERCAL y Brainfuck.
http://www.nyx.net/~gthompso/quine.htm

Lista exhaustiva de lenguajes de programación, antiguos y modernos:
http://ftp.wustl.edu/doc/misc/lang-list.txt

La Galería de los Descifradores CSS es una página creada para defender que un programa de ordenador puede ser acogido dentro de la ley de libertad de expresión, ya que al parecer un juez estadounidense declaró ilegal un programa escrito en lenguaje C que descifraba los sectores encriptados de los discos DVD, que utilizan un sistema criptográfico denominado CSS. Hay ejemplos en muchos otros lenguajes (entre ellos, cómo no, Brainfuck), y otras muchas formas de expresar el programa original: versiones recitadas del programa en formato MP3, descripciones detalladas del algoritmo paso a paso que pueden ser utilizadas para rehacerlo, y muchas otras divertidas maneras de convertir el algoritmo a formas que sí están claramente protegidas por la libertad de expresión. Dando vueltas a la tuerca, lleva el tema a extremos que rayan el ridículo, como la existencia de números primos ilegales.
http://www.cs.cmu.edu/~dst/DeCSS/Gallery/

2009-12-26T13:50:00.001+01:00

Me faltan palabras. El diccionario de la Real Academia Española incluye incremento y decremento, así como incrementar, pero no decrementar.

Fraccionar archivos usando Reed-Solomon

2009-12-26T11:43:00.001+01:00

Hace tiempo que necesitaba una utilidad capaz de dividir un archivo en varias partes. Pero no que hiciera sólo eso, que para eso ya existen muchas (Hacha, por ejemplo), sino una tal que si se pierden algunas partes (con un valor máximo de «algunas» decidido de antemano) todavía se pueda recuperar el archivo original.

El uso que le quería dar es una copia de seguridad distribuida. Se divide el archivo que se quiere guardar en múltiples partes y se suben a diferentes lugares: MediaFire, MegaUpload, FileFactory, 4shared, ADrive... debidamente cifradas de antemano si queremos preservar nuestra intimidad, claro. Si a la hora de recuperar las partes hay alguno de los servicios que ha cerrado, o que ha borrado el archivo, o cuya clave no nos funciona por alguna razón, siempre es posible reconstruir el original usando los demás, suponiendo que el número de bajas no sea excesivo.

La solución obvia es subir el archivo completo a cada uno de los alojamientos remotos. El problema está en el tamaño máximo soportado por cada alojamiento y en el ancho de banda total que hay que usar para subir tantas veces el mismo archivo.

Esto sugiere una pregunta: ¿Es posible obtener, a partir de un archivo dado, n+m archivos, de manera que si de ellas se pierden m partes cualesquiera, se pueda reconstruir el archivo original?

Sí, se puede, y además de forma óptima, es decir, que si el archivo tiene B bytes, el tamaño de cada bloque sería exactamente B/n si B es múltiplo de n. Si no lo es, no importa: nos guardamos la longitud original del archivo y añadimos bytes (por ejemplo, ceros) hasta llegar al siguiente múltiplo de n. Después, tras reconstruirlo, truncamos el archivo por su longitud original.

De hecho, el principio para hacerlo es el que se emplea en el RAID. No me refiero a la marca de insecticida, sino a un sistema genérico para agrupar varios discos (Redundant Array of Inexpensive —o Independent— Disks).

Según la forma de usar los discos, existen varios tipos de RAID, a los que se les asigna números. Algunos de esos tipos contienen información redundante para prevenir fallos de las unidades de disco. Los más básicos son RAID 1, RAID 3 y RAID 6. RAID 1 es el sistema más obvio: todos los discos tienen el mismo contenido. Es como la idea de subir el mismo archivo a todas partes. RAID 3 lo hace mejor: si hay N discos, la capacidad efectiva es N-1, y si se estropea uno, se puede reconstruir a partir de los demás. El sistema que emplea es muy sencillo: cada bit del disco extra es el XOR de todos los demás. Así, si R, S y T son los discos que contienen los datos normales, el disco U contiene R⊕S⊕T. Si se estropea R, se puede recuperar su contenido calculando S⊕T⊕U, ya que puesto que U=R⊕S⊕T, S⊕T⊕U = S⊕T⊕(R⊕S⊕T) = (quitando paréntesis y reordenando) S⊕S⊕T⊕T⊕R = 0⊕0⊕R = R. Lo mismo se aplica al resto de discos.

Sin embargo, no se puede extender el mismo truco a otro disco más y conseguir que si fallan dos discos cualesquiera, ambos se puedan recomponer. El truco del XOR está limitado a un disco fallido como máximo. Esto quiere decir que si falla un disco durante la recomposición de los datos originales (o hasta que se reemplaza el disco fallido), se pierden los datos. Para conseguir tolerancia a dos fallos o más, hace falta recurrir a los códigos Reed-Solomon. Esto es lo que hace el RAID 6.

No es trivial operar con estos códigos; hacen falta algunos conceptos de álgebra lineal y de estructuras algebraicas. Puesto que no encontré ningún programa ya hecho para dividir y recomponer datos, tuve que hacerme uno propio. Lo que sigue es una síntesis de lo que he averiguado durante su elaboración.

Hay un tutorial sobre códigos Reed-Solomon aplicados a sistemas RAID, aquí: [1] (PDF). La descripción de la matriz necesaria para generar los códigos (y su inversa para decodificarlos) es errónea; hay un artículo que la enmienda aquí: [2] (PDF).

Así que tenemos un archivo conceptualmente dividido en n bloques de datos, y queremos generar a partir de ellos un total de n+m bloques de datos, tales que si se pierden cualesquiera m de los n+m bloques, podamos reconstruir los que se han perdido. Para conseguirlo, dividiremos los bloques en palabras, es decir, conjuntos de bits de una longitud fija predeterminada w. El número de bits por palabra w es un valor escogido de tal forma que 2^w sea mayor que el máximo valor de n+m que vamos a emplear. Por ejemplo, si escogemos w=8 (por tanto las palabras son bytes), podremos dividir el archivo original en un máximo de 255 partes contando las que se pueden perder; por ejemplo, n=200, m=55.

Pero para empezar, supongamos que trabajamos en el dominio de los números reales; luego ya veremos cómo hacer lo mismo sólo con enteros de w bits. El problema consiste entonces en encontrar, a partir de una serie de datos d₁, d₂, ..., d_n, una serie de elementos c₁, c₂, ..., c_n+m que tengan la propiedad deseada. Veamos cómo hallarlos.

Dispondremos los datos en forma de una matriz columna, D. Para resolver el problema hemos de encontrar dos matrices A y B. La matriz A debe cumplir esta condición: que el producto AD sea una matriz columna C que contiene los elementos c₁, c₂, ..., c_n+m. La matriz B, por su parte, tiene que cumplir esta condición: si cogemos n elementos distintos cualesquiera de los n+m que tiene C y formamos con ellos una matriz columna C’, entonces BC’=D.

Si tenemos esas dos matrices A y B, el problema estará resuelto: si podemos usar A para calcular C, obtendremos c₁, c₂, ..., c_n+m y por tanto generar los bloques; si podemos usar B para calcular D a partir de cualquier subconjunto de n elementos distintos de C, podemos reconstruir los datos originales.

El problema, pues, radica en cómo construir las matrices A y B. Veamos la forma.

Para poder multiplicarla por D, la matriz A tiene que tener n columnas; para dar como resultado una matriz columna con n+m elementos, tiene que tener n+m filas. La característica que deseamos que tenga A, ya veremos después por qué, es que al tachar m filas cualesquiera, la matriz resultante sea siempre invertible (lo que equivale a requerir que su determinante no sea nulo). ¿Cómo lo conseguimos?

La respuesta viene de la mano de una familia de matrices llamadas matrices de Vandermonde. Estas matrices se construyen como sigue: sean a₁, a₂, ..., a_k escalares arbitrarios; entonces la fila i está compuesta por una sucesión geométrica que comienza en a_i⁰=1:

(Se define 0⁰=1 a este efecto). El determinante de una matriz cuadrada de Vandermonde nunca es cero si ninguno de los escalares está repetido (concretamente, su valor es ∏(a_j - a_i) para todos los posibles pares ordenados a_i, a_j de escalares que intervienen, que no será cero a menos que haya escalares repetidos), así que, si formamos una matriz rectangular de Vandermonde más alta que ancha con todos los escalares distintos, entonces al tachar cualesquiera filas que la hagan cuadrada, el determinante de la matriz resultante no será cero.

De modo que ese es el truco para construir nuestra matriz A: como una matriz de Vandermonde. Usaremos como escalares los números de fila empezando en cero, y se elevarán a los números de columna empezando en cero. La primera fila será pues: 0⁰=1, 0¹=0, 0²=0, ..., 0^n-1=0; la segunda será 1⁰=1, 1¹=1, 1²=1, ..., 1^n-1=1; la tercera será 2⁰=1, 2¹=2, 2²=4, 2³=8, ..., 2^n-1, etcétera. Todas sus submatrices cuadradas de orden n serán entonces invertibles, que es la propiedad que buscábamos.

Ahora veamos cómo construir B para reconstruir los datos originales a partir de C’, que como hemos dicho, es un subconjunto de n elementos de C. Está claro que B tiene que ser una matriz cuadrada de orden n, ya que al multiplicarla por C’, que tiene n elementos, tiene que darnos D, que también tiene n elementos.

Fijemos nuestra atención por un momento en cómo se construye la matriz C. Cada elemento c_i es el producto de la fila i de A por la única columna de D. Construyamos ahora una matriz A’ cuyas filas sean únicamente aquellas filas de A cuyo índice i coincide con el correspondiente de cada elemento c_i en C’. Es decir, construyamos A’ de tal manera que se cumpla la relación A’D=C’.

Entonces ahora es obvio que para hallar D, basta con invertir la matriz A’ puesto que A’^-1A’D=A’^-1C’, luego D=A’^-1C’, por tanto la matriz B buscada es simplemente A’^-1. Sabemos además que A’ es invertible porque la hemos construido así a propósito.

Recapitulando lo que llevamos hasta ahora, se trata de construir un par de matrices A y B tales que al tachar cualesquiera m filas de A, la submatriz resultante siga siendo invertible; para reconstruir los datos a partir de un subconjunto C’ de n bloques de los n+m que hemos generado, construimos A’ como la submatriz de A resultante de dejar únicamente las filas que se corresponden con las presentes en C’, y al invertirla obtenemos B.

Veamos un ejemplo. Tomemos n=3 y m=2. Tenemos tres datos d₁, d₂ y d₃ a partir de los cuales queremos obtener cinco elementos c₁, c₂, c₃, c₄ y c₅. Construimos primero la matriz A y la usamos para obtener los bloques:

Ahora supongamos que sólo tenemos los bloques 1, 3 y 5 y nos faltan los bloques 2 y 4, y queremos reconstruir los datos d₁, d₂ y d₃. Construimos la matriz C’ que consta simplemente de c₁, c₃ y c₅ y construimos también A’, usando las filas 1, 3 y 5 de A, la invertimos y la multiplicamos por C’ para obtener D:

Como cortesía adicional, podemos refinar la matriz A para que cada c_i para i entre 1 y n sea igual a d_i. Para ello, se pueden convertir las n primeras filas de A en una matriz identidad mediante transformaciones elementales, que son unas transformaciones que no afectan a la invertibilidad de la matriz. El algoritmo a aplicar, que también nos sirve para invertir la matriz, se llama algoritmo de Gauss-Jordan. Está explicado en la referencia [2].

Muy bien, muy bonito, pero estamos trabajando con reales de tamaño arbitrario, no con enteros de w bits. ¿Cómo hacemos para que no nos aparezcan números racionales o demasiado grandes?

Los cuerpos de Galois

Un cuerpo finito o de Galois (abreviado GF) es un cuerpo con un número de elementos finito. Hasta aquí, obvio. El más simple es GF(2) que tiene dos elementos, llamémosles 0 y 1. En ese cuerpo, la suma se define igual que en la aritmética en módulo dos (es decir, equivale a la operación XOR) y el producto es el aritmético habitual, que al ser realizado sólo con los elementos 0 y 1, equivale a la operación AND.

Como curiosidad, existen cuerpos de Galois de orden primo y de orden la potencia de un primo, pero no de ningún otro. Por ejemplo, no existen cuerpos de Galois de orden 6, porque 6 no es primo ni es la potencia de un primo, pero sí de orden 9, porque 9 = 3² y 3 es primo. Para construir un cuerpo de Galois de orden primo p (como el caso p = 2 recién nombrado), se puede usar la aritmética en módulo p. Sin embargo, la adición y la multiplicación módulo pⁱ para i > 1 no forman un cuerpo, por lo que hay que emplear otro sistema para construirlo.

Para crear cuerpos de Galois de orden 2^w, se usan como elementos polinomios de grado w con coeficientes en GF(2), es decir, los coeficientes pueden ser sólo 0 y 1, y al operar entre ellos se aplican las reglas de GF(2). La suma es entonces suma de polinomios, pero al ser los coeficientes de GF(2), al sumar o restar dos coeficientes se hace en realidad un XOR entre ellos. El producto es... bueno, el producto es un dolor de muelas. Para calcularlo hay que hallar el producto de los polinomios, módulo un polinomio especial llamado generador, característico del cuerpo con el que estamos trabajando.

Para traducir los polinomios a números enteros, se guarda el coeficiente del término de grado i en el bit i del número. Así, por ejemplo, el polinomio x²+1 en GF(2⁴) se almacena en un entero con el valor binario 0101, es decir, el valor decimal 5. Para sumar (o restar) dos elementos del cuerpo, basta entonces con hacer el XOR bit a bit. En la práctica, para multiplicar de forma eficiente se usan una tabla de logaritmos y una de antilogaritmos, es decir, a*b=antilog(log(a)+log(b)), considerando a=0 y b=0 como casos especiales. La división se traduce igualmente como el antilogaritmo de la resta de logaritmos. (Esa suma y esa resta concretas se hacen en aritmética convencional módulo 2^w-1).

Lo más interesante es que las propiedades de las matrices con las que aquí trabajamos se mantienen cuando operamos en GF(2^w), con tal de que 2^w sea mayor que el número de filas y de columnas de la matriz. Esto nos permite trabajar todo el tiempo con enteros mientras las operaciones las realicemos en el cuerpo. Obsérvese que el RAID 3 equivale a trabajar con w=1 y construir la matriz A de la siguiente forma: las n primeras filas forman una submatriz identidad, y la fila n+1 consiste en todo unos. Aunque en ese caso no se cumple que 2^w > n+m, sí que se cumple que todas las submatrices de orden n de A son invertibles, que es el requisito principal.

El programa

Con todos esos datos ya se puede realizar un programa como el que yo requería. He escogido w=8 porque, además de trabajar con bytes, que es rápido, existe el problema de que el algoritmo de Gauss-Jordan es de orden O(n³) y el almacenamiento de las matrices requiere O(n²). Si hubiera escogido w=16, la matriz requeriría un mínimo de 8 Gb de memoria para almacenarla completa y el algoritmo de Gauss-Jordan prefiero no pensar cuántas operaciones requeriría. Con w=8, la matriz necesita a lo sumo 64 Kb y en el peor caso Gauss-Jordan requiere del orden de 8 millones de operaciones. El inconveniente es que no se puede dividir el archivo en más de 255 partes en total, pero era una solución de compromiso necesaria. De todas formas, para mis propósitos es suficiente. El polinomio generador que he usado es el que viene en el tutorial para w=8, o sea, x⁸ + x⁴ + x³ + x² + 1.

He probado a dividir un archivo de 4,4 Gb en 255 partes de las cuales 8 se podían perder. Lo he reconstruido tras quitar ocho partes elegidas a dedo. El resultado coincidía con el original tal y como se esperaba.

Aún no he decidido la licencia (probablemente será GPL2 o GPL3), y está pendiente de una limpieza para hacerlo presentable. Si hay demanda, tal vez lo haga público. ¿Alguien más quiere el programa?

Referencias

[1] http://www.cs.utk.edu/~plank/plank/papers/CS-96-332.pdf
[2] http://www.cs.utk.edu/~plank/plank/papers/CS-03-504.pdf

¡Feliz aniversario, Newton!

2009-12-25T14:11:00.004+01:00

Ditto.

Civilización en el cráter Hale

2009-12-21T13:45:00.011+01:00

Hay un mito reciente circulando por la red que hace referencia a la posibilidad de que ciertas imágenes capturadas por la sonda Mars Express de la ESA representen en realidad signos de civilización [1] [2] [3] [4].

La controversia está causada por una confusión de quienes buscan inspirar sus fantasías en esas imágenes. El argumento principal es que, puesto que los mismos patrones se pueden ver en varias imágenes en diferentes posiciones, están necesariamente sobre la superficie de Marte y no son, por tanto, defectos en la captura de la imagen.

La imagen del vídeo [2] no se encuentra ya en la página que el autor indica, así que aquí hay un enlace directo: http://www.esa.int/esa-mmg/mmg.pl?idf=SEMPMT0A90E. Es una imagen de 2283×1522 píxels con este aspecto:

Crater Hale in perspective, looking west
Credits: ESA/DLR/FU Berlin (G. Neukum)

No confíe el lector en la versión aquí replicada para análisis alguno, puesto que esta imagen está reducida y comprimida, y en los detalles pequeños, de los cuales aquí se han perdido muchos, radica la cuestión. Descargue la versión original de la web de la ESA si desea seguir este texto.

Aquí ya salta claramente a la vista un aspecto. O Marte es pequeñito y cuadrado, o esa imagen es un render en tres dimensiones usando un mapa de elevación y una textura. La descripción de la imagen dice así:

This perspective view, taken by the High Resolution Stereo Camera (HRSC) on board ESA's Mars Express spacecraft, shows Crater Hale on Mars.

The image is centred at latitude 36° South and longitude 324° East. The image was taken with a ground resolution of about 40 metres per pixel during Mars Express orbit 533 in June 2004. [...]

Esto es un error de la ESA, pues esa descripción, tal y como está escrita, da a pensar que esa imagen que se ve es directamente la captura de la sonda, cuando en realidad no es así: es la proyección en tres dimensiones de la misma utilizando un mapa de altura. La textura es casi con toda probabilidad esta: http://www.esa.int/esa-mmg/mmg.pl?idf=SEMTQWWJD1E y es la imagen de referencia que vamos a tomar en el siguiente análisis. Los datos de elevación para obtener el mapa de altura han sido obtenidos a partir de una versión estereoscópica capturada por la sonda, tal que esta: http://www.esa.int/esa-mmg/mmg.pl?idf=SEM1QWWJD1E.

De modo que los «analistas» toman imágenes que se ven en varias perspectivas, amplían la misma zona y en todas les aparecen los mismos patrones geométricos. Al hacerlo, no se dan cuenta de que están todo el tiempo observando la misma imagen aplicada como textura al mismo mapa de elevación colocado en diversas posiciones para hacer el render 3D.

Aquí vemos un detalle de estos patrones, sobre la imagen en perspectiva (recorte tomado tal cual de las coordenadas 1226,0 - 1522,446):

Y aquí vemos la misma zona de la imagen original (tomada de las coordenadas 1300,40 - 1450,190; después girada 180° para que la posición coincida con la anterior, después ampliada un 300% y por último aplicando el filtro Normalize de GIMP, aunque con cualquier método de aumento del contraste se apreciará el cuadriculado igualmente):

Se puede observar que, efectivamente, los patrones cuadriculados coinciden para la vista en perspectiva y para la imagen original. Lógico, es la misma imagen, con el contraste aumentado en la vista en perspectiva debido a la iluminación 3D. Más de uno estará sin duda preguntándose, a la vista de las imágenes, por qué tanto revuelo por unos artefactos JPEG. Es una buena pregunta que cabría dirigir a los proponentes de estas ideas. Para los que no, van unas explicaciones. El análisis es extensible a todas las porciones que muestran «signos de civilización», pero nos centraremos en el recorte recién presentado.

Funcionamiento de la cámara

La Cámara Estéreo de Alta Resolución (HRSC, por sus siglas en inglés) es una cámara que registra la imagen línea a línea de barrido, a diferencia de las cámaras convencionales que registran la imagen completa cada vez. Cada línea contiene 5.184 píxels; la altura no depende de la resolución de la cámara, sino que es indefinida. La frecuencia de los barridos depende de la velocidad de movimiento de la sonda, para hacer coincidir los tamaños horizontal y vertical. Se toman nueve canales simultáneamente: tres de RGB, tres de datos tridimensionales, uno del infrarrojo cercano y dos de fotometría. Hay más información sobre la cámara aquí: HRSC on Mars Express.

Para poder transmitir a la Tierra la ingente cantidad de datos generada por la cámara, fue preciso hacer algunas concesiones. Concretamente, hubo que reducir en algunos casos el número de pixels y que comprimir mediante JPEG, buscando un compromiso entre la calidad de la imagen y el ancho de banda de la transmisión. Aun con esas reducciones, la cantidad de datos transmitida está en el orden de los terabytes. Lo fundamental aquí es que la versión que llega a la Tierra ya está comprimida con JPEG. Aunque en la galería se presenten archivos TIFF comprimidos sin pérdida, las imágenes que contienen ya han pasado por una compresión JPEG en su transmisión a la Tierra.

Algoritmo de compresión

Conceptualmente, la compresión JPEG funciona, a grandes rasgos, como sigue. Se divide la imagen en cuadrados de 8x8 píxels (los bordes necesitan tratamiento especial si la resolución de la imágen no es múltiplo de 8). Para cada cuadrado, se realiza una transformada discreta del coseno (DCT), lo que se traduce en la práctica en descomponer el cuadrado en una combinación lineal de estos cuadrados:

Cuadros de la transformada discreta del coseno usada en la compresión JPEG. Imagen generada mediante un programa en PHP listado en un apéndice al final de la entrada.

Es decir, se descompone como la suma del primer cuadro multiplicado por un número, más el segundo multiplicado por otro número, más el tercero multiplicado por otro... En total, sesenta y cuatro coeficientes. Esos coeficientes (que pueden ser negativos) son los que en realidad se guardan, en lugar de los píxels. Después es posible reconstruir el cuadrado original a partir de esos sesenta y cuatro valores. La compresión se consigue reduciendo la precisión con que se almacenan. En realidad, lo que se guarda son unos números enteros que representan los coeficientes con la precisión reducida. Se almacenan, además, en formato comprimido (típicamente Huffman), pudiendo llegar a ocupar cada uno incluso tan poco como un bit.

Además de esto, en las imágenes en color también hay un cambio de espacio de color, de RGB a YCbCr, para codificar la luminancia y la crominancia de forma distinta, puesto que el ojo es más sensible a los cambios de iluminación que a los de color. Así, la crominancia se codifica en píxels más «gordos» o más «anchos» que la luminancia, lo que implica menos información que comprimir. A este proceso se le llama downsampling (reducción de muestreo) de la crominancia.

Esa es la base de la teoría. Si hay alguien interesado, existen explicaciones más detalladas en [5], [6], [7] y [8], por ejemplo (la última incluye además código Haskell para decodificar un JPEG simple monocromo).

Dependiendo de multitud de factores, es posible que en el proceso de compresión queden muchos de los cuadros anulados (coeficiente cero) y tan sólo se vean uno o dos sumados. Además, cuando la diferencia de tonalidad de una zona es escasa, el rango dinámico es bajo y las variaciones pueden verse reducidas incluso a dos tonos. Cuando esto ocurre, el efecto (amplificado a blanco y negro puros) es el representado en la siguiente figura:

O su inverso:

Comparemos de nuevo con la imagen marciana:

O los marcianos cultivan sus campos dándoles forma de cuadro de DCT, o esto tiene todo el aspecto de ser artefactos (efectos secundarios no deseados debidos a la pérdida por la compresión).

Desmontando excusas

Vamos a ir viendo y comentando las objeciones con las que me he encontrado.

Es que es la única zona fotografiada por la Mars Express en la que se dan esos defectos. Eso es porque a la ESA se les ha pasado censurarlo.

No. Es la única fotografía donde se ven a simple vista, pero los defectos están en más imágenes, aunque en la mayoría de las demás hay que saber cómo sacarlos a relucir.

Ante todo, hay que tener en cuenta que esa no es la imagen tal como la tomó la sonda, como más adelante veremos, sino una versión postprocesada para hacerla más brillante y mejorar el contraste. Esa mejora del contraste es la que hace que los defectos salgan a la luz. Eso es aún más notable en la versión 3D.

Un ejemplo donde se ven defectos similares:

«Echus Chasma, nadir view», obtenido de http://www.esa.int/esa-mmg/mmg.pl?idf=SEMG9GSHKHF, mostrando en un recuadro la región recortada a continuación. Credits: ESA/ DLR/ FU Berlin (G. Neukum).

Echus Chasma, fragmento ampliado de la versión TIF en alta resolución, comprimido sin pérdida y sin ningún postprocesado. Coordenadas origen: (5920, 1200) - (6320, 1600).

A simple vista no se ven los mismos defectos, pero si descomponemos la imagen en YCbCr (el espacio de color en el que trabaja la compresión JPEG), obsérvese lo que aparece en el canal Cb:

Parece que se adivina algo. Mejoremos el contraste (usando Normalize):

Ahí están de nuevo. Obsérvese el tamaño de los puntos de la cuadrícula secundaria, mucho mayores que los píxels de la imagen. 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.

Pero has tenido que hacer malabarismos para sacar esos defectos a relucir. En la imagen original se ven a simple vista o simplemente aumentando un poco el contraste.

Es cierto que ha habido que hacer algunos malabarismos, pero no es cierto que en la imagen original se vean tan fácilmente. Sólo se ve en imágenes postprocesadas. Las siete que hay del Hale en la galería de imágenes de la ESA (a fecha de escritura de esta entrada) son postprocesadas y proceden de la misma imagen original.

¿Y cuál es la imagen original? Para averiguarlo tenemos que seguir las pistas indicadas en este breve artículo: [9]. Esto nos conduce a la web de la Freie Universität Berlin (FUB). Tienen un subdominio específico para el mapa de Marte elaborado por la Mars Express: http://hrscview.fu-berlin.de/. Buscamos una imagen que incluya el cráter Hale y la órbita Nº. 533, que es la nombrada en la descripción de la imagen que nos interesa.

Está aquí: [10].

Está disponible para descarga en dos formatos: PDS (alojado en el PSA, el Planetary Science Archive de la ESA) y VICAR (alojado en la propia FUB). Ninguno de los dos formatos es reconocido por Gimp directamente (aunque hay un plugin para leer PDS aquí: http://registry.gimp.org/node/1627), pero el VICAR tiene una estructura lo bastante sencilla como para que se pueda leer sin necesidad de conversores específicos. El ImageMagick que tengo viene con códec de VICAR, así que quien tenga la misma suerte puede usarlo para convertir los archivos a un formato reconocible por nuestro programa gráfico sin más. El xloadimage también soporta VICAR y también es capaz de realizar la conversión con el parámetro -dump. Nos interesan los canales rojo, verde y azul (los acabados en re4.53.bz2, gr4.53.bz2 y bl4.53.bz2, respectivamente).

Para los que no quieran instalarse el ImageMagick sólo para convertirlo, explicamos aquí cómo hacerlo de forma artesanal pero sencilla. El formato VICAR es muy simple: consta de una cabecera en ASCII y a continuación, los datos crudos de la imagen. En este caso todos los archivos son imágenes en escala de grises con 8 bits por píxel. Al no soportar compresión, han sido comprimidos con bzip2 para que ocupen menos. Los usuarios de Windows que no conozcan el bzip2 quizá puedan descomprimirlo con WinRar o WinZip.

Para convertir la imagen descomprimida a formato TGA, más popular, basta con descargar este archivo [11] y anteponerlo al VICAR, con lo que se convertirá en TGA. Para anteponer el archivo, el Linux y el Windows tienen formas diferentes de hacerlo. En Windows, en una ventana de símbolo del sistema, se puede escribir:

copy /b h0533_0000.tgahdr + h0533_0000.re4.53 h0533_0000.re4.53.tga
copy /b h0533_0000.tgahdr + h0533_0000.gr4.53 h0533_0000.gr4.53.tga
copy /b h0533_0000.tgahdr + h0533_0000.bl4.53 h0533_0000.bl4.53.tga

Y en Linux, en una ventana de terminal:

cat h0533_0000.tgahdr h0533_0000.re4.53 > h0533_0000.re4.53.tga
cat h0533_0000.tgahdr h0533_0000.gr4.53 > h0533_0000.gr4.53.tga
cat h0533_0000.tgahdr h0533_0000.bl4.53 > h0533_0000.bl4.53.tga

El archivo h0533_0000.tgahdr sirve sólo para imágenes con resolución 3512×19608, por lo que la única imagen adicional para la que servirá es para la infrarroja, por si alguien tiene curiosidad.

Tras añadir la cabecera TGA al archivo VICAR, hay que desechar las tres primeras líneas, ya que no son datos de imagen, sino de la cabecera VICAR, que todavía está en el archivo. De todas formas, la parte que nos interesa está cerca del límite inferior de la imagen. Es el último cráter grande visible, y está cortado por la derecha (por eso la imagen en la galería de la ESA también lo está).

Cada imagen TGA se puede usar como uno de los canales RGB para recomponer la imagen. En Gimp esto se puede hacer con Compose. Temporalmente (durante unas pocas semanas desde la fecha de escritura de esta entrada), la imagen resultante está disponible para descarga aquí: [temp1]. Ocupa 48 Mb comprimida como PNG. La versión descomprimida ocupa más de 200 Mb, así que es preferible que tengamos un ordenador con bastante memoria si queremos abrirla con un navegador. Los créditos de rigor:

HRSCview. Freie Universitaet Berlin and DLR Berlin, http://hrscview.fu-berlin.de/

Esta es «casi» la imagen original usada por la ESA para obtener la imagen principal del Hale de la galería. Aquí está la misma zona que en las imágenes anteriores, una vez recortada y rotada, con su color original y con los datos byte a byte coincidentes con los originales:

Es de destacar lo oscura que está, por lo que siendo datos de 8 bits, el rango dinámico está obviamente mermado. También está muy azulada; no hay apenas tonos rojizos. Nada comparable a ese cráter Hale brillante que se nos muestra en http://www.esa.int/esa-mmg/mmg.pl?idf=SEMTQWWJD1E.

Veamos su descomposición RGB (clic para ampliar):

Descomposición RGB del recorte original anterior (vista en rojo, verde y azul).

Para apreciar mejor los detalles, veamos lo mismo pero en escala de grises:

Descomposición RGB del recorte original anterior (vista en escala de grises).

Todavía no se ven muy bien, así que aquí va una versión con el contraste mejorado:

Versión con contraste mejorado de la imagen anterior.

Con esto ya podemos sacar algunas conclusiones. El canal R ha quedado prácticamente destrozado por los artefactos de compresión, al estar tan oscuro. El canal G y el B aún son un poco aprovechables. Comparemos ahora con la descomposición RGB de la imagen de la galería de la ESA:

Descomposición RGB del fragmento de interés de http://www.esa.int/esa-mmg/mmg.pl?idf=SEMTQWWJD1E.

El canal G y el B coinciden, sin duda, pero ¿de dónde ha salido ese canal R tan nítido comparado con la imagen VICAR?

La respuesta: del canal nadir. Sí, esa imagen con la friolera de 14048×78432 píxels y 354 Mb comprimidos (más de 1 Gb descomprimido) que hay para descarga. Abarca la misma área pero a mayor resolución. Concretamente, 4 veces más resolución en cada eje (es decir, 16 píxels por cada píxel de las otras).

He comprobado que coinciden. No puede generarse un TGA porque el tamaño vertical es mayor que el máximo admitido por dicho formato, que es 65.535, así que lo he convertido a PGM. Al Gimp le ha costado un rato cargar la imagen, otro rato hacer el recorte del cráter y otro rato cerrarla, pero al final obtuve mi premio, un recorte de 800×800 de la zona de interés (clic para la versión completa):

Recorte del canal nadir captado por la HRSC en la órbita 533 de la sonda Mars Express (original sin modificar).

Una vez escalada y ajustados los niveles, la coincidencia es casi total:

Comparación de la vista nadir (izquierda) con el canal R de la imagen de la ESA (derecha).

Las escasas diferencias se deben probablemente a pequeños ajustes del autor de la imagen de la galería para orientarla de acuerdo con una proyección nadir y hacerla coincidir con los canales G y B.

Y el canal G (verde) exhibe exactamente los mismos defectos que la imagen de la discordia:

Comparación de los defectos del canal G de la imagen original con los defectos de la imagen en perspectiva

En resumen, la imagen del cráter Hale usada como textura en los render 3D es una versión retocada, con color falso (en concreto, un canal rojo que no es el real sino que procede de la imagen nadir pancromática) de una imagen muy oscura y deteriorada de partida, en la que los defectos de compresión salen a la luz en cuanto se aumenta el contraste. Al usar la misma imagen para todas las proyecciones, los defectos han sido reproducidos de igual manera. Se aplica tanto a http://www.esa.int/esa-mmg/mmg.pl?idf=SEMPMT0A90E como a http://www.esa.int/esa-mmg/mmg.pl?idf=SEMCMT0A90E.

Si fuera como dices, se verían patrones similares en otras imágenes.

Sólo en las que han sido postprocesadas, amplificando los defectos sustancialmente. Como en esta imagen de Google Maps: [12]

¿Puedes acaso mostrar una del mismo cráter donde no se vean los mismos patrones?

Sí. Hay más imágenes del cráter Hale, como estas de la NASA: [13]

Pero esa es de la NASA y podrían haber sido más cuidadosos encubriendo. Además, esa imagen tiene menos resolución.

Bien, pues veamos más imágenes de la FUB que recogen el cráter Hale. La órbita 511: [14]. Puesto que ya hemos visto cómo extraerla, vamos al grano. Aquí una cabecera apropiada para una imagen con esa resolución: [15]. La imagen recompuesta (2294×14826, 28 Mb) está temporalmente disponible para descarga aquí: [temp2]. Se ve nuestra zona de interes por los pelos (la raya negra de arriba es el borde de la captura):

Recorte de la porción de interés de la imagen VICAR en [14].

La imagen es más clara, con lo cual hay mayor rango dinámico y la calidad por tanto es mejor, como se ve en la descomposición RGB siguiente, incluyendo el canal R, que, aunque deteriorado, al menos ya muestra algún detalle:

Descomposición RGB de la imagen anterior con los niveles ajustados.

Compárese con la descomposición RGB de la anterior, la correspondiente a la órbita 533:

¿Tiene defectos de compresión la 511? Sí, sin duda. ¿En los mismos lugares? Definitivamente no. Son imágenes distintas. Los patrones han cambiado de forma por completo, porque no eran sino defectos del JPEG.

Otras imágenes del cráter Hale que al lector le puede interesar estudiar: [16], [17].

Conclusiones finales

Los defectos de la compresión JPEG de la imagen tomada como origen para obtener las demás, eran demasiado acusados en el canal R como para poder usarlos, por lo que han sido descartados y reemplazados; los canales G y B se han mantenido, y sus defectos han trascendido a las imágenes finales, siendo los del canal G los más acusados y visibles. Otras tomas del mismo cráter no exhiben los mismos patrones, sino otros diferentes. Se trata pues, sin duda, de artefactos de compresión JPEG.

Y a modo de postdata, la imagen de la órbita 2526 procesada por el visor HRSCview, donde no se ve más que lo que hay, un cráter: 2526_0001.

Apéndice

A continuación se lista el programa en PHP para obtener la imagen con los cuadrados DCT del JPEG.

<?php
  // Resolución de color (Nº. de tonos de gris). Máx. 255.
  $r = 255;

  $img = imagecreate(300, 300);
  $clr = array();
  $bg = imagecolorallocate($img, 255, 128, 64); // Fondo
  $clr[0] = imagecolorallocate($img, 0, 0, 0);
  for ($i=2; $i<256; $i++) $clr[$i-1] = imagecolorallocate($img, $i, $i, $i);
  for ($yy = 0; $yy < 8; $yy++) {
    imagefilledrectangle($img, 0, 38*$yy+34, 299, 38*$yy+37, $clr[254]);
    imagefilledrectangle($img, 38*$yy+34, 0, 38*$yy+37, 299, $clr[254]);
    for ($xx = 0; $xx < 8; $xx++)
      for ($y = 0; $y < 8; $y++)
        for ($x = 0; $x < 8; $x++) {
          $c = (  cos((2*$x+1)*$xx*pi()/16)
                * cos((2*$y+1)*$yy*pi()/16) + 1.0) * 0.4999999;
          imagefilledrectangle($img, $xx*38+1+$x*4, $yy*38+1+$y*4,
                                     $xx*38+4+$x*4, $yy*38+4+$y*4,
                               $clr[floor($c*$r)*(254.9999999/($r-1))]);
        }
  }
  header('Content-type: image/png');
  imagepng($img);
  imagedestroy($img);
?>

Hay un color para los bordes y 255 grises. Para dar cabida al color de los bordes, se ha eliminado el color con RGB (1, 1, 1). El parámetro $r es la resolución de color, esto es, el número de colores (tonos de gris) que habrá en la imagen. Ajustándolo a 2 se obtiene la versión bicolor usada en el texto. Para obtener la imagen en negativo, cámbiese floor por 254-floor.

Agradecimientos

Agradecimientos a Julio por los datos que aportó en la discusión sobre este tema, especialmente algunos enlaces de los presentados.

También a la ESA, la FUB y el DLR (el Centro Aeroespacial Alemán) por hacer públicas las imágenes y los datos.

Referencias

[1] http://www.marsanomalyresearch.com/evidence-reports/2005/084/hale-civ-evidence.htm
[2] http://www.youtube.com/watch?v=qcR7VX-FwDY
[3] http://www.youtube.com/watch?v=PDEiHJwjCwc
[4] http://www.youtube.com/watch?v=0-dHqJYcDOM
[5] http://www.ams.org/featurecolumn/archive/image-compression.html
[6] http://dvd-hq.info/data_compression_2.php
[7] http://www.cs.sfu.ca/CC/365/mark/material/notes/Chap4/Chap4.2/Chap4.2.html
[8] http://www.imperialviolet.org/binary/jpeg/
[9] http://adsabs.harvard.edu/abs/2008LPI....39.1822M
[10] http://hrscview.fu-berlin.de/cgi-bin/ion-p?page=product.ion&code=25554104&image=0533_0000
[11] http://www.formauri.es/personal/pgimeno/xfiles/Hale/h0533_0000.tgahdr
[12] http://maps.google.com/maps?f=q&source=s_q&q=15%C2%B039%2702.89%22S+128%C2%B041%2751.78%22E&sll=37.0625,-95.677068&sspn=33.077336,63.369141&ie=UTF8&ll=-15.650674,128.69778&spn=0.002454,0.003868&t=h&z=18
[13] http://alderaan.arc.nasa.gov/pdsimages/select?qt=simple&q=product_id%3A%22611A46%22
[14] http://hrscview.fu-berlin.de/cgi-bin/ion-p?page=product.ion&code=78872241&image=0511_0000
[15] http://www.formauri.es/personal/pgimeno/xfiles/Hale/h0533_0000.tgahdr
[16] http://hrscview.fu-berlin.de/cgi-bin/ion-p?page=product.ion&code=79936214&image=2526_0001
[17] http://hrscview.fu-berlin.de/cgi-bin/ion-p?page=product.ion&code=99640167&image=4343_0000.

Actualización

La FUB confirma mis hallazgos: Respuesta de la FUB sobre las imágenes del Hale

Aproximando el círculo

2009-12-07T20:30:00.034+01:00

Las curvas de Bézier son una construcción geométrica muy útil usada en multitud de ámbitos, especialmente en los relacionados con el dibujo. Fueron desarrolladas por el físico y matemático francés Paul de Faget de Casteljau mientras trabajaba para Citroën, y popularizadas y patentadas por el ingeniero francés Pierre Étienne Bézier durante su trabajo en Renault. Son segmentos de ciertas curvas paramétricas, cuyo parámetro se halla entre 0 y 1. Las más comunes son las cuadráticas (usadas sobre todo en fuentes TTF) y las cúbicas (usadas en casi todos los programas de dibujo vectorial y en lenguajes gráficos como el PostScript). Las cuadráticas requieren un punto extra, además del punto origen y el destino, y las cúbicas dos puntos extra. Tienen muchas propiedades atractivas para el dibujo; por ejemplo, que en los extremos son tangentes a las líneas que van desde los mismos hasta los puntos de control inmediatos, lo cual permite encadenarlas para formar curvas más largas sin aparentes ángulos, o que es sencillo subdividir un segmento dado en un punto arbitrario del mismo para obtener dos segmentos.

Existe una interpretación geométrica sencilla para la curva de Bézier de grado n. Phil Tregoning creó las siguientes imágenes casi autoexplicativas sobre la interpretación geométrica de las curvas de Bézier, en este caso la cuadrática y la cúbica:

(Fuente: Wikpedia).

Para la cuadrática, por ejemplo, primero se hace una interpolación lineal del segmento P₀P₁ entre 0 y 1 según el parámetro t, y luego se hace lo mismo con el segmento P₁P₂. Los dos puntos hallados determinan un tercer segmento, que al interpolarlo entre 0 y 1 según t, da un punto de la curva. La cúbica requiere seis interpolaciones lineales: los tres segmentos P₀P₁, P₁P₂ y P₂P₃, los dos segmentos intermedios obtenidos con las interpolaciones anteriores, y el segmento final.

Las ecuaciones paramétricas de la curva cuadrática y de la cúbica son relativamente sencillas:

B²(t) = P₀ (1-t)² + 2 P₁ t (1-t) + P₂ t²
B³(t) = P₀ (1-t)³ + 3 P₁ t (1-t)² + 3 P₂ t² (1-t) + P₃ t³

Es posible convertir una curva cuadrática en cúbica. Para hacerlo, hemos de tomar puntos P₁ y P₂ estratégicamente; concretamente, si Q₀, Q₁ y Q₂ son los puntos que definen la curva cuadrática, hay que escoger P₁ de forma que esté a 2/3 del camino entre Q₀ y Q₁, y P₂ de forma que esté a 2/3 del camino entre Q₂ y Q₁, y, por supuesto, P₀ = Q₀ y P₃ = Q₂. La curva cúbica resultante coincide en todos sus puntos con la cuadrática.

Como es de esperar, lo contrario no es posible en general: no se puede obtener una curva cuadrática que coincida con una cúbica. Lo que sí se puede hacer es aproximarla, usando más de un segmento de curva cuadrática.

Y es que las curvas de Bézier son en realidad muy útiles para aproximar figuras. Un caso particular donde se usan curvas de Bézier para aproximar una figura es el de los círculos. Con la cantidad suficiente de segmentos de curva de Bézier cúbica, es posible hallar una aproximación más que decente a una circunferencia.

Tres segmentos son definitivamente insuficientes; el resultado es demasiado deforme. Sin embargo, con cuatro segmentos basta para obtener una excelente aproximación; tan buena, de hecho, que muchos programas de dibujo vectoriales implementan sus círculos internamente mediante curvas de Bézier, en lugar de usar genuinos círculos. Entre los que lo hacen están Inkscape, Skencil (antes Sketch) y Sodipodi (del que salió Inkscape), tres conocidos programas libres de dibujo vectorial.

Si aplicamos una transformación afín a los puntos de control (P₀...P_n) de una curva de Bézier, el resultado que obtenemos es equivalente a transformar cada punto de la curva. Esta deseable propiedad nos permite usarlas para obtener la aproximación de una elipse en lugar de la de una circunferencia.

Para obtener la aproximación de un cuarto de circunferencia, hay que colocar los cuatro puntos de la forma que sigue. Supondremos que se trata de aproximar un círculo de radio unidad centrado en el origen; los demás se pueden obtener fácilmente escalando y desplazando puntos.

El primer punto, P₀, hay que situarlo en (0, 1); el segundo punto, P₁, en (k, 1) para cierto valor de k; el tercero, P₂, en (1, k) y el cuarto, P₃, en (1, 0). Con esto se aproxima un cuarto de circunferencia. Los demás segmentos se obtienen fácilmente por simetría y traslación.

¿Qué valor de k es apropiado? Hay quien sugiere usar k=4/3 (2^½-1) ~= 0,552284749...; este valor está calculado para que cuando t = 1/2, el punto de la curva resultante esté a distancia 1 del centro, de modo que coincida con el que se le supone a una circunferencia.

Sin embargo, ese valor tiene sus desventajas: en casi todos los puntos, el círculo aproximado resultante es ligeramente más grande que el real, lo que determina que su área sea también más grande. En concreto, el área excede la teórica del círculo en aproximadamente un 0,028%. No es mucha la diferencia, pero si se es un perfeccionista como algunos de nosotros, molesta. ;)

El área de nuestro segmento de Bézier (véase por ejemplo Paul's Online Math Notes - Area with Parametric Equations sobre cómo obtenerla) es A = 1/2 + 3/5 k - 3/20 k². Si la igualamos a π/4 y resolvemos k, obtendremos el valor de k que hace que el área coincida con la del círculo. El valor resulta ser k = 2 - (22/3 - 5/3 π)^½ ~= 0,551778477... (la otra solución da k > 1, que no nos interesa).

Este último valor de k da una curva que cruza varias veces el círculo, ~~por lo que la distancia es menor~~ dando al mismo tiempo una distancia ligeramente más pequeña, y en general es una aproximación mejor.

No es que se vaya a notar mucho la diferencia, todo sea dicho. Por ejemplo, el Inkscape usa k = 0,552 y no me había percatado de ello hasta que he mirado el código para escribir este texto. Pero, vaya, al menos quien use el valor de k sugerido aquí podrá tener la conciencia tranquila de que sus círculos son la mejor aproximación posible a un círculo real.

Actualización a 11 de diciembre

Ese valor de k que iguala las áreas tiene un pequeño problema. Aunque el área sea correcta, la distancia a una circunferencia real es casi la misma que con el valor de 4/3(2^½-1), sólo ligeramente menor. En particular, con el valor que iguala áreas es de 0,0002684... mientras que con el que iguala el punto medio es de 0,0002753...

El hecho de que cruce la circunferencia, por tanto, no constituye garantía por sí mismo de que la distancia sea menor, aunque esta vez haya habido suerte y haya sido así. He corregido esa parte de la entrada.

Y es posible reducir aún más esa distancia. Esta gráfica representa la distancia entre cada punto de la curva y la circunferencia de radio unidad, con t en el eje de abscisas, para tres valores de k (hemos ampliado la escala del eje de ordenadas para verla mejor):

El del centro es el que está usando Inkscape. Con k = 0,552 la distancia máxima resulta de sólo 0,000212..., que está más cerca de la circunferencia ideal. El valor de k que minimiza la distancia se obtiene de una ecuación polinómica de 6º grado que no voy a reproducir por ser bastante larga, que resulta en un valor de k ~= 0,55191502449...; la distancia máxima a la circunferencia ideal que se obtiene con dicho valor es 0,000196076...

Así que sólo nos queda decidir qué objetivo perseguimos. Si se trata de igualar el área, el valor de k que lo consigue es el de 0,551778...; si se trata de minimizar la distancia a la circunferencia verdadera, el valor es en cambio el de 0,551915... Elija veneno.

Números en espiral

2009-12-06T21:21:00.003+01:00

A veces, las entrevistas de trabajo van acompañadas de preguntas-prueba para evaluar la capacidad del entrevistado. Google es conocido por hacer ese tipo de preguntas; entre las más recientes hay una que me parce especialmente chocante: How many resumes does Google receive each year for software engineering?

Pero buena parte de las preguntas bien podrían entrar en la categoría de pasatiempos lógicos, aunque con la presión de una entrevista de trabajo, cabe suponer que se siente de una forma diferente.

Eso me ha recordado un problema para una entrevista de trabajo sobre el que me hablaron tiempo ha. En una hoja de cálculo, se nos dan un número de fila y de columna que determinan una casilla a la que llamaremos origen. La intención es numerar las casillas que la rodean de la forma siguiente. La casilla origen se numera con un uno, la de su derecha con un dos. A la de abajo de la dos se le asigna el número tres, la de la izquierda de la tres es la cuatro, la de la izquierda de la cuatro es la cinco. La de arriba de la cinco es la seis, sobre la seis va la siete, a la derecha de la siete la ocho, y así sucesivamente, en espiral, cada casilla tiene su número. Por ejemplo, si el origen estuviera en la fila 4833, columna 1938, los alrededores de esa tabla tendrían este aspecto:

	...	1936	1937	1938	1939	1940	...
...	...	...	...	...	...	...	...
4831	...	21	22	23	24	25	26
4832	...	20	7	8	9	10	27
4833	40	19	6	1	2	11	28
4834	39	18	5	4	3	12	29
4835	38	17	16	15	14	13	30
...	37	36	35	34	33	32	31

El problema consiste en determinar, dadas la fila y columna origen y una fila F y una columna C arbitrarias, qué número correspondería a la casilla en la fila F columna C.

Me contaban que uno de los entrevistados escribió un algoritmo para resolverlo usando el lenguaje de script de la hoja de cálculo, y que dicha persona se jactaba de que el tiempo de ejecución era O(n), siendo n el número que le correspondería a la casilla en cuestión.

¿Es posible hacerlo mejor que eso?

Sí, es posible. Deje el lector aquí de leer si quiere intentarlo por sí mismo. Si no, continúe tras la línea.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

Observemos una característica de las diagonales. La diagonal que empieza en uno y se extiende hacia arriba y a la derecha (resaltada en verde a continuación), consiste en los números 1², 3², 5², ... y la que empieza en cuatro y se extiende hacia abajo e izquierda (señalada en amarillo), consiste en los números 2², 4², 6², ...

	...	1936	1937	1938	1939	1940	...
...	...	...	...	...	...	...	...
4831	...	21	22	23	24	25	26
4832	...	20	7	8	9	10	27
4833	40	19	6	1	2	11	28
4834	39	18	5	4	3	12	29
4835	38	17	16	15	14	13	30
...	37	36	35	34	33	32	31

¿Es casual esa observación, o hay algún motivo para que sea así? Para responder esa pregunta, basta fijarse en todos los números entre el 1 y cada uno de los que se encuentran en esas diagonales. Por ejemplo, observemos el 1, 2, 3 y 4. Forman un cuadrado de lado dos, así que los números en cierto modo cuentan su área. Ahora observemos el 1, 2, 3, 4, 5, 6, 7, 8 y 9. Forman un cuadrado de lado 3. Los números entre el 1 y el 16 forman un cuadrado de lado 4. Para formar un cuadrado de lado 5 no tendríamos más que añadirle al de lado 4 los cuadrados numerados entre el 17 y el 25 inclusive, y eso es justo lo que ocurre. No es casualidad, pues. Existe una relación numérica.

Para perfilar mejor lo que será la fórmula final, hay que fijarse en qué efecto tienen la fila y la columna a la hora de determinar el cuadrado en el que cae la casilla objetivo. Observemos que los cuadrados con lado impar siempre tienen el elemento origen (el 1) justo en el centro, mientras que los de lado par lo tienen «casi» en el centro.

Si, para una casilla dada, conseguimos determinar un cuadrado que tenga el origen justo en el centro (para lo cual sólo consideraremos cuadrados de lado impar) y para el que esa casilla sea parte de su perímetro, tenemos ya casi todo el problema resuelto, porque inmediatamente conocemos todos los números que forman su perímetro. Por ejemplo, para la casilla en la fila 4833, columna 1940, queremos hallar el cuadrado formado por las casillas de la 1 a la 25, ya que es el que tiene el 11 en su perímetro y el 1 en el centro.

Para calcular ese cuadrado, necesitaremos más pasos. La resta entre el número de columna de la celda y la del origen determina la diferencia horizontal, y haciendo lo mismo con las filas obtenemos la diferencia vertical. Sus valores absolutos son las distancias horizontal y vertical, respectivamente. La mayor de esas distancias servirá para determinar el cuadrado que buscamos. Llamémosla d. Entonces, (2d+1)² es el área del cuadrado buscado. Los números de su perímetro están comprendidos entre el (2d-1)²+1 y el (2d+1)²; el número de su vértice inferior izquierdo es (2d)²+1 y los otros dos vértices no los necesitamos, pues podemos descontar desde el mayor en las horizontales y contar desde el menor en las verticales.

Al determinar cuál de las dos distancias era mayor, si la horizontal o la vertical, hemos averiguado de paso si el número cae en un lado horizontal o en uno vertical del cuadrado; los signos de las diferencias nos ayudarán a distinguir el lado concreto. Usando el vértice como base y la otra diferencia como desplazamiento, obtendremos nuestro número.

La fórmula resultante, en OpenOffice, es:

=SI(ABS(CELDA("COL") - {col_origen}) > ABS(CELDA("ROW") - {fila_origen});
    SI(CELDA("COL") < {col_origen};
        4*SUMA.CUADRADOS({col_origen} - CELDA("COL")) + 1
            + {fila_origen} - CELDA("ROW") + {col_origen} - CELDA("COL");
        SUMA.CUADRADOS(2*(CELDA("COL") - {col_origen}) - 1)
            + CELDA("ROW") - {fila_origen} + CELDA("COL") - {col_origen}
    );
    SI(CELDA("ROW") < {fila_origen};
        SUMA.CUADRADOS(2*({fila_origen} - CELDA("ROW")) + 1)
            + CELDA("COL") - {col_origen} + CELDA("ROW") - {fila_origen};
        4*SUMA.CUADRADOS(CELDA("ROW") - {fila_origen}) + 1
            + {col_origen} - CELDA("COL") + {fila_origen} - CELDA("ROW")
    )
)

Que es O(1) para números razonablemente normales y casi instantánea de calcular en OpenOffice. Para números muy grandes, que las hojas de cálculo normales no pueden manejar, entraría en juego la complejidad de la multiplicación, O(log² n) en el peor de los casos, pero nunca O(n).

Escape del escape del escape

2009-12-04T20:00:00.001+01:00

Reproduzco aquí esta entrada que en su día fue publicada en Uno por uno, uno...

Existe en muchos sistemas informáticos un medio para escribir caracteres que dentro del contexto en el que se escriben tendrían otro significado. Por ejemplo, en HTML se usa el símbolo & para introducir caracteres o comandos especiales; en las URLs el símbolo usado es el %, en MIME es el signo =, en el prompt de MSDOS era el signo dólar, y el lenguaje C y muchos otros derivados usan la barra invertida (\). Nada que objetar; es un excelente medio para conseguir incluir caracteres que podemos querer usar y la sintaxis del sistema en cuestión nos lo impediría sin ellos. Estos caracteres se suelen llamar «escapes», ya que nos permiten «escapar» de las limitaciones de dicho sistema.

De hecho, en casi todos los casos el propio carácter especial necesita una forma de ser expresado mediante sí mismo: el & se escribe & en HTML, el % se escribe %25 en una URL y el = se escribe =3D en MIME. Algunos han tenido una «feliz» idea: cuando se escribe dos veces el carácter de escape, significa el propio carácter de escape. Así, en el prompt de MSDOS se escribiría $$ para significar un solo símbolo dólar, y en C y similares, se usa \\ para indicar una sola barra invertida.

Pobres de nosotros, quienes tuvieron esa última ocurrencia de duplicar el carácter, no pensaron en las consecuencias. Valga como ejemplo el hecho de que el C, el sh, las expresiones regulares y el PHP emplean todos el mismo convenio de carácter especial (\) y duplicación para obtenerlo (\\).

Supongamos este escenario: tenemos que escribir en PHP una página web para un lugar que aloja archivos fuente en C, que admita que sus usuarios busquen cadenas de texto en dichos archivos con expresiones regulares. Por fastidiar, el PHP donde se va a alojar no tiene compilada la librería de expresiones regulares, así que la solución pasa por invocar el comando 'grep' de la línea de comandos. Algunas búsquedas comunes irán ya codificadas de antemano dentro del código PHP. ¿Cómo habría que escribir en PHP la cadena que buscara, en el código fuente en C, una ruta de un archivo como C:\Dir\Arch.txt?

En el archivo en C, esas cadenas vendrían escritas como "C:\\Dir\\Arch.txt", debido a la duplicación del carácter de escape. Así que eso es lo que tiene que buscar el grep. Pero, como las expresiones regulares también utilizan el mismo carácter de escape, en realidad la línea de comandos del grep debería parecerse a: grep 'C:\\\\Dir\\\\Arch.txt' *.c

Sin embargo, existe alguna incompatibilidad en los caracteres de escape dependiendo del shell (el ash también requiere que se duplique la barra invertida en las cadenas entre apóstrofes, a diferencia del bash; sólo las cadenas entre comillas son compatibles entre sí). De modo que, para asegurar que funcionará tanto en ash como en bash, en lugar de eso habría que prescindir de los apóstrofes y emplear comillas, teniendo que escribir: grep "C:\\\\\\\\Dir\\\\\\\\Arch.txt" *.c

¿Y qué cadena fija escribiríamos en nuestro fuente en PHP?

$cadena = 'grep "C:\\\\\\\\\\\\\\\\Dir\\\\\\\\\\\\\\\\Arch.txt" *.c';

Si todos los sistemas hubieran tenido el convenio de que para generar una barra invertida bastara con un carácter que NO es una barra invertida, la cosa sería mucho más sencilla. Por ejemplo, supongamos que la secuencia \k representara una barra invertida en todos los sistemas implicados en nuestro ejemplo. Entonces, el código fuente en C contendría algo como: "C:\kDir\kArch.txt", por lo que la línea de comandos del grep sería: grep "C:\kkkDir\kkkArch.txt" *.c, y nuestra cadena fija: $cadena = 'grep "C:\kkkkDir\kkkkArch.txt" *.c', lo cual únicamente significa agregar una k en cada nivel, mucho más inocente que la duplicación. Porque, imagínense, si esa cadena tuviera que ir escrita en algo como un generador para esos archivos PHP, quedaría así:

'$cadena = \'grep "C:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\Dir\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\Arch.txt" *.c\';'

Así que, por favor, si alguna vez necesita escoger un carácter de escape, piénselo dos veces antes de elegir la barra invertida, y tres veces antes de decidir que la duplicación del carácter es una referencia a sí mismo.

Nuevo espacio

2009-12-03T19:48:00.002+01:00

Hace mucho tiempo, en una galaxia muy lejana, existía un mundo en el que no se conocían los blogs y lo que se estilaba eran las páginas web personales. A alguien se le ocurrió entonces la idea de utilizar el típico formato de boletín de noticias para escribir textos cuyos contenidos eran un diario exhibicionista, y nacieron los weblogs (ahora abreviados como blogs).

Durante un tiempo, quien tenía un blog era el «rey del mambo». A medida que el formato se popularizaba, y con el empujón de Google Blogger y otros servicios similares, esa percepción de exclusividad fue mutando a vulgaridad.

Fiel a mi costumbre de ir a la mía, desoí a quienes me preguntaban, uno tras otro: «Pero, ¿cómo es que todavía no tienes un blog?», una canción que inevitablemente me resonaba a una viñeta de Mafalda.

Alas, al final he sucumbido. A menudo me encuentro con que quiero expresar algo que creo que puede interesar a más gente y no tengo dónde. Mi página personal no tiene cabida para el tipo de contenidos efímeros propios de un blog, como opuestos a los contenidos estáticos atemporales propios de una página personal; eso por no nombrar que lleva ya muchos años sin actualizar, aunque tengo planes para ella.

A veces le he «gorroneado» su blog a Lola Cárdenas [1] [2] [3] [4] [5] [6] [7], pero llega un momento en que uno se siente mal parasitando un espacio cuya temática difiere tanto, normalmente, de lo que quiero escribir.

Como sucede con las entradas antes citadas, es de esperar que en realidad aquí haya muy pocas actualizaciones. Espero que el lector las encuentre lo bastante jugosas como para tener en cuenta este lugar cuando haya novedades.

Declaro, pues, inaugurado este nuevo espacio.

Pero móvil, ¡nunca!

Programa:
Entrada:
Salida:
Ejecutar: