La Sombra de Dijkstra

Sobre el arte y la práctica de la programación

Desafío Octubre: Código Spaghetti

| Comentarios

Después de una larga pausa volvemos con los desafíos, esta vez vamos a jugar con Fortran IV :).

Hay lenguages antiguos, como Fortran IV que usan sentencias goto condicionales e incondicionales, en vez de estructuras como if y while.

Además en Fortran IV cada sentencia ocupa una linea de código. Las primeras 5 posiciones están reservadas para colocar una etiqueta numérica, que corresponde a un número entero. La posición 6 está reservada para una marca de continuación, pero no la vamos a considerar en este ejercicio, la dejaremos en blanco. Por lo tanto las sentencias propiamente tal empiezan a partir de las posiciones 7 en adelante.

Una sentencia goto se ve así:

goto etiqueta

y una sentencia condicional se escribe así:

if (expresion)goto etiqueta

Donde “etiqueta” es un número.

Hay otras sentencias, pero sólo los goto condicionales empiezan con “if(” y finalizan con “)goto etiqueta”. En Fortran IV los espacios se ignoran. Consideraremos que la sentencia “stop” sólo aparece al final de un programa, y detiene la ejecución del programa.

Si les interesan conocer las posibles operaciones de un programa Fortran IV consideren las descritas en este enlace.

Desafío El desafío es determinar si dos programas Fortran IV son equivalentes. Diremos que dos programas son equivalentes si, para todas las entradas posibles, ejecutan exactamente la misma secuencia de sentencias, ignorando los gotos incondicionales y las etiquetas. Diremos que dos secuencias de sentencias son las mismas si son textualmente identicas después de eliminar espacios y etiquetas. Asuman que cada goto condicional se tomará en algunos casos y no en otros. Los gotos incondicionales se ejecutan siempre.

Los siguientes programas de ejemplo son equivalentes:

Programa 1:

Programa 2:

Se debe crear un programa que reciba como entradas dos programas Fortran IV y escriba en pantalla: “los programas son equivalentes” o “los programas no son equivalentes”.

El plazo para este desafío es el 30 de octubre, los programas deben ser capaces de procesar programas de hasta 1.000 lineas.

Ganará el programa más rápido y más sencillo (menor cantidad de lineas de código) que resuelva este desafío. Si hay suficientes participantes (más de 6) habrá premio :)

“May the odds be ever in your favor”

Cierre Del Desafío Julio Agosto

| Comentarios

Ayer se cerró el desafío Julio Agosto, con sólo dos participantes, el ganador del anterior desafío Daniel Molina (damowe), y Hector Rodriguez(hrodrigu), quien me envió su solución por correo electrónico y que he publicado en GitHub.

Son dos soluciones muy buenas, la de Daniel como siempre en Haskell con un código bastante elegante, la pueden ver en su repositorio GitHub. Sin embargo, hasta ahora no contiene la solución a la flor.

La versión de Hector es sorprendente, al menos para mi, porque no esperaba una solución en JavaScript! Lo otro que me gusta es la elegancia y concisión del código, 70 lineas de javascript. Excelente! :)

Hector además entrega la solución al L-System de la flor:

Así que el ganador de esta oportunidad de Hector Rodriguez, felicitaciones! Gracias también a Daniel por participar.

Me pondré en contacto con Hector para hacerle entrega de su GiftCard.

Al parecer este desafío estuvo bastante difícil, espero que en el próximo tengamos más participantes. Les pido a todos ustedes que me ayuden a promover esta actividad.

Entre Algoritmos Y Patrones

| Comentarios

La mayor parte de los programadores corporativos del mundo tienen un rutinario trabajo que se puede super simplificar en uno de estos dos modelos:

  • Transaccional: crear un formulario y copiar los datos ingresados a través de este a una base de datos.

  • Batch: leer o escribir archivos desde o hacia una base de datos.

Niklaus Wirth expresó una famosa ecuación como título a uno de sus libros:

 Algoritmos + Estructuras de Datos = Programas

Eso puede haber sido cierto en 1976, pero ¿sigue siéndolo aún en el siglo XXI?

Hemos evolucionado mucho en un desarrollo espiral, para un observador poco atento pareciera que la computación se moviera como un péndulo, van de un paradigma al opuesto y vuelven, pero yo no creo que sea así, con cada ciclo aprendemos algo y lo incorporamos.

Sin embargo hay que reconocer que hay mucho de re inventar la rueda, muy poco de investigación profunda, la urgencia por resolver el problema lleva a muchos a rehacer una solución que ya existía, y con peor desempeño muchas veces.

