Displicencias

Como armar un gateway SMS con tu celular

2009-09-17T06:19:00.008-02:00

Estuve averiguando y al parecer la única manera de hacer una aplicación que reciba mensajes de texto y pueda responder a los mismos, es apersonarse muy bien trajeado en una empresa que brinde servicios de alertas SMS y cuestiones afines, y firmar un jugoso contrato para obtener el muy preciado servicio. Ojo, enviar mensajes SMS desde una computadora es mucho más sencillo: la mayoría de los carriers permiten hacerlo enviando un correo electrónico a una dirección conveniente. El problema está en recibir los benditos textos: ¿qué pasa si quiero hacer el Twitter argentino, y quiero que mis usuarios posteen actualizaciones desde su celular? ¿qué pasa si quiero preguntarle a mi máquina como va la descarga de mi torrent?

El servicio necesario para enviar o recibir SMS desde una computadora conectada a Internet se denomina gateway SMS, y si bien el servicio de envío lo proveen las mismas compañías de telefonía celular, la recepción es más delicada, ya que nadie provee un servicio de acceso sencillo para forwardearme los mensajes que lleguen a un determinado número a mi aplicación. A continuación voy a explicar como se puede fabricar un gateway SMS fatto in casa utilizando un celular común y silvestre.

Ingredientes

Una computadora con un adaptador Bluetooth (o no, ver nota a continuación)
Un celular con Bluetooth
Python + python-bluez

En mi caso utilicé mi maltrecho Nokia 6103, y la solución que propongo debería funcionar en cualquier celular con dos dedos de frente (o sea, la gran mayoría de los Nokia y Sony Ericcsson, y tal vez algún que otro Motorola).

Técnicamente no es necesario usar bluetooth puesto que lo que vamos a hacer es enviar comandos AT estándar sobre un enlace serial. Esto se puede hacer tanto por Bluetooth como con el cable adaptador USB o serial correspondiente, artículo del que no dispongo. Debería ser trivial portar las ideas de mi programa para funcionar con un enlace cableado.

Como sistema operativo utilicé Ubuntu 9.04, pero debería funcionar en casi cualquier sistema actual puesto que las librerías necesarias funcionan también en Windows.

Pasos a seguir

El funcionamiento del gateway que propongo es sencillo; se conecta al teléfono mediante la conexión inalámbrica y puede realizar una de tres acciones:

Enviar un mensaje de texto a un número determinado
Obtener todos los mensajes de texto almacenados en el teléfono
Borrar todos los mensajes de texto almacenados en el teléfono

El único paso manual consiste en identificar la dirección de hardware del teléfono para indicarla al conectarse. En Linux esto puede hacerse habilitando Bluetooth tanto en el celular como en la computadora, activando en el teléfono el modo "visible", y finalmente ejecutando el comando hcitool scan.

Tras ingresar dicho valor en el script que pongo a continuación, se realizará la conexión con el celular. Es probable que el celular requiera una aprobación manual para cada vez que se realice una conexión (un mensaje del tipo "¿Desea conectarse con el dispositivo XXX?"). Como esto no es muy cómodo en un servidor, en los teléfonos Nokia esta opción puede desactivarse una vez que se ha establecido la conexión (en el apartado "Conexiones activas" del menú Bluetooth, se puede indicar que un cierto dispositivo no requiere confirmación).

El código que adjunto a continuación hace el resto del trabajo, gran parte del cual consiste en parsear el extraño formato PDU en que el teléfono entrega los mensajes de texto cuando se le pide. El código que hace esto está fuertemente basado en smspdu, que modifiqué para hacer un poco más amigable.

Seguir leyendo >>

gateway.py

#!/usr/bin/python

#Copyright (c) 2009 Gonzalo Sainz-Trapaga
#Permission is hereby granted, free of charge, to any person obtaining a copy
#of this software and associated documentation files (the "Software"), to deal
#in the Software without restriction, including without limitation the rights
#to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
#copies of the Software, and to permit persons to whom the Software is
#furnished to do so, subject to the following conditions:
#
#The above copyright notice and this permission notice shall be included in
#all copies or substantial portions of the Software.
#
#THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
#IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
#FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
#AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
#LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
#OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
#THE SOFTWARE.

import bluetooth
import select
import pdu

DEBUG = False

class Nokia6103:
    def __init__(self, hwaddr, port):
        self.sockfd = bluetooth.BluetoothSocket(bluetooth.RFCOMM)
        self.sockfd.connect((hwaddr, port))
        self._send('ATZ')

    def _log(self, s):
        if DEBUG:
            print s

    def _read(self):
        i = [self.sockfd]
        w = []
        e = [self.sockfd]
        out = ''
        while True:
            ir, wr, er = select.select(i, w, e, 3)
            if len(ir) == 0:
                self._log("Select: espera finalizada - saliendo.")
                break
            if len(er) > 0:
                self._log("Select: condicion de excepcion - saliendo.")
                break
    
            out += i[0].recv(1000)
            if out.find('OK\r\n') != -1:
                self._log("Select: OK alcanzado - saliendo.")
                break
        return out
    
    
    def _send(self, s):
        self.sockfd.send('%s\r' % s)
        out = self._read()
        self._log(out)
        return out

    def sendSMS(self, num, txt):
        self._send('AT+CMGF=1')
        self._send('AT+CMGS="%s"' % num)
        self.sockfd.send(txt + "\n")
        self.sockfd.send(chr(26))

    def getAllSMS(self):
        s = self._send('AT+CMGL=4')
        lines = s.split('\r\n')
        lines.pop(0)
        msgs = []
        for i, msg in enumerate(lines):
            if i % 2 == 0:
                if not msg.startswith('+CMGL'):
                    break
            else:
                msgs.append(pdu.decodePdu(msg))
        return msgs

    def deleteAllSMS(self):
        self._send('AT+CMGD=1,4')

    def close(self):
        self.sockfd.close()

if __name__ == '__main__':
    port = 1
    hwaddr = '00:19:B7:XX:XX:XX'
    n = Nokia6103(hwaddr, port)
    print n.sendSMS('+541150501234', 'Mensaje de prueba!')
    print n.getAllSMS()

pdu.py

#Copyright (c) 2009 Eric Gradman, Gonzalo Sainz-Trapaga
#Permission is hereby granted, free of charge, to any person obtaining a copy
#of this software and associated documentation files (the "Software"), to deal
#in the Software without restriction, including without limitation the rights
#to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
#copies of the Software, and to permit persons to whom the Software is
#furnished to do so, subject to the following conditions:
#
#The above copyright notice and this permission notice shall be included in
#all copies or substantial portions of the Software.
#
#THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
#IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
#FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
#AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
#LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
#OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
#THE SOFTWARE.
from cStringIO import StringIO
from math import ceil
from binascii import unhexlify, hexlify
from itertools import cycle
from datetime import datetime


