martes, 29 de marzo de 2011

Algoritmos de clasificación y problema de cambio de monedas, en C

Hola. Revisando el disco duro de hace algunos años me he encontrado con unas prácticas de la carrera (del 2003-2004), el análisis y diseño de algoritmos de clasificación y la resolución del ejercicio (mediante ciertas técnicas) de cambio de monedas. Bien , pues ya es hora de compartir este trabajo, por si alguien lo necesita. Estos trabajos están hechos en C, en plataforma Linux.

Se pueden descargar del repositorio de este blog, en:

https://sites.google.com/site/elviajedelnavegante/documentacion

Los ficheros son ALGORITMOS DE ORDENACION.zip y PROBLEMA DEL CAMBIO DE MONEDAS.zip.

Algoritmos de ordenación

Este trabajo recoge el análisis, diseño e implementación, en C, de los algoritmos de clasificación más importantes, a saber:

- Algoritmo de selección directa.
- Algoritmo de burbuja.
- Algoritmo de inserción directa.
- Algoritmo de burbuja mejorado.
- Algoritmo de QuickSort.
- Algoritmo de MergeSort.
- Algoritmo de QuickSort no recursivo.
- Algoritmo de MergeSort no recursivo.
- Algoritmo de QuickSort con elección de pivote.

Aquí se incluyen estudios de coste promedio, estudio teórico del tiempo de ejecución, estudios experimentales de todos los algoritmos de clasificación, etc.

Cambio de monedas

Resolución del problema de cambio de monedas por backtracking (árbol de soluciones, tiempos de ejecución, reducción de número de nodos e implementación) y por programación dinámica (ecuación de recurrencia y solución óptima, estudio teórico del tiempo de ejecución e implementación).

Por último comentar que los ficheros .zip contienen tanto la documentación como los fuentes, incluidos los Makefile.

Saludos.

martes, 22 de marzo de 2011

Script para pasar código Python a HTML

Hola. En este artículo vamos a crear un script para pasar código fuente Python (.py) a formato HTML (y de esta manera mostrar dicho código en una página web). Además vamos a darle  coloración al código Python. Debe de haber formas más simples, sin duda, de resolver este tipo de problemáticas, ... a mí se me ha ocurrido esta.

Como siempre, el fichero .py que contiene el script se puede obtener del repositorio de este blog, en:

https://sites.google.com/site/elviajedelnavegante/

El fichero se llama mi_tokenize.zip, el cual contiene el script mi_tokenize.py.

En este problema no se ha utilizado programación orientada a objetos, esto es, no se implementa ninguna clase. Todo se resuelve con programación imperativa (mediante funciones).

Al grano...

El funcionamiento es sencillo, en términos generales. De lo que se trata es que, a partir de un fichero de código fuente Python, se genera otro (con extensión html) con código HTML, que representa el código Python formateado (con indentación y coloreado de código).

Un ejemplo sería el siguiente:


La captura de arriba es del Stani's Python Editor. Abajo nos encontramos el mismo código, formateado en HTML y coloreado, en Firefox.


¿Cómo enfocar el problema?

Pasar código Python a html es casi trivial. Únicamente hay que abrir un fichero .py, leerlo, crear otro fichero con una cabecera html, incluir dicho código Python y cerrar el html. Listo, ya tenemos el código en una página web.

El verdadero problema es el coloreado del código, ya que se tiene que identificar los diferentes bloques de código a los que se quieren dar color. En nuestro caso, daremos color a los comentarios, a las cadenas y a las palabras clave de la versión que utilicemos de Python.

¿Cómo hacerlo? Mediante los módulos cStringIO y tokenize, que se pueden encontrar en cualquier distribución de Python.

cStringIO sirve para crear, a partir de una cadena, un buffer de cadena. tokenize es el módulo que nos permite analizar código Python e identificar componentes del mismo (comentarios, cadenas, etc) a partir de un buffer de cadena. Mejor lo vemos con los pasos que debe de dar nuestro script:

1) Cargamos en memoria un fichero .py con el método read() de open

2) Mediante cStringIO creamos un fichero en memoria ó buffer de cadena, el cual es necesario para utilizar el tokenize. En realidad esto sirve para iterar, línea a línea sobre una cadena con varias líneas (con saltos de línea). Por ejemplo:

import cStringIO

cadena = '''
Este es un ejemplo
de la potencia del
módulo cStringIO
'''

texto = cStringIO.StringIO(cadena)
for i in texto: print i

