17 de diciembre de 2013

Documentando programas en Python

Introducción

Para mucha gente (yo incluido), la idea de tener que documentar un programa genera el mismo entusiasmo que cuando pensamos sobre la ingesta diaria recomendada de verduras. Son de esas cosas que sabemos que son buenas y debemos procurar, pero definitivamente no nos fascinan.


Sin embargo, la verdad es ésta: no importa lo fabuloso que sea un programa, nadie lo usará si no queda claro la manera de utilizarlo. En este sentido la documentación juega un rol primordial. Aunque yo sea el único usuario de mi programa, resulta más sencillo entender y reutilizar lo que escribí hace seis meses si cuento con una documentación adecuada.

Nos debe quedar claro que, como maestros de programación, tenemos la responsabilidad de inculcar la importancia de la documentación a nuestros alumnos.

Pero, ¿por qué nos disgusta tanto la tarea de escribir documentación para nuestros programas? La razón es simple: es más divertido escribir código que documentarlo. Empero, si deseamos que nuestros programas trasciendan más allá del momento en que los escribimos necesitamos dedicarles algo de tiempo para documentarlos.

Una buena noticia es que Python cuenta con un mecanismo bastante sencillo y conveniente para elaborar la documentación técnica de un programa. A continuación expondré dicho mecanismo.

Cadenas de documentación 

En Python, un docstring o cadena de documentación es una literal de cadena de caracteres que se coloca como primer enunciado de un módulo, clase, método o función, y cuyo propósito es explicar su intención. Un ejemplo sencillo (todos estos ejemplos funcionan en Python 3):
def promedio(a, b):
    'Calcula el promedio de dos números.'
    return (a + b) / 2
Un ejemplo más completo:
def formula_cuadratica(a, b, c):
    """Resuelve una ecuación cuadrática.

    Devuelve en una tupla las dos raíces que resuelven la
    ecuación cuadrática:
    
        ax^2 + bx + c = 0.

    Utiliza la fórmula general (también conocida
    coloquialmente como el "chicharronero").

    Parámetros:
    a -- coeficiente cuadrático (debe ser distinto de 0)
    b -- coeficiente lineal
    c -- término independiente

    Excepciones:
    ValueError -- Si (a == 0)
    
    """
    if a == 0:
        raise ValueError(
            'Coeficiente cuadrático no debe ser 0.')
    from cmath import sqrt
    discriminante = b ** 2 - 4 * a * c
    x1 = (-b + sqrt(discriminante)) / (2 * a)
    x2 = (-b - sqrt(discriminante)) / (2 * a)
    return (x1, x2)