def decodePdu(s):
    s = unhexlify(s)
    d = StringIO(s)

    # parse SMSC information
    p = {}
    p['smsc_len'] = d.read(1)
    p['type_of_address'] = d.read(1)
    p['sc_num'] = unsemi(d.read(ord(p['smsc_len'])-1))

    p['msg_type'] = d.read(1)
    p['address_len'] = d.read(1)
    p['type_of_address'] = d.read(1)

    p['sender_num'] = unsemi(d.read(int(ceil(ord(p['address_len'])/2.0))))
    p['pid'] = d.read(1)
    p['dcs'] = d.read(1)
    ts = d.read(7)
    p['ts'], p['tz'] = parseTimeStamp(ts)

    p['udl'] = d.read(1)
    p['user_data'] = d.read(ord(p['udl']))
    p['user_data'] = decodeUserData(p['user_data'])

    
    for f in ['sc_num', 'sender_num']:
        if p[f].endswith('f'):
            p[f] = p[f][:-1]
    
    return p

def unnibleSwapChar(c):
    c = ord(c)
    d1 = c & 0x0F
    d2 = c >> 4
    return int(str(d1) + str(d2))

def parseTimeZone(c):
    c = ord(c)
    d1 = c & 0x0F
    d2 = c >> 4

    neg = d1 >> 3
    d1 = d1 & 0x7
    
    units = int(str(d1) + str(d2))
    if neg:
        zona = '-'
    else:
        zona = ''
    zona += str(units // 4)
    zona += ':'
    zona += "%.02d" % ((units % 4) * 15)

    return zona


def parseTimeStamp(s):
    ts = s[:6]
    tz = s[-1:]

    f = [unnibleSwapChar(c) for c in ts]
    f[0] = f[0] + 2000

    zona = parseTimeZone(tz)
    return datetime(*f), zona

def decodeUserData(s):
    bytes = map(ord, s)
    strips = cycle(range(1,9))
    out = ""
    c = 0    # carry
    clen = 0 # carry length in bits
    while len(bytes):
      strip = strips.next()
      if strip == 8:
        byte = 0
        ms = 0
        ls = 0
      else:
        byte = bytes.pop(0)
        # take strip bytes off the top
        ms = byte >> (8-strip)
        ls = byte & (0xff >> strip)
      #print "%d byte %x ms %x ls %x" % (strip, byte, ms, ls)

      # append the previous
      byte = ((ls << clen) | c) & 0xff
      out += chr(byte)

      c = ms
      clen = strip % 8

    if strip == 7:  out += chr(ls) # changed 6/11/09 to incorporate Carl's suggestion in comments
    return out

def unsemi(s):
    """turn PDU semi-octets into a string"""
    l = list(hexlify(s))
    out = ""
    while len(l):
      out += l.pop(1)
      out += l.pop(0)
    return out

PyCon AR 2009 en Buenos Aires

2009-08-14T20:29:00.006-02:00

Hace un tiempo vi en la facultad los primeros afiches llamando a enviar charlas y presentaciones para realizarse en la PyCon 2009, la primera conferencia sobre Python en español! Se va a realizar los días 4 y 5 de septiembre en la sede de la Universidad de Belgrano, las charlas plenarias son de:

Jacob Kaplan-Moss, uno de los lead developers de Django
Collin Winter, uno de los core developers de Python que está trabajando en Google en el proyecto Unladen Swallow (un intérprete optimizado que busca multiplicar por 5 la velocidad actual de Python).

Además de éstas que son plenarias, está plagado de otras charlas de menor envergadura, además de las llamadas charlas relámpago que duran solo 5 minutos. Los temas son de los más diversos, y van desde una introducción al lenguaje a cómo usar Python para manipular su propio bytecode.

En resumen, novatos, hackers añejos e incluso personas que solo haya oído hablar de Python van a tener cosas para mirar y aprender. La inscripción es gratuita, solo hay que registrarse en el sitio web de la conferencia.

Python 3: iteradores en map y filter

2009-04-28T03:23:00.008-02:00

Las primitivas funcionales map y filter se agregaron a Python en Enero de 1994 por un programador cuya identidad hoy se desconoce. De esta manera, lo que antes se escribía repetidas veces con un bucle puede reducirse a una única y expresiva línea de código.

lista = [1,2,3,4]

# utilizando un bucle
lista_mapeada = []
for e in lista:
    lista_mapeada.append(f(e))

lista_filtrada = []
for e in lista:
    if f(e):
        lista_filtrada.append(e)

# utilizando map y filter
lista_mapeada = map(f, lista)
lista_filtrada = filter(f, lista)

En Python 2.0 se agregaron listas por comprensión, que ofrecen una sintaxis más intuitiva para las primitivas map y filter.

lista_mapeada = [f(e) for e in lista]
lista_filtrada = [e for e  in lista if f(e)]

Si están familiarizados con lenguajes como Haskell, que utilizan evaluación lazy o perezosa conocen algunas de las ventajas de esta característica en un lenguaje de programación: la evaluación de algunas expresiones no se hace inmediatamente sino que se pospone hasta que el valor es realmente necesario.

En el contexto de las primitivas map y filter que nos conciernen, la ventaja de la evaluación lazy es que no se computan hasta tanto no se accede al contenido de las listas resultantes. Con esto en mente, en Python 2.4 se agregaron generadores por comprensión (simplemente remplazando los corchetes por paréntesis en la sintaxis anterior). El resultado es un generador: un objeto que se comporta parcialmente como una lista, dado que puede iterarse sobre el (aunque no puede indexarse y accededer directamente a su i-ésimo elemento).

gen_mapeado = (f(e) for e in lista)
gen_filtrado = (e for e  in lista if f(e))

La mejora más inmediata es la performance: en lugar de aplicar la función completamente en el momento, no se hacen los cómputos requeridos hasta que se accede al resultado. Por esta razón, la librería estándar itertools incluye primitivas imap, ifilter y varias más que devuelven generadores en lugar de listas, puesto que en muchos casos este comportamiento es deseable.

En Python 3, sencillamente se cambió el comportamiento de las primitivas convencionales para que devuelvan iteradores en lugar de listas. Así, los nuevos map, filter, zip y compañía se comportan como los anteriores itertools.imap, iterators.ifilter y iterators.izip.

# Python 3
>>> l = map(f, [1,2,3,4])
>>> l[2]
TypeError: object is unsubscriptable

El nuevo comportamiento no es compatible hacia atrás, pero puede resolverse esta diferencia sencillamente cambiando todas las llamadas map(l) (y los otros) por list(map(l)), lo cual produce un comportamiento casi idéntico en Python 3 y Python 2 (y digo casi porque si el map original devolvía una tupla o un string, pueden haber diferencias).

Python 3: codificaciones y más

2009-02-21T02:27:00.001-02:00

Unicode, bytes y strings

Otro punto importante de cambios en Python 3 es como el lenguaje trata el texto, unificando todos los strings bajo Unicode. Históricamente, Python tenía un tipo especial de string Unicode, con una sintaxis especial, que era hermano del str convencional (dado que ambos heredaban de BaseString).

Esta distinción entre str y unicode como tipos básicos se efectuaba en el código fuente con su sintaxis específica:

str_normal = "Hola Mundo!"
str_unicode = u"Hola Mundo!" # nótese la 'u' antes de la primera comilla

Sin embargo, este paradigma no era muy feliz. Un str convencional carecía de una codificación particular y podía producir una serie de ambigüedades, en particular a la hora de realizar comparaciones entre cadenas de texto Unicode y cadenas de texto de 8 bits convencionales (en muchos casos se pueden producir Warnings o incluso excepciones).

A partir de Python 3, se utiliza una convención mucho más apropiada. Existen finalmente dos tipos básicos para las finalidades en las que regularmente se utilizan strings:

bytes, que es una secuencia de caracteres de 8 bits sin ninguna codificación particular
texto, que es una secuencia de caracteres textuales, y como tal representa palabras u otro texto y soporta la noción de encoding

La sintaxis para éstos es:

str_bytes = b"Hola Mundo!" # nótese la 'b' antes de la primera comilla
str_texto = "Hola Mundo!"

Esto tiene como consecuencia que al momento de declarar un string (y como lo más usual es utilizarlas para almacenar texto), se utilizará una cadena Unicode como corresponde para tener correcto soporte de internacionalización. Para el manejo de datos binarios o blobs de caracteres sin interpretación, el tipo bytes está disponible.

Codificación del código fuente

A su vez, y dado que Python históricamente no soportaba varias codificaciones de fuente, a partir de Python 2.0 (y junto con la introducción del soporte Unicode) se introdujo la posibilidad de declarar la codificación de un archivo mediante un comentario especial. Finalmente, desde 2.5, la aparición de caracteres no-ASCII en un archivo de fuente Python que no tuviera su codificación declarada producía un error.

A partir de Python 3, la codificación por defecto es UTF-8 a menos que se indique lo contrario utilizando la declaración que existe desde Python 2. Este valor por defecto es más razonable (ya que UTF-8 es el estándar de facto en la mayoría de los entornos modernos) y evita la necesidad de estar especificando permanentemente la codificación cada vez que debe crearse un nuevo archivo de código fuente.

En resumen

Una vez más se reemplazaron algunos casos por defecto para hacerlos más apropiados, rompiendo así la compatibilidad hacia atrás en pos de la sanidad del código fuente. El soporte de cadenas de texto internacionalizadas es ahora transparente y no requiere ningún esfuerzo adicional por parte del programador. Asimismo, la modificación en el source encoding ahorra un poco de texto innecesario al comienzo de cada nuevo archivo, manteniendo la esencia minimalista del código fuente de Python.

Como siempre, hay un resumen completo de los cambios en el changelog de Python 3. Además, hay una discusión interesante en Slashdot respecto de este tema, donde además se discuten las diferencias respecto del método adoptado por Ruby para soporte Unicode (es interesante puesto que Ruby tiene sus raíces en países de Asia, que es donde Unicode recibe más críticas por supuestas limitaciones técnicas).

¡Se me pisan los horarios!

2009-02-20T04:38:00.013-02:00

Un grafo es esencialmente un dibujito que consta de bolitas y rayitas. Detrás de su inocente aspecto, los grafos ocultan poderosas herramientas matemáticas para resolver problemas muy comunes. Por su naturaleza simple, son una buena muestra de que la matemática no trata solamente de números.

El plan de carrera de Ciencias de la Computación es un poco peliagudo. La carrera está prevista para hacerse en 5 años, a los que se suma el Ciclo Básico Común para lograr un total de 6. Este cuatrimestre (el primero de mi cuarto año en la facultad) me toca una situación que hasta ahora vine esquivando por poco.

Resulta que si bien el plan indica que en este año deben cursarse 4 materias obligatorias y 2 optativas, mis planes de hacer 3 obligatorias en el primer cuatrimestre se ven frustrados por la superposición de horarios. Las materias se superponen solamente una hora, con lo cual parecería ser que alguien intentó (sin éxito) que esto no ocurra.

¿Y ahora quién podrá defenderme?

Con mis planes aparentemente arruinados por la burocracia, me veo en la disyuntiva de elegir qué cursar. Tengo una serie de problemas: hay algunas materias cuyos horarios se superponen, otras que no me interesan, otras que me quiero sacar de encima y al menos una que la tengo que cursar sí o sí porque una materia del segundo cuatrimestre la requiere.

Este problema es un caso típico de algo que se resuelve de forma sencilla utilizando grafos. Lo primero que hay que hacer es modelar la información que tengo, que son materias, días y horarios. El grafo que propongo tiene una bolita o nodo por cada materia, y una rayita o eje une a dos materias cuando los horarios de éstas se superponen.

Para construir el grafo voy a usar un pequeño pedazo de código que a partir de los horarios decide si dos materias se superponen o no. A continuación este programa produce un archivo dot, que utilizando GraphViz puedo representar como imagen. Si me limito a las materias que puedo cursar en este momento (obviando las que ya hice, y las que todavía no puedo hacer), me queda algo así:

Puse de color verde las materias obligatorias, y la única materia que tengo que cursar obligadamente es Paradigmas de Lenguajes de Programación, ya que Ingeniería de Software II depende de ella.

El dibujo tiene una complejidad muy alta, ya que hay muchas materias. Si miran con cuidado verán que hay una línea que une a Bases de Datos con Teoría de Lenguajes, ambas de color verde. Por lo tanto, estas dos materias tienen sus horarios superpuestos y no puedo cursar ambas a la vez.

Una cualidad interesante es que el dibujo de arriba contiene toda la información necesaria para resolver el problema: los días de la semana, las horas, la aritmética, los feriados y la mar en coche desaparecieron de la vista. Esta capacidad de abstracción es un rasgo fundamental del uso de grafos.

¿Qué estamos buscando?

Necesito encontrar un conjunto de materias (bolitas en el grafo) que no tengan líneas entre sí. Esto se llama, en términos de grafos, un conjunto independiente. Existen muchos conjuntos independientes, y uno muy sencillo es simplemente tomar una materia sola. Claro que si curso una sola materia por cuatrimestre no me voy a recibir muy rápido, así que voy a intentar hacer algo mejor.

Me gustaría que el conjunto de materias elegidas tenga las siguientes características:

Tiene que ser independiente (sin rayitas entre las bolitas), ya que de otro modo dos materias tendrían sus horarios superpuestos.
Tiene que contener a la materia Paradigmas de Lenguajes de Programación (porque de otro modo me atrasa el cuatrimestre que viene)
Tiene que contener al menos otra materia obligatoria, sea Teoría de Lenguajes o Bases de Datos
Y por último, tiene que tener al menos 3 materias

Si escribo el código de esta restricción en Python, me queda lo siguiente:

def esConveniente(s):
    return esIndependiente(s) and \
           "Paradigmas de Lenguajes de Programación" in s and \
           ("Teoría de Lenguajes" in s or "Bases de Datos" in s) and \
           len(s) >= 3

Para terminar solo es cuestión de dejar que la computadora haga su trabajo, y me diga qué me conviene cursar el cuatrimestre que viene. Tras una (instantánea) corrida, resulta que solo hay 7 combinaciones posibles que reúnen los criterios que describí arriba:

gomo@ciabatta:~$ python inscripcion.py
Formas válidas de cursar materias: 233
Formas de cursar 'convenientes': 7

Paradigmas de Lenguajes de Programación, Lógicas Modales, Bases de Datos
Paradigmas de Lenguajes de Programación, Computación Gráfica, Bases de Datos
Visualización de la Información, Paradigmas de Lenguajes de Programación, Teoría de Lenguajes
Visualización de la Información, Paradigmas de Lenguajes de Programación, Lógicas Modales, Teoría de Lenguajes
Paradigmas de Lenguajes de Programación, Lógicas Modales, Teoría de Lenguajes
Visualización de la Información, Paradigmas de Lenguajes de Programación, Computación Gráfica, Teoría de Lenguajes
Paradigmas de Lenguajes de Programación, Computación Gráfica, Teoría de Lenguajes

Solo me resta elegir la opción que más me divierta, y voilà! Pueden ver el código completo en Python si siguen leyendo este post.

Ver el código completo >>

Código completo en Python

#!/usr/bin/python
# *-* encoding: utf-8 *-*

materias = {'Estadística y Data Mining':               (('Ma',1800,2100), ('Mie',1800,2100)                   ),
            'Inteligencia Artificial':                 (('Lu',1800,2200), ('Ma', 1900,2200)                   ),
            'Metaheurísticas':                         (('Ma',1800,2100),                                     ),
            'Redes Neuronales':                        (('Ma',1800,2100), ('Jue',1800,2100)                   ),
            'Seguridad de la Información':             (('Lu',1800,2200), ('Mie',1800,2200)                   ),
            'Teoría de Juegos':                        (('Lu',1800,2100), ('Mie',1800,2000)                   ),
            'Paradigmas de Lenguajes de Programación': (('Ma',1700,2000), ('Jue',1700,1930)                   ),
            'Bases de Datos':                          (('Mie',1830,2200),('Vie',1700,2230)                   ),
            'Teoría de Lenguajes':                     (('Lu',1800,2100), ('Mie',1700,1930), ('Jue',1930,2200)),
            'Lógicas Modales':                         (('Lu',1400,1800),                                     ),
            'Computación Gráfica':                     (('Lu',1400,1700), ('Vie',1400,1700),                  ),
            'Procesamiento de Lenguaje Natural':       (('Mie',1900,2200),                                    ),
            'Grafos y Tratabilidad Computacional':     (('Ma',1800,2200), ('Jue',1800,2200),                  ),
            'Programación Orientada a Objetos':        (('Lu',1900,2200), ('Mie',1900,2200),                  ),
            'Simulación de Eventos Discretos':         (('Lu',1800,2200), ('Mie',1800,2200),                  ),
            'Visualización de la Información':         (('Vie',1900,2200),                                    ),
}


def sePisan(h1, h2):
    '''Determina si dos horarios se superponen'''
    for c1 in h1:
        for c2 in h2:
            if c1[0] == c2[0]:

                # cual empieza antes?
                if c1[1] <= c2[1]:
                    prim = c1
                    seg = c2
                else:
                    prim = c2
                    seg = c1

                # si la primera termina despues de 
                # que empiece la otra, se pisan
                if prim[2] > seg[1]:
                    return True

    return False


def getDot():
    '''Devuelve un source DOT para el grafo de materias'''
    buf = []
    
    buf.append('graph grafo {')

    # genero IDs para los nodos
    i = 0
    ids = {}
    mats = {}
    for m in materias:
        ids[m] = i
        mats[i] = m
        i += 1

    for i in ids.values():
        buf.append('node%s [label="%s"]' % (i, mats[i]))
 
    ejes = []

    for m1 in materias:
        for m2 in materias:
            if m1 != m2 and sePisan(materias[m1], materias[m2]):
                if not (ids[m2], ids[m1]) in ejes:
                    buf.append('node%s -- node%s' % (ids[m1], ids[m2]))
                    ejes.append((ids[m1], ids[m2]))

    buf.append('}')

    return '\n'.join(buf)


def subconjuntos(s):
    '''Dada una secuencia s devuelve todos los subconjuntos de sus elementos'''
    if s == []:
        return []
    else:
        e = s[0]
        resto = s[1:]

        sin = subconjuntos(resto)
        con = subconjuntos(resto)

        for sub in con:
            sub.append(e)
        con.append([e])

        return sin + con
            

def esIndependiente(s):
    '''Determina si el conjunto de materias es independiente'''
    for m1 in s:
        for m2 in s:
            if m1 != m2:
                if sePisan(materias[m1], materias[m2]):
                    return False
    return True


def esConveniente(s):
    return esIndependiente(s) and \
           "Paradigmas de Lenguajes de Programación" in s and \
           ("Teoría de Lenguajes" in s or "Bases de Datos" in s) and \
           len(s) >= 3
           

if __name__ == '__main__':
    s = subconjuntos(materias.keys())
    
    print "Formas válidas de cursar materias: %s" % len([x for x in s if esIndependiente(x)])
    print "Formas de cursar 'convenientes': %s" % len([x for x in s if esConveniente(x)])
    print

    for c in [x for x in s if esConveniente(x)]:
        print ', '.join(c)

Python 3: es excepcional

2008-12-27T03:14:00.007-02:00

El manejo de excepciones en Python 3 recibió también un cambio menor, pero que tiene por objeto evitar una fuente muy común de bugs en el código producidos por el descuido del programador.

Lanzando

En Python 2.x, la sintaxis para lanzar una excepción era usualmente la siguiente:

raise ValueError, "Error de valor!" # o bien
raise ValueError("Error de valor!")

Sin embargo, existe una cantidad de casos diferentes y poco conocidos que se detallan en un largo párrafo del manual de referencia. Está claro que esto es poco deseable, puesto que introduce complicaciones en el lenguaje con el objeto de facilitar usos poco comunes.

Volviendo al caso "usual" citado antes, si bien ambos casos eran equivalentes, se decidió eliminar el primero puesto que la sintaxis resulta un poco confusa. Al leer, no se entiende fácilmente que en realidad el argumento que viene después de la coma en el raise se pasa al constructor de la excepción. Por lo tanto, de ahora en más habrá que restringirse a la segunda opción:

raise ValueError("Error de valor!")

Atajando

Del mismo modo, para atrapar una excepción, se utilizaba el siguiente bloque:

try:
    ... # codigo que lanza una excepción
except ValueError:
    ... # codigo que maneja la excepción

Ahora, si se desea observar el contenido de la excepción para manipularlo de alguna manera, se utiliza el siguiente bloque except:

except ValueError, e:
    print e # "e" referencia la excepción

La dificultad en este caso proviene del uso de la variable e, que puede fácilmente confundirse en el contexto siguiente:

try:
    ... # codigo que lanza una excepción
except (ValueError, TypeError):
    print e

Como se observa, la idea del código es atrapar una excepción de cualquiera de los dos tipos especificados. Sin embargo, muchas veces en las que se desea hacer esto, se termina escribiendo:

except ValueError, TypeError:
    ... # TypeError es ahora una ref. a la excepción!

Está claro que el comportamiento no es el esperado: el bloque citado no atrapa las excepciones de tipo TypeError, sino que únicamente presta atención a los ValueError.

Para evitar esta situación, se introduce a partir de Python 3 una nueva sintaxis que reutiliza el keyword as, ya utilizado antes con las inclusiones de módulos externos para establecer un nombre diferente al módulo importado. La nueva sintaxis se ve así:

except (ValueError, TypeError) as e:
    ... # "e" es lo que uno espera

Gracias a estos cambios se eliminan varias ambiguedades y semánticas complicadas en pos de la simplicidad. Con cambios como estos se hace que el código sea más legible para quienes son nuevos con el lenguaje, y se evitan bugs difíciles de detectar en el manejo de excepciones.

Python 3: es de colección

2008-12-10T21:49:00.010-02:00

Otro de los sets de cambios incluídos en la nueva versión de Python afecta a las colecciones. Entran en esta categoría los diccionarios, conjuntos y secuencias.

Sets y Frozensets son ahora builtin

En Python 3, set es un builtin (ya no es necesario importarlo del módulo sets). Set es una estructura de datos que representa un conjunto de elementos sin un orden específico. La implementación utiliza una tabla de hash, al igual que los diccionarios.

El tipo set es mutable (una misma instancia puede recibir modificaciones), al igual que las listas. Como la listas en Python tienen un equivalente inmutable (las tuplas), los conjuntos lo tienen también en el tipo frozenset. Cabe aclarar que estos tipos ya existían en Python 2.x, pero en Python 3 fueron promovidos a la librería estándar y ya no es necesario importar ningún módulo para utilizarlos.

>>> s = set()          # creo un set vacío
>>> for i in [1,2,3]:
...     s.add(i)
...
>>> 3 in s
True
>>> 4 in s
False
>>> s.remove(2)
>>> s
{1, 3}
>>> fs = frozenset()   # creo un frozenset vacío
>>> fs2 = fs.union(s)  # lo uno con el set {1, 3}
>>> fs2
frozenset({1, 3})      # obtengo un nuevo frozenset
>>> fs
frozenset()            # fs se mantiene intacto

Hay más información en la documentación oficial de set y frozenset.

Nuevos literales y expresiones por comprensión

Set viene acompañado de un literal para su creación: no es necesario construirlo agregando tediosamente elementos a un set vacío como hice arriba. Sin embargo, como la sintaxis es similar a la del literal de diccionarios, hay que tener cuidado al crear uno vacío! El constructor de set vacío es set(), ya que {} está reservado para los diccionarios.

>>> s = {1, 2, 3, 4}           # creo un conjunto
>>> d = {1: 'uno', 2: 'dos'}   # creo un diccionario
>>> s = {}                     # ojo! crea un diccionario
>>> type(s).__name__
'dict'
>>> s = set()

Pero todavía hay más! Python 3 finalmente incorpora diccionarios por comprensión, y ya que estamos en la volada, conjuntos por comprensión. La sintaxis es exactamente la que uno esperaría, muy similar a la de listas por comprensión. Es curioso mencionar que la propuesta de diccionarios por comprensión proviene del PEP 274 (de 2001!). En 2008, Python 3 incorpora esta deseable funcionalidad: se terminaron los días de usar una lista porque es más cómodo!

>>> numeros = [1,2,3,4,5,6,7,8,9,10]
>>> def esPar(x):
...     return x % 2 == 0
...
>>> pares = {x for x in numeros if esPar(x)}
>>> pares
{8, 2, 4, 10, 6}
>>> cuad_impares = {x: x*x for x in numeros if not esPar(x)}
>>> cuad_impares
{1: 1, 3: 9, 9: 81, 5: 25, 7: 49}

Novedades en diccionarios

En primer lugar hay que notar que el método has_key() de diccionarios fue eliminado. Este método era redundante; estas dos expresiones eran equivalentes en Python 2.x, introduciendo una ambigüedad innecesaria:

>>> dicc.has_key('clave')
True
>>> 'clave' in dicc
True

En Python 2.x los métodos keys(), values() y items() de un diccionario devolvían listas contiendo los datos del diccionario (sus claves, sus valores, y los pares clave-valor respectivamente). Asimismo, existían funciones análogas iterkeys, iteritems y itervalues. Estas últimas devolvían iteradores sobre las mismas secuencias que las anteriores.

Python 3 introduce el concepto de vista. Una vista es un objeto intermedio entre el diccionario y los elementos devueltos por los métodos descritos en el párrafo anterior. Los mismos objetos que usábamos en Python 2.x pueden obtenerse ahora a partir de la vista en lugar del diccionario propiamente dicho. Veamos como:

>>> d = {1:'uno', 2:'dos', 3:'tres'}    # armo un diccionario

# Python 2.x
>>> it = d.iterkeys()  # obtengo un iterador sobre las claves
>>> keys = d.keys()    # obtengo una lista de claves
>>> keys
[1, 2, 3]

# Python 3
>>> v = d.keys()    # obtengo la "vista" del diccionario d
>>> type(v).__name__
'dict_keys'
>>> it = iter(v)    # construyo un iterador a partir de la vista (no del dict!)
>>> keys = list(v)  # construyo una lista a partir de la vista

La utilidad de la vista no es aparente aún: sin embargo, la vista introduce una nueva posibilidad. Es claro que la lista obtenida a partir de keys() en Python 2.x está desconectada del diccionario: toda modificación al diccionario posterior a la creación de la lista no se ve reflejada en la misma. Los iteradores se comportan de forma similar: si se modifica el diccionario durante la iteración, se produce una excepción.

>>> d = {1:'uno', 2:'dos', 3:'tres'}
>>> it = d.iterkeys()
>>> del(d[2])
>>> for key in it:
...     print key
... 
Traceback (most recent call last):
RuntimeError: dictionary changed size during iteration

Lo curioso de la vista es que ella también es iterable! (además del iterador que devuelve al aplicarle iter()). Y esta iteración si soporta modificaciones durante su ejecución. De modo que en Python 3, podríamos hacer esto:

>>> v = d.keys()
>>> del(d[2])
>>> for key in v:
...     print(key)
...
1
3

Si obtenemos a partir de la vista el iterador "tipo Python 2.x", tendremos el mismo comportamiento que antes (se emite una excepción al modificar el tamaño del diccionario sobre el que se está iterando).

En resumen, Python 3 incorpora el tipo set a la librería estándar, y notaciones literales y por comprensión tanto para conjuntos como para diccionarios. Estas facilidades hacen más ameno el uso de los tipos de datos correctos para cada tarea, en casos en los que muchas veces se utilizaba una lista por comodidad de notación. Por último, las vistas introducen funcionalidad adicional a los diccionarios, permitiendo modificarlos mientras se los recorre además de mantener las operaciones existentes.

Python 3: diferencias de orden

2008-12-07T21:55:00.008-02:00

Otro de los cambios introducidos en Python 3 es la abolición del argumento cmp en la operación de ordenamiento de secuencias. Este argumento permitía especificar una función de comparación para utilizar como criterio de ordenamiento, lo cual era bastante cómodo en muchas situaciones. La función debía seguir el modelo de cmp (la builtin).

>>> cmp(1,2)
-1
>>> cmp(2,1)
1
>>> cmp(1,1)
0

Esto se usa mucho para ordenar según el valor de alguna clave particular en el caso de objetos personalizados.

>>> def cmp_edad(p1, p2):
...     return cmp(p1.edad, p2.edad)
... 
>>> class Persona:
...     def __init__(self, nombre, edad):
...             self.nombre = nombre
...             self.edad = edad
...     def __repr__(self):
...             return "%s (%s años)" % (self.nombre, self.edad)
... 
>>> personas = [Persona('Juan', 15), Persona('Lautaro', 3), Persona('Ifigenio', 73)]
>>> personas
[Juan (15 años), Lautaro (3 años), Ifigenio (73 años)]
>>> personas.sort(cmp=cmp_edad)
>>> personas
[Lautaro (3 años), Juan (15 años), Ifigenio (73 años)]

Python 3 elimina esta posibilidad para forzar en cambio la utilización del argumento key. La diferencia es sutil: el valor de key es una función de un único argumento que devuelve una clave que luego se utilizar para ordenar. Esta técnica se llama DSU (por Decorate, Sort, Undecorate) o transformación de Schwartz. Es realmente meritorio lo de este tipo Schwartz, porque logró ponerle su nombre a algo muy simple en 1994, uniéndose a otros personajes avivados similares (como Bolzano!).

La ventaja está en que la implementación con cmp realiza O(n log n) llamadas a la función de comparación, mientras que usando DSU la clave se evalúa una única vez para cada elemento de la secuencia, lo cual es O(n). Si la función de cálculo de la clave es costosa, esto puede hacer una diferencia apreciable en el rendimiento del algoritmo.

Veamos como quedaría el código anterior:

>>> def key_edad(p):
...     return p.edad
... 
>>> personas.sort(key=key_edad)
>>> personas
[Lautaro (3 años), Juan (15 años), Ifigenio (73 años)]

Hay una cuestión más sutil respecto de porqué se decidió eliminar cmp. No solo la función se ejecuta más veces, sino que además el uso corriente utiliza una función anónima (lambda) para hacerlo. Algo del estilo de:

>>> personas.sort(cmp=lambda x,y: cmp(x.edad, y.edad))

Esto tiene el problema añadido de que, si bien la rutina de sorting está implementada en C, la función de comparación no. Esto implica que cada vez que hace falta comparar dos elementos, hay además que hacer un cambio de contexto a Python con el costo adicional que esto representa. El idiom que utiliza key viene con un aditamento: el módulo operator incluye, a partir de 2.4, las funciones attrgetter y itemgetter. Estas funciones, al estar implementadas en C, son mucho más rápidas que sus contrapartidas en Python. Veamos como quedaría lo anterior utilizando la "forma Python 3":

>>> personas.sort(key=operator.attrgetter('edad'))

De esta forma, todo el ciclo de ordenamiento se ejecuta en C y no se repiten cálculos innecesarios, logrando así ordenar de forma muy eficiente. Hay mucha más información sobre ordenamiento de secuencias en Python (pre-3.0) en el wiki oficial.

En resumen, lo que se hizo fue eliminar una forma popular de ordenar secuencias. Las razones son técnicas además de filosóficas: la variante cmp no solo introduce una decisión a la hora de ordenar (¿qué uso? ¿cmp o key?), sino que una de las opciones produce código naturalmente menos eficiente que la otra.

Benchmark

A pedido del público, una comparación entre la alternativa típica de Python 2 usando cmp con lambda contra la versión de Python 3. En el código de prueba ordeno una larga secuencia de objetos en base al valor de su atributo (entero) i. El código que resulta es el siguiente:

class Pepe:
    def __init__(self, i):
        self.i = i

nums = range(1000000)
random.shuffle(nums)
pepos = map(Pepe, nums)

p1 = pepos[:]
p2 = pepos[:]

t = Timer()

# Version cmp
t.start()
p1.sort(lambda x,y: cmp(x.i, y.i))
print "Version lambda: ",
t.stop()

# Version key
t.start()
p2.sort(key=operator.attrgetter('i'))
print "Version key:    ",
t.stop()

La diferencia es abrumadora, no hay más que ver la salida del programa para una secuencia de 1 millón de elementos:

Version lambda:  21.29 segundos
Version key:     3.78 segundos

La versión key es unas 6 veces más rápida. Solo porque es divertido, les dejo un gráfico que compara la performance de los dos métodos (tiempo en segundos vs. cantidad de objetos a ordenar).

Python 3: pequeños cambios misceláneos

2008-12-06T23:32:00.018-02:00

El operador <>
No existe más, debería usarse != en su lugar (más de una manera de hacer lo mismo!)

El operador !=
Por defecto devolverá lo opuesto de ==, a menos que este último lance NotImplementedError. Este comportamiento es esperable y por tanto su ausencia era una fuente de bugs. En su momento reporté un bug en el ORM de Django por esta precisa razón.

print es una función
Anteriormente, print era un statement: una palabra reservada del lenguaje con tratamiento especial (como es el caso de if o class). En Python 3 print pasa a ser una función convencional. Esto es consistente con el hecho de que no hay ninguna razón para que no lo sea! Si bien va a ser necesario agregar paréntesis que antes no hacían falta, también va a ser posible utilizar print como antes era imposible.

# Python 2.x
print "hola mundo"    # imprime y va a la línea
print "hola mundo",   # imprime y no va a la línea
map(print, [1,2,3,4]) # error!

# Python 3.x
print("hola mundo")
print("hola mundo", end="")
map(print, [1,2,3,4]) # ok!

La mayoría de la sintaxis especial (y muchas veces extraña) de print ahora se reemplaza con keywords para la función. Hay más información en la página de cambios en Python 3 y en la documentación.

La división anda bien
El histórico problema de que la división de enteros da entero en Python se eliminó de una buena vez. Esto era un problema clásico al comenzar a programar, y forzaba a castear a float en muchas ocasiones para asegurarse de que al menos uno de los dos argumentos de la división sea float (en ese caso la división puede devolver float).

uno = 1
dos = 2

# Python 2.x
a = uno / dos
b = uno // dos
c = float(uno) / 2
print a # imprime 1
print b # imprime 1
print c # imprime 0.5

# Python 3.x
a = uno / dos
b = uno // dos
c = float(uno) / 2
print(a) # imprime 0.5 :D
print(b) # imprime 1
print(c) # imprime 0.5

Unificación de Int y Long
En Python 2 existían las dos clases de enteros, y si bien interoperaban entre ellas perfectamente, al imprimir un entero largo por pantalla se imprimía una curiosa L al final.

>>> import sys
>>> sys.maxint
2147483647
>>> sys.maxint + 1
2147483648L # <- "L" al final
>>> type(sys.maxint).__name__
'int'
>>> type(sys.maxint+1).__name__
'long'

Como la constante sys.maxint quedó por lo tanto sin uso, fue eliminada también.

reduce() no es más builtin
En Python 1.0 (allá por 1994) se agregaron varias primitivas de programación funcional: map, filter, reduce. Estas primitivas permiten, usando una única llamada, reescribir varios bucles simples que se suelen utilizar al programar.

Si bien map y filter quedan casi sin cambios en Python 3, reduce se eliminó porque produce código difícil de leer y por lo tanto es más conveniente utilizar un ciclo en lugar de la función. Para los que deseen seguirla utilizando, reduce ahora vive en el módulo functools.

Hace un tiempo expliqué map, filter y reduce en el foro de PC++.

Volaron muchos otros builtins
Todos los siguientes builtins volaron. Los idioms que los reemplazan están disponibles en la documentación sobre cambios en Python 3.

apply
callable
coerce
reload
file
y varios más!

Python 3 está entre nosotros

2008-12-06T23:05:00.004-02:00

El 3 de diciembre salió Python 3 (anteriormente llamado Python 3000). Por primera vez en la historia, Python rompe la compatibilidad hacia atrás para mejorar (y en cierta manera, purificar) el lenguaje.

There should be one —and preferably only one— obvious way to do it

"Debería haber una (y preferentemente solo una) manera obvia de hacerlo". Esa cita proviene del Zen de Python, una suerte de poema-chiste-documento que contiene las filosofías detrás del diseño del lenguaje de programación. La que cito arriba, en particular, se contrapone fuertemente con el slogan de Perl: "Hay más de una manera de hacerlo". Los programas en Perl se caracterizan por su muy pobre legibilidad - al punto que a veces se dice que Perl es un lenguaje de solo escritura (una vez que está escrito, nadie podrá leerlo!).

Esa cita es una parte esencial de las modificaciones que sufrió Python en su versión 3. Con el paso de los años, Python fue creciendo y acumulando librerías y funcionalidades. En muchos casos, existían varias maneras de hacer lo mismo sin que quedara claro cual era la mejor. Por esta razón, se eliminaron muchas formas redundantes de hacer cosas, y se aprovechó para corregir algunos detalles que vinieron mal de fábrica. Por supuesto, también hay nuevas funcionalidades.

En el sitio web oficial hay una página detallando todos los cambios en Python 3.

En los próximos días voy a estar comentando algunos de los cambios que se hicieron en Python 3, sus razones de ser, y sus implicaciones en el uso del lenguaje. Python es más simple, consistente (y lindo!) que nunca.

Estrellas Mágicas

2008-11-05T03:28:00.014-02:00

En PC++ hay personajes curiosos. Uno de ellos es DjGera, que hace unos días propuso este problema:

Ubicar los números del 1 al 16 de forma que todas las columnas, filas y diagonales sumen 34.

Como buen ser humano mi primer instinto es mirar el problema fijo a ver si se me ocurre una solución. Pasados 10 minutos me empieza a dar hambre y recuerdo que para algo estudio Lic. en Computación.

Rápidamente, hay 16! = 2.1e13 formas de poner los números en el dibujo. Si obviamos las rotaciones y reflexiones de una misma solución, quedan apenas 653 837 184 000 formas posibles (seiscientos mil millones aproximadamente). Si bien las computadoras de hoy son rápidas, los problemas con números de esta magnitud todavía no son razonables para tratarlos "a lo bruto".

Solución con Programación Lineal

Al mirar el problema uno piensa bastante rápido (o no) en esas clases de álgebra lineal y empieza a imaginar matrices ralas y triangulaciones. Las restricciones del tipo "esta variable y esta otra deben sumar tanto" son efectivamente lineales y por lo tanto pueden representarse de forma matricial. Sin embargo, el problema como está planteado no es un sistema lineal convencional, por dos razones:

Las variables son enteras, no reales
Las variables deben ser todas distintas

Con estos añadidos, el problema se sale de la programación lineal y entra en la programación entera, un área que es computacionalmente mucho más difícil. Estos temas son objeto de la materia Investigación Operativa que es una de las gemas del Departamento de Computación de la UBA. Desgraciadamente, todavía no tuve oportunidad de cursar esa materia. Pensándolo un poco llegué a la conclusión de que probablemente esta no fuera la ruta más sabia, pero Martín, un poco más piola y sobre todo mucho más optimista, me mostró que estaba equivocado.

La técnica para resolver el problema usando programación entera es esencialmente:

Plantear la matriz asociada a las restricciones lineales
Triangularla con el método de eliminación gaussiana
Tras este paso, queda una matriz singular de rango 8
Fijar 8 de las 16 variables en valores enteros de 1 a 16
Resolver las 8 variables restantes; si sus valores son enteros, están entre 1 y 16 y son diferentes a los 8 valores elegidos en el punto anterior, encontramos una solución.
Volver al paso 4 para cada valuación distinta de las 8 variables a fijar

El algoritmo es entonces una combinación de programación lineal con fuerza bruta, pero programado en Mathematica tarda unas 10 horas en hallar todas las soluciones posibles, lo cual es muy respetable.

Solución con Algoritmo Genético

Con el rabo entre las piernas frente a la completitud y elegancia de la solución propuesta por Martín, implementé un algoritmo genético para resolver el problema. Sin demasiado trabajo el algoritmo encuentra una solución muy rápido (en unos 5 segundos con Psyco). Este tipo de algoritmos no deja de sorprenderme, puesto que si se observa el código las heurísticas de mutación y apareamiento son totalmente primitivas, y sin embargo el rendimiento del mismo es excelente.

#!/usr/bin/python
# estrella.py
# Resuelve la estrella magica de 16 puntas con un algoritmo genetico.

import random
import sys

tam_poblacion = 400
natalidad = 0.15
mutacion = 0.5
max_generacion = 500

# restricciones lineales
m = [[0,1,3,4],
     [4,5,7,8],
     [8,9,11,12],
     [12,13,15,0],
     [14,15,1,2],
     [2,3,5,6],
     [6,7,9,10],
     [10,11,13,14]]

# funcion de aptitud
def fitness(cand):
    fit = 0
    for eq in m:
        fit_local = -34
        for j in eq:
            fit_local += cand[j]
        fit += abs(fit_local)
    
    # esto fuerza que el primer numero sea el 16
    # y filtra las rotaciones de la misma solucion
    if cand[0] != 16:
        fit += 1000

    return fit

# funcion de apareamiento
def cruzar(c1, c2):
    l = [c1,c2]
    random.shuffle(l)
    c1, c2 = l
    c = c1[:8]
    for each in c2:
        if not each in c:
            c.append(each)
    return c

# funcion de mutacion
def mutar(cand):
    # "ejercito" al generador pseudoaleatorio
    # esto mejora bastante la velocidad de convergencia!
    i1 = random.randint(0,15)
    i2 = random.randint(0,15)
    
    i1 = random.randint(0,15)
    i2 = random.randint(0,15)
    
    i1 = random.randint(0,15)
    i2 = random.randint(0,15)

    c = cand[:]
    c[i1], c[i2] = c[i2], c[i1]
    
    return c

def avanzar_gen(pob):
    nacen = int(tam_poblacion * natalidad)
    mutan = int(tam_poblacion * mutacion)

    # unos se aparean
    for i in range(nacen):
        papa, mama = random.sample(poblacion, 2)
        poblacion.append(cruzar(papa, mama))

    # nacen unos mutados
    for i in range(mutan):
        deforme = random.sample(poblacion, 1)[0]
        poblacion.append(mutar(deforme))

    # ordeno por fitness
    poblacion.sort(lambda x,y: cmp(fitness(x), fitness(y)))
    
    # mato a los menos aptos
    while(len(poblacion) > tam_poblacion):
        poblacion.pop()
    

numeros = range(1,17)

# inicializador de poblacion
def init_pob():
    poblacion = []
    for i in range(tam_poblacion):
        cand = numeros[:]
        random.shuffle(cand)
        poblacion.append(cand)
    return poblacion


if __name__ == '__main__':
    while True:
        print
        print "Comenzando simulacion..."
        gen = 0
        poblacion = init_pob()
        min_fit = 1000
        while min_fit !=0:
            avanzar_gen(poblacion)
            gen += 1
            f = fitness(poblacion[0])
            
            if f < min_fit:
                print "Fitness: %s (gen %s)" % (f, gen)
            min_fit = f
            
            if min_fit == 0:
                print "Eureka!"
                print poblacion[0]
                sys.exit(0)
            if poblacion[0] == poblacion[len(poblacion)-1] or gen >= max_generacion:
                break

La ejecución se ve aproximadamente así (con un poco de suerte!):

gomo@ciabatta:~$ time python estrella.py

Comenzando simulacion...
Fitness: 30 (gen 1)
Fitness: 18 (gen 4)
Fitness: 16 (gen 10)
Fitness: 10 (gen 15)
Fitness: 8 (gen 30)
Fitness: 6 (gen 44)
Fitness: 4 (gen 47)
Fitness: 2 (gen 99)
Fitness: 0 (gen 237)
Eureka!
[16, 3, 11, 2, 13, 7, 14, 9, 5, 10, 1, 15, 4, 6, 12, 8]

real 0m2.449s
user 0m2.420s
sys 0m0.028s

Por su naturaleza, el tiempo que insume el algoritmo genético es muy variable y no encuentra siempre la misma solución. Por esta razón el programa hace varios intentos en lugar de perseverar con la misma simulación si observa que está tardando mucho en encontrar una solución.

Agregado el 10/12/2008
Solución con Backtracking

Tras discutir en un foro, considero que es mejor aclarar lo siguiente: los algoritmos propuestos arriba no son ni de cerca los más eficientes que se conocen para este problema. Un simple algoritmo de backtracking encuentra una solución de forma certera y bastante más veloz que lo que propongo arriba.

El interés del post era mostrar dos técnicas interesantes para resolver el problema, sin ánimos de indicar que eran particularmente aptas o buenas para la tarea. A modo de ilustración, adjunto el código del algoritmo de backtracking.

def buscarSolucion(actual, restantes):
    if restantes == []:
        return actual
    else:
        for r in restantes:
            nuevo_act = actual + [r]
            nuevo_rest = restantes[:]
            nuevo_rest.remove(r)
            
            s = None
            if esValidoParcial(nuevo_act):
                s = buscarSolucion(nuevo_act, nuevo_rest)
                
            if not s is None:
                return s
            

def esValidoParcial(perm):
    l = [[0,1,3,4],
         [4,5,7,8],
         [8,9,11,12],
         [12,13,15,0],
         [14,15,1,2],
         [2,3,5,6],
         [6,7,9,10],
         [10,11,13,14]]

   
    for rest in l:
        s = 0
        c = 0
        for k in rest:
            if len(perm) > k:
                s += perm[k]
                c += 1
        
        if c == 4 and s != 34:
            return False
        elif c < 4 and s >= 34:
            return False
    
    return True

if __name__ == "__main__":
    numeros = range(1,17)
    print buscarSolucion([], numeros)

3 implementaciones de Fibonacci

2008-11-01T21:23:00.006-02:00

En la charla sobre técnicas algorítmicas usé el algoritmo para calcular números de Fibonacci para mostrar como se podía mejorar la eficiencia de un programa utilizando la técnica de programación dinámica. El algoritmo trivial de Fibonacci utiliza recursión múltiple. Esto produce una cantidad exponencial de llamadas, lo que resulta en un algoritmo de complejidad O(2ⁿ).

def fibo1(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo1(n-1) + fibo1(n-2)

La técnica de Programación Dinámica consiste en resolver primero subproblemas que están contenidos dentro del problema total, y luego servirse de las soluciones a los subproblemas para resolver el problema total.

Un ejemplo sencillo es el problema de obtener un camino mínimo entre dos puntos. El popular algoritmo de Dijkstra para caminos mínimos utiliza la técnica de programación dinámica.

Para el caso de Fibonacci, los subproblemas son los números de Fibonacci más pequeños que el que queremos calcular. En la implementación anterior, estos números se obtienen con llamadas recursivas. Sin embargo, si comenzamos calculando desde los números de Fibonacci más pequeños y con ellos vamos construyendo los más grandes, se puede realizar el cálculo en O(n).

def fibo2(n):
  if n == 0 or n == 1:
      return 1
  else:
      nm1 = 1
      nm2 = 1
      i = 1
      while i < n:
          nm1, nm2 = nm2, nm1 + nm2
          i = i+1
      return nm2

Un tiempo después Fede me comentaba sobre un algoritmo de Divide & Conquer que permite calcular aún más rápido los números de Fibonacci.

El algoritmo se basa en la siguiente identidad (donde F_n es el enésimo término de la sucesión o secuencia de Fibonacci):

Como existe un algoritmo de Divide & Conquer para elevar un número (o en este caso, una matriz) a una cierta potencia, nos podemos servir de él. Este algoritmo de potenciación es la función aLaN() en el código que sigue. Gracias al mismo, podemos calcular números de Fibonacci en tiempo O(log n).

def fibo3(n):
    # esta funcion multiplica 2 matrices de 2x2
    def multiplicar(m, n):
        return [m[0]*n[0]+m[1]*n[2],
                m[0]*n[1]+m[1]*n[3],
                m[2]*n[0]+m[3]*n[2],
                m[2]*n[1]+m[3]*n[3]]
    # esta funcion eleva una matriz de 2x2 a la k
    # usando el algoritmo de D&C
    def aLaN(m, k):
        if k == 0:
            return [1,0,0,1]
        elif k == 1:
            return m
        else:
            if k % 2 == 0:
                return aLaN(multiplicar(m,m),k/2)
            else:
                return multiplicar(aLaN(multiplicar(m,m),k/2),m)
    
    inicial = [1,1,1,0]
    return aLaN(inicial, n)[0]

Esto permite ver que el correcto uso de técnicas algorítmicas puede mejorar sustancialmente el rendimiento de los algoritmos. Si bien el programa presentado es de juguete, el conocimiento de estas técnicas puede abrir nuevas posibilidades a la hora de desarrollar software.