Devuelve:

Este es un ejemplo
de la potencia del
módulo cStringIO

3) Mediante tokenize, y a partir del buffer de cadena creado en el paso anterior, podemos obtener los token (elementos de código), iterando sobre ellos, e identificando los elementos de código Python.

En la documentación de Python tenéis una explicación muy buena (en inglés) de estos dos módulos:



Puff!!! Una explicación algo extraña. Veámoslo con un ejemplo. Imaginemos que hemos cargado mediante el método read() de open un fichero con código Python con el siguiente contenido:

# -*- coding: utf-8 -*-
# Código Python.
for i in range(0,5):
  print "Número ", i

Mediante los pasos anteriores vamos a identificar los elementos del código, a saber, comentarios, palabras clave y cadenas. El código que haría esta operación podría ser el siguiente:

# Creamos buffer de cadena.
texto = cStringIO.StringIO(cadena)

# Creamos tokens.
tokens = tokenize.generate_tokens(texto.readline)

for a,b,c,d,_ in tokens:
  if a == tokenize.STRING:
    print "Cadena: %s en posición [%s,%s]" %( b,c,d) 
  if a == tokenize.NAME and b in keyword.kwlist:
    print "Palabra clave: %s en posición [%s,%s]" % (b,c,d)
  if a == tokenize.COMMENT:
    print "Comentario: %s en posición [%s,%s]" % (b,c,d)

Dando como resultado:

Comentario: # -*- coding: utf-8 -*- en posición [(1, 0),(1, 23)]
Comentario: # Código Python. en posición [(2, 0),(2, 17)]
Palabra clave: for en posición [(3, 0),(3, 3)]
Palabra clave: in en posición [(3, 6),(3, 8)]
Palabra clave: print en posición [(4, 2),(4, 7)]
Cadena: "Número " en posición [(4, 8),(4, 18)]

Por tanto, mediante el módulo tokenize podemos identificar todos los elementos de los que se compone un código Python. La idea fundamental es esta. Aparte, mediante operaciones de transformación entre listas y cadenas, y demás operaciones se llega al resultado esperado.

¿Y cómo se colorea el texto? Pues mediante código HTML del tipo:


Así el otro hándicap es que a partir de las coordenadas de los elementos de código a colorear hay que insertar código HTML.

El script mi_tokenize.py

Tal como antes se ha comentado, el lector puede obtener el código de este script en el repositorio de El viaje del navegante. Aquí se presentan capturas de pantalla del código, debido principalmente a que se utiliza sintaxis html en el código Python, y no mezclar cosas.

Módulos que se cargan y estructuras que se definen:


Importamos los módulos necesarios y creamos un diccionario para colorear los elementos de código Python.

El código principal que ejecuta el script:


Podemos observar que el script pide dos argumentos para funcionar, el primero el fichero Python y el segundo el nombre del fichero html que se generará (se le da extensión .html si esta se omite) . A continuación llamamos a la función cargar_fichero que devuelve, mediante read() una cadena con el contenido del fichero. Finalmente, mediante la función tokenizar_codigo se crea una cadena con sintaxis html y Python, que se guarda en el fichero identificado por f_html_nombre.

Función para cargar el fichero .py:


Darse cuenta que reemplazamos ciertos caracteres especiales en html.

La función que analiza el código creando una cadena con html y código Python es la siguiente:


Esta función podría haberse escrito de otra forma, para ahorrar código, pero me ha parecido más pedagógico realizarlo de esta forma. Como se puede observar se utilizan cStringIO y tokenize. Devuelve una cadena con código html. Esta última función utiliza dos funciones auxiliares, a saber:

La función para insertar los elementos de html:


Y la función para incluir la cabecera y pie del documento de la página web:


Pero como no es lo mismo andar el camino que conocer el camino, es mejor probar el script. El lector puede pensar que sería mucho mejor utilizar CSS para estos menesteres, y en cierta manera, es verdad, pero no es objetivo de este post hacer un tratado sobre web y CSS. Lo verdaderamente importante es el parseo de código Python y el tratamiento de cadenas.

Se insta al lector a mejorar el código.

Saludos.

domingo, 20 de marzo de 2011

Mis antiguos juegos DOS en mi nuevo Linux Ubuntu

Hola. Este no es un post sobre Python, pero tenía que escribirlo, ya que llevo emocionado toda la mañana jugando a mis antiguos juegos de MS-DOS.