En su discurso de recepción del premio Turing de 1968 Richard Hamming dijo lo siguiente:

Whereas Newton could say, “If I have seen a little farther than others, it is because I have stood on the shoulders of giants,” I am forced to say, “Today we stand on each other’s feet.” Perhaps the central problem we face in all of computer science is how we are to get to the situation where we build on top of the work of others rather than redoing so much of it in a trivially different way.

Mientras que Newton podía decir, “Si he visto más lejos que otros, es porque me paré sobre hombros de gigantes¨, yo estoy forzado a decir, “Hoy en día nos paramos sobre los pies de los otros”. Quizás el problema principal que enfrentamos en toda la ciencia de la computación es cómo llegaremos a la situación donde construyamos sobre el trabajo de otros más que rehaciendo tanto de aquello de una forma trivialmente diferente.

Así que ahí está el desafío de todo gran programador, construir a partir de lo que ya existe, no reinventar la rueda para que le salga cuadrada ;).

Nos movemos entre algoritmos y patrones de diseño, estamos llamados a innovar a partir de las herramientas básicas de nuestra profesión y a partir del trabajo previo de quienes nos precedieron. Domina los algoritmos, estudia los patrones, conoce tus frameworks, sus fortalezas, sus limitaciones, juega en el área chica, donde se aplican esos conocimientos para crear una solución a un problema, o una gran innovación. Pero preocúpate de aprender de los que estuvieron antes que tú en este mundo, no seas tan soberbio, la rueda te puede salir cuadrada.

Off Topic: queda una semana para el cierre del desafío Julio Agosto, espero sus respuestas…

Desafío Julio - Agosto 2012: L-Systems

| Comentarios

IMPORTANTE: Dado algunas solicitudes en privado y puesto que este post fue publicado el día 14 de julio, he decidido ampliar el plazo hasta el 15 de septiembre. Aún hay tiempo para que puedan participar.

Un L-System es un tipo de gramática formal que es usada para modelar el desarrollo de las plantas. Este tipo de sistemas permite generar una clase de fractales conocidos como sistemas iterativos de funciones.

Este video muestra varios L-Systems generados mediante un programa en C++ y Open GL

Los L-Systems fueron creados por el biólogo y botánico húngaro Aristid Lindenmayer, uno de los primero L-System creados por Lindenmayer fue este modelo de crecimiento de un alga:

variables: A B estado inicial o axioma: A reglas: (A-> AB), (B->A)

si n cuenta las iteraciones de estas reglas a partir del estado inicial produce las siguientes secuencias:

n = 0: A n = 1: AB // aplicando la primera regla n = 2: AB A // A-> AB y B -> A n = 3: AB A AB // A-> AB, B->A, A -> AB n = 4: AB A AB AB A // A-> AB, B->A, A-> AB, A->AB, B-> A n = 5: AB A AB AB A AB A AB // A-> AB, B->A, A->AB, A-> AB, B->A, A->AB, B->A, A->AB …

Si contamos la longitud de cada string generado obtenemos la secuencia de Fibonacci sin el primer 1 (1,2,3,5,8,13…).

Lo interesante es cuando asociamos los strings resultantes a instrucciones para dibujar.

Por ejemplo, supongamos que tenemos el siguiente L-System:

variables: 0 1 constantes: [ ] axioma: 0 reglas: (1 -> 11), (0->1[0]0)

Entonces aplicamos el axioma recusivamente a través de las reglas y tenemos:

axioma: 0 primera recursión: 1[0]0 segunda recursión: 11[1[0]0]1[0]0 tercera recursión: 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0

Si definimos las siguientes reglas de dibujo:

0: dibujar un segmento que representa una hoja 1: dibujar un segmento de linea representando una rama [: guardar la posición y el ángulo, girar 45 grados a la izquierda ]: recuperar la posición y el ángulo, girar 45 grados a la derecha

Usando un stack LIFO y usando una tortuga para dibujar (como la de Logo, o Python), tenemos: la siguiente secuencia de imágenes:

Pueden leer más detalles sobre los L-Systems en esta entrada en Wikipedia.

Bien, ahora el desafío.

Desafío Julio - Agosto 2012, L-Systems

Asuman que existe un programa que recibe las especificaciones para dibujar un L-System y genera un dibujo, usando turtle graphics.

Las especificaciones se describen en un archivo ascii con la siguiente estructura:

La primera linea debe contener la instrucción lar que especifica el largo de un segmento de linea a dibujar (en pixels), por ejemplo:

lar 50

