Category Archives: Programación

Escritos sobre código, algoritmos y lenguajes de programación

Obteniendo todas las posibles “palabras” de 7 letras (o menos)

Últimamente, el juego al que más le dedico tiempo (además de Tekken) es a Angry Words (apalabrados en español). Con eso que me gusta Scrabble desde hace mucho, me relaja mientras voy en el tren y al mismo tiempo me ayuda a practicar mi vocabulario.

De la misma manera, le he estado dedicando tiempo a aprender Haskell, ya que veo que algunas cosas de PLN podrían ser implementadas más fácilmente con programación funcional.

Buscaba un problema que me ayudara a practicar Haskell, a dar mis primeros pinitos en el lenguaje. Y mientras disfrutaba el mencionado juego y veía que es más de “ponle lo que sea a ver si pega” en vez de “piensa en alguna palabra interesante”, se me ocurrió crear un programa que, dada una serie de letras, mostrara todas la combinaciones posibles entre ellas. Lo veía fácil y factible, por lo que me decidí a poner manos a la obra.

¿Qué tan difícil puede ser?… me pregunté. Y aunque no es algo tan complicado, sí me tomó más tiempo del que pensaba debido a que había que hacer el cambio a programación funcional y no a imperativa.

Primero, a definir el algoritmo:

Tomemos una palabra de 3 letras (por conveniencia, más adelante verán por qué), digamos “ola”. ¿Qué es lo que quiero obtener? La lista de posibles permutaciones con esas 3 letras, es decir: ola, oal, loa, lao, aol, alo. Aquí me di cuenta de un patrón: tomo una letra de la palabra, la pongo al principio, y simplemente tomo las otras 2 letras restantes y les cambio el orden. Para comenzar, tomo la “o” como la letra principal, entonces me quedo con “la”, y las únicas combinaciones posibles son “la” y “al”; después, agrego la letra principal “o” y la pongo al principio de cada palabra, obteniendo “ola”,”oal”. Continúo con la siguiente letra, la “l”, la tomo como principal, quedándome “oa”, de la cual obtengo “oa” y “ao”; le pongo la “l” al principio de cada una y obtengo “loa”,”lao”. Por último tomo la “a” como letra principal, lo que me deja con “ol” como el resto, obteniendo “ol” y “lo”; le pongo la “a” al principio de cada una y resultan “aol”, “alo”. Juntando todos los resultados parciales, obtengo la lista de palabras que estoy buscando.

Con la definición anterior, recursivamente se pueden analizar palabras de cualquier longitud. ¿Buenas noticias para los que juegan apalabrados? En teoría, si es que tienen la paciencia de ver todos los resultados. ¿Cuántos son? Saquemos cuentas:

Una palabra de 3 letras resultó en una lista de 6 palabras. ¿Cuántas resultarán de una de 4? Como lo que buscamos son permutaciones, la fórmula es sencilla:

n!

Revisemos: 3! = 3x2x1 = 6. ¡Bien! Si cuadra el resultado

Entonces, con 4 letras tendremos: 4! = 4x3x2x1 = 24 Todavía no son muchas…

Con 5 : 5! = 5x4x3x2x1 = 120 ya da flojera ver tantas permutaciones…

¿Y con 7? Pues 7! = 7x6x5x4x3x2x1 = 5040 Está bien que no haya límite de tiempo en cada jugada de apalabrados, pero qué flojera (o ganas de ganar) de aquél(la) que se ponga a leerla cada vez.

¡Ajá! Dirán ustedes: ¿qué pasa si hay letras repetidas? Obviamente habrá palabras repetidas también, lo cual reduce nuestra lista. ¿A cuánto? Oh benditas matemáticas:

n!/(a!b!c!…)

En donde a es el número de veces que se repite una letra, b es el número de veces que se repite otra, c es el número de veces que se repite otra… y así sucesivamente.

