29 de diciembre de 2016

Errare humanum est


Durante el semestre académico que recién terminó (agosto-diciembre de 2016) tuve la oportunidad de dar el curso de Fundamentos de programación. Esta materia la he impartido pocas veces, sin embargo los aprendizajes que me llevo como educador siempre son muy valiosos. Es muy interesante trabajar con alumnos que recién comienzan su carrera profesional y que también están iniciando su inmersión al mundo de la programación de computadoras.

Grupo 4 de la materia
Fundamentos de programación del ITESM CEM,
semestre agosto-diciembre de 2016.

Cuando se comienza a aprender algo nuevo es de esperarse que se cometerán errores. Como dijo alguna vez el renombrado escritor irlandés Bram Stoker:
Aprendemos de los fracasos, no de los éxitos.
Errar es humano, y en esta entrada del blog de EduPython comentaré, a partir de mi experiencia, sobre los cuatro errores más frecuentes que cometen los alumnos cuando están aprendiendo a programar usando el lenguaje Python, así como algunas recomendaciones de cómo evitarlos.

Paréntesis mal balanceados

Este es el error más común que he observado al inicio del curso. Se tiene una instrucción la cual requiere del uso de paréntesis anidados, por ejemplo:
print(sqrt(x ** 2 + y ** 2)
En el código anterior se puede observar que está faltando cerrar un paréntesis al final. Al intentar ejecutarlo, el intérprete de Python marca usualmente un error de sintaxis. La cuestión es que dicho error se marca en la siguiente línea, no en la línea donde está realmente el problema.

Aquí recomiendo dos cosas:
  1. Acostumbrar a los alumnos a buscar los errores de sintaxis no solo en la línea donde se señala el problema, sino también una o varias líneas antes.
  2. Enseñar a los alumnos a comprender y utilizar las pistas visuales que brindan los editores al momento de cerrar paréntesis, llaves y corchetes. En el caso del IDLE, cuando se cierra alguno de estos elementos (paréntesis, llaves y corchetes) se ensombrece toda la expresión desde el elemento correspondiente de apertura. En la siguiente imagen puede uno notar que falta cerrar el paréntesis de la función print():

    IDLE

    Otros editores, como Spyder, parpadean o usan un color de fondo diferente para destacar los paréntesis que se están abriendo y/o cerrando: 

  3. Spyder

Indentación incorrecta

En Python la indentación sirve para indicar que un grupo de instrucciones conforman un mismo bloque. Este efecto se logra con llaves ({ y }) o las palabras reservadas begin y end en otros lenguajes.

La indentación obligatoria de Python es algo positivo, ya que obliga a los alumnos a adquirir prácticas de escritura de código legible. Normalmente los editores para código de Python ayudan a producir programas con la indentación correcta sin requerir mucho esfuerzo. Sin embargo se pueden producir errores cuando se copia y pega código de otro lado o cuando se insertan o borran espacios de manera no intencional, por ejemplo:

Programa con error de indentación

En el programa de arriba, la línea 5 está indentada con un espacio más hacia la derecha con respecto a las otras líneas del mismo bloque (las líneas 3 y 8). El editor, Spyder en este caso, nos echa la mano al señalar que hay un problema en el programa colocando un signo de admiración en el margen izquierdo en la línea infractora.

Mis recomendaciones para evitar este error:
  1. Enfatizar a los alumnos sobre la importancia que tiene la indentación y la correcta alineación de las instrucciones para establecer la estructura lógica de sus programas. Si van a copiar y pegar código, se deben asegurar que todas las instrucciones queden alineadas en el lugar debido.
  2. Nunca mezclar en un mismo programa caracteres de espacio (código ASCII 32) con caracteres de tabulador (código ASCII 9). Esto no debe ser problema en la mayoría de los editores que soportan Python. Cuando el usuario presiona la tecla «Tab», usualmente los editores insertan cuatro espacios en lugar de insertar el carácter de tabulador. Sin embargo este comportamiento se puede cambiar en la configuración de la mayoría de los editores. Yo recomiendo no alterar la configuración en este sentido ya que no es fácil distinguir a primera vista un tabulador de una secuencia de varios espacios.

Uso incorrecto de return

Las funciones son uno de los mecanismos de abstracción más poderosos que tenemos disponibles en Python y en casi cualquier otro lenguaje de programación. Yo generalmente cubro este tema desde muy temprano en el curso de Fundamentos de programación. Cuando los alumnos comienzan a escribir sus propias funciones el principal error que observo es el uso incorrecto de la instrucción return. Los errores caen en alguno de los siguientes dos casos:
  • return inexistente. Esto sucede cuando una función implementa correctamente un cierto algoritmo, pero carece de la instrucción return necesaria para devolver el resultado correspondiente. Por ejemplo, la siguiente función cuenta la cantidad de números negativos contenidos en una lista:
    def cuenta_negativos(a):
        resultado = 0
        for x in a:
            if x < 0:
                resultado += 1
    
    En Python todas las funciones siempre devuelven un valor. Por omisión devuelven None, a menos que explícitamente se indique otro valor dentro de una instrucción return. En el ejemplo anterior no hay un return explícito, así que la función siempre devuelve None. Por tanto, la forma correcta de escribir cuenta_negativos es:
    def cuenta_negativos(a):
        resultado = 0
        for x in a:
            if x < 0:
                resultado += 1
        return resultado
    
    Una variación de este problema es cuando una función tiene varias condiciones que utilizan instrucciones return pero no son exhaustivas. Por ejemplo, analicemos la siguiente función:
    def positivo_o_negativo(x):
        if x < 0:
            return 'negativo'
        if x > 0:
            return 'positivo'
    
    Esta función devuelve las cadenas 'negativo' o 'positivo' si el parámetro x es menor o mayor a cero, respectivamente. Sin embargo, ¿qué pasa si x es igual a cero? Tenemos aquí un código en donde las condiciones no son exhaustivas produciendo un bug muy sutil. Al no cumplirse alguna de las dos condiciones la función termina sin ejecutar un return explícito, por tanto devuelve None. Hay varias formas de corregir el problema. Una de ellas consiste en suponer que si un número no es negativo debe ser entonces positivo. Agregando una cláusula else al if tenemos:
    def positivo_o_negativo(x):
        if x < 0:
            return 'negativo'
        else:
            return 'positivo'
    
    Con este cambio la función jamás devolverá None siempre que x sea un valor numérico.
  • return fuera de lugar. En este caso el error consiste en incluir la instrucción return dentro de la función pero en un lugar que hace que el flujo de ejecución termine de manera prematura. Continuando con el ejemplo de la función cuenta_negativos, a menudo veo que algunos alumnos escriben erróneamente el código así:
    def cuenta_negativos(a):
        resultado = 0
        for x in a:
            if x < 0:
                resultado += 1
                return resultado
    
    La instrucción return se ejecutará cuando la condición del if resulte verdadera. El return provoca que la función termine inmediatamente, por lo que las iteraciones pendientes del ciclo for ya no se ejecutarán. En otras palabras, la función devuelve el valor 1 en cuanto encuentra la primer número negativo en la lista a. Si a no tiene números negativos el for concluye de manera normal, y como no hay posteriormente un return explícito entonces devuelve None. Una variación, igualmente incorrecta, es ésta:
    def cuenta_negativos(a):
        resultado = 0
        for x in a:
            if x < 0:
                resultado += 1
            return resultado
    
    Aquí el return es parte del bloque del for. Esto quiere decir que la función siempre termina en la primera iteración del ciclo, devolviendo uno si el primer número de a es negativo, o cero en caso contrario. Como caso especial, si la lista a está vacía devuelve None, ya que el ciclo for termina de manera normal y después no hay return explícito. Podemos observar que la única diferencia sintáctica entre la versión correcta y los dos códigos erróneos es el nivel de indentación que tiene la instrucción return.
Para evitar errores asociados al uso incorrecto del return recomiendo:
  1. Resaltarle a los alumnos la manera en que trabaja la instrucción return. Es muy importante que entiendan que cuando se ejecuta esta instrucción la función termina de manera inmediata sin importar que estuviera en medio de un ciclo o que existieran otras instrucciones posteriores pendientes a ser ejecutadas. Si una función está devolviendo None seguramente está haciendo falta un return explícito en algún lado.
  2. Promover que los alumnos realicen pruebas de escritorio de sus funciones, utilizando diferentes valores de entrada y procurando revisar de manera exhaustiva los casos normales y extremos.

Variables fuera de alcance

Para definir una variable en Python basta con asignarle un valor inicial. Si esta asignación ocurre dentro de una función, la variable en cuestión es local a dicha función y eso significa que no se puede acceder a ella desde otras funciones. Las variables locales son algo bueno ya que tienen un alcance y tiempo de vida limitado a una región usualmente reducida de código. Esto conlleva a que una función sea, en principio, más fácil de entender y modificar de manera aislada. Sin embargo, es bastante común que algunos principiantes intenten acceder a variables que están fuera de alcance (definidas en otra función),  por ejemplo:
from math import sqrt

def hipotenusa():
    return sqrt(a ** 2 + b ** 2)

def principal():
    a = float(input('Primer cateto: '))
    b = float(input('Segundo cateto: '))
    c = hipotenusa()
    print('La hipotenusa es', c)
La función principal() define tres variables locales: a, b y c. La función hipotenusa() intenta usar dos de esas variables (a y b) produciendo un error ya que no están visibles en ese contexto. La forma más sencilla de corregir este problema es enviar como parámetros aquellos datos que deseemos compartir:
from math import sqrt

def hipotenusa(a, b):
    return sqrt(a ** 2 + b ** 2)

def principal():
    a = float(input('Primer cateto: '))
    b = float(input('Segundo cateto: '))
    c = hipotenusa(a, b)
    print('La hipotenusa es', c)
Los parámetros a y b de la función hipotenusa() reciben una copia de los valores de las variables locales a y b de la función principal(). Aquí utilizamos los mismos nombres (a y b) en ambas funciones por mera conveniencia, pero no tiene que ser así.

Mi recomendación para evitar problemas con variables fuera de alcance consiste en hacerles entender a los estudiantes cuáles son las implicaciones de que una variable sea local a una función. Así mismo, es necesario explicarles que cuando un programa requiere compartir información entre dos funciones se pueden utilizar parámetros para enviar datos de entrada y la instrucción return para devolver datos de salida. Esta es generalmente la manera más adecuada de diseñar un programa pues lo hace más legible y facilita su mantenimiento. Alternativamente, es posible usar variables globales o incluso definir funciones más extensas (por ejemplo unir hipotenusa() y principal() en una sola función). Sin embargo estas opciones provocan normalmente que el código sea más complicado de entender y modificar, por lo que conviene disuadir a los estudiantes de hacer esto, especialmente en las primeras etapas de un curso introductorio de programación.

Conclusión

En mi experiencia, los problemas más usuales que tienen los estudiantes al comenzar a programar en Python se pueden resumir en:
  • Falta de comprensión clara sobre algunos conceptos fundamentales (indentación, instrucción return, alcance de las variables).
  • Falta de conocimiento de cómo usar las herramientas disponibles (principalmente el editor).
Los alumnos aprenden a evitar caer en ciertas trampas al momento en que entienden bien los conceptos y obtienen más experiencia usando las herramientas apropiadas.

Amigo lector, si eres maestro y enseñas a programar, ¿qué tipo de errores has visto que tus alumnos cometen frecuentemente? ¿Cómo le haces para evitar que los cometan? Usa la sección de comentarios para compartir tus experiencias. Gracias de antemano.

14 de octubre de 2016

Aprendizaje vivencial con juegos de estrategia

En la semana del 26 al 30 de septiembre de 2016 se llevó a cabo en el Tecnológico de Monterrey la segunda edición de un evento denominado “Semana i”. Una vez por año, durante una semana completa, se suspenden todas las clases de nivel licenciatura en la institución con el fin de que los estudiantes afronten y resuelvan un reto de tiempo completo:
El aprendizaje basado en retos se fundamenta en el aprendizaje vivencial, enfoque pedagógico que forma parte del Modelo Educativo Tec21 con el que se involucra activamente al estudiante en una situación o problemática real, relevante, y de vinculación con el entorno. Semana i implica la definición de un reto, su análisis y resolución y la implementación y evaluación de una solución. Así, se desarrollan o fortalecen las competencias profesionales y personales de los alumnos1.
En la Semana i 2016 más de 50 mil alumnos y 3 mil profesores participaron en 1,400 proyectos que se llevaron a cabo en 26 campus del Tecnológico de Monterrey. Cada alumno tuvo la opción de llevar a cabo su reto en su propio campus, en otro campus, en México o incluso en el extranjero.


Reto IA con juegos de estrategia

Para la Semana i 2016 el profesor Roberto Martínez Román, colega de mi departamento, y yo diseñamos durante varios meses un reto titulado “Introducción a la inteligencia artificial orientada al diseño y programación de juegos de estrategia”. La actividad estuvo dirigido a alumnos de segundo a quinto semestre de las carreras de Ingeniero en Sistemas Computacionales (ISC) e Ingeniero en Sistemas Digitales y Robótica (ISDR). El objetivo principal del reto consistía en que los estudiantes diseñaran y programaran en Python un jugador autónomo inteligente que fuera capaz de competir en un torneo de juegos de estrategia contra los programas elaborados por sus demás compañeros.


El reto procuró fortalecer las siguientes competencias disciplinares y transversales:
  • Uso de TI para la solución efectiva de problemas
  • Pensamiento lógico y algorítmico
  • Reflexión ética
Se inscribieron 57 alumnos en total (todos del Campus Estado de México), con los que se conformaron 20 equipos compuestos de 2 o 3 integrantes cada uno. Los estudiantes tuvieron la libertad de formar sus equipos y nombrarlos a su gusto.

Alumnos y profesores en el último día del reto

A continuación realizo un recuento de todas las actividades que conformaron nuestro reto durante la Semana i 2016.

Arrancando el reto

Desde unos días antes de comenzar el reto creamos un grupo de Facebook para servirnos como principal medio de comunicación entre instructores y alumnos. Ahí estuvimos publicando anuncios y fotos durante toda la Semana i (e incluso un poco después).

Grupo de Facebook

A las nueve de la mañana del lunes 26 de septiembre dio inicio nuestro reto. Comenzamos explicando lo que planeábamos hacer, presentando la página web del reto, y dando un espacio para la conformación de los equipos de trabajo. También aprovechamos para hacer una breve introducción a los conceptos de “inteligencia artificial” y “prueba de Turing”.

Alan M. Turing, padre de la inteligencia artificial

Concurso de programación

El mismo día lunes tuvimos un concurso de programación con la intención de que los alumnos tuvieran la oportunidad de recordar un poco cómo programar con Python. Cabe mencionar que todos nuestros estudiantes ya habían trabajado con Python anteriormente, al menos durante el curso Fundamentos de programación que llevan en primer semestre, sin embargo la mayoría tenía varios semestres de no utilizarlo.


Antes del concurso invertimos una hora en un taller de preparación. Para el taller y el concurso utilizamos la plataforma de programación competitiva omegaUp.com, la cual permite crear competencias en línea de manera bastante sencilla. En el taller se utilizó el problema titulado “El mayor de dos” para que los equipos se familiarizaran con los mecanismos necesarios para resolver y subir problemas de programación usando Python.

El concurso tuvo una duración de tres horas. Cada equipo, sin importar el número de integrantes, podía utilizar hasta dos computadoras: una para programar y enviar las soluciones, y la otra para revisar la documentación. Los siete problemas del concurso fueron los siguientes:
  1. Bit de paridad (100 puntos)
  2. Calculando divisores (100 puntos)
  3. Buscando el mayor (100 puntos)
  4. Tabla de factoriales (100 puntos)
  5. Multiplicación binaria (200 puntos)
  6. Perímetro de asteriscos (200 puntos)
  7. Conociendo la moda (200 puntos)
El juez en línea se encargó de evaluar las soluciones que enviaron los equipos y de llevar la cuenta de los problemas resueltos, el tiempo transcurrido de cada envío y las penalizaciones aplicadas por envíos de soluciones incorrectas.  Al terminar el concurso teníamos una tabla con todos los equipos rankeados del primer al último lugar.

El concurso de programación

El primer equipo en resolver todos los problemas del concurso tardó solo 40 minutos. Al finalizar el concurso, trece equipos habían resuelto correctamente los siete problemas.

Framework Dagor para juegos de estrategia

El martes por la mañana les presentamos a los alumnos el framework Dagor2. Yo me encargué de diseñar y programar este framework con el fin de utilizarlo como herramienta central para este reto. Muchas de las ideas de Dagor fueron tomadas del sitio Gamesman elaborado por el profesor Dan Garcia de la Universidad de California en Berkeley. El software y la documentación de Dagor están disponibles en la página del reto. Dagor es software libre y se distribuye bajo la licencia GPLv3.

Dagor sirve para programar diversos tipos de jugadores que compiten entre sí para ganar un juego combinacional. En teoría de juegos, un juego combinacional tiene las siguientes características:
  • Siempre hay dos jugadores que toman turnos para tirar de manera alternada.
  • No hay elementos aleatorios como dados o cartas barajadas.
  • Ambos jugadores tienen información perfecta (no hay información oculta).
  • El juego es finito — debe terminar eventualmente.
  • Usualmente el último jugador en tirar gana.
Dagor es un módulo de Python que implementa el patrón de diseño conocido como método de la plantilla (Template Method). De manera muy general, para escribir el código de un jugador inteligente se requiere escribir una clase que implemente dos métodos:
  • tira: Este método se invoca automáticamente por el controlador del juego cuando le toca al código de mi jugador realizar su tiro.
  • heuristica: Este método lo implementamos para poder evaluar diversas posiciones durante el juego y decidir cuál nos conviene más al momento de realizar nuestro tiro.
El código fuente de Dagor muestra cómo implementar diversas categorías de jugadores para diferentes juegos. Hay tres categorías de jugadores:
  • Jugadores aleatorios: Realizan tiros válidos pero siempre al azar, salvo que puedan producir en un momento dado un tiro ganador.
  • Jugadores interactivos: Permiten que un usuario humano interactúe con el juego a través de la consola y verifican que los tiros seleccionados sean válidos.
  • Jugadores estratégicos: Implementan una o varias estrategias que les permitan jugar de manera inteligente.
El código de los jugadores es modular e intercambiable. Esto significa, por ejemplo, que podemos tener un juego en donde un jugador aleatorio compita con un jugador estratégico. O podemos tener un juego con dos jugadores aleatorios, o cualquier otra combinación que deseemos. Juegos como estos, siempre y cuando no involucren usuarios humanos, se llevan a cabo muy rápido (en unos cuantos segundos), de tal forma que podemos darnos el lujo de tener encuentros compuestos de muchos juegos entre los mismos dos jugadores.

El taller de Dagor

El juego de Orugas

Concretamente, el reto de nuestros alumnos fue implementar un jugador estratégico inteligente con Dagor para el juego de Orugas. A continuación se encuentran las reglas de este juego.


Las reglas

Piezas y tablero: Este juego se juega en un tablero rectangular de n renglones por m columnas, donde 4 ≤ n ≤ 10, 4 ≤ m ≤ 10. Inicialmente cada jugador ocupa una localidad del tablero (la cabeza de la oruga), determinada de manera aleatoria.

Para tirar: Cada jugador controla una oruga que crece rápidamente a partir de su cabeza. Durante el turno de un jugador, éste debe seleccionar una localidad contigua vacía en la que pueda crecer la cabeza de su oruga. La oruga puede crecer hacia la localidad de arriba, abajo, izquierda o derecha, mas no en diagonal. Es posible crecer saliéndose de una orilla del tablero y llegar a su correspondiente localidad opuesta.

Para ganar: Un jugador gana cuando su oponente ya no tenga una localidad donde crecer.

En el tablero, el primer jugador usa el símbolo B (blanco) como cabeza y b para el resto del cuerpo. El segundo jugador usa el símbolo N (negro) como cabeza y n para el resto del cuerpo.

Ejemplo

El siguiente es un tablero de Orugas de 4 renglones por 5 columnas, donde las posiciones iniciales de B y N son determinadas de manera aleatoria:
   0   1   2   3   4 
0    |   |   |   |   
  ---+---+---+---+---
1    |   |   |   |   
  ---+---+---+---+---
2    |   |   | N |   
  ---+---+---+---+---
3    | B |   |   |   
B tira primero. Tiene la opción de moverse a la izquierda, a la derecha y hacia arriba. También puede moverse hacia abajo, pero como está en la orilla se iría al extremo opuesto del tablero (renglón 0, columna 1). El jugador decide moverse hacia arriba al renglón 2, columna 1:
   0   1   2   3   4 
0    |   |   |   |   
  ---+---+---+---+---
1    |   |   |   |   
  ---+---+---+---+---
2    | B |   | N |   
  ---+---+---+---+---
3    | b |   |   |   
Ahora es el turno de N y se mueve hacia abajo al renglón 3, columna 3:
   0   1   2   3   4 
0    |   |   |   |   
  ---+---+---+---+---
1    |   |   |   |   
  ---+---+---+---+---
2    | B |   | n |   
  ---+---+---+---+---
3    | b |   | N |   
El juego continúa de esta forma, alternando los turnos entre B y N. Finalmente, en el tiro número 11, el jugador B se mueve al renglón 0, columna 2:
   0   1   2   3   4 
0  b | b | B |   |   
  ---+---+---+---+---
1  b | N | n |   |   
  ---+---+---+---+---
2  b | b | n | n |   
  ---+---+---+---+---
3    | b | n | n |   
En este momento el jugador N está completamente bloqueado por lo que no puede moverse a ningún lado. Por tanto N pierde en este turno y B resulta el ganador de este juego.

Desarrollando el jugador estratégico

El tiempo con el que contaron los alumnos para diseñar e implementar su jugador estratégico fue relativamente corto: desde el martes por la tarde hasta el jueves por la mañana.

En esencia, los alumnos tuvieron que programar una manera de evaluar qué tan buenas o malas eran ciertas posiciones en el juego y seleccionar la que les daba una mejor ventaja en cada tiro. Podían considerar, por ejemplo, qué tantas opciones de movimiento quedaban disponibles para su jugador después de un tiro, o qué tanto podían alejarse del jugador contrario con el fin de evitar un posible bloqueo más adelante. Hubo un equipo que diseñó una estrategia para cuando eran los segundos en tirar, y ésta consistía en imitar como espejo los tiros del contrario bajo el supuesto de que perdería primero por bloquearse solo. 

El miércoles antes del medio día los instructores realizamos una revisión del avance de cada equipo con el fin de verificar que estuvieran trabajando adecuadamente y resolver cualquier duda que pudieran tener. Ese mismo día por la tarde tuvimos un pre-torneo voluntario. Los equipos que quisieron pudieron competir entre sí para tener una idea más clara de qué tan efectivo estaba siendo su código. Seis de los veinte equipos participaron en este pre-torneo.

A todos los estudiantes se les permitió observar el pre-torneo, sin importar si su equipo estaba participando o no. Sin embargo, no se permitió que los equipos vieran el código de los demás, solo que vieran los resultados de los encuentros. El pre-torneo también sirvió para que los instructores nos percatáramos de las dificultadas logísticas que podrían llegar a presentarse al día siguiente en el torneo real. Nos dimos cuenta de que era necesario automatizar el proceso del torneo lo más que pudiéramos, de otra forma resultaría demasiado tardado.

El pre-torneo

Torneo de estrategias

El momento de la verdad por fin llegó. El jueves a las 11 de la mañana nos dimos cita en el salón de congresos del campus para llevar a cabo el torneo de estrategias. Los equipos debían habernos enviado por correo electrónico sus programas antes de la hora señalada. Cada programa se inspeccionó manualmente para verificar que fuera un módulo válido de Python y que no tuviera código malicioso o instrucciones prohibidas (acceso a Internet, manipulación de archivos, creación de procesos externos, etc.).

Se definió al inicio del torneo que cada encuentro consistiría de 100 juegos en un tablero de 7 renglones por 6 columnas, en donde cada tiro debería efectuarse en menos de 3 segundos. Durante el desarrollo del proyecto los alumnos desconocían el tamaño que tendría el tablero durante el torneo, solo sabían que los renglones y columnas estarían entre 4 y 10. El turno inicial de cada juego se iría alternando entre los dos jugadores, es decir, el primer jugador comenzaría 50 juegos del encuentro y el segundo jugador comenzaría los otros 50.

Inicialmente el programa de cada equipo se enfrentó al jugador aleatorio provisto por Dagor. A los equipos que ganaran al menos 60 de los 100 juegos de este encuentro se les brindarían 20 puntos extra sobre la calificación final del reto. De nuestros veinte equipos, solo dos no lograron cubrir este objetivo.

Cerca de la una de la tarde, y después de resolver varias dificultades técnicas, comenzamos el torneo de todos contra todos. En total hubo 190 encuentros (el número de combinaciones de 20 elementos tomando 2 a la vez) cada uno consistiendo de 100 juegos. Cada equipo recibió una cierta cantidad de puntos dependiendo del resultado de cada encuentro:
  • 3 puntos si ganó 51 juegos o más
  • 1 punto si ganó exactamente 50 juegos
  • 0 puntos si ganó 49 juegos o menos
El ranking de cada equipo en el torneo se determinó por el total de puntos obtenidos.

Se utilizaron múltiples scripts para automatizar todo el proceso del torneo, desde la ejecución de los encuentros hasta la contabilización de los resultados. La mitad (aproximadamente) de los encuentros se corrieron en la computadora portátil del profesor Roberto Martínez, y la otra mitad en mi computadora. Se utilizó una tercera computadora para ir proyectando a la audiencia los resultados conforme se iban obteniendo3.

Después de un poco más de dos horas, el torneo había terminado. El equipo que obtuvo el primer lugar investigó e implementó el algoritmo minimax con poda alfa-beta. Esto le permitió ser el vencedor en sus 19 encuentros, 7 de los cuales ganó 100 juegos a 0. El segundo lugar solo perdió un encuentro, y el tercer lugar perdió dos.

El torneo

Conferencia del Dr. Edgar Vallejo

El viernes estuvo mucho más relajado que los días anteriores. Ese día tuvimos el honor de contar con la presencia del Dr. Edgar Emmanuel Vallejo Clemente, profesor de nuestro departamento, quien nos presentó la conferencia titulada “Predicción de epidemias de Zika usando redes sociales y redes de contacto vectorial”. 

El profesor Edgar Vallejo en su conferencia

La plática fue sobre el proyecto que está siendo elaborado por el Dr. Vallejo y su alumno de doctorado Héctor Manuel Sánchez Castellanos. El objetivo es que a través de un modelo informático sea posible estimar el riesgo de infectarse con el virus del Zika. Este modelo permitirá que se haga una predicción temprana de brotes para que se tomen las medidas necesarias para el control de la enfermedad. El proyecto fue uno de los ganadores los Premios de Investigación en América Latina de Google 2016. El premio consistió en un apoyo económico para que los involucrados puedan llevar a cabo sus investigaciones.

Reflexión ética

El mismo día viernes les proyectamos a los alumnos la película “Ex Machina (2015)”.  Esta reciente cinta británica es una excelente película de ciencia ficción que trata sobre un joven programador que es seleccionado para ser el juez en una prueba de Turing, en donde deberá evaluar las cualidades humanas presentes en la I.A. de un asombroso robot humanoide con forma femenina. El filme permite abrir una discusión y reflexión muy interesante sobre los conflictos morales que podríamos afrontar al interactuar con máquinas que se comportan con una inteligencia similar a la de los seres humanos.

Alicia Vikander, Domhnall Gleeson y Oscar Isaac
protagonizan “Ex Machina (2015)”, A24 Films.

Al finalizar la película, les pedimos a los alumnos que respondieran en equipo a las preguntas de discusión de RameyLady tomadas de su sitio web Just:Words.

Premiación

Como última actividad del día viernes, entregamos reconocimientos a los equipos que obtuvieron los primeros tres lugares tanto en el concurso de programación como en el torneo de estrategias. Y con esto clausuramos nuestro reto de la Semana i.

Los profesores responsables del reto, Ariel Ortiz y Roberto
Martínez, con el equipo nokygerand, ganador del
primer lugar tanto del concurso de programación como
del torneo de estrategias. El equipo está integrado
por Andrés de Lago Gómez y  Gerardo Galván Olvera,
ambos alumnos de tercer semestre de la carrera ISC.

Documentando la experiencia

Durante toda la semana cada equipo fue documentando en su propio blog las impresiones y experiencias de las actividades que se fueron realizando. A continuación se listan los blogs de todos los equipos:

Conclusión

Nuestra Semana i 2016 resultó, tanto para los alumnos como para los instructores, un evento bastante agotador pero con un saldo final positivo. Me sentí muy complacido con los resultados obtenidos. Los comentarios de la mayoría de los alumnos fueron en general muy favorables.

Este fue un comentario bastante alentador tomado del blog del equipo rebelcoder:
Este reto me resultó grato desde muchos aspectos y considero que también me llevo muchas experiencias y aprendizajes nuevos. Los principales aprendizajes que me llevo tienen que ver con el “diseño e implementación de una solución de software ante un problema”, ya que la mayoría de los proyectos en los cuales he estado normalmente sabíamos el proceso para llegar a la solución o conocíamos la solución y aplicábamos reingeniería. En cambio en este reto no conoces el proceso para llegar al final ni tampoco la solución final para el problema del juego de Orugas, generando que nosotros tuviéramos que idear muchos algoritmos, casos de prueba y comparar otras soluciones para ver cuál era la mejor.
Este reto de la Semana i enfocado en el desarrollo de una Inteligencia Artificial en un Juego de Estrategia me gustó mucho y la verdad me agradaron mucho todas las actividades que hicimos. Lo que más me emocionó fue el torneo en sí cuando nosotros veíamos los resultados de cada uno de los enfrentamientos entre nuestros códigos y al final cuando nos enteramos del lugar en que quedamos. Gracias profesor Ariel y profesor Roberto por haber realizado esta actividad para nosotros.
— Servio Reyes
Hubo algunos detalles que nos señalaron varios participantes en cuestión de posibles mejoras. Un tema recurrente fue el manejo de los tiempos, al parecer muchos equipos hubieran querido contar con más tiempo para implementar su jugador estratégico. Algunos también sugirieron que se le permitiera al equipo ganador exponer ante los demás la manera en que diseñaron su solución. Me parece que vale mucho la pena considerar estos comentarios para mejorar el reto para cuando se llegue a ofrecer nuevamente en un futuro.


1 Inicia la segunda edición de Semana i con más retos en movimiento.

2 La palabra Dagor significa “batalla” en el idioma sindarin (conocido también como élfico gris), creado por el escritor británico J. R. R. Tolkien, autor del “Señor de los anillos”.

3 Lo que se estuvo proyectando realmente eran los resultados de unos comandos de SQL que tecleaba en el momento para consultar la base de datos con los resultados. Por falta de tiempo no pude automatizar esta parte del proceso.

3 de agosto de 2016

Ada Lovelace: Pionera de la programación

Esta entrada del blog de EduPython fue elaborada por mi buena amiga y ex-alumna Samantha Montserrat Ponce Aparicio, quien se tomó el tiempo para leer y escribir sus impresiones del libro titulado “Ada, the Enchantress of Numbers: Poetical Science” de Betty Alexandra Toole, publicado por Critical Connection en octubre del 2010.
Samantha es una de las mujeres programadoras más talentosas que he conocido. Actualmente estudia la carrera de Ingeniero en Sistemas Computacionales en el Tecnológico de Monterrey, Campus Estado de México, y está por graduarse en unos pocos meses.
Es un gran gusto y honor tener a Samantha como la primera autora invitada del blog de EduPython. 
Ariel Ortiz.
Agosto, 2016.


Antes de leer sobre la vida de Ada Lovelace, lo único que sabía es que era considerada la primera programadora. Nunca se me ocurrió averiguar qué programó, en qué computadora, cómo era su vida y si realmente había sido la primera persona en programar.

Los primeros años de vida de Ada

La vida de Ada Lovelace fue verdaderamente complicada. Fue hija de Lord Byron, sí, el poeta romántico, y Lady Byron quienes se separaron unos meses después de su nacimiento por las diferencias de pensamiento que tenían, ella pensaba en números y él en versos.

Ada de niña, retrato en exhibición
en Somerville College, Oxford.

Augusta Ada Byron nació en Londres el 10 de diciembre de 1815. Después de la separación, Lady Byron se quedó con la custodia de Ada y decidió educarla promoviendo en ella el gusto por la ciencia y las matemáticas, con la esperanza de que no fuera a seguir los malos pasos de su padre en el mundo del arte y la poesía. Ada aprendió a concretar ideas en forma de bloques en lugar de simplemente seguir la teoría, a pesar de que en ese tiempo solamente se utilizaban conceptos intangibles, incluso para enseñar a los niños.

El poeta George Gordon Byron, padre de Ada.

Uno de los datos tristes sobre Ada es que nunca conoció a su padre. Él murió en abril de 1824 y ella solamente lo vio en un retrato poco antes de cumplir 20 años. Por eso resintió a su madre durante toda su vida.


Al no tener hermanos, decidió enfocarse en observar a su gato Mrs. Puff, porque todos sabemos que la vida con gatos es mejor. A los 12 años decidió que quería volar, así que después de investigar e imaginar, escribió todo lo que encontró en un libro llamado Flyology, pero como su madre se burló de ella, abandonó el proyecto, a pesar de que sus teorías eran bastante acertadas. William Henson utilizó las mismas ideas para el diseño de su Aerial Steam Carriage, también llamado Ariel, como un profesor que conozco ☺.

Sus tutores se quejaban porque ella cuestionaba todo lo que enseñaban. Siempre buscó aplicar conceptos matemáticos en juegos, diagramas y metáforas, pues esa era la forma en la que ella aprendía mejor.

Después de haber estado enferma y en cama por tres años, decidió que además de estudiar matemáticas, quería aprender música y equitación. Cuando leí sobre esto me sentí identificada con ella, porque toda la vida me han gustado las matemáticas y las computadoras, pero también me gusta cantar, bailar y probar artes nuevas, por ejemplo, hace pocos meses empecé a tomar clases de danza aérea en telas.

La máquina analítica

Cuando Ada tenía casi 18 años conoció a Charles Babbage, y la vida de ambos cambió. Charles Babbage es conocido por haber inventado la primera computadora mecánica, que se programaba por medio de tarjetas perforadas. Su único y gran problema es que el gobierno no le daba los fondos necesarios para sus proyectos.

Charles Babbage, matemático,
filósofo, ingeniero e inventor.

Es ahí cuando Ada se ofreció a hacer notas sobre su invento, la máquina analítica, para conseguir fondos para toda la investigación de Babbage. En esas notas, Ada incluía diagramas, tablas y párrafos enteros sobre el poder de la máquina analítica. Por primera vez se utilizaron conceptos tales como: ciclo, índice y paralelismo, los cuales son básicos en la programación hoy en día.

Máquina analítica de Charles Babbage.
Ejemplar en exhibición en el museo de ciencia de
Londres. Solo una parte de esta máquina
se construyó antes de su muerte en 1871.

Como era muy importante destacar sobre invenciones anteriores, incluyendo la máquina diferencial diseñada también por Babbage, Ada se dio a la tarea de buscar un problema que solo pudiera resolverse con la máquina analítica. El problema que finalmente escogió y programó fue el de los números de Bernoulli, por esto se dice que ella fue la primera programadora. Lo cierto es que Babbage fue el primer programador, ya que tenía algunos ejemplos para poder probar su máquina, pero Ada fue quien documentó un programa computacional completo por primera vez.

El legado de Ada

Lo que más me encanta de Ada es su forma de pensar. Siempre cuestionaba todo y no se quedaba callada si no entendía algún concepto o no le parecía correcto. Quería aprender los principios y saber porqué las cosas eran como decían ser. Su pensamiento artístico le ayudaba a ver las matemáticas desde otro punto de vista y eso fue su gran colaboración con el trabajo de Babbage. Estoy segura de que sin las notas de Ada, la máquina analítica de Babbage hubiera pasado desapercibida, ya que ni el mismo Babbage sabía el poder de su invento hasta que Ada comenzó a ayudarlo.

Ada era, a mi parecer, bastante popular, o por lo menos se juntaba con personas muy reconocidas. Su tutor por un tiempo fue Augustus De Morgan, quien hizo las leyes de De Morgan, su mejor amigo fue Charles Babbage, sus amigos fueron Sir David Brewster, el inventor del caleidoscopio, Andrew Crosse, conocido por la electrocristalización, Charles Dickens, Michael Faraday y Florence Nightingale.

Se casó con William King en 1835 y en 1838 se volvieron conde y condesa de Lovelace, de ahí su nombre. Durante toda su vida se enfermó bastante y terminó muriendo en 1852 a la temprana edad de 37 años.

Daguerrotipo de Augusta Ada King,
Condesa de Lovelace, 1844.

Me parece importante que las personas en el mundo de la programación conozcan sobre Ada Lovelace, en especial las mujeres, para que se den cuenta que una mentalidad diferente puede lograr grandes cosas. Ada, a pesar de haber tenido una vida corta, hizo una contribución tan grande que incluso existe un importante lenguaje de programación que lleva su nombre.


Es sorprendente lo que se puede lograr con una forma diferente de pensar, puede que con eso logremos cosas aún más grandes, superando incluso a la invención de la computadora.

Apéndice: Los números de Bernoulli

El siguiente diagrama podría ser considerado el primer programa computacional publicado. Describe la manera de calcular los números de Bernoulli utilizando la máquina analítica de Charles Babbage:

Diagrama para calcular los números de Bernoulli.


Los números de Bernoulli se utilizan en algunas series de expansión para diferentes funciones (trigonométricas, hiperbólicas, gamma, etc.) y son extremadamente importantes en el análisis y la teoría de números.

De manera simplificada, para evitar meternos en demasiados detalles, el k-ésimo número de Bernoulli \(B_k\) se define usando la siguiente relación de recurrencia: \begin{equation} B_k = \left\{\begin{matrix} 1 & \textrm{si} \;\; k = 0\\ - \sum\limits_{i = 0}^{k - 1} \binom{k}{i} \frac{B_i}{k + 1 - i} & \textrm{si} \;\; k > 0 \end{matrix}\right. \end{equation} La fórmula anterior utiliza el coeficiente binomial, el cual se define de esta manera: \begin{equation*} \binom{k}{i} = \frac{k!}{i! \;(k-i)!} \end{equation*} El siguiente código es la traducción directa a Python 3 de estas dos fórmulas:

from math import factorial

def binomial(k, i):
    """Regresa el coeficiente binomial C(k, i),
    es decir, el número de formas distintas de
    seleccionar i elementos a partir de un
    conjunto de tamaño k.
    """
    return (factorial(k) //
            (factorial(i) * factorial(k - i)))

def bernoulli(k):
    """Regresa el k-ésimo elemento de la
    secuencia de números de Beroulli.
    """
    if k == 0:
        return 1
    else:
        return -sum([binomial(k, i) * bernoulli(i)
                     / (k + 1 - i)
                     for i in range(k)])
Con esto podemos usar el siguiente ciclo for para imprimir los números de Bernoulli B0 al B20:
for i in range(21):
    print('B({:2}) = {:10.5f}'.format(i, bernoulli(i)))
El uso del método format() permite que la salida aparezca adecuadamente alineada y con exactamente cinco dígitos después del punto decimal. La salida es la siguiente:
B( 0) =    1.00000
B( 1) =   -0.50000
B( 2) =    0.16667
B( 3) =   -0.00000
B( 4) =   -0.03333
B( 5) =   -0.00000
B( 6) =    0.02381
B( 7) =    0.00000
B( 8) =   -0.03333
B( 9) =   -0.00000
B(10) =    0.07576
B(11) =   -0.00000
B(12) =   -0.25311
B(13) =    0.00000
B(14) =    1.16667
B(15) =   -0.00000
B(16) =   -7.09216
B(17) =    0.00000
B(18) =   54.97118
B(19) =   -0.00000
B(20) = -529.12424
Vale la pena notar que Bk = 0 para todos los valores de k impares, con la excepción de k = 1.

Es conveniente comentar también que nuestra implementación es extremadamente ineficiente. Entre más grande sea el valor de k el programa se vuelve perceptiblemente más lento. Alternativamente, el algoritmo de Akiyama–Tanigawa permite calcular los números de Bernoulli de manera optimizada. El sitio de RosettaCode.org muestra cómo implementar dicho algoritmo usando Python y otra treintena de lenguajes de programación.

3 de julio de 2016

Midiendo distancias: el sensor ultrasónico

En esta entrada del blog veremos como usar la Raspberry Pi (RPi) junto con un sensor ultrasónico para medir la distancia a la que se encuentra algún objeto posicionado en frente de nuestro dispositivo.

El sensor ultrasónico que utilizaremos es el HC-SR04:

Sensor de distancia ultrasónico HC-SR04.

Este sensor es económico (tiene un precio comercial que oscila entre dos y cuatro dólares estadounidenses) pero bastante potente. Permite calcular distancias en un rango de 2 a 400 cm. y resulta relativamente fácil programarlo.

Un sensor ultrasónico funciona de manera similar a la capacidad de ecolocación que tienen ciertos animales tales como los murciélagos y delfines: el animal emite un sonido que rebota al encontrar un obstáculo; la distancia se estima a partir del tiempo que tarda en regresar el eco de la señal. El sonar que utilizan los submarinos para navegar en el océano está basado también en este mismo principio.

Ecolocación: el murciélago A genera un echo E que rebota
en la presa B generando una onda reflejada R. Con eso el
murciélago puede determinar la distancia d a su presa.
Imagen recuperada de: Wikimedia Commons.
 

Se dice que un sonido es ultrasónico cuando su onda tiene una frecuencia que se halla por arriba del espectro audible por el oído del ser humano, generalmente arriba de los veinte mil hertz.

El hardware

Además de un sensor HC-SR04 y una RPi (de cualquier generación) adecuadamente equipada y configurada, requeriremos los siguientes componentes de hardware:
  • Un protoboard
  • Dos resistencias R1 y R2 (ver discusión posterior)
  • Cables conectores

Vista esquemática del sensor HC-SR04.

El sensor HC-SR04 cuenta con cuatro pines:
  • VCC: Alimentación de 5 voltios
  • TRIG: Trigger o activador (entrada) del sensor
  • ECHO: Eco (salida) del sensor
  • GND: Tierra
Es importante mencionar que la señal de salida ECHO del HC-SR04 es de 5V. Esto hace que el sensor sea compatible con Arduino y otras plataformas de microcontroladores. Sin embargo, para la RPi los pines GPIO de entrada son de 3.3V. Si se envía una señal de 5V a un puerto desprotegido de entrada de 3.3V, éste puede resultar dañado, y eso es algo que definitivamente queremos evitar. Necesitaremos usar un circuito divisor resistivo para disminuir el voltaje de salida del sensor y así permitir que la RPi reciba la señal correspondiente sin problemas.

Un divisor resistivo consiste de dos resistencias (R1 y R2) en serie conectadas a un voltaje de entrada (Vin), el cual debe ser reducido a un voltaje de salida (Vout). En nuestro circuito, Vin corresponderá al pin ECHO, el cual requiere disminuir de 5V al Vout que necesitamos de 3.3V. El siguiente esquema muestra la disposición que deben tener las resistencias:


Un divisor resistivo se define a partir de la siguiente fórmula:


Sabemos que Vin = 5V y Vout = 3.3V. Por tanto lo que nos interesa calcular es:


Despejando tenemos:


Si conocemos el valor de la resistencia R2 podemos calcular directamente la resistencia R1. Por ejemplo, si R2 = 2kΩ, R1 tendría que ser igual a 1030.303Ω o algún otro valor cercano (por ejemplo 1kΩ).

La siguiente figura, elaborada en Fritzing, muestra la manera de conectar todos nuestros componentes:

Vista de protoboard Fritzing de un sensor HC-SR04 conectado a la RPi.

Las conexiones son las siguientes:
  • El pin VCC del sensor se conecta a cualquier pin de 5V de la RPi.
  • El pin TRIG del sensor se conecta al pin GPIO 23 de la RPi.
  • El pin GPIO 24 de la RPi se conecta a una pista disponible del protoboard. Un extremo de la resistencia R2 se conecta a esta pista, y el otro extremo se conecta a tierra (cualquiera de los pines GND de la RPi). Un extremo de la resistencia R1 se conecta también a esta pista, y el otro extremo se conecta al pin ECHO del sensor.
  • El pin GND del sensor se conecta a tierra (cualquiera de los pines GND de la RPi).

Vista física del sensor ultrasónico de distancias
colocado en el protoboard con sus respectivos
cables conectores.

El software

Para controlar el sensor y realizar las mediciones debemos efectuar lo siguiente:
  1. Poner TRIG en bajo durante dos segundos con el fin de estabilizarlo.
  2. Poner TRIG en alto por 10µs (diez microsegundos) y ponerlo inmediatamente después en bajo. En este momento el sensor envía 8 pulsos ultrasónicos de 40kHz y coloca ECHO en alto. Es necesario detectar cuando ocurre esto último para comenzar a medir el tiempo en ese preciso instante.
  3. ECHO se mantiene en alto hasta que reciba el eco reflejado por algún obstáculo. En ese momento ECHO se pone en bajo y significa que hay que terminar la medición del tiempo.
  4. A partir de la medición de tiempo obtenida ya podemos calcular la distancia como se discute a continuación.
Sabemos que la velocidad v es igual a distancia d entre tiempo t:


Despejando la distancia d, tenemos que ésta es igual a la velocidad v multiplicada por el tiempo t:


La velocidad que usaremos aquí es la del sonido, que es de 34,300 centímetros por segundo. Al final necesitamos dividir a la mitad el valor resultante debido a que nuestra medición corresponde al tiempo que tarda el pulso ultrasónico en llegar al obstáculo y regresar nuevamente al sensor.


En esta última fórmula, el tiempo t debe estar en segundos y la distancia resultante d en centímetros.

Con todo lo anterior tomado en cuenta, ya estamos en condiciones de escribir un programa en Python que controle un sensor ultrasónico HC-SR04. El código debe comenzar con las inicializaciones y configuraciones necesarias, similares a las que se explican detalladamente en la entrada titulada El LED parpadeante.

El programa completo en Python 2.7 se muestra a continuación:
# coding: utf-8

# Archivo: ultrasonico.py

# Importar las funciones necesarias de los módulos RPi,
# y time.
import RPi.GPIO as GPIO
import time

# Pin GPIO donde está conectado el activador (entrada) del
# sensor HC-SR04.
TRIG = 23

# Pin GPIO donde está conectado el eco (salida) del sensor
# HC-SR04.
ECHO = 24

# Indicar que se usa el esquema de numeración de pines
# de BCM (Broadcom SOC channel), es decir los números de
# pines GPIO (General-Purpose Input/Output).
GPIO.setmode(GPIO.BCM)

# Establecer que TRIG es un canal de salida.
GPIO.setup(TRIG, GPIO.OUT)

# Establecer que ECHO es un canal de entrada.
GPIO.setup(ECHO, GPIO.IN)

print "Medición de distancias en progreso"

try:
    # Ciclo infinito.
    # Para terminar el programa se debe presionar Ctrl-C.
    while True:

        # Apagar el pin activador y permitir un par de
        # segundos para que se estabilice.
        GPIO.output(TRIG, GPIO.LOW)
        print "Esperando a que el sensor se estabilice"
        time.sleep(2)

        # Prender el pin activador por 10 microsegundos
        # y después volverlo a apagar.
        GPIO.output(TRIG, GPIO.HIGH)
        time.sleep(0.00001)
        GPIO.output(TRIG, GPIO.LOW)

        # En este momento el sensor envía 8 pulsos
        # ultrasónicos de 40kHz y coloca su salida ECHO
        # en HIGH. Se debe detectar este evento e iniciar
        # la medición del tiempo.
        print "Iniciando eco"
        while True:
            pulso_inicio = time.time()
            if GPIO.input(ECHO) == GPIO.HIGH:
                break

        # La salida ECHO se mantendrá en HIGH hasta recibir
        # el eco reflejado por el obstáculo. En ese momento
        # el sensor pondrá ECHO en LOW y se debe terminar
        # la medición del tiempo.
        while True:
            pulso_fin = time.time()
            if GPIO.input(ECHO) == GPIO.LOW:
                break

        # La medición del tiempo es en segundos.
        duracion = pulso_fin - pulso_inicio

        # Calcular la distancia usando la velocidad del
        # sonido y considerando que la duración incluye
        # la ida y vuelta.
        distancia = (34300 * duracion) / 2

        # Imprimir resultado.
        print "Distancia: %.2f cm" % distancia

finally:
    # Reiniciar todos los canales de GPIO.
    GPIO.cleanup()
En una terminal necesitamos correr el siguiente comando para ejecutar nuestro programa:
sudo python ultrasonico.py
Mientras el programa se esté ejecutando se puede acercar y alejar algún objeto del sensor para ver si el programa funciona correctamente. Podemos usar una regla o cinta métrica para verificar los resultados. La salida del programa debe verse algo así:
Medición de distancias en progreso
Esperando a que el sensor se estabilice
Iniciando eco
Distancia: 79.30 cm
Esperando a que el sensor se estabilice
Iniciando eco
Distancia: 78.91 cm
Esperando a que el sensor se estabilice
Iniciando eco
Distancia: 79.70 cm
Esperando a que el sensor se estabilice
Iniciando eco
Distancia: 12.73 cm
Esperando a que el sensor se estabilice
Iniciando eco
Distancia: 12.49 cm
Esperando a que el sensor se estabilice
Iniciando eco
Distancia: 12.57 cm
Esperando a que el sensor se estabilice
Iniciando eco
Distancia: 78.82 cm
Esperando a que el sensor se estabilice
Es necesario presionar Ctrl-C para terminar el programa.

13 de junio de 2016

Combinaciones, permutaciones y otras diversiones

Imaginemos que estamos en una heladería y queremos un Tres Marías. Este delicioso postre se prepara con tres bolas de helado de diferentes sabores. La heladería cuenta con helado de los siguientes sabores: cereza, chocolate, fresa, nuez y vainilla. Con esta información, ¿qué elecciones de sabores tenemos para crear nuestro Tres Marías?      


La respuesta son las siguientes diez opciones:
  • Cereza, chocolate y fresa.
  • Cereza, chocolate y nuez.
  • Cereza, chocolate y vainilla.
  • Cereza, fresa y nuez.
  • Cereza, fresa y vainilla.
  • Cereza, nuez y vainilla.
  • Chocolate, fresa y nuez.
  • Chocolate, fresa y vainilla.
  • Chocolate, nuez y vainilla.
  • Fresa, nuez y vainilla.
Analicemos otro problema. Tenemos las siguientes tres letras: i, o, r. ¿Qué palabras podemos formar usando solamente esas tres letras?  Supongamos que no nos importa que algunas de las palabras formadas no existan en el idioma español. La respuesta son seis palabras:
  • ior
  • iro
  • oir
  • ori
  • rio
  • roi
El problema de los helados es un problema de combinaciones: deseamos determinar las formas de agrupar los elementos de un conjunto en donde no importa el orden en que se colocan dichos elementos. Un Tres Marías de chocolate, fresa y vainilla es igual a uno de fresa, vainilla y chocolate. Por otro lado, el problema de las letras es un problema de permutaciones: a diferencia de las combinaciones, aquí el orden sí nos interesa. No es lo mismo “rio” que “oir”.

Tradicionalmente, muchos libros de probabilidad y estadística comienzan con una descripción de cómo calcular el número de combinaciones o permutaciones de un conjunto. Sin embargo, si lo que nos interesa es obtener un listado con dichas combinaciones o permutaciones es muy probable que estos libros no expliquen la manera de hacerlo. Afortunadamente, con Python y un poco de ingenio podemos resolver este problema.

NOTA: Todo el código que aquí se presenta fue probado con Python 3.5.

Recordando al conjunto potencia

En nuestra entrada anterior discutimos cómo programar una función que calcula el conjunto potencia. Repetiremos aquí el código correspondiente por conveniencia, ya que estaremos haciendo uso de él más adelante.
def potencia(c):
    """Calcula y devuelve el conjunto potencia del 
       conjunto c.
    """
    if len(c) == 0:
        return [[]]
    r = potencia(c[:-1])
    return r + [s + [c[-1]] for s in r]

def imprime_ordenado(c):
    """Imprime en la salida estándar todos los
       subconjuntos del conjunto c (una lista de
       listas) ordenados primero por tamaño y
       luego lexicográficamente. Cada subconjunto
       se imprime en su propia línea. Los
       elementos de los subconjuntos deben ser
       comparables entre sí, de otra forma puede
       ocurrir un TypeError.
    """
    for e in sorted(c, key=lambda s: (len(s), s)):
        print(e)

Combinaciones

Se llama combinaciones de m elementos tomando n elementos a la vez (donde mn) a todas las agrupaciones posibles de tamaño n que pueden hacerse con los m elementos. Recordemos que no importa el orden de los elementos. Para esta discusión también supondremos que los elementos no se repiten.

Regresemos al problema original de las tres bolas de helado. Lo que queremos es encontrar todas las combinaciones que se pueden formar a partir de 5 sabores de helado tomando 3 sabores a la vez.

Primero veamos qué obtenemos cuando calculamos el conjunto potencia con los cinco sabores de helado:
>>> imprime_ordenado(
...     potencia(['cereza', 'chocolate', 'fresa', 
...               'nuez', 'vainilla']))
[]
['cereza']
['chocolate']
['fresa']
['nuez']
['vainilla']
['cereza', 'chocolate']
['cereza', 'fresa']
['cereza', 'nuez']
['cereza', 'vainilla']
['chocolate', 'fresa']
['chocolate', 'nuez']
['chocolate', 'vainilla']
['fresa', 'nuez']
['fresa', 'vainilla']
['nuez', 'vainilla']
['cereza', 'chocolate', 'fresa']
['cereza', 'chocolate', 'nuez']
['cereza', 'chocolate', 'vainilla']
['cereza', 'fresa', 'nuez']
['cereza', 'fresa', 'vainilla']
['cereza', 'nuez', 'vainilla']
['chocolate', 'fresa', 'nuez']
['chocolate', 'fresa', 'vainilla']
['chocolate', 'nuez', 'vainilla']
['fresa', 'nuez', 'vainilla']
['cereza', 'chocolate', 'fresa', 'nuez']
['cereza', 'chocolate', 'fresa', 'vainilla']
['cereza', 'chocolate', 'nuez', 'vainilla']
['cereza', 'fresa', 'nuez', 'vainilla']
['chocolate', 'fresa', 'nuez', 'vainilla']
['cereza', 'chocolate', 'fresa', 'nuez', 'vainilla']
El resultado consta de 32 subconjuntos (25=32). Si observamos cuidadosamente, hay exactamente 10 subconjuntos que son de cardinalidad 3. Esos 10 subconjuntos son precisamente las 10 diez combinaciones que se pueden formar a partir de un total de 5 elementos tomando 3 elementos a la vez. Sabiendo esto, podemos definir en una sola línea la función en Python que sirve para calcular combinaciones:
def combinaciones(c, n):
    """Calcula y devuelve una lista con todas las
       combinaciones posibles que se pueden hacer
       con los elementos contenidos en c tomando n
       elementos a la vez.
    """
    return [s for s in potencia(c) if len(s) == n]
Como podemos observar, aquí utilizamos una lista por comprensión, la cual se puede leer así: para cada subconjunto s que pertenece al resultado del conjunto potencia de c, conservar solo aquellos valores de s en donde su cardinalidad sea igual a n. Probando la función podemos ver que sí produce los resultados esperados:
>>> imprime_ordenado(
        combinaciones(['cereza', 'chocolate', 'fresa',
                       'nuez', 'vainilla'], 3))
['cereza', 'chocolate', 'fresa']
['cereza', 'chocolate', 'nuez']
['cereza', 'chocolate', 'vainilla']
['cereza', 'fresa', 'nuez']
['cereza', 'fresa', 'vainilla']
['cereza', 'nuez', 'vainilla']
['chocolate', 'fresa', 'nuez']
['chocolate', 'fresa', 'vainilla']
['chocolate', 'nuez', 'vainilla']
['fresa', 'nuez', 'vainilla']
El número de posibles combinaciones se denota \({}_m C_n \) y se calcula así: $$ {}_m C_n = \frac{m!}{n! \; (m - n)!} $$ En donde m es la cardinalidad del conjunto inicial y n es la cardinalidad de los subconjuntos que deseamos formar. El signo de admiración es la operación de factorial. Verificando nuestro ejemplo, donde m = 5 y n = 3, el resultado obtenido es el que hemos estado manejando: 5!/(3!*2!) = 120/(6*2) = 120/12 = 10.

La función en Python que calcula el número de combinaciones queda así:
from math import factorial

def numero_combinaciones(m, n):
    """Calcula y devuelve el número de combinaciones
       posibles que se pueden hacer con m elementos
       tomando n elementos a la vez.
    """
    return factorial(m) // (factorial(n) * factorial(m - n))
Podemos asegurarnos que las dos funciones que definimos, combinaciones() y numero_combinaciones(), son consistentes entre sí:
>>> len(combinaciones(range(20), 1))
20
>>> len(combinaciones(range(20), 1)) \
    == numero_combinaciones(20, 1)
True
>>> len(combinaciones(range(20), 10))
184756
>>> len(combinaciones(range(20), 10)) \
    == numero_combinaciones(20, 10)
True
>>> len(combinaciones(range(20), 20))
1
>>> len(combinaciones(range(20), 20)) \
    == numero_combinaciones(20, 20)
True
NOTA: El carácter de diagonal invertida (\) usado arriba indica que la instrucción continúa en la línea de abajo.

Permutaciones

Una permutación es la variación de la disposición u orden de los elementos de un conjunto.  Usaremos recursión para diseñar un algoritmo que permita permutar una lista. Hay que definir, entonces, dos cosas: el caso base y la llamada recursiva.

Caso base: El resultado de permutar un conjunto vacío es un conjunto que contiene al conjunto vacío.

Llamada recursiva: Nos interesa resolver una versión más simple del problema. Puede ser algo así: permutar el mismo conjunto de entrada pero quitándole un elemento, por ejemplo el primero. Analicemos la siguiente figura para comprender lo que deseamos lograr:


La llamada original es: permuta({x, y, z}). Vamos a hacer una llamada recursiva con el mismo conjunto pero sin su primer elemento. La llamada sería: permuta({y, z}). Por definición (o sea, por acto de fe) la llamada recursiva debe devolvernos lo siguiente: {{y, z}, {z, y}}. Ahora respondamos a la pregunta: ¿Qué se le debe hacer al resultado de la llamada recursiva permuta({y, z}) para convertirlo en el resultado esperado de la llamada original permuta({x, y, z})? El uso de los colores en la figura de arriba nos permiten responder a esta pregunta.

Tomemos el primer subconjunto del resultado de la llamada recursiva: {y, z}. A partir de éste, debemos insertar x (el elemento eliminado al momento de hacer la llamada recursiva) en cada posición posible de dicho subconjunto. Dado que hay dos elementos en el subconjunto, existen tres posibles posiciones de inserción: al inicio, en medio y al final. Los tres nuevos subconjuntos serían: {x, y, z}, {y, x, z} y {y, z, x}. Lo anterior hay que repetirlo para el segundo subconjunto de la llamada recursiva, en esta caso: {z, y}. Ahora obtendríamos: {x, z, y}, {z, x, y} y {z, y, x}. El proceso se repetiría de esta misma forma en caso de que el resultado de la llamada recursiva tuviera más subconjuntos. Todos los subconjuntos que generamos aquí conforman el resultado esperado de la llamada original.

Dividamos el problema en varias funciones de Python para simplificar su resolución.

La siguiente función crea una nueva lista a partir de una lista existente lst pero insertando el elemento x en la posición del índice i:
def inserta(x, lst, i):
    """Devuelve una nueva lista resultado de insertar
       x dentro de lst en la posición i.
    """
    return lst[:i] + [x] + lst[i:]
La expresión lst[:i] es una rebanada de la lista lst comenzando desde el inicio y hasta el elemento anterior al índice i. De manera similar, la expresión lst[i:] es una rebanada de la lista lst comenzando en el elemento del índice i y hasta el final de la lista. En medio de esas dos rebanadas creamos una nueva lista conteniendo a x. Por último, concatenamos todo en orden para crear la lista resultante.

NOTA:  Las listas de Python tienen un método insert() que podría parecerse mucho a nuestra función. Sin embargo nuestra versión no modifica la lista original, mientras que la de Python sí. Las funciones que definimos más adelante suponen que las inserciones no alteran la lista original.

Ejemplos de uso:
>>> inserta(42, [1, 2, 3], 0)
[42, 1, 2, 3]
>>> inserta(42, [1, 2, 3], 3)
[1, 2, 3, 42]
>>> inserta(42, [1, 2, 3], 1)
[1, 42, 2, 3]
La siguiente función nos genera una lista de listas con todas las posibles inserciones de un elemento:
def inserta_multiple(x, lst):
    """Devuelve una lista con el resultado de
       insertar x en todas las posiciones de lst.  
    """
    return [inserta(x, lst, i) for i in range(len(lst) + 1)]
La función range() produce los índices de todas las posiciones en las que deseamos hacer una inserción (desde 0 hasta el número de elementos de la lista original) y la lista por comprensión se encarga de llamar nuestra función inserta() para hacer el resto del trabajo.

La función inserta_multiple() puede usarse así:
>>> inserta_multiple(42, [])
[[42]]
>>> inserta_multiple(42, [1])
[[42, 1], [1, 42]]
>>> inserta_multiple(42, [1, 2])
[[42, 1, 2], [1, 42, 2], [1, 2, 42]]
>>> inserta_multiple(42, [1, 2, 3])
[[42, 1, 2, 3], [1, 42, 2, 3], [1, 2, 42, 3], [1, 2, 3, 42]]
Ahora sí, ya estamos en condiciones de implementar la función permuta():
def permuta(c):
    """Calcula y devuelve una lista con todas las
       permutaciones posibles que se pueden hacer
       con los elementos contenidos en c.
    """
    if len(c) == 0:
        return [[]]
    return sum([inserta_multiple(c[0], s)
                for s in permuta(c[1:])],
               [])
La expresión permuta(c[1:]) genera recursivamente todas las permutaciones de nuestro conjunto original c pero sin su primer elemento. Por cada subconjunto s devuelto por permuta(), la lista por comprensión realiza el inserta_multiple() con el primer elemento de c como argumento. Hay que tener en cuenta que esta lista por comprensión devuelve una lista de listas de listas. Esto quiere decir que hay un nivel en exceso de listas anidadas. Usamos la función sum() para concatenar las listas que están anidadas en la lista más externa y con ello nos queda el resultado que deseamos. El segundo parámetro de sum() es el valor con el que inicia la sumatoria, que por omisión es el número cero pues sum() se usa principalmente para sumar números. Sin embargo, si en su lugar se le manda una lista vacía como argumento la función sum() realiza una concatenación de listas, que es justamente lo que queremos.

Probemos permuta() con el segundo problema que propusimos al inicio de esta entrada:
¿Qué palabras podemos formar usando las letras i, o, r?
>>> imprime_ordenado(permuta(['i', 'o', 'r']))
['i', 'o', 'r']
['i', 'r', 'o']
['o', 'i', 'r']
['o', 'r', 'i']
['r', 'i', 'o']
['r', 'o', 'i']
Probando con otras entradas:
>>> permuta([])
[[]]
>>> permuta([1])
[[1]]
>>> permuta([1, 2])
[[1, 2], [2, 1]]
>>> imprime_ordenado(permuta([1, 2, 3]))
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
>>> imprime_ordenado(permuta([1, 2, 3, 4]))
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]
El número de permutaciones que se pueden obtener para un conjunto de cardinalidad n es: n!. Esto lo podemos verificar con el siguiente código:
>>> from math import factorial
>>> len(permuta(range(3)))
6
>>> len(permuta(range(3))) == factorial(3)
True
>>> len(permuta([]))
1
>>> len(permuta([])) == factorial(0)
True
>>> len(permuta(range(1)))
1
>>> len(permuta(range(1))) == factorial(1)
True
>>> len(permuta(range(5)))
120
>>> len(permuta(range(5))) == factorial(5)
True
>>> len(permuta(range(8)))
40320
>>> len(permuta(range(8))) == factorial(8)
True
En ocasiones puede resultar deseable calcular las permutaciones de un conjunto pero tomando solamente n elementos a la vez. Para ello podemos recurrir a la función combinaciones() junto con permuta():
def permutaciones(c, n):
    """Calcula y devuelve una lista con todas las
       permutaciones posibles que se pueden hacer
       con los elementos contenidos en c tomando n
       elementos a la vez.
    """
    return sum([permuta(s)
                for s in combinaciones(c, n)],
               [])
En este código usamos una lista por comprensión para calcular todas las combinaciones de c tomando n elementos a la vez, y luego permutar cada subconjunto obtenido. Finalmente concatenamos con sum() todas las listas con las permutaciones resultantes.

Ejemplo de uso:
>>> permutaciones([1, 2, 3], 0)
[[]]
>>> permutaciones([1, 2, 3], 1)
[[1], [2], [3]]
>>> permutaciones([1, 2, 3], 2)
[[1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]]
>>> imprime_ordenado(permutaciones([1, 2, 3, 4], 3))
[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]
Si m es la cardinalidad del conjunto original y vamos a formar grupos tomando n elementos a la vez, entonces el número de permutaciones posibles se denota \({}_m P_n\), y su fórmula es: $$ {}_m P_n = \frac{m!}{(m - n)!} $$ La función en Python que realiza este cálculo es:
def numero_permutaciones(m, n):
    """Calcula y devuelve el número de permutaciones
       posibles que se pueden hacer con m elementos
       tomando n elementos a la vez.
    """
    return factorial(m) // factorial(m - n)
Ahora verifiquemos si numero_permutaciones() es consistente con lo que permutaciones() nos devuelve:
>>> len(permutaciones(range(10), 0))
1
>>> len(permutaciones(range(10), 0)) \
    == numero_permutaciones(10, 0)
True
>>> len(permutaciones(range(20), 1))
20
>>> len(permutaciones(range(20), 1)) \
    == numero_permutaciones(20, 1)
True
>>> len(permutaciones(range(20), 4))
116280
>>> len(permutaciones(range(20), 4)) \
    == numero_permutaciones(20, 4)
True

Conclusión

El conjunto potencia y las listas por comprensión son nuestros mejores amigos para divertirnos diseñando algoritmos que generan combinaciones y permutaciones.



Finalmente, vale la pena comentar que el módulo itertools, disponible tanto en Python 2 como en Python 3, proporciona toda la funcionalidad que describimos aquí (y mucha más) en forma de generadores combinatorios. Sugiero utilizar dicho módulo si se tiene interés de obtener combinaciones y/o permutaciones sin tener que conocer los detalles de su implementación:
>>> from itertools import combinations, permutations
>>> list(combinations([1, 2, 3, 4], 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
>>> list(permutations([1, 2, 3, 4], 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), 
(1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), 
(2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), 
(3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), 
(4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]