La segunda línea contiene el ángulo inicial especificado mediante la instrucción ang expresada en grados, por ejemplo:

ang 60

luego se especifica el axioma mediante la instrucción axi, por ejemplo:

axi A

luego vienen las reglas, una por linea. Los símbolos de las reglas pueden ser:

!ATENCION, he editado las reglas de generación por favor revisenlas:

  • + : gira la tortuga a la izquierda de acuerdo a la cantidad de grados definida con la instrucción ang

  • - :   gira la tortuga a la derecha de acuerdo a la cantidad de grados definida con la instrucción ang

  • B: mueve la tortuga hacia atrás   la cantidad de pixeles definidos con la instrucción lar dejando un trazo

  • b:  mueve la tortuga hacia atrás  la cantidad de pixeles definidos con la instrucción lar sin dejar trazo

  • F: mueve la tortuga hacia adelante  la cantidad de pixeles definidos con la instrucción lar dejando un trazo

  • f: mueve la tortuga hacia adelante  la cantidad de pixeles definidos con la instrucción lar

  • Letras mayúsculas (excepto B y F) que indican las variables de las reglas.

Finalmente viene la instrucción iter que indica cuantas veces se itera las reglas para obtener el dibujo.

ejemplo: así luciría un archivo de entrada

lar 20 ang 60 axi A A:A+ZF++ZF-FA–FAFA-ZF+ Z:-FA+ZFZF++ZF+FA–FA-A iter 2

Al interpretar este archivo el programa dibuja una figura  similar a esta:

El desafío consiste en escribir un programa que reciba un archivo con el formato definido, y luego usarlo para esta imagen:

 

Además, aquel que entregue un L-System que genere la imagen más cercana a una planta o una flor tiene más posibilidades de ganar.

Los criterios para elegir ganador serán:

  • la calidad del código del programa

  • el que genere el L-System más simple para dibujar las figuras

  • el que genere la flor o planta más hermosa (en el jurado estará mi esposa ;))

El premio es una giftcard de amazon de US$ 25 y el plazo de entrega es el 15 de septiembre 25 de agosto .

El Ganador Del Desafío De Junio 2012, Problema De Hamming

| Comentarios

Es hora de entregar el premio al ganador del desafío de Junio.

Participaron:

  • Javier Rovegno: con dos soluciones, la segunda es correcta, esencialmente calcula todos los números posibles dentro del rango, y luego ordena la secuencia. Su solución está aquí.

  • Felipe Bañados: con una elegante solución en Haskell, que basicamente implementa la misma solución que expuse en el post anterior, es decir, calcular las secuencias H(p1), H(p2) y H(p3) y luego el merge. Su solución está acá.

  • Carlos Rodriguez: que colaboró con una versión en Pascal! y otra en Python. Al igual que Javier implementa el mecanismo de calcular las secuencias y luego ordenarlas. La versión en pascal está acá y la versión en python acá.

  • Mauricio Quezada: con el mismo tipo de solución en python que propuse inicialmente, generación de los iteradores y luego un merge. Esa versión está acá.

  • Daniel Molina, con una muy eficiente solución en Haskell, tengo la impresión que trata de usar el mínimo de memoria posible, pero supongo que un experto haskell debería opinar. Su solución está acá.

  • Aldrin Martoq, con dos soluciones en C, la segunda versión opera con enteros de 128bits, es la solución más rápida de todas (excepto por la de Jed Davis), claro que tiene un alto uso de memoria.  Su solución en 128 bits está acá.

Les agradezco a todos su tiempo y participación.

Los dos finalistas son Aldrin Martoq y Daniel Molina, pues tienen las soluciones más eficientes de todas las presentadas.

La verdad es que es muy dificil decidir el ganador entre los dos, la razón es que la solución de Aldrin es la más rápida y ocupa menos memoria, pero no es capaz de calcular la secuencia H(7,13,19,10000), el programa de Daniel sí lo hace  y en menos de 1 segundo. Por otro lado, la solución de Aldrin puede calcular en menos tiempo la secuencia H(2,3,5,100000).  Pero la versión de Daniel supera el limite H(2,3,5,100525) de la solución de Aldrin. Por esto último decido que el ganador es Daniel Molina, con quien me pondré en contacto para enviarle su Gift Card.

Gracias nuevamente por participar, estén atentos al próximo desafío.

Respuesta Al Desafío De Junio, El Problema De Hamming

| Comentarios

[caption id=”attachment_417” align=”alignright” width=”222”] Richard Hamming[/caption]