Supongamos que tenemos las letras “atajada” (si las tienen, ¡no la piensen y jueguen esa palabra!). La letra “a” se repite 4 veces, entonces, tendremos:

7!/4! = 7x6x5 = 210

Quizá pude haber pensado el algoritmo con una palabra de 4 letras desde el principio, y aunque sí revisé a mano después, me era más fácil iniciar con una de 3 (sólo 6 posibles permutaciones).

Luego, a hacer el programa. El resultado, a sabiendas de que puede haber una mucho mejor implementación, es una belleza de 18 líneas de código (y porque puse doble enter en algunos lugares):

Continue reading Obteniendo todas las posibles “palabras” de 7 letras (o menos)

XMonad: Cambiar el nombre del layout que se muestra

Hace tiempo escribí sobre XMonad y un xmonad.hs básico en donde mostraba cómo mostrar íconos en vez del título del layout. Esta vez esalgo similar, pero como ahora sí estoy estudiando Haskell en forma, ando buscando cómo hacer lo que quiero con guards:

En uno de los escritorios estoy usando LayoutCombinators para combinar 2 layouts (concretamente simpledTabbed y DragPane Horizontal). Al mostrarse el nombre del layout aparece lo siguiente:

“combining Tabbed Simplest with DragPane Horizontal 0.1 0.099999999”

Debido a su longitud, me quita espacio del título de la ventana activa, por lo que pensé hacer un shorten, pero después recordé que en la laptop hago pattern matching para mostrar un ícono en vez del nombre del layout, por lo que pensé hacer algo parecido: si el nombre del layout comienza con “combining”, muestro un nombre que yo defina, y en cualquier otro caso muestro el nombre original.

El layout quedó así:

myXmobarPP h = xmobarPP
             { ppOutput = hPutStrLn h
             , ppCurrent = xmobarColor "green" "" 
             , ppHidden = xmobarColor "#5f7962" ""
             , ppVisible = xmobarColor "#f4a460" ""
             , ppUrgent = xmobarColor "#cc0000" "" . wrap "*" "*"
             , ppSep = " | "
             , ppWsSep = "  "
             , ppLayout = xmobarColor "#5CBAF5" "" .
                          (\lName -> showLayoutName lName)
             , ppTitle = xmobarColor "white" "" . shorten 150
             }

showLayoutName :: String -> String  
showLayoutName a | Just rest <- stripPrefix "combining" a = "Tabbed + DragPane H" 
showLayoutName a = a

Donde lo que quiero hacer está en ppLayout: una expresión lambda para revisar si el título comienza con “combining” o no. Esa revisión la hago en la función showLayoutName con la función stripPrefix, que recibe una lista y regresa otra lista que contiene los elementos después del prefijo indicado si es que existe, o Nothing en caso contrario. Si el título del Layout comienza con “combining”, regreso “Tabbed + DragPane H”, y si no, simplemente regreso lo que me llegó.

Intenté hacerlo con guards, pero nomás no me compiló el código, y como estoy en el trabajo, no me dio más tiempo de probar, por eso lo implementé como aquí se muestra.

Si quisiera hacerlo en Scala, el código quedaría así:

val xmobarColor = (bgColor: String) => (fgColor: String) => (output: String) => {
  // Hacer algo con los parámetros y regresar un String
  ...
}

