Python 3: codificaciones y más

sábado, 21 de febrero de 2009
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!

viernes, 20 de febrero de 2009
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)