La cadena de documentación en el segundo ejemplo es una cadena multi-líneas, la cual comienza y termina con triples comillas ("""). Aquí se pueden observar el uso de las convenciones establecidas en el PEP 257 (Python Enhancement Proposals):
  • La primera línea de la cadena de documentación debe ser una línea de resumen terminada con un punto. Debe ser una breve descripción de la función que indica los efectos de ésta como comando. La línea de resumen puede ser utilizada por herramientas automáticas de indexación; es importante que quepa en una sola línea y que esté separada del resto del docstring por una línea en blanco.
  • El resto de la cadena de documentación debe describir el comportamiento de la función, los valores que devuelve, las excepciones que arroja y cualquier otro detalle que consideremos relevante.
  • Se recomienda dejar una línea en blanco antes de las triples comillas que cierran la cadena de documentación.
Todos los objetos documentables (módulos, clases, métodos y funciones) cuentan con un atributo __doc__ el cual contiene su respectivo comentario de documentación. A partir de los ejemplos anteriores podemos inspeccionar la documentación de las funciones promedio y formula_cuadratica desde el shell de Python:
>>> promedio.__doc__
'Calcula el promedio de dos números.'
>>> formula_cuadratica.__doc__
'Resuelve una ecuación cuadrática.\n\n    Devuelve en una 
tupla las dos raíces que resuelven la\n    ecuación 
cuadrática:\n    \n        ax^2 + bx + c = 0.\n\n    
Utiliza la fórmula general (también conocida\n    
coloquialmente como el "chicharronero").\n\n    
Parámetros:\n    a -- coeficiente cuadrático (debe ser 
distinto de 0)\n    b -- coeficiente lineal\n    
c -- término independiente\n\n    Excepciones:\n    
ValueError -- Si (a == 0)\n    \n    '
Sin embargo, si se está usando el shell de Python es mejor usar la función help(), dado que la salida producida queda formateada de manera más clara y conveniente:
>>> help(promedio)
Help on function promedio in module __main__:

promedio(a, b)
    Calcula el promedio de dos números.
>>> help(formula_cuadratica)
Help on function formula_cuadratica in module __main__:

formula_cuadratica(a, b, c)
    Resuelve una ecuación cuadrática.
    
    Devuelve en una tupla las dos raíces que resuelven la
    ecuación cuadrática:
    
        ax^2 + bx + c = 0.
    
    Utiliza la fórmula general (también conocida
    coloquialmente como el "chicharronero").
    
    Parámetros:
    a -- coeficiente cuadrático (debe ser distinto de 0)
    b -- coeficiente lineal
    c -- término independiente
    
    Excepciones:
    ValueError -- Si (a == 0)
Ciertas herramientas, por ejemplo shells o editores de código, pueden ayudar a visualizar de manera automática la información contenida en los comentarios de documentación. La siguiente imagen muestra como el shell del ambiente de desarrollo integrado IDLE muestra la línea de resumen como descripción emergente (tool tip) al momento en que un usuario teclea el nombre de la función:

De esta manera un usuario puede tener a su alcance de manera sencilla toda la información que necesita para poder usar nuestras funciones.

Generando documentación en páginas de HTML

Los docstrings se pueden usar también para producir documentación en páginas de HTML que pueden ser consultadas usando un navegador de web. Para ello se usa el comando pydoc desde una terminal. Por ejemplo, si las dos funciones anteriores (promedio y formula_cuadratica) se encuentran en un archivo fuente llamado ejemplos.py, podemos ejecutar el siguiente comando en una terminal dentro del mismo directorio donde está el archivo fuente:
pydoc -w ejemplos
La salida queda en el archivo ejemplos.html, y así se visualiza desde un navegador:

La documentación de pydoc explica otras monerías que puede hacer esta utilería de Python.

Docstrings vs. comentarios

Un comentario en Python inicia con el símbolo de número (#) y se extiende hasta el final de la línea. En principio los docstrings pudieran parecer similares a los comentarios, pero hay una diferencia pragmática importante: los comentarios son ignorados por el ambiente de ejecución de Python y por herramientas como pydoc; esto no es así en el caso de los docstrings.

A un nivel más fundamental hay otra diferencia aún más grande entre los docstrings y los comentarios, y ésta tiene que ver con la intención:
  • Los docstrings son documentación, y sirven para entender qué hace el código.
  • Los comentarios sirven para explicar cómo lo hace.
La documentación es para la gente que usa tu código. Los comentarios son para la gente que necesita entender cómo funciona tu código, posiblemente para extenderlo o darle mantenimiento.

Conclusiones

El uso de docstrings en Python facilita la escritura de la documentación técnica de un programa. Escribir una buena documentación requiere de disciplina y tiempo pero sus beneficios se cosechan cuando alguien (quizás mi futuro yo dentro de seis meses) necesita entender qué hace nuestro software. Los docstrings no sustituyen otras buenas prácticas de programación, como son el uso apropiado de comentarios o el empleo de nombres descriptivos para variables y funciones, por lo que resulta importante enseñar y promover con nuestros alumnos todas estas prácticas de manera conjunta desde temprano en su formación como programadores.

26 de octubre de 2013

Sphere Online Judge

Introducción

Hace algo de tiempo publiqué en este blog una entrada que presentaba al Proyecto Euler. Como lo expliqué en ese momento, Project Euler es un sitio web que contiene centenas de problemas de tipo matemático que pueden ser resueltos escribiendo un programa de computadora. En esta ocasión quiero presentar otro sitio web que personalmente me parece más interesante: el Sphere Online Judge (SPOJ).


En el Proyecto Euler se describe un problema y el usuario debe proveer un resultado que comúnmente es un simple número. Realmente no importa cómo se llegue al resultado final. Puede ser que el usuario resuelva el problema con lápiz y papel, o puede ser que escriba un programa de computadora que tarde varios días en llegar al resultado. En el SPOJ, por otro lado, se proporciona la descripción de un problema y el usuario debe escribir y subir un programa completo que lo resuelva. En unos cuantos segundos el juez en línea del SPOJ ejecuta y evalúa de manera automática dicho programa para finalmente proporcionar un veredicto que puede ser de aceptación o de rechazo. Los programas que se suben al SPOJ deben cumplir con ciertos requerimientos en cuanto al tamaño del código fuente, a la memoria que utilizan y al tiempo en que tardan en correr.

El SPOJ resulta un excelente recurso de preparación para estudiantes interesados en participar en competencias de programación, como son la Olimpiada Internacional de Informática (IOI) y el Concurso Internacional Universitario de Programación de la ACM (ACM-ICPC).

Equipo de programación competitiva del
Tec de Monterrey, Campus Estado de México,
en la final mundial del ACM-ICPC en la
Technische Universiteit Eindhoven (TUE),
Países Bajos, abril 1999.

El SPOJ cuenta con una base de datos con más de diez mil problemas. Las soluciones pueden ser programadas en más de cuarenta lenguajes diferentes, incluyendo Python por supuesto. Al momento en el que escribo estas líneas, el juez en línea acepta soluciones escritas en Python versiones 2.7 y 3.2.3.

En mi experiencia la mayor parte de los problemas publicados en el SPOJ se pueden resolver usando Python. Sin embargo, sí existen algunos problemas que no pueden ser resueltos en Python debido a que las implementaciones disponibles del lenguaje no son suficientemente rápidas para cumplir con los límites impuestos en cuanto a los tiempos de ejecución. También, en raras ocasiones, algunos problemas explícitamente prohíben utilizar Python.

Usando Python en el SPOJ

El primer paso para comenzar a usar el SPOJ consiste en registrarse en el sitio. Dicho registro es gratis y no toma más que unos cinco minutos en completarse: https://www.spoj.com/register/

La gran mayoría de los problemas del SPOJ se resuelven en tres pasos:
  1. Leer datos de la entrada.
  2. Transformar dichos datos utilizando algún algoritmo.
  3. Producir una salida con los resultados del paso anterior.
La redacción de cada problema incluye siempre al menos un caso de prueba.

La entrada de los programas solución se debe leer desde stdin (standard input o entrada estándar) y la salida se debe escribir a stdout (standard output o salida estándar). Normalmente stdin y stdout están asociados al teclado y a la pantalla de la computadora. En Python 3 las acciones de lectura y escritura se pueden llevar a cabo con las funciones input y print, respectivamente. En Python 2 en lugar de usar la función input se debe usar la función raw_input.

Tomemos como ejemplo al primer problema del SPOJ. Este problema, el cual sirve primordialmente para familiarizarse con el mecanismo de envío de programas solución, requiere leer una secuencia de números enteros. Dichos números se deben imprimir en la salida hasta que se lea el número 42. Cuando eso ocurra el programa debe terminar. El 42 no se debe imprimir, ni tampoco ninguno de los número subsecuentes de la entrada. Por tanto, dado la siguiente entrada:
1
2
88
42
99
La salida esperada es:
1
2
88
El siguiente programa en Python 3 resuelve el problema:
# Programa: TEST.py

while True:
    n = int(input())
    if n == 42: break
    print(n)
Es posible correr el programa e ir tecleando manualmente los números conforme el programa los vaya requiriendo. Sin embargo esta forma de probar el programa es susceptible a que se cometan errores de captura. Adicionalmente, las líneas de entrada y salida aparecen intercaladas, lo que hace difícil corroborar que la salida del programa sea efectivamente la esperada.

Lo más recomendable es correr el programa desde una terminal (también conocida como “línea de comando” o “símbolo del sistema”) y redireccionar stdin para que la entrada se reciba desde un archivo. Para ello primeramente se debe crear un archivo de texto con el contenido de la entrada a probar. A este archivo yo normalmente le llamo in.txt. Se puede simplemente “copiar y pegar” el texto deseado desde la página del SPOJ al lugar donde se está editando el archivo in.txt.

En Windows la funcionalidad de una terminal se obtiene corriendo el programa cmd.exe. Una vez abierta la ventana correspondiente, hay que cambiarse al directorio donde se guardaron los archivos TEST.py e in.txt, por ejemplo:
cd \Users\MiCuenta\Documents
Posteriormente se ejecuta el programa así:
python TEST.py < in.txt
La salida debe ser la que se indicó arriba. Sin embargo, si el sistema indica que no puede encontrar el programa ejecutable python, entonces probablemente se pueda corregir esta situación indicando la ruta completa donde está instalado Python 3, algo así como:
c:\Python33\python TEST.py < in.txt
Si se está usando Mac o Linux, los pasos son similares. En la terminal se debe uno primero cambiar al directorio donde están los archivos TEST.py e in.txt, por ejemplo:
cd /home/MiCuenta/Documents
Luego, el programa se debe ejecutar así:
python3 TEST.py < in.txt
El símbolo de “menor que” (<) utilizado al momento de correr un programa en una terminal sirve para redireccionar stdin. Esto es, en lugar de recibir la entrada desde el teclado, la entrada será tomada del archivo cuyo nombre viene inmediatamente después del símbolo “menor que”.

Si deseamos que la salida del programa se vaya a un archivo (en lugar de irse a la pantalla de la terminal) podemos redireccionar también stdout. En este caso usamos el símbolo de “mayor que” (>) seguido del nombre del archivo de salida, tal como se muestra a continuación:
python3 TEST.py < in.txt > out.txt
Dejar la salida del programa en un archivo puede resultar útil si deseamos comparar cuidadosamente dicha salida con la salida esperada según la especificación del problema. Dicha salida esperada debe colocarse en otro archivo. Luego, desde la terminal se pueden usar los comandos fc (en Windows) o diff (en Mac y Linux) para comparar de manera automática los dos archivos de texto (el que tiene la salida esperada y el producido por nuestro programa). El uso de una herramienta para realizar la comparación de archivos, en lugar de hacerlo “a ojo del buen cubero”, es indispensable cuando el tamaño de los contenidos es de más de unas cuantas líneas de texto.

Una vez que tenemos la certeza de que nuestro programa funciona correctamente, podemos entonces subirlo al SPOJ para que sea evaluado por el juez en línea. La página de cada problema tiene una liga de submit en la parte superior izquierda. El código del programa se puede “copiar y pegar” directamente en un área de texto dentro del formulario que aparece, o alternativamente se puede usar el botón de “Examinar...” para seleccionar el archivo guardado en alguna parte de nuestro equipo. Es importante verificar que los campos de Language (Python 3.2.3) y Problem code or id (TEST) sean los correctos. Si todo está bien, presionamos el botón “Send”.

Después de un instante aparece en la página el estado del juez en línea indicando su veredicto:


El primer renglón tiene la evaluación de nuestro programa recién enviado. Si aparece el renglón en gris significa que está aún en proceso de evaluación. Si el renglón está en naranja significa que el programa tuvo algún problema y fue rechazado. Si el renglón está en verde quiere decir que fue aceptado. ¡Yupi!


Sin embargo, si un problema es rechazado, es posible corregirlo y volverlo a enviar tantas veces como sea necesario.

Un problema puede ser rechazado por diversos motivos:
  • CE compilation error: El programa contiene uno o más errores sintácticos.
  • WA wrong answer: El programa se ejecutó con éxito, pero los resultados son incorrectos. Probablemente se está interpretando el problema de manera incorrecta o incompleta, o simplemente el programa tiene un error de lógica.
  • TLE time limit exceeded: El programa se tarda en ejecutar más tiempo que lo que tiene permitido. Esto puede ser causado debido a que el algoritmo está mal diseñado y resulta muy lento, o que el programa contiene un ciclo infinito, o incluso se puede deber a que el programa se detiene por estar esperando datos de entrada inexistentes. También, como ya mencioné anteriormente, puede deberse a que el intérprete de Python resulta muy lento para resolver el problema en cuestión. Si ese es el caso, puede ser que el mismo algoritmo implementado en un lenguaje como C sí corra dentro del tiempo límite.
  • RE runtime error: El programa produjo algún error a tiempo de ejecución. Cuando se utiliza Python la causa más comunes es un NZEC (non-zero exit code). Esto quiere decir que el programa abortó debido a que se generó una excepción que no fue atrapada. Por ejemplo, se intentó dividir un entero entre cero o acceder a un elemento de una lista usando un índice fuera de rango. Normalmente estos son producidos por errores de lógica en nuestro programa.
Una descripción más detallada del uso del SPOJ se puede consultar en la siguiente liga: How to cope with SPOJ?

Consejos para usar el SPOJ

Al intentar resolver un problema del SPOJ es muy importante leer detenidamente la especificación correspondiente. Cuando el juez en línea marca un WA (wrong answer) muy a menudo resulta que se pasó por alto algún pequeño detalle contenido en la redacción del problema.

Es posible que el programa genere los resultados correctos, pero la salida producida no está en el formato solicitado. Incluso puede ser que un carácter de espacio no solicitado al final de una línea en la salida sea suficiente para que la solución sea rechazada. Por tanto, es muy importante cuidar esos pequeños detalles.

Al estar usando Python, conviene leer la entrada una línea completa a la vez. Por ejemplo, si la descripción de problema dice que una línea de la entrada contiene los números enteros a, b y c separados entre sí por un espacio en blanco, una forma muy sencilla de leer dichos números en Python 3 sería así:
datos = input().split()
a = int(datos[0])
b = int(datos[1])
c = int(datos[2])
Alternativamente, usando una asignación paralela y una list comprehension, podemos reducir el código anterior a una sola línea: 
a, b, c = [int(x) for x in input().split()]
Otra recomendación es probar nuestros programas con más casos que los que se incluyen como ejemplo en la redacción del problema. Casi siempre los casos de ejemplo son muy sencillos, pero los casos de prueba que usa el juez en línea son mucho más grandes y exhaustivos. Hay que probar siempre los casos extremos. Por ejemplo, si el problema establece que el programa debe recibir un número entre 0 y 1,000,000, es importante hacer pruebas con varios números incluyendo 0 y 1,000,000.

Al final de la redacción de cada problema viene una sección de comentarios de usuarios. A veces se pueden encontrar ahí algunas pistas o casos adicionales que pueden ayudarnos a entender los motivos por los que el juez en línea está rechazando nuestra solución.

Problema sugeridos

A continuación listo una decena de problemas del SPOJ que se pueden resolver usando unas cuantas líneas de código en Python. Algunos de estos problemas son relativamente fáciles, otros son más retadores.

Desventajas del SPOJ

Como educadores, es importante tener en cuenta las siguientes limitaciones del SPOJ al momento de usarlo con nuestros alumnos:
  • Casi todos los problemas del SPOJ están redactados en inglés, lo cual puede reducir su utilidad para aquellas personas que no se les facilita leer en este idioma.
  • Por diseño, la retroalimentación que brinda el juez en línea es bastante limitada. Esto no es problema cuando un programa es aceptado. Sin embargo, cuando el programa es rechazado con WA (wrong answer) no hay más información para conocer el origen del error. Esto puede resultar bastante frustrante. El SPOJ busca que los usuarios diagnostiquen y corrijan sus propios errores. 
  • El SPOJ solo evalúa que un programa funcione correctamente de acuerdo a la especificación dada y dentro de las restricciones estipuladas referentes a tiempo de ejecución, tamaño del código fuente y uso de memoria. Otros atributos que son muy importantes al momento de programar (legibilidad del código, diseño, documentación, uso de buenas prácticas, etc.) no figuran en absoluto al momento en el que el juez en línea emite su veredicto. Aunque relevantes, estos atributos pueden considerarse un tanto subjetivos, por lo que resulta en principio complicado que pudieran evaluarse efectivamente de forma automatizada.

Otros Jueces en Línea

El SPOJ se originó en Polonia a mediados de la década pasada. Probablemente hoy en día es el juez en línea más popular del mundo. Sin embargo no es el único. Otros dos sitios que funcionan de manera similar al SPOJ (y que aceptan soluciones escritas en Python) son:
  • Caribbean Online Judge: Juez en línea de la Universidad de las Ciencias Informáticas (UCI) de Cuba. Acepta soluciones en Python versión 2.6.5.
  • Timus Online Judge: Juez en línea de la Universidad Ural Federal de Rusia. Acepta soluciones en Python versiones 2.7.3 y 3.3.0.
El primer juez en línea fue el UVa Online Judge. Éste fue desarrollado por la Universidad de Valladolid en España y se abrió al público en el año de 1997. Su principal limitación es que solamente acepta soluciones en C/C++, Java y Pascal.

Conclusión

La práctica hace al maestro. Si se quiere dominar el arte de resolver problemas a través de la programación es indispensable practicar, practicar y practicar. Y después, hay que seguir practicando todavía más. Con un acervo de miles de problemas y un mecanismo que permite obtener una retroalimentación instantánea, el SPOJ es una de las mejores herramientas que tenemos disponibles para este fin.

20 de agosto de 2013

¿Dónde quedó el do-while?

Una de las estructuras de control de ejecución que no está presente en el lenguaje de programación Python es el ciclo do-while. Tanto alumnos como maestros me han preguntado sobre sobre la manera más conveniente de darle la vuelta a esta limitación del lenguaje. En esta entrada del blog de EduPython responderé de manera extensiva a esta pregunta.

Para empezar, conviene distinguir entre los dos tipos de ciclo que encontramos en muchos lenguajes de programación: el ciclo while y el ciclo do-while. Existe un tercer tipo de ciclo, el ciclo for, pero no es relevante para esta discusión.

El ciclo while

En la familia de lenguajes basados en C (por ejemplo C++, C#, Java, JavaScript, etc.), el ciclo while tiene la siguiente sintaxis:
// Ciclo while
while (condición) {
    cuerpo
}
El siguiente diagrama de flujo muestra como se comporta este tipo de ciclo:

Ciclo while

Podemos ver que primero se evalúa la condición. Si ésta resulta falsa, la instrucción termina. Sin embargo, si resulta verdadera el cuerpo se ejecuta, y posteriormente se vuelve a evaluar la condición. Esto se repite efectivamente mientras la condición siga dando un valor de verdadero. Normalmente se supone que algo ocurrirá dentro del cuerpo del ciclo que hará que la condición sea eventualmente falsa1.

El ciclo do-while

La sintaxis de la instrucción do-while en los lenguajes basados en C es la siguiente:
// Ciclo do-while
do {
    cuerpo
} while (condición);
Y éste es el diagrama de flujo respectivo:

Ciclo do-while
Aquí se puede observar que primero se ejecuta el cuerpo y hasta después se evalúa la condición. Si ésta última resulta falsa, entonces la instrucción termina. Pero si resulta verdadera, entonces se vuelve a ejecutar el cuerpo seguido de la evaluación de la condición. Esto se repite mientras que el resultado de la condición siga dando verdadero.

while vs. do-while

La diferencia central entre el ciclo while y ciclo do-while radica en el número mínimo de veces que se ejecuta el cuerpo respectivo. En el caso de la instrucción while, el cuerpo se ejecuta un mínimo de cero veces, mientras que la instrucción do-while el mínimo es una vez. A nivel sintáctico, la diferencia entre ambos ciclos se enfatiza por la posición en la que debe ir la expresión condicional: en la instrucción while va antes del cuerpo y en la instrucción do-while va después de éste2.

Cuando llego a impartir un curso de introducción a la programación me gusta presentarle a mis alumnos el siguiente ejemplo para ayudarles a entender la diferencia entre estos dos tipos de ciclos: 
Hay un chavo tímido que está con una chava que le gusta y desea darle de besos (todos los que se puedan). Existen dos alternativas:
  • Alternativa 1: El chavo le pregunta a la chava si la puede besar. Si la chava dice que no, al chavo no le queda mas que aguantarse. Pero si la chava dice que sí, el chavo besa a la chava y luego le vuelve a preguntar si la puede besar otra vez, repitiendo este proceso hasta que la chava diga que no.
  • Alternativa 2: El chavo besa a la chava. El chavo le pregunta a la chava si la puede besar otra vez. Si la chava dice que sí, el chavo besa nuevamente a la chava y luego le vuelve a preguntar si la puede besar una vez más, repitiendo este proceso hasta que la chava diga que no.
En la alternativa 1, si la chava no quiere besos, entonces el chavo nunca la podrá besar. Sin embargo en la alternativa 2, si la chava no quiere besos, el chavo por lo menos le alcanza a robar uno3. Por tanto la alternativa 1 es un ejemplo del ciclo while, mientras que la alternativa 2 es un ejemplo del ciclo do-while.

Implementación del ciclo do-while en Python

Un caso de uso típico del ciclo do-while es cuando requerimos solicitar al usuario un cierto dato de entrada el cual debe ser validado. Si el dato capturado contiene algún error, entonces se debe solicitar nuevamente la entrada y se debe validar otra vez, repitiendo esto hasta que la entrada sea correcta. Por ejemplo, en pseudocódigo lo anterior se podría expresar así:
  • Hacer lo siguiente:
    • Sea e una cadena solicitada al usuario.
    • Sea r igual a verdadero si e contiene el nombre de una de las estaciones del año (primavera, verano, otoño o invierno), o falso en caso contrario.
    • Si r es falso, imprimir un mensaje de error.
  • Repetir lo anterior mientras r sea falso.
  • Imprimir un mensaje de éxito.
En este ejemplo el cuerpo del ciclo se debe ejecutar al menos una vez. Tal como se mencionó al inicio de este texto, el lenguaje Python cuenta con la instrucción while, mas no con la instrucción do-while. Dada esta restricción, podemos re-plantear el código de tal forma que tenga la siguiente estructura:

Simulación de un ciclo do-while mediante
un ciclo while y duplicación del cuerpo
En el diagrama de flujo anterior vemos que el cuerpo del ciclo (el cuadro rojo) se duplica de manera íntegra antes de la condición, y con ello garantizamos que el cuerpo efectivamente se ejecuta por lo menos una vez. Combinando y traduciendo el diagrama de flujo y el pseudocódigo obtenemos el siguiente programa en Python 3.x:
e = input('Introduce el nombre de una estación '
          'del año: ')
r = e.lower() in ['primavera', 'verano', 'otoño',
                  'invierno']
if not r:
    print('"{0}" no es el nombre de una estación '
          'del año.'.format(e))
    print('Favor de volverlo a intentar.')

while not r:
    e = input('Introduce el nombre de una estación '
              'del año: ')
    r = e.lower() in ['primavera', 'verano', 'otoño',
                      'invierno']
    if not r:
        print('"{0}" no es el nombre de una estación '
              'del año.'.format(e))
        print('Favor de volverlo a intentar.')

print("Muy bien.")
Las ocho líneas que aparecen antes del while se repiten también en su cuerpo. Aunque la funcionalidad obtenida es exactamente la esperada, la solución no es recomendable precisamente debido a la duplicación de código. El programa es más largo de lo necesario y obliga a ocupar más tiempo al momento de leerlo e intentar comprenderlo. Pero peor aún: si se requiere hacer un cambio en cualquiera de esas líneas, las modificaciones se tienen que hacer en dos lugares distintos; resulta muy fácil alterar el código en un lugar y olvidarse que hay otra parte que también necesita el mismo cambio.

Cuando se tienen instrucciones duplicadas éstas pueden ser eliminadas aplicando una refactorización de código conocida como extracción de método. Sin embargo en nuestro ejemplo hay una solución más sencilla: podemos garantizar que el cuerpo del ciclo while se ejecutará al menos una vez si nos aseguramos que la condición del ciclo es verdadera antes de la primera iteración. Modificando nuestro código tendríamos lo siguiente:
r = False

while not r:
    e = input('Introduce el nombre de una estación '
              'del año: ')
    r = e.lower() in ['primavera', 'verano', 'otoño',
                      'invierno']
    if not r:
        print('"{0}" no es el nombre de una estación '
              'del año.'.format(e))
        print('Favor de volverlo a intentar.')

print("Muy bien.")
En este caso pudimos remplazar las ocho líneas de código que estaban antes del while por una sola línea: r = False. Con esa sola instrucción obligamos a que la condición del ciclo (not r) sea verdadera la primera vez que se evalúa, y por lo tanto haciendo que se ejecute efectivamente el cuerpo al menos una vez. El valor de la variable r se re-asigna dentro del cuerpo del ciclo, así que de ese nuevo valor dependerá que el cuerpo se vuelva a ejecutar, tal como ocurría desde la primera versión del programa.

Otra alternativa en Python, que resulta una solución más general, consiste en escribir un ciclo “infinito” (usando un instrucción while True:) y añadir una instrucción if con un break al final del cuerpo. La condición de este if es la misma que la condición del do-while, pero en forma lógicamente negada, ya que la condición se usa en este caso para indicar cuando se debe terminar el ciclo en lugar de establecer el criterio de permanencia en éste. Esta forma resulta más conveniente que las otras dos planteadas anteriormente gracias a que es prácticamente una simple traducción del ciclo do-while. Modificando una vez más el código de arriba obtendríamos lo siguiente:
while True:
    e = input('Introduce el nombre de una estación '
              'del año: ')
    r = e.lower() in ['primavera', 'verano', 'otoño',
                      'invierno']
    if not r:
        print('"{0}" no es el nombre de una estación '
              'del año.'.format(e))
        print('Favor de volverlo a intentar.')

    # Condición para romper el ciclo.
    if r: 
        break

print("Muy bien.")
Cuando se ejecuta un break el ciclo en el que está contenido termina de manera inmediata, continuando el flujo de control del programa en la siguiente instrucción posterior al ciclo.

Ciclo loop-with-exit

La instrucción condicional que contiene el break ni siquiera tiene que ser la última instrucción del cuerpo del while. De hecho, a veces resulta útil que se encuentre entre dos porciones de código. A la estructura de control de flujo que cumple con la descripción anterior se le conoce como loop-with-exit (ciclo con salida)  y está soportada de manera directa en lenguajes de programación como Ada y versiones modernas de Fortran y Basic. Dicha estructura tiene la siguiente forma:

Ciclo loop-with-exit
Aquí podemos notar que el cuerpo se divide en dos partes (Cuerpo-1 y Cuerpo-2) y que la condición de terminación del ciclo se encuentra justo entre ambas partes.

El siguiente ejemplo muestra la implementación de un ciclo loop-with-exit en Python. El programa solicita al usuario una cadena de entrada, la convierte a mayúsculas, imprime el resultado y repite todo este proceso. Sin embargo, si la cadena capturada es vacía el ciclo se termina.
while True:
    e = input('Introduce una cadena de caracteres, '
              'o vacío para terminar: ')

    # Condición para romper el ciclo.
    if e == '':
        break

    m = e.upper()
    print('Convertido a mayúsculas: {0}'.format(m))

print('Fin.')
Para que el código resulte más claro, se recomienda que solo haya una instrucción break dentro del ciclo. Esta recomendación surge desde de los años sesenta y setenta, cuando autores como Edsger W. Dijkstra y C.A.R. Hoare iniciaron una campaña a favor de la programación estructurada. La idea fundamental consistía en evitar la escritura de lo que se conoce de forma despectiva como “código espagueti”. Desde entonces se estableció que por legibilidad los ciclos debían contar con un solo punto de entrada y un solo punto de salida.

La instrucción while-else

Ya entrados en el uso del while y el break de Python, quizás valga la pena mencionar una peculiaridad poco conocida del lenguaje: el while puede tener un else asociado, de forma similar a como ocurre con la instrucción if. En este caso el cuerpo del else se ejecuta solo si el while concluye de manera “normal” (cuando su condición resulta falsa) en lugar de terminar por una instrucción break anidada dentro del ciclo. Por ejemplo:
n = [4, 8, 15, 16, 23, 42]
x = 16
i = 0
while i < len(n):
    if x == n[i]:
        print('Se encontró el {0} en el índice {1}.'
              .format(x, i))
        break
    i += 1
else:
    print('No se encontró el {0}.'.format(x))
Este programa produce la siguiente salida:
Se encontró el 16 en el índice 3.
En este caso el código asociado al else no se ejecuta porque el ciclo termina debido a un break. Sin embargo, si cambiamos la segunda línea del programa de arriba por x = 20, la salida ahora sería:
No se encontró el 20.
Dado que ahora el ciclo termina gracias a que en algún momento la condición del while se hace falsa, el cuerpo del else ahora sí se ejecuta.

En general el uso del while-else no es común, y su uso no es muy recomendable debido a que es un ciclo con un punto de entrada pero con dos puntos de salida, haciéndolo en principio más difícil de entender.

Conclusión

A pesar de que Python no cuenta con la instrucción do-while es muy fácil emularla con un while True: y un if con un break al final del cuerpo del ciclo. Esta forma se puede generalizar en una instrucción conocida como loop-with-exit, en donde el if con el break puede ir en cualquier parte del cuerpo del ciclo. Sin embargo es importante procurar que nuestro código sea fácil de entender, por lo que de preferencia los ciclos solo deben tener un punto de entrada y un punto de salida. Haciendo esto cumplimos con un principio fundamental de la programación estructurada.


Notas:

1 Por lo menos así es cuando existe solamente un hilo de ejecución. Un hilo distinto pero concurrente al que está ejecutando el ciclo también puede hacer que la condición cambie.

2 Existen algunas variaciones del ciclo do-while en otros lenguajes. Un ejemplo es la instrucción repeat-until del lenguaje Pascal. La principal diferencia entre estas dos instrucciones es que para terminar un ciclo do-while se requiere que su condición sea falsa, mientras que para terminar un ciclo repeat-until su condición debe ser verdadera. En ambos casos el cuerpo del ciclo se ejecuta mínimo una vez.

3 Este ejemplo es solo para fines ilustrativos. En ningún momento se está consintiendo a que los chavos besen a las chavas sin su permiso.

11 de julio de 2013

La curva de dragón: el fractal de Parque Jurásico

Hace precisamente 20 años, en 1993, se estrenó a nivel mundial la película “Parque Jurásico”. Esta cinta de ciencia ficción, dirigida por Steven Spielberg, trata sobre el colapso de un parque temático ubicado en una remota isla de Costa Rica, cuyas atracciones principales eran dinosaurios genéticamente reconstruidos. La cinta está basada en una novela del mismo nombre, escrita por Michael Crichton y publicada en 1990.

Personalmente me encanta la película, sin embargo, por trillado que suene, soy de la opinión que la novela es aún mucho mejor.

John Michael Crichton,
autor del libro “Parque Jurásico”.

El grueso de la novela se divide en siete secciones que el autor llama “iteraciones”. Justo al inicio de cada una de estas iteraciones viene un dibujo junto con una cita atribuida al Dr. Ian Malcolm, uno de los personaje centrales de la novela. Por ejemplo:


Ian Malcolm es un matemático, experto en teoría del caos. Durante el transcurso de la historia, Malcolm hace varias predicciones basadas en esta teoría sobre las consecuencias negativas que podrían ocurrir al momento de intentar controlar la naturaleza. Lamentablemente, dichas predicciones resultan ser acertadas.

La figura que se muestra al inicio de cada iteración es un fractal conocido como “curva de dragón” o “dragón de Heighway”. Gracias a su aparición en la novela de Crichton, también se le conoce hoy en día como “fractal de Parque Jurásico”. John Heighway, Bruce Banks y William Harter, físicos de la NASA, fueron los primeros en investigar sobre este fractal a mediados de los años sesenta.

En la novela, Malcolm utiliza las curvas de dragón como una manera de simular las acciones “caóticas” que sucederían dentro del parque. Las siguientes dos imágenes muestran las curvas de dragón de la cuarta y séptima iteración, respectivamente. En la segunda figura podemos ver que el fractal tiene una apariencia similar a lo que podría ser un dragón. De ahí es donde toma su nombre.



La teoría del caos en esencia establece que pequeñas variaciones en las condiciones iniciales de un sistema dinámico pueden implicar grandes diferencias en su comportamiento futuro. El ejemplo clásico es:  “el aleteo de las alas de una mariposa puede provocar un Tsunami al otro lado del mundo”. La curva de dragón no tiene realmente que ver con esto, ya que puede ser producida de manera totalmente predecible a través de un algoritmo. Sin embargo, eso no hace que este fractal sea menos interesante.

En las siguientes secciones veremos dos maneras de generar la curva de dragón.

Construyendo la curva de dragón con papel

Tomamos una hoja tamaño carta y cortamos una tira por la parte larga de la hoja. La tira puede ser de unos 2 o 3 centímetros de ancho.


Paso 1: Doblar la tira a la mitad, tomando el extremo izquierdo y doblando hacia la derecha. La tira queda dividida en dos partes iguales. Todos los dobleces en lo sucesivo se deben hacer en este mismo sentido.


Paso 2: Si desdoblamos la tira y nos aseguramos que el doblez quede en un ángulo recto, obtenemos la siguiente figura que es una curva de dragón de orden 1:


Paso 3: Volvemos a doblar la tira en dos como estaba al final del paso 1, y hacemos un nuevo doblez a la mitad, otra vez tomando el extremo izquierdo y doblando hacia la derecha. La tira queda dividida en cuatro partes iguales:


Paso 4: Al desdoblar la tira, cuidando que todos los dobleces queden como ángulos rectos, tenemos ahora una curva de dragón de orden 2:


Vale la pena notar que la misma figura del paso 2 aparece aquí dos veces. La segunda vez aparece rotada 90° del punto en donde termina la primera.

Paso 5: Volvemos a doblar la tira como estaba hasta el paso 3 y hacemos otro doblez a la mitad. La tira queda ahora dividida en ocho partes iguales:


Paso 6: Al desdoblar la tira tenemos un curva de dragón de orden 3:


Notar aquí también que la figura del paso 4 se repite dos veces. Igualmente, la segunda instancia aparece rotada 90°.

Paso 7: Nuevamente regresamos a los dobleces del paso 5, y hacemos otro doblez por la mitad. Ahora la tira queda dividida en dieciséis partes iguales:


Paso 8: Desdoblamos la tira por última vez y nos queda una curva de dragón de orden 4, la cual es simétrica al dibujo de la primera iteración de la novela de “Parque Jurásico”:


Ahora es la figura del paso 6 la que se repite dos veces. La segunda figura también está rotada en un ángulo recto.

Todo este proceso se puede repetir en teoría un número infinito de veces. Sin embargo existe un límite físico respecto al número de dobleces que se le pueden realizar a una tira de papel. La buena noticia es que tenemos menos límites al momento de programar nuestra computadora.

Programando la curva del dragón en Python

Podemos usar gráficas de tortuga para dibujar la curva del dragón. Hay varias formas de realizar la implementación, pero una manera sencilla de hacerlo es calcular primero todos los giros que tiene que hacer la tortuga antes de comenzar a dibujar.

El algoritmo consiste en producir una cadena de letras I y D, donde I representa un giro de 90° a la izquierda y D un giro de 90° a la derecha. El pseudocódigo del algoritmo recursivo quedaría así:
  • Para una curva de orden 0, el resultado es una cadena vacía, ya que no se requiere hacer giro alguno.
  • Para una curva de cualquier otro orden n, donde n > 0:
    • Sea c la cadena de la curva de dragón de orden n – 1.
    • Sea r la cadena en reversa de c.
    • Sea i la cadena formada por los elementos de r, pero invirtiendo cada I por D y cada D por I.
    • El resultado consiste en concatenar los siguientes tres elementos: c, I, i.
La traducción directa a Python 3.x se muestra a continuación. Por simplicidad se usan listas de caracteres para representar las diversas cadenas que aparecen en el pseudocódigo en lugar de utilizar strings.
def curva(n):
    """Devuelve una lista de caracteres con los giros
       requeridos para dibujar la curva de dragón de orden
       n. La letra 'I' significa girar a la izquierda, 
       mientras que la letra 'D' significa girar a la 
       derecha.
    """
    if n == 0:
        return []
    else:
        c = curva(n - 1)
        r = c[::-1]
        i = ['I' if g == 'D' else 'D' for g in r]
        return c + ['I'] + i
El siguiente código usa la función curva() para mostrar los giros requeridos con el fin de dibujar las curvas de dragón de órdenes 0 al 5:
for i in range(6):
    print('orden {0}: {1}'.format(i, ''.join(curva(i))))
La salida sería:
orden 0:
orden 1: I
orden 2: IID
orden 3: IIDIIDD
orden 4: IIDIIDDIIIDDIDD
orden 5: IIDIIDDIIIDDIDDIIIDIIDDDIIDDIDD
Una vez que tenemos los giros necesarios para la curva de dragón resulta muy directo el mecanismo para realizar el dibujo usando gráficas de tortuga:
  • Mover la tortuga hacia adelante x pixeles.
  • Por cada elemento g en la lista de giros de la curva de dragón de orden n, hacer lo siguiente:
    • Si g es I, girar la tortuga 90° a la izquierda.  
    • Si g es D, girar la tortuga 90° a la derecha.
    • Mover la tortuga hacia adelante x pixeles.
El código correspondiente en Python queda así:
from turtle import *

def dragon(n, x):
    """Dibuja una curva de dragón de orden n en donde
       cada segmento de la curva es de longitud x.
    """
    fd(x)
    for g in curva(n):
        if g == 'I':
            lt(90)
        else: # g == 'D'
            rt(90)
        fd(x)
Agregando un poco de código para inicializar la tortuga de manera conveniente, ya tenemos un programa que dibuja una curva de dragón de orden 8:
hideturtle()       
pensize(3)         
color('SteelBlue')
speed('fastest')   
setheading(180)    
dragon(8, 15)      
done()
Se puede observar que el dibujo resultante es idéntico al que aparece como cuarta iteración de la novela de Crichton.

dragon(8, 15)

Algunos otros ejemplos variando los valores de n (orden) y x (longitud) de la curva:

dragon(0, 200)

dragon(4, 50)

dragon(11, 5)

dragon(16, 1)

En la última figura el tamaño de la pluma utilizada (establecida con la función pensize()) es 1 en lugar de 3.


Referencias

4 de julio de 2013

La sección de oro

Introducción

“Donald en el País de las Matemágicas” (Walt Disney Productions, 1959) es un corto animado que dura 27 minutos y muestra de manera entretenida el papel que juegan las matemáticas en el mundo real. En México, dicho corto se puede encontrar en el DVD titulado “Fábulas de Disney, Volumen tres”.


El corto completo también está disponible en YouTube con doblaje en español latinoamericano. Una de las partes que más me gusta es la referente a la explicación de la sección de oro (conocida también como número áureo, razón áurea, razón dorada, media áurea, proporción áurea y divina proporción, entre otros). Invito al lector a que vea el video; estoy seguro que le resultará muy interesante. A mi me gusta ponérselos a mis alumnos antes de introducir el tema de gráficas de tortuga.



Calculando \(\varphi\) de manera algebraica

La sección de oro, representada por la letra griega \(\varphi\) (fi), es un número irracional (esto quiere decir que no se puede escribir como una fracción). Se obtiene dividiendo una línea en dos partes, una larga y otra corta, de manera que la parte larga dividida entre la corta es igual al total de toda la línea dividido entre la parte larga. Gráficamente se puede expresar de la siguiente forma:


Toda la línea mide una unidad. Las dos partes de la línea son (x) y (1 - x), que corresponden a la parte larga y corta respectivamente. Por tanto, la sección de oro se puede expresar usando la ecuación (1): \begin{equation} \varphi = \frac{1}{x} = \frac{x}{1-x} \tag{1} \end{equation} \begin{equation} 1(1 - x) = x(x) \end{equation} \begin{equation} 1 - x = x ^ 2 \end{equation} \begin{equation} x ^ 2 + x - 1 = 0 \tag{2} \end{equation} Usando simples despejes algebraicos, la razón de la ecuación (1) se puede transformar hasta llegar a (2). Para encontrar el valor de x a partir de la ecuación cuadrática (3) se puede usar la fórmula general (4) (conocida también coloquialmente en México como “la fórmula del chicharronero”, ya que hasta el señor que vende chicharrones la conoce). \begin{equation} a x ^ 2 + b x + c = 0 \tag{3} \end{equation} \begin{equation} x = \frac{-b + \sqrt{b^2 - 4ac}}{2a} \tag{4} \end{equation} A partir de (2), tenemos que a = 1, b = 1 y c = –1. Haciendo las sustituciones correspondientes en (4), se puede determinar finalmente en (5) el valor de \(\varphi\) según su definición en (1). \begin{equation} x = \frac{-(1) + \sqrt{(1)^2 - 4(1)(-1)}}{2(1)} \end{equation} \begin{equation} x = \frac{-1 + \sqrt{1 + 4}}{2} \end{equation} \begin{equation} x = \frac{\sqrt{5}-1}{2} \end{equation} \begin{equation} \varphi = \frac{1}{x} = \frac{2}{\sqrt{5}-1} = 1.61803398874989484820\ldots \tag{5} \end{equation}

Usando números de Fibonacci para calcular \(\varphi\)

Otra forma de calcular la sección de oro es utilizando los números de Fibonacci. Se puede obtener una aproximación de \(\varphi\) al dividir fib(n) entre fib(n-1), para n > 1. Entre mayor sea el valor de n, mejor será la aproximación de \(\varphi\). Poniendo esto en código de Python para n = 100 tenemos:
def fib(n):
    a = 1
    b = 0
    for i in range(n):
        a, b = b, a + b
    return b

def fi(n):
    return fib(n) / fib(n - 1)

print('\N{Mathematical Italic Small Phi} =', fi(100))
NOTA: Todo el código de Python presentado en este artículo requiere Python 3.x.

La salida producida es:
𝜑 = 1.618033988749895
El resultado es exactamente el esperado hasta el decimocuarto dígito después del punto decimal.

Usando \(\varphi\) para calcular los números de Fibonacci

También es posible calcular el elemento n-ésimo de la sucesión de Fibonacci utilizando la razón áurea \(\varphi\) a partir de la siguiente fórmula:
\begin{equation} \textrm{fib} (n) = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}} \end{equation} Podemos verificar que dicha fórmula produce los valores correctos corriendo el siguiente programa:
from math import sqrt

fi = 1.618033988749895

def fib(n):
    return (fi ** n - (1 - fi) ** n) / sqrt(5)

for i in range(16):
    print("fib({0}) = {1}".format(i, fib(i)))
Esta es la salida correspondiente:
fib(0) = 0.0
fib(1) = 1.0
fib(2) = 1.0
fib(3) = 2.0
fib(4) = 3.0000000000000004
fib(5) = 5.000000000000001
fib(6) = 8.000000000000002
fib(7) = 13.000000000000002
fib(8) = 21.000000000000004
fib(9) = 34.00000000000001
fib(10) = 55.000000000000014
fib(11) = 89.00000000000003
fib(12) = 144.00000000000006
fib(13) = 233.00000000000006
fib(14) = 377.00000000000017
fib(15) = 610.0000000000003
Podemos notar algunos pequeños errores asociados a la perdida de precisión en los dígitos posteriores al punto decimal. Esto es inherente al uso de números de punto flotante. Aún así, los resultados son bastante próximos a los valores esperados.

La espiral dorada

La espiral dorada (también conocida como espiral áurea) es una espiral logarítmica cuyo factor de crecimiento es \(\varphi\). Resulta relativamente sencillo dibujar dicha espiral usando Python y gráficas de tortuga. El truco consiste en saber cómo dibujar un arco. El módulo turtle de Python tiene una función llamada circle() que recibe dos argumentos (realmente son tres, pero podemos ignorar el tercer argumento): un radio R (en pixeles) y un ángulo θ (en grados). La siguiente imagen muestra la manera de interpretar los argumentos de la función circle():


Si θ = 360 (o si dicho argumento se omite), entonces la función circle() dibuja un círculo completo con radio R.

La espiral dorada está conformada por n arcos dibujados de forma consecutiva, cada arco de 90° y con un radio que se multiplica por \(\varphi\) en cada iteración. En este caso, decimos que n es el orden de la espiral. El siguiente código muestra como combinar todos estos elementos:
from turtle import *      # Importar las funciones de gráficas 
                          # de tortuga.

fi = 1.618033988749895    # Definir 𝜑 (sección de oro).

def espiral(n):
    radio = 10            # Definir radio inicial del primer 
                          # arco.    
    for i in range(n):    # Repetir n veces.
        circle(radio, 90) # Dibujar el arco de un cierto radio 
                          # y 90 grados.
        radio *= fi       # Aumentar radio por el factor 𝜑.

hideturtle()       # Esconder la tortuga.
color('SteelBlue') # Establecer color de la pluma: azul 
                   # metálico.
pensize(20)        # Establecer tamaño de la pluma: 20 pixeles.
speed('fastest')   # Establecer velocidad de tortuga: máxima.
setheading(270)    # Apuntar la tortuga hacia el sur.
espiral(8)         # Dibujar espiral de orden 8.
done()             # Evitar que la ventana se cierre 
                   # inmediatamente.
Al ejecutar el programa obtenemos la siguiente figura:

Espiral dorada de orden 8.
Podemos producir una imagen más interesante si dibujamos los cuadrados que contienen a cada uno de los arcos. Al hacer esto podemos observar que la espiral dorada está contenida dentro de una serie (conceptualmente infinita) de rectángulos dorados.
from turtle import *

fi = 1.618033988749895

def cuadro(longitud):
    """Dibuja un cuadrado relleno cuyos lados son de tamaño
       'longitud'.
    """
    begin_fill()
    for i in range(4):
        fd(longitud)
        lt(90)
    end_fill()

def rectangulo_dorado(n, longitud):
    """Dibuja un rectángulo dorado compuesto de 'n'
       cuadrados. El primer cuadrado tiene sus lados de
       tamaño 'longitud'.
    """
    for i in range(n):
        cuadro(longitud)

        # Mover la tortuga a la esquina contraria y girarla
        # 90 grados a la izquierda.
        fd(longitud)
        lt(90)
        fd(longitud)

        longitud *= fi

def espiral_dorada(n, radio):
    """Dibuja una espiral dorada compuesta de 'n' arcos. El
       primer arco tiene un radio de tamaño 'radio'.
    """
    for i in range(n):
        circle(radio, 90)
        radio *= fi

def espiral(n, radio):
    """Dibuja una espiral dorada de orden 'n' sobre el
       rectángulo dorado que lo alberga.
       El primer arco/cuadro tiene un radio/lado de tamaño
       'radio'.
    """

    color('White')
    fillcolor('SteelBlue')
    pensize(1)
    rectangulo_dorado(n, radio)

    # Regresa la tortuga al centro de la pantalla pero sin
    # dibujar por su paso.
    penup()
    home()
    pendown()

    color('Gold')
    pensize(4)
    espiral_dorada(n, radio)

hideturtle()
speed('slow')
espiral(11, 2)
done()
El código anterior es más elaborado pero el resultado bien vale la pena:

Espiral dorada de orden 11 sobre su
rectángulo dorado correspondiente.

28 de junio de 2013

Los números de Fibonacci

Introducción

La sucesión de los números de Fibonacci1 aparece a menudo en las clases de programación, ya que puede ser utilizada para enseñar dos temas muy importantes: ciclos y recursión.

Lo que ahora conocemos como la sucesión2 de Fibonacci ya había sido estudiada desde tiempos remotos por matemáticos de la India. Sin embargo, fue hasta el año 1202 que el matemático italiano Leonardo de Pisa, también conocido como Fibonacci, describió esta sucesión al mundo occidental en su libro titulado Liber Abaci (El libro del cálculo). La sucesión de Fibonacci tiene aplicaciones en matemáticas y ciencia de la computación. Aparece también con frecuencia en la naturaleza, por ejemplo en la disposición de las hojas en el tallo de una planta o el cono de un pino.

Leonardo de Pisa, alias Fibonacci
Leonardo de Pisa,
alias Fibonacci

La sucesión de Fibonacci fue explicada por Leonardo de Pisa de una manera un tanto pintoresca. Supongamos que tenemos una pareja (un macho y una hembra) de conejos recién nacidos. Estos conejos alcanzan su madurez sexual a los dos meses de edad y a partir de ese momento, en cada mes sucesivo, pueden reproducirse dando a luz a una nueva pareja (también un macho y una hembra). Suponiendo, así mismo, que los conejos nunca se mueren y que no tienen problemas con el incesto entre hermanos, podemos calcular el número de parejas de conejos que se van acumulando a través de los meses:

La sucesión de Fibonacci a partir de una pareja de conejos.

En los meses 1 y 2 solo hay una pareja de conejos. Para el mes 3 la pareja ya tuvo a su primer par de hijos, por tanto hay dos parejas en total. Para el mes 4, la pareja original vuelve a tener otro par de hijos, pero la pareja que nació en el mes 3 todavía no puede tener hijos. Esto quiere decir que hay un total de tres parejas en el mes 4. Para el mes 5, la pareja original vuelve a tener un nuevo par, y la pareja que nació en el mes 3 ya tiene también su primer par. El mes 5 termina con cinco parejas a partir de las tres que ya había más las dos que nacieron ese mes.

Podemos observar que para calcular el número total de parejas de conejos en un cierto mes n basta con sumar las parejas que ya existen (el total del mes anterior a n) más las nuevas parejas que nacerán durante ese mes (el total de parejas que había dos meses antes de n, ya que todas esas parejas están sexualmente maduras para el mes n).

A partir de lo que hemos planteado podemos definir a la sucesión de Fibonacci como una sucesión infinita de números enteros cuyos primeros dos elementos son 0 y 1 (aunque la figura de arriba no lo muestra, está implícito que en el mes 0 hay cero parejas de conejos), y todos los elementos posteriores son la suma de los dos anteriores:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
En términos matemáticos, tenemos la siguiente relación de recurrencia: $$ \textrm{fib}(n) = \left\{\begin{matrix} 0 & \textrm{si} \; n = 0 \\ 1 & \textrm{si} \; n = 1\\ \textrm{fib}(n - 1) + \textrm{fib}(n - 2) & \textrm{si} \; n > 1 \end{matrix}\right. $$

Implementación recursiva

La ecuación de la sección anterior puede traducirse directamente a Python (simplificando un poco las condiciones) para obtener una función recursiva:
# Fibonacci version recursiva
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
Se puede probar la función desde el shell de Python:
>>> fib(0)
0
>>> fib(1)
1
>>> fib(5)
5
>>> [fib(i) for i in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
Aunque elegante, la definición anterior es extremadamente ineficiente. Por ejemplo, la siguiente figura muestra todas las operaciones que se requieren para calcular el elemento de la sucesión cuando n=5. Los rectángulos representan llamadas recursivas a la función fib, mientras que los círculos representan los resultados devueltos del caso base.


En este caso, para calcular fib(5), se requiere primero calcular fib(4) y fib(3). Pero para calcular fib(4) se requiere calcular también fib(3) (además de fib(2)). Aquí es donde se puede ver el origen de la ineficiencia: varias operaciones se realizan múltiples veces. Del árbol de la figura anterior podemos ver que:
  • fib(5) se realiza en total 1 vez.
  • fib(4) se realiza en total 1 vez.
  • fib(3) se realiza en total 2 veces.
  • fib(2) se realiza en total 3 veces.
  • fib(1) se realiza en total 5 veces.
Observando el total de veces que se realiza cada llamada a fib para un cierto valor, no debe resultar muy sorprendente notar que la sucesión de Fibonacci también aparece ahí.

Si el número que se desea obtener de la sucesión es relativamente grande
(n > 30), el tiempo que tarda en terminar la función puede ser considerable. El lector puede intentar calcular fib(35) para poderse dar una idea.

Memoización

Para corregir el problema mencionado anteriormente podemos recurrir a una técnica de optimización conocida como memoización (no confundir con memorización), la cual consiste en evitar que las llamadas a una función repitan los cálculos asociados a argumentos previamente procesados. La manera de implementar esta técnica es bastante sencilla usando un diccionario inicialmente vacío. Cuando una función f es invocada con un argumento x, se revisa si x existe como llave en el diccionario. En caso afirmativo, la función termina inmediatamente devolviendo el valor del diccionario asociado a x. En caso negativo, se calcula y devuelve de manera normal el resultado de f(x), pero antes de terminar la función se guarda dicho resultado en el diccionario asociándolo a la llave x. Con esto logramos que para cada valor de x solo se calcule f(x) a lo mucho una vez.

El beneficio de la técnica de memoización es lograr una mejora en el tiempo de ejecución de una función. El principal inconveniente es que requiere utilizar más memoria (para guardar todos los resultados que se vayan calculando).

Vale la pena memoizar una función f siempre y cuando se cumplen las tres siguientes condiciones:
  • f es referencialmente transparente. Esto significa, para fines de nuestra discusión, que f siempre devuelve exactamente el mismo resultado si se invoca con el mismo argumento de entrada.
  • El tiempo de acceso al diccionario debe ser perceptiblemente menor al tiempo de ejecución de f.
  • f debe ser invocada en nuestro programa de manera bastante frecuente con los mismos argumentos.
Nuestra implementación recursiva de la sucesión de Fibonacci cumple con las tres condiciones.

Este es el código de la función fib de la sección anterior modificado para incluir memoización tal como se describió arriba:
# Fibonacci version recursiva con memoizacion
cache = {0: 0, 1: 1}
def fib(n):
    if n not in cache:
        cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]
Como se puede observar, se añadió la variable global cache, a la cual se le asigna un diccionario con las llaves 0 y 1, y cuyos valores asociados son también 0 y 1 respectivamente (los primeros dos valores de la sucesión). Con ello se puede eliminar el código que de manera explícita checa los casos base de la definición recursiva. La variable cache tiene que ser global3 dado que deseamos que el diccionario preserve sus valores entre dos o más invocaciones de fib.

El lector ahora puede verificar que fib devuelve un resultado prácticamente de manera instantánea:
>>> fib(35)
9227465
>>> fib(100)
354224848179261915075

Implementación iterativa

Tal como vimos desde la sección de introducción, para poder calcular el elemento n de la sucesión de Fibonacci solo se requieren los dos elementos anteriores. A partir de los dos elementos iniciales podemos determinar cualquier elemento posterior en la sucesión usando un simple ciclo. En cada iteración del ciclo se deben actualizar un par de variables con el fin de que éstas siempre contengan los valores de los dos últimos elementos de la sucesión calculados hasta el momento.

El código quedaría así:
# Fibonacci version iterativa
def fib(n):
    a = 1
    b = 0
    for i in range(n):
        a, b = b, a + b
    return b
La función define dos variables locales: a y b. La variable b representa el último elemento de la sucesión calculado hasta el momento, mientras que a representa el penúltimo. Si b se inicializa con 0, ¿con qué valor se debe inicializar a dado que debe ser un elemento anterior al 0 en la sucesión? La respuesta es 1, ya que en la siguiente iteración el nuevo valor de b debe ser 1, y debe ser a su vez el resultado de sumar los valores previos de a y b (1 y 0, respectivamente).

El ciclo for se repite n veces gracias a la función range(). El cuerpo del ciclo se encarga de actualizar las variables a y b con el fin de tener un nuevo último y un nuevo penúltimo elemento al final de cada iteración. Por ejemplo, al inicio de la sexta iteración a=3 y b=5. Al termino de esa iteración a debe tener el valor original de b, y b debe tener la suma de los valores originales de a y b. Es decir, a=5 y b=8. Esto se logra en Python con la instrucción
a, b = b, a + b
la cual se conoce como una “asignación paralela”. Ésta consiste en asignar de manera simultánea las variables del lado izquierdo del símbolo de asignación con los valores que están del lado derecho.

De forma un poco más general:
a, b, c, d = 1, 2, 3, 4
es equivalente a:
a = 1
b = 2
c = 3
d = 4
La ventaja de este tipo de instrucción es que podemos usar las mismas variables en ambos lados de la asignación sin preocuparnos por el orden en que serán actualizadas y sin tener que introducir variables temporales.

En nuestro caso, si no tuviéramos forma de hacer una asignación paralela, la instrucción del cuerpo del ciclo tendría que ser dividida en tres instrucciones además de requerir una variable temporal t:
t = b
b = a + b
a = t
Si no se introduce la variable temporal t la variable a terminaría con el mismo nuevo valor de b y no con el valor anterior de b.

Finalmente, una vez que el ciclo termina, la variable b contiene el elemento deseado y por tanto se devuelve usando la instrucción return.

Podemos probar nuestro código para valores chicos y grandes de n:
>>> fib(1)
1
>>> fib(100)
354224848179261915075
>>> [fib(i) for i in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
Nuestra solución iterativa es computacionalmente mucho más eficiente que la primera versión recursiva, a tal grado que ni siquiera hace falta recurrir a la técnica de memoización descrita anteriormente para obtener un buen desempeño.

Notas:

1 Mucha de la información aquí presentada fue tomada del artículo Fibonacci number de Wikipedia.

2 Frecuentemente a la “sucesión de Fibonacci” se le ha llamado erróneamente “serie de Fibonacci”. “Sucesiones” y “series” pueden parecer la misma cosa, pero en realidad una serie es la suma de una sucesión. Por ejemplo, dada la sucesión: {1, 2, 3, 4}, la serie correspondiente a ésta sería: 1+2+3+4=10.

3 El principal problema de que la variable cache sea global es que se puede leer y modificar, de manera intencional o accidental, desde cualquier otra parte del programa. Por eso es que procuramos desalentar en nuestros alumnos el uso de variables globales. Pero entonces, ¿qué alternativas tenemos? Una opción consiste en definir una clase en la que se utilice una variable de instancia para encapsular al diccionario que se requiere en el proceso de memoización. Otra opción es usar cerraduras léxicas (lexical closures en inglés) para definir un decorador que memoice funciones de manera genérica. Lamentablemente, ambas opciones hacen que este ejercicio sea mucho más complejo, así que, por simplicidad y por el momento, mejor nos quedamos con una variable global.