val showLayoutName = (layout: String) => {
  layout.startsWith("combining") match {
    case true => "Tabbed + DragPane H"
    case _ => layout
}

// Asignando todo a ppLayout

val ppLayout = ((xmobarColor("#5CBAF5")("")) compose showLayoutName)

// Siendo layoutName el nombre del layout actual

ppLayout(layout)

Aunque sigo siendo novato en Scala (y para esos fines, en programación funcional), me late más la forma concisa de Haskell. Hacer function composition en scala es agregar demasiadas palabras (aunque si usara scalaz todo cambiaría), mientras que en Haskell el currying, la aplicación parcial y la composición se hacen sin mayor complicación.

Sigo estudiando y practicando.

Referencia dinámica a tipos de clase en Java

Necesitaba aplicar una serie de operaciones en distintos tipos de datos que comparten ciertas características. Hice lo lógico: creé una clase abstracta que implementa las funciones básicas de las características en común e hice que las demás clases fueran subclases de ella.

public abstract class BaseClass {

   // Propiedades y métodos comunes implementados aquí

}
public class SubClass1 extends BaseClass  {

   // Propiedades y métodos exclusivos
}
public class SubClass2 extends BaseClass {

    // Propiedades y métodos exclusivos
}

En los métodos que aplican las operaciones en cuestión declaré como parámetro la super clase (la abstracta) para que pudiera recibir cualquier subclase. El código quedó más o menos así.

public PriorityQueue<BaseClass> operation1 (List<? extends BaseClass> list) {
    // Hacer algo con los elementos en la lista
}

Hasta aquí todo bien.

El problema surgió cuando dentro de una de las operaciones tenía que modificar varias propiedades comunes de los objetos incluidos en la lista. Debido a la forma en la que Java pasa los parámetros (por valor,  aunque los objetos siempre pasan por referencia. Ver aquí), modificar en el método una de las propiedades del objeto no serviría de nada. Lo primero que se me vino a la mente fue crear clones de los objetos de la lista, pero muchos dicen que hay que evitarlos en la medida de lo posible, en especial cuando se tiene una estructura de clases compleja y algunos objetos no implementan la interface Clonable.

Ya he trabajado con clones antes y no hubo mucho problema. Sin embargo, quería ver si podía aplicar la solución de crear copy constructors para cada clase en la estructura y llamarlos dinámicamente. El problema es que necesitaba saber en tiempo real a qué clase pertenecían los objetos en la lista. Cierto: puedo hacer una serie de if con instanceof para probar cada una de las clases, pero se me hacía que había una mejor solución. Un simple:

BaseClass copy = new BaseClass(originalobject)

está fuera de contexto porque la clase base es abstracta (no se puede instanciar directamente).

La solución es relativamente sencilla: después de crear el copy constructor y de llamar en él al copy constructor de la superclase, en las operaciones tomo la clase de los elementos de la lista y creo dinámicamente una instancia de su copy constructor, la cual puedo llamar para crear una nueva instancia de la clase que contendrá los elementos del objeto original más lo que haya necesitado modificar. Al final meto todo en una cola que se ordena solita (basada en el compare de la clase) y es lo que regreso.

Los métodos que se usan:

  • Object.getClass() : para obtener en tiempo real la clase del objeto en cuestión.
  • Class.getDeclaredConstructor(Class) : para obtener el constructor que reciba los parámetros indicados. Como en este caso se trata de copy constructors, el único parámetro es un objeto de la misma clase, determinado con el getClass().
  • Constructor.newInstance(Object): para obtener una nueva instancia de la clase. En este caso, el constructor debe recibir como parámetro un objeto de la clase BaseClass o alguna de sus subclases.

Algo más o menos así:

public abstract class BaseClass {

   protected BaseClass() {
      // Inicialización de propiedades en común
   }

   // Copy Constructor
   protected BaseClass (BaseClass bc) {
       // copiar los datos de bc a esta instancia
   }

}

public class SubClass1 extends BaseClass {

    public SubClass1 {
       super();
       // Inicialización de propiedades exclusivas
    }

    // Copy Constructor
    public SubClass1 (SubClass1 sc1) {
        super(sc1);
        // Copiar los datos exclusivos de sc1 a esta instancia
    }
}

public class SubClass2 extends BaseClass {

    public SubClass2 {
       super();
       // Inicialización de propiedades exclusivas
    }

    // Copy Constructor
    public SubClass2 (SubClass2 sc2) {
        super(sc2);
        // Copiar los datos exclusivos de sc2 a esta instancia
    }
}

Y las operaciones:

public PriorityQueue<BaseClass> operation1 (List<? extends Searchable> list) {

    Class<? extends BaseClass> objclass = null;
    Constructor<? extends BaseClass> theConstructor = null;
    BaseClass newElement = null;

    for (BaseClass bc : list) {
       // Hacer algo con los datos

      objclass = bc.getClass();
      theConstructor = objclass.getDeclaredConstructor(objclass);
      newElement = theConstructor.newInstance(bc);

       // Hacer las operaciones restantes, crear la cola y devolverla
    }
}

Una alternativa más para la referencia dinámica a las clases y sus constructores.

XMMS2 en XMonad

En el post donde hablé de XMonad no puse el script que uso para mostrar información de XMMS2 con dzen en XMonad. Aquí lo agrego:

/usr/local/bin/dzen-xmms2

#!/bin/bash

ICONS=/home/mmedina/Images/Icons/xbm8x8
FONT=-sazanami-*-*-*-*-*-11-10-0-0-p-*-*-*

while true; do
     check=`xmms2 current | tr -d "\n" | wc -m`
     if [ $check == 0 ]; then
     	 echo "^i(${ICONS}/note.xbm) No songs being played"
     else
          current=`xmms2 current`
          totalsongs=`xmms2 list | grep / | wc -l`
    	  cursongstr=`xmms2 list | grep "\->" | cut -d"/" -f1 | tr -d "\->["`
	  cursongnum=`gcalctool -s "${cursongstr} + 1"`
          echo "^i(${ICONS}/note.xbm) ($cursongnum/$totalsongs) $current"
     fi
     sleep 3

done | dzen2 -x 1350 -y 0 -w 350 -h 11 -ta r -fg white -fn $FONT

Dando como resultado:

En el xmonad.hs tengo ligadas las funciones principales de XMMS2 a una combinación de teclas que me permiten controlar la reproducción de audio sin tener que abrir algún programa o escribir comandos en una terminal. Nota: éste no es el xmonad.hs completo:

  dzproc <- spawnPipe myStatusBar
  dateproc <- spawnPipe myDateBar
  xmms2proc <- spawnPipe myMusicBar

  xmonad $ defaultConfig {
  	 terminal = "urxvt -fg white -bg black -tr -sh 10 -fn 'xft:Dejavu Sans Mono:pixelsize=10' +sb"
	 , modMask = mod4Mask
         , startupHook = setWMName "LG3D"
	 , manageHook = manageDocks <+> myManageHook <+> manageHook defaultConfig
         , layoutHook = myLayout
         , logHook = dynamicLogWithPP $ myDzenPP dzproc
             , workspaces = ["term","web","ide","emacs","mail","ooffice","acroread","VB","misc"]
         } `additionalKeys`
	 [ ((controlMask, xK_Print), spawn "sleep 0.2; scrot -s")
	 , ((0, xK_Print), spawn "scrot")
	 , ((mod1Mask, xK_Shift_L), spawn "chkblayout")
	 , ((mod4Mask .|. shiftMask, xK_w), spawn "setwallpaper")
         , ((mod4Mask .|. shiftMask, xK_q), spawn "gnome-session-save --gui --kill")
         , ((mod4Mask .|. shiftMask, xK_l), spawn "gnome-screensaver-command -l")
         , ((mod4Mask .|. shiftMask, xK_z), spawn "xmms2 prev")
         , ((mod4Mask .|. shiftMask, xK_x), spawn "xmms2 pause")
         , ((mod4Mask .|. shiftMask, xK_c), spawn "xmms2 play")
         , ((mod4Mask .|. shiftMask, xK_v), spawn "xmms2 next")
         , ((mod4Mask .|. shiftMask, xK_b), spawn "xmms2 stop")
         , ((mod4Mask, xK_Up), spawn "amixer set Master 3%+")
         , ((mod4Mask, xK_Down), spawn "amixer set Master 3%-")
	 ]

myBgcolor = "#000000"
myStatusBar = "/usr/bin/dzen2 -x 0 -y 0 -h 11 -w 800 -ta l -fn -sazanami-*-*-*-*-*-11-10-0-0-p-*-*-*"
myDateBar = "/usr/local/bin/miscbarinfo"
myMusicBar = "/usr/local/bin/dzen-xmms2"

Estoy buscando una forma de revisar si el daemon de XMMS2 está siendo ejecutado o no. La idea es que si no lo está, ni me canso en parsear la salida de xmms2 current.

Callbacks en Java

Hace días necesitaba implementar algo en Java que me permitiera emular callbacks. Habiendo usado tanto tiempo Java fue curioso que de primera instancia no se me ocurriera usar interfaces. Un googlazo me enseñó la luz, y de ahí en delante fue nada más crear las clases necesarias.

El escenario es el siguiente: hay una clase que hace las veces de fábrica para crear instancias de otra, pero la forma de extraer la información es diferente dependiendo del documento en cuestión. Cada documento está clasificado en grupos, por lo que sé qué reglas tengo que usar para extraer lo de cada grupo. Ciertamente podría hacer todo con un parámetro y revisar el valor con un if para saber qué rutina ejecutar, pero si existen los callbacks, qué mejor (aunque Java no usa apuntadores).

Lo primero es crear la interface que las clases se van a cargar de implementar. Algo como:

public interface OmniAnalyzer {
    public void analyzeDocument(String document);
}

Después, hay que crear una clase por cada grupo de documentos a analizar, y hacer que cada una implemente la interface arriba mostrada:

public class GroupAAnalyzer implements OmniAnalyzer {
    @Override
    public void analyzeDocument(String document) {
       // Analizar documento de acuerdo a reglas de grupo A
    }
}
public class GroupBAnalyzer implements OmniAnalyzer {
   @Override
   public void analyzeDocument(String document) {
       // Analizar documento de acuerdo a reglas de grupo B
   }
}

Y al momento de analizar un documento, en vez de declarar que usamos una instancia de alguna de las clases anteriores, referenciamos directamente la interface que implementan. Así, independientemente de la clase (y las reglas) que se utilice, simplemente hay que llamar a las funciones que sabemos que están implementadas.

public class General {

  private static void analyzeDocument(OmniAnalyzer analyzer, String document) {
    analyzer.analyzeDocument(document);
  }

  public static void main(String a[]) {
    String doc = a[0];
    int group = Integer.parseInt(a[1]);
    OmniAnalyzer analyzer = null;

    if (group == 0)
     analyzer = new GroupAAnalyzer();
    else if (group == 1)
     analyzer = new GroupBAnalyzer();
    else {
       System.err.println("Only accepting groups 0 or 1");
       System.exit(1);
    }

    analyzeDocument(analyzer, doc);
  }
}

Con esto se deja la puerta abierta para agregar nuevos grupos en caso de ser necesario, y sin necesidad de darle en la torre a lo que ya está hecho.

Expresión regular para filtrar "@" y algunas URL

Ayer que estaba analizando una serie de textos en japonés, estuve intentando hacer una expresión regular que me ayudara a filtrar URL y algunas palabras que comenzaban con arroba y podían terminar con 2 puntos.

Aunque necesitaba implementarlo en Java, primero hice pruebas en Python para evitarme la pena de tener que hacer una clase pequeña.

Por supuesto, la parte de la URL es muy común, así que en vez que reinventar el hilo negro, mejor busqué en internet. Al final, terminé con ésta:

String a = "El texto con arrobas y URL";

System.out.println(a.replaceAll("(^|\\b)?@\\w+:?(\\b)?|(http|ftp|https):\\/\\/[\\w\\-_]+(\\.[\\w\\-_]+)+([\\w\\-\\.,@?^=%&amp;:/~\\+#]*[\\w\\-\\@?^=%&amp;/~\\+#])?","");

Sé que hay más opciones para filtrar la URL, pero ésta cumplió el trabajo.

Por cierto, @mecart comentó que parecía un nuevo smiley 😛

De hilos en Java

Aunque me gustan muchos lenguajes de programación, he usado Java como lenguaje principal desde que llegué a Japón. En realidad no hay una razón específica para ello, simplemente sentía que necesitaba practicar más en él, puesto que había estado usando mayormente C, y sentía que Java se me estaba olvidando… y aquí me tienen 7 años y medio después usándolo todavía. De vez en cuando también sale algo en Python, y Haskell es primordialmente para XMonad, pero de C lo último que hice fue un minijuego de PSP hace 4 años.

Después de usar un lenguaje de programación por un rato, se vuelve fácil sentarse a desarrollar algo sin la preocupación de estar leyendo cómo implementar algo en él… Sin embargo, siempre se aprende algo nuevo, y cada día lo reafirmo con cada aplicación que desarrollo.

He programado con hilos en Java desde hace mucho, pero nunca me había puesto a leer con detalle las clases del paquete java.util.concurrent. El control de hilos (el principal esperando mientras que otros realizan tareas de forma concurrente) lo implementaba con wait(), notifyAll() y boolean. Primitivo, pero funcionaba. Cuando necesito esperar un sólo hilo uso join(). Pero estaba seguro que debería haber algo ya en las clases de Java que hiciera lo que yo hacía, algo así como cuando aprendes lo que son las listas ligadas, implementas una pila con todos sus métodos y después  te dicen que ya hay una clase Stack que hace todo eso, y muchas veces de forma más eficiente (no siempre, aclaro). Fue entonces cuando descubrí las clases CountDownLatch y ThreadPoolExecutor.

Continue reading De hilos en Java

Obteniendo muchos registros de una base de datos

Aunque he trabajado con bases de datos durante mucho tiempo, no me considero un experto, y ésta es la prueba.

Sabemos que en una base de datos relacional lo recomendado es normalizar las tablas para evitar tener datos nulos, vacíos o repetidos en una sola tabla, y usando la primary key creamos relaciones entre las tablas para poder recuperar los datos cuando sea necesario. Pero cuando se tiene una cantidad de datos que comienza a ser grande (hablamos del order de millones de registros), ¿hacer un join para obtener los datos es la mejor opción?

Seguramente habrán escuchado sobre las key-value stores o bases de datos con tablas key-value , en las que se deja todo el control al programador con tal de evitar esos join y así “ganar” velocidad. Yo aprendí a usar siempre bdd relacionales, pero siempre he estado abierto a mejores propuestas, sobre todo cuando se tienen millones de registros y la velocidad del query es primordial. Sé que los join son lentos, pero el mantenimiento de una key-value store también es una tarea que puede ser desgastante. ¿A qué tirarle?

Si alguien tiene experiencia en esto, se aceptan sugerencias 🙂

Por acá un artículo que analiza los pros y contras de las bdd relacionales vs. las key-value stores: Is the Relation Database Doomed?

Buen código, mal código

Leí este artículo hace unos días, y me dio la idea de escribir al respecto la primera entrada de este blog.

Como se menciona en el artículo referido, es fácil decir que un código es malo cuando está hecho de una forma que no es la que uno acostumbra. Entender código ajeno toma tiempo, y hay veces en que mejor optamos por rehacer las cosas a nuestra manera en vez de tratar de comprender qué pensó (o de cuál fumó) el programador para sacar un código así. Claro que si vemos un código complicado, que no entendemos pero que sabemos que funciona, es mejor no reinventar la rueda y dejarlo así. Las 2 caras de la moneda.

Continue reading Buen código, mal código