Mi primer PC fue allá por 1988 ú 89, ya no recuerdo. Un 8086 de 640 Kb, diskettera de 5 un cuarto y otra de 3 y medio. Monitor CGA monocromo (luego cambiaría a un TARGA VGA, todo un lujo). Por supuesto, un sistema operativo MS-DOS 3.22, que era lo máximo.

Hacía mis pinitos con Logo (AV, GD, GI, ...) y luego GW-BASIC (return, goto's, ...). Ahí es donde empezó mi curiosidad por la profesión, que ya viene de lejos.

Pero lo mejor, de verdad, lo mejor, eran los videojuegos. Unas auténticas joyas de programación, con los recursos hardware tan limitados que había por aquel entonces (comparado con ahora, claro) .

Yo no soy ningún entusiasta de los juegos de hoy día (de hecho, no juego), pero sí de los de mi época ochentera y noventera (el último el PC-FUTBOL 6.0, ¡qué maravilla!).

En mi nuevo Linux he descubierto que también está el DOSBox (que ya utilicé alguna vez en Windows), el cual es un emulador de entornos MS-DOS. Lo he instalado desde el Centro de software de Ubuntu. Hay muchas posibles configuraciones de esta aplicación. Aquí hay algunas guías:

http://www.arcades3d.com/textos/tutdosbox_uso.var

http://manualinux.my-place.us/dosbox.html

http://www.dosbox.com/DOSBoxManual.html

Lo único que he configurado para hacer funcionar DOSBox ha sido modificar la etiqueta [autoexec] del fichero de configuración dosbox-0.73.conf, que se encuentra en el directorio ./dosbox de la carpeta de usuario.



Como se puede observar he incluido la configuración del teclado al español:

keyb sp 437

 y he montado la unidad C: en el directorio donde tengo todos mis juegos DOS, mediante:

mount c /home/angel/juegos/dos

Arrancas el emulador DOSBox...


Increíble la sensación de jugar a juegos DOS desde un Linux!!!! Y lo mejor de todo, que funcionan a la velocidad de tu antiguo PC.

Xenon 2

Un clásico de arcades. Y menuda música que tiene (el altavoz echaba chispas)!!!



Digger 

¿Quién no ha jugado a este juego? ¿Y la música del Pop-corn? Bestial!!!


Y otros clásicos como Arkanoid, Volfied, Pacman, Striker, Rampage, Tetris (el auténtico de 1986), Sol Negro, .... En total tengo unos 118 juegos de los ahora denominados Abandonware.

Y no sé porqué, pero estos juegos, para mí, son mucho más adictivos e impresionantes que los de hoy día, ¡Y TODO EN MI LINUX!

Saludos.

martes, 15 de marzo de 2011

Me cambio a Linux

Hola. Después de algunos años en sistemas Windows XP (desde 2003, en donde dejé abandonada a su suerte a mi fabulosa RedHat 6), me vuelvo a Linux, a Linux Ubuntu definitivamente, con Python 2.6.6 y como IDE de desarrollo el Stani's Python Editor (SPE).

A partir de este post, todo lo que escriba se realizará en esta plataforma. La razón para el cambio es el intento de trabajar con Windows 7, en mi PC. La consecuencia: Un SO tiene que ayudar al desarrollador, y en mi caso, con mi máquina, eso es muy complicado (¡tarda más en ponerse en marcha que ejecutar NetBeans en un 486!).

No intento desprestigiar la familia de SO's Windows 7 ni nada parecido. Únicamente, que no es bueno para mí. Y como mi Linux Ubuntu 10.04 no me da problemas de rendimiento, pues me quedo aquí.

Por último decir que si por alguna excepción escribiera algo para Windows, sería con Windows XP SP3, y con el IDE PyScripter, uno de los entornos de desarrollo más potentes para Python en plataformas de Microsoft.

Saludos.

martes, 1 de marzo de 2011

Pasar parámetros entre frames en wxPython

Hola. En este artículo vamos a ver una forma muy sencilla de pasar parámetros entre 2 frames en wxPython, uno padre de otro. El paso de mensajes ó parámetros entre objetos se puede hacer de varias formas, siendo la que vamos a ver una de las más fáciles.

Aunque lo vamos a ver con un ejemplo (esto es, código), no está de más explicar el funcionamiento. La aplicación es un fichero .py donde tenemos una aplicación wxPython, que instancia una clase (frame_principal). Dicha clase, al hacer click en un botón instancia una segunda clase (frame_secundario). Cuando se introducen datos en el frame_secundario (objeto) y se hace click en un botón, se devuelve dicha información al frame_principal, que lo muestra. Es decir, se introducen datos en un frame y los devuelve al frame maestro desde que fue instanciado (llamado).

¿Cómo se ha hecho? La cuestión es que cuando se instancia el frame_secundario en el frame_principal, se le pasa como parámetro una referencia de él mismo. En frame_secundario se crea un atributo (self.padre), que contiene la referencia al frame padre en donde fue creado.

Este ejemplo se ha realizado en Linux Ubuntu y el editor joe. El código es el siguiente:


# -*- coding: utf-8 -*-
# El viaje del navegante.
# Ejemplo de paso de parámetros entre 2 frames en wxPython.

# Importamos las wx
import wx

# Creamos una clase frame que pide un dato.
class frame_secundario(wx.Frame):
  def __init__(self, parent):
    # Este es el constructor. Darse cuenta que se pasa como
    # parámetro parent, esto es, la referencia del frame que instancia
    # a esta clase. La guardamos.
    self.padre = parent
    # Llamamos al constructor de la clase de la que hereda.
    wx.Frame.__init__(self, None, -1, title = "Introduce un valor")
    # Creamos un sizer horizontal.
    sizer = wx.BoxSizer( wx.HORIZONTAL )
    # Creamos una caja de texto.
    self.caja_texto = wx.TextCtrl(self, -1)
    # Creamos un botón.
    self.boton = wx.Button(self, -1,"ACEPTAR")
    # Añadimos al sizer la caja y el botón.
    sizer.Add(self.caja_texto, 0, wx.ALL, 5)
    sizer.Add(self.boton, 0, wx.ALL, 5)
    # Incluimos el sizer en el frame.
    self.SetSizer(sizer)
    # Creamos el binding. Cuando se haga click en el
    # botón se lanzará el manejador de eventos correspondiente.
    self.boton.Bind(wx.EVT_BUTTON, self.OnClickBoton)

  # Manejador de eventos.   
  def OnClickBoton(self, event):
    # Obtenemos datos de la caja de texto.
    dato = self.caja_texto.GetValue()
    # Podríamos escribir directamente en el objeto
    # que se desease.
    self.padre.caja_texto.SetValue(dato)
    # Nos vamos.
    self.Destroy()
  
# Creamos la clase de la ventana principal.   
class frame_principal(wx.Frame):
  def __init__(self):
    # Constructor. Llamamos al constructor de la clase wx.Frame.
    wx.Frame.__init__(self, None, -1, title = 'Ventana Principal')
    # Creamos un sizer horizontal.
    sizer = wx.BoxSizer( wx.HORIZONTAL )
    # Creamos un botón.
    self.boton = wx.Button(self, -1, "Crear Frame Secundario")
    # Creamos una caja de texto de solo lectura.
    self.caja_texto = wx.TextCtrl(self, -1, style = wx.TE_READONLY)
    # Añadimos al sizer la caja y el botón.
    sizer.Add(self.boton, 0, wx.ALL, 5)
    sizer.Add(self.caja_texto, 0, wx.ALL, 5)
    # Asociamos el sizer al frame.
    self.SetSizer(sizer)
    # Creamos el binding. Cuando se haga click en el
    # botón se lanzará el manejador de eventos correspondiente.
    self.boton.Bind(wx.EVT_BUTTON, self.OnClickBoton)
     
  # Manejador de eventos.   
  def OnClickBoton(self, event):
    # Si se hace click se crea una instancia del frame_secundario.
    frame = frame_secundario(self)
    # Mostramos.
    frame.Show()
      
# Creamos una aplicación wxPython.
aplicacion = wx.PySimpleApp()
# Instanciamos el frame principal.
frame = frame_principal()
# Y por supuesto, no olvidar mostrarlo.
frame.Show()
# Esperamos a capturar eventos.
aplicacion.MainLoop()
   

El código está muy comentado, pero volvemos a analizarlo. Se crea una aplicación wxPython, que instancia la clase frame_principal.


Si hacemos click en el botón "Crear Frame Secundario" se instancia la clase frame_secundario, creando un segundo frame:



Incluimos un texto en la caja de texto, PYTHON!!!, y hacemos click en el botón Aceptar. 


Tal como se aprecia en el código, se envía el dato al frame padre y se destruye la instancia del frame_secundario.Y el resultado es:






En el código se ha resaltado en verde el paso de la referencia del frame padre. 


Saludos.