Richard Hamming fue un notable matemático norteamericano, en 1945 trabajó en el proyecto Manhattan programando uno de los primeros computadores, desarrolló un programa que debía determinar si la explosión de la bomba atómica era capaz de incendiar la atmósfera, uno de los mayores temores de los científicos de esa época y que determinó la viabilidad de los lamentables bombardeos posteriores a Hiroshima y Nagasaki.

Después de este periodo trabajó con Claude Shannon en los laboratorios Bell, y fue uno de los fundadores la Asssociation for Computing Machinery (ACM). Recibió el premio Turing en 1968. La IEEE estableció en 1988 una medalla que lleva su nombre, y que se entrega anualmente a personas que logren avances notables en ciencias o tecnologías de la información.

Aparte del problema que nos convoca, Hamming es famoso por haber desarrollado el código de detección y corrección de errores que lleva su nombre, que permite que las comunicaciones y el almacenamiento de información sea una cosa segura y eficiente.

El resumía su filosofía sobre la computación numérica en la frase: “The purpose of computing is insight, not numbers”.

Dijkstra en su libro A Discipline of Programming plantea y populariza una versión del problema de Hamming.

La versión original de Dijkstra es imprimir en orden los números de la forma 2i3j5k, para enteros no negativos i,j, k.

Estos números se conocen como números regulares, o números de Hamming, en teoría músical se conoces como temperamento justo, o mesotónico, a la entonación que sigue una secuencia de números regulares (si no me equivoco, Andy Summer, el guitarrista de Polices aplica este tipo de afinamiento).

Para resolver el problema Dijsktra considera los siguientes pasos:

  • La secuencia de Hamming comienza con el número 1

  • Si el número h está en la secuencia, entonces deben estar los número 2h, 3h y 5h.

  • Por lo tanto, la secuencia H puede ser generada escribiendo el valor 1 y luego se debe mezclar con la secuencia 2H, 3H y 5H.

Nuestro problema es una generalización, en así que reemplazamos 2, 3 y 5 por p1, p2, y p3.

Con esto podemos tener nuestra primera solución, que voy a escribir en Python:

Por supuesto falta el detalle, de las funciones times y merge, esto lo pueden encontrar en mi repositorio en GitHub.

Esta solución muestra la elegancia de las lazy evaluation de los lenguajes funcionales.

Hay varios problemas con esta solución, ¿pueden identificarlos?

Lo más notable es el uso de memoria, ejecutar este programa con los parámetro 7 13 19 500 consume rápidamente sobre los 4 gb!!

Una discusión interesante sobre como resolver este problema se encuentra en Lambda The Ultimate en este artículo, de ahí adapté esta solución, que es bastante eficiente, aunque es difícil de entender, así que acá hay otros dos desafíos, explicar cómo funciona esta solución y extenderla para que funcione con números más grandes:

Esta solución fue planteada por Jed Davis. En el próximo post voy a entregar los premios, así que estén atentos. :)

Respuesta Pendiente, Desafío De Mayo, Cálculo De La Varianza

| Comentarios

Estaba por publicar la respuesta al desafío de junio y noté que no les respondí la solución al desafío de mayo, así que hay que cumplir con los compromisos, así que aquí va. Para los que están esperando la respuesta y los ganadores del desafío de Junio tendrán que esperar un día más, así que los que aún no se animan, tienen unas horas más para intentar ganar la giftcard de Amazón.

Tengo que mencionar que participaron sólo 2 lectores, Daniel Molina y Javier Rovegno, que hicieron la investigación respectiva.

El desafío consistía en calcular la Varianza de la forma más rápida posible, y con la mayor precisión.

En el desafío les mostré una implementación simple basada en la transcripción de la fórmula:

Hay que recordar un par de  resultados fundamentales de la operación con  números en punto flotante. Primero, no son capaces de representar números de precisión infinita, segundo la suma de números en punto flotante no es asociativa, es decir (a+b)+c no es siempre igual que a+(b+c). Cuando tenemos series largas de sumas el error de aproximación puede llevar a un resultado catastrófico, de hecho, el algoritmo mostrado puede llevar a un resultado negativo con ciertos conjuntos de datos, y por ende la desviación estándar, que es la raiz cuadradada de la varianza, puede resultar en un número imaginario, lo que en términos de programación puede generar una excepción en el cálculo.

Ahora, un poco de álgebra nos convencerá de que la expresión:    =    se puede escribir de la siguiente forma:

(sí se que su álgebra está oxidada, pero créanme que es verdad).

Teniendo esto, la varianza se puede calcular como:

Lo que nos lleva a este algoritmo:

def varianza(X[]):
    let n = 0
    let media = 0
    let M2 = 0
    let delta = 0





    for x in X:
        n = n + 1
        delta = x - media
        media = media + delta/n
        M2 = M2 + delta*(x - media)

    return M2/(n - 1)

Y esta es la solución que estaba pendiente, gracias a Daniel y Javier por participar. Mañana veremos la solución al desafío de Julio y entregaremos el premio.

Gracias por participar.

Desafío 2012-06 El Problema De Hamming (Hay Premio)

| Comentarios

Esta es una variante del problema de Haming, que el mismo Dijkstra aborda en uno de sus escritos.

La secuencia de Hamming

Tomemos 3 números primos p1, p2 y p3. Definiremos la secuencia de Haming H(p1,p2,p3) como un conjunto que contiene, en orden incremental, todos los números naturales cuyos únicos divisores primos son p1,p2 y p3.

Por ejemplo H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, …

Definiremos el número Hi(p1,p2,p3), o número de Hamming sub i, con i = 1,2,… al i-ésimo número de la secuencia de Haming H(p1,p2,p3).

Así que H5(2, 3, 5)=6 y H9(2,3,5)=12

El problema consiste en escribir un programa que reciba 4 números: p1 p2 p3 i, y retorne un único entero correspondiente a Hi(p1,p2,p3). Todos los números serán menores que 10ˆ18.

Ejemplo de entrada:

hamming 7 13 19 100

Salida esperada:

# 26590291

El programa debe correr en menos de 1.000 milisegundos y consumir la menor cantidad de memoria posible.

Ganará el programa más rápido. Da lo mismo el lenguaje de programación. Lo ideal es que envíen instrucciones de compilación.

El premio: 1 Gift Card de Amazon de us$ 25. Sólo habrá premio para el primer lugar.

Nota: La respuesta y premación del desafío de mayo viene en el próximo post.

Nota 2: no todos los desafíos tendrán premio.

Mini Desafío: Zig Zag

| Comentarios

No es primera vez que publico este desafío, pero seguramente hay muchos de ustedes que no lo conocen, vamos a ver si este tiene más éxito, considérenlo un calentamiento para el desafío de Junio :)

El desafío es el siguiente:

Producir un arreglo zig-zag.

Un arreglo zig-zag es un arreglo cuadrado de los primeros N2 enteros, donde los números van ordenados de menor a mayor distribuidos en forma de zig zag a lo largo de las anti diagonales de la matriz (ver la figura).

Por ejemplo, si N es 5, el programa debe producir este arreglo:

0   1   5   6  14 2   4   7 13  15 3   8 12 16  21 9 11 17 20  22 10 18 19 23  24

  • Aunque esto puede parecer un juego de ingenio, un tanto inútil, la verdad es que este tipo de arreglos es usado en el algoritmo de compresión de imágenes JPEG.

Desafío Avanzado: mi solución la describí en este artículo en LNDS hace unos años atrás, el desafío avanzado es escribir un algoritmo más eficiente que el que descrito ahí.

Un Desafío Sin Respuestas

| Comentarios

Lamentablemente hasta ahora sólo tengo una respuesta al desafío de mayo, el valiente fue Javier Rovegno, quién además ha investigado bastante sobre el tema.

He usado esta misma pregunta varias veces en pruebas de selección de personal (es buena idea aparte de ver el currículum, preguntarle a los ingenieros de software si son capaces de programar). Normalmente a mis entrevistados les doy a escoger entre varias preguntas, por ejemplo, le presento 3 preguntas y les doy a elegir 2. Nunca he visto que alguien haya contestado esta pregunta.

Si les pregunto por el clásico Fizz Buzz varios lo intentan, no muchos lo resuelven bien, pero lo intentan. También les pregunto por variantes del problema de Siracusa y varios intentan abordar ese problema. Pero pregunto por el cálculo de Desviación Estándar y nadie se atreve.

Muchas veces espero que apliquen el truco de expandir la serie de modo que se den cuenta de que se puede calcular la desviación estándar con un sólo ciclo. Con esa respuesta me doy por satisfecho, pero hasta ahora nadie lo intentó (salvo Javier Rovegno). No espero que implementen el algoritmo de Welford (que es un algoritmo maravilloso y que estudiaremos en el próximo post).

Mi pregunta es ¿por qué le tienen tanto miedo a este problema? ¿O será que los programadores son malos calculando? No se, qué opinan ustedes? Quizás sólo exagero, y la verdad es que no hay tantos lectores de este blog como esperaba.