Category Archives: Programación

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

Funciones como ciudadanos de primera clase y expresiones lambda

En la entrada anterior, varias personas me hicieron el apunte de que debería haber puesto la última parte (donde explico para qué puede ser útil ese conocimiento) en el principio. Otros comentaron que aunque es posible entender el escrito, sí es necesario conocer ciertos conceptos, como mapeo, para “agarrar el hilo”.

Agradezco mucho sus comentarios 🙂

Aunque no pretendo hacer (de momento) una guía exhaustiva sobre programación funcional, sí me gustaría plasmar algunos conceptos básicos que puedan servir para despertar el interés de investigar más.

Cabe mencionar que programar en forma funcional no necesariamente es mejor que la programación orientada a objetos. Cada paradigma tiene pros y contras, pero conocer lo que cada uno ofrece nos permite tomar mejores decisiones a la hora de crear código o de seleccionar un lenguaje para ciertas tareas.

Vayamos al grano:

Continue reading Funciones como ciudadanos de primera clase y expresiones lambda

Monads – Yo también tenía que escribir al respecto

Seguí la tradición: cuentan las leyendas que cuando una persona comienza a ver la luz al usar Monads, invariablemente escribe un tutorial. Pero en mi caso, no es un tutorial, sino más bien una breve explicación de lo que son, junto con algunos ejemplos. Esto es con el fin de que yo mismo compruebe si entiendo el concepto general, y al mismo tiempo de que salgan gurús en programación funcional y me corrijan y me digan en qué estoy mal.

Ésta no es una guía exhaustiva, y omitiré muchos conceptos, pero pondré referencias por aquello de que haya interesados en el tema.

Como nota, sé que en español los términos son Funtor mónadas, pero nada más no me entran en la cabeza, por lo que los usaré en inglés. Además, aunque no está dirigido a un lenguaje en particular, la mayoría de los ejemplos mostrados están en Scala.

Continue reading Monads – Yo también tenía que escribir al respecto

8-puzzle: Implementación sencilla de A*

Hace poco estuve leyendo unas notas de un curso en línea sobre planeación en IA. En una de ellas me encontré con un algoritmo que tenía rato que no veía ni utilizaba, y me dio curiosidad por implementarlo en Scala; me refiero al algoritmo A*.

En vez de explicar qué hace específicamente el algoritmo, un googlazo o una búsqueda en Wikipedia proveen información más detallada al respecto. El problema a resolver era el famoso 8-puzzle, aquel cuadro con números del 1 al 8 en el que hay que ponerlos en orden:

El algoritmo A* aplicado a este problema lo pueden encontrar fácilmente con una búsqueda en internet, pero como yo quería practicar Scala (lenguaje que uso en mis proyectos) me puse a ver qué tal me quedaba. Solamente tuve un problema en el algoritmo: tuve que usar un mutable hashset (horror, lo sé), porque al usar uno inmutable el tiempo de ejecución se hacía muy largo. Si hay alguien por ahí que quiera optimizar el código, adelante. También implementé la solución de forma imperativa nada más para comparar.

Aquí el código. Recuerden que esto no es la mejor implementación, y que por ende, puede mejorar. Los heurísticos implementados son Manhattan Distance (distancia de un estado x a uno meta) Misplaced tiles (contar el número de cuadros que no están en su lugar. El segundo también lleva a la solución, pero tarda más en encontrarla. La función principal (solve) está optimizada como tail recursive para evitar un posible stack overflow. Además, van a ver muchos val quizá innecesarios que puse para darle legibilidad al depurarlo en el caso de que fuera necesario.

Sugerencias y comentarios son bienvenidos:

Continue reading 8-puzzle: Implementación sencilla de A*

Notas rápidas al trabajar con Access

Ignoremos el hecho de que Access es MALO, pero MALO con ganas. No tengo idea de por qué no hicieron las cosas en Oracle, pero también pasaremos eso por alto.

Una pequeña lista de problemas que me he encontrado al trabajar con esta aberración. Nota: estoy trabajando con Access 2010.

  • Las consultas que usan LIKE necesitan * en vez de %. Ejemplo:
    (Mal) Select nombre from agenda where name like ‘%Medina%’
    (Bien) Select nombre from agenda where name like ‘*Medina*’
  • Lo anterior es FALSO si la consulta se envía desde fuera (en mi caso, C#).
    A fuerzas necesita el %
  • No se puede hacer un join de tablas con campos de tipo “Memo” (no me pregunten por qué tengo que hacer joins con ese tipo de información :S).
    El tipo de datos “Memo” no guarda los datos en la tabla, sino en otro lugar y la tabla contiene solamente un apuntador a esos datos. Como SQL no sabe qué onda con apuntadores, te dice que no es posible hacer el join.
  • Al parecer, al crear una consulta directamente en SQL es necesario guardarla primero antes de ejecutarla si se quiere que Access respete la indentación que le dimos. No he comprobado esto al 100%, pero sí golpeé el monitor cuando abrí una mega consulta que hice y Access me mostró todo por ningún lado, mientras que otras sí las dejaba como las había formateado.
  • No se puede poner comentarios con “–” en el SQL que maneja Access. Horrible, si me permiten el comentario.
  • Access no aguanta hacer subqueries muy pesadas. Una consulta estilo:
    Select id from agenda 
    where nombre in (
        -- Una súper consulta incluyendo más subqueries, union, left outer join, etc.
    )

    hace que Access te diga “esa operación no se puede realizar en subqueries.

    La misma consulta en MySQL y PostgreSql corre sin problemas, por lo que el SQL está correcto.

Sé que soy un completo Noob en esto de Access, por lo que se aceptan sugerencias y correcciones.

Programando “de forma normal”

La semana pasada, y de hecho también este lunes, estuvo simplemente fatal. En el trabajo aplicaron la súper estrategia de meter a alguien en un proyecto del que no tiene idea de cómo está compuesto, y le echan trabajo que, como siempre, era para ayer, sin contar que todo está hecho en un lenguaje que ese alguien nunca ha usado y un juguete que simula ser una base de datos (léase “Access”). ¿Necesito decir que ese alguien era yo?

He trabajado en desarrollo de sistemas antes y sé lo que son los tiempos que se manejan en el proceso: nunca son reales y uno tiene que andar a la carrera para poder sacar “los pequeños cambios” que curiosamente salen después de que los requerimientos fueron tomados, aceptados y congelados. Pero quizá lo que más me sorprende es la reafirmación de que en muchos lugares el software que se usa para producción dista mucho de tener una calidad siquiera aceptable, y Japón no es la excepción. Cierto. He visto código que sí está bien hecho, con buen formato y con su respectiva documentación, pero son pocos los casos.

Lo que tocó hacer estaba en C# y la base de datos en Access… simplemente increíble. El código estaba bien estructurado, pero había funciones que realizaban más de una tarea y que eran enormes; comentarios totalmente inexistentes que hacían mucho más difícil de entender lo que el programador pensó al momento de codificar. Lo grave del asunto es que, después de tanto tiempo y de haber trabajado en 3 países, ya considero esto como normal puesto que entiendo que muchas veces se anda a las carreras con tal de cumplir con los tiempos establecidos aunque tu vida social desaparezca por ello.

Justo el buen panda me envió este artículo en el que se habla de lo que aquí comento, especialmente aplicado a programas que manejan acciones de empresas y de cómo pueden hacer perder millones por un simple error. Además de los tiempos, muchas empresas no toman en consideración las pruebas ya que representan un costo extra, y es casi verdad universal que quienes manejan las empresas piensan que con ver correr el prototipo de un sistema es suficiente para decidir si funciona o no.

Aclaro aquí algo: yo también he estado en la situación de que hay que acabar a como dé lugar sin importar cómo quede el código, y estoy seguro que mi forma de estructurar programas puede mejorar. En resumen: no me creo ni soy el mejor desarrollador del mundo. No obstante, estoy completamente seguro de que muchos me darían la razón si vieran el código del que estoy hablando.

De código de investigación ni hablamos. Me da pavor ver lo que hice durante mi estancia en la universidad…

Como quieran y gusten, terminé lo que tenía que hacer en el tiempo que me establecieron, pero para lograrlo me tuve que quedar hasta muy tarde en el trabajo (el lunes salí a las 11:30 pm y apenas alcancé tren a la casa). Sin embargo, hoy ha comenzado a otra parte del proyecto, y para los tiempos que manejan no me va a quedar de otra que echarme un clavado al código ya hecho, entender lo que hace (y viendo como hay valores que pasan por referencia, como las propiedades de los objetos están definidas como públicas… y mejor no le sigo) y reusar lo que sea posible. El problema a resolver es interesante, y de hecho me gustaría pensarlo en términos de probabilidad y hasta algoritmos como el Hill Climbing, pero todo indica que no tengo el tiempo que necesito para realizar el análisis que eso implica.

Con todo, es totalmente un placer decirles que la diferencia entre mi trabajo anterior y éste es como del cielo a la tierra. Compadezco a mis ex compañeros por tener que trabajar en una situación tan estresante.

Aquí seguimos.

 

Encuentra la diferencia – versión Kanji – en Scala

Y ya con este código dejo el tema por la paz. Lo pongo para que quede en el registro:

object Uniques {
  def main(a: Array[String]) {
    if (a.length != 1) {
      println("Need an argument to analyze")
      sys.exit(1)
    }
    else {
      findUniques(a(0)) match {
        case l if (l.isEmpty) => println("All characters are the same")
        case l => l foreach println
      }
    }
  }

  def findUniques(seq: String) =  seq filter {c => seq.count(_ == c) == 1} map {c => "Unique instance found: " + c + " in position " + (seq.indexOf(c) + 1)}
}

Y probando el caso en cuestión:

mmedina@yggdrasil-m:~/Programming/Scala/Tests$ scala Uniques "麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈 麈麈麈麈麈麈麈麈麈"
Unique instance found: 塵 in position 66

Hacerlo para que funcione con otros tipos de datos sin cambiar nada de código no es muy complicado.

Encuentra la diferencia – versión Kanji – en Haskell

Lo prometido es deuda. Siguiendo con el escrito anterior, aquí está el código que resuelve el problema, pero ahora en Haskell:

import qualified Data.ByteString as B
import qualified Data.ByteString.UTF8 as U
import System.Environment(getArgs)
import Data.List
import Data.Maybe

main = do
    putStrLn "Write the sequence you want to analyze:"
    B.getLine >>=  processArguments

processArguments :: B.ByteString ->  IO ()
processArguments xs = findUniques $ U.toString xs

findUniques = printUniques . findUniques'

findUniques' :: (Eq a, Show a) => [a] ->  [(a,Int)]
findUniques' xs = let uniques = filter (\i ->  countInstances i xs == 1) $ nub xs
                  in [(x,y) | x <- uniques, y <- mapMaybe (\i ->  i `elemIndex` xs) [x]]

printUniques :: (Eq a, Show a) =>  [(a,Int)] ->  IO ()
printUniques [] = putStrLn "All instances are the same"
printUniques us = mapM_ putStrLn $ map (\c →  ((("Unique instance: " ++ ) $ show $ fst c) ++ ) $ ((" in position " ++ ) $ show $ (+1) $ snd c)) us

countInstances :: (Eq a, Show a) =>  a ->  [a] ->  Int
countInstances _ [] = 0
countInstances c (x:xs)
    | c == x = 1 + countInstances c xs
    | otherwise = countInstances c xs

 

Es un hecho que puedo usar un where en la definición de printUniques, pero bueno, el caso es que funciona:

mmedina@yggdrasil-m:~/Programming/Haskell/FindDifference$ ./fdc
Write the sequence you want to analyze:
麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈
Unique instance: '\22645' in position 66

Todo muy bonito, sí. Pero entonces: ¿para qué tanto código en Haskell? Explico:

Continue reading Encuentra la diferencia – versión Kanji – en Haskell

Encuentra la diferencia – versión Kanji

Hace unos días, me llegó un retweet con lo siguiente:

【間違い探し☆超超超超上級編】 麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈 解けたらRT!

El punto es encontrar el kanji que es diferente, y al hacerlo, enviar el mensaje en un RT. Según el principio del mensaje, este problema es de nivel súper-súper-súper-súper avanzando.

“Buena forma de pasar el tiempo”, pensé, pero no para resolverlo “a mano”, sino creando un programa que lo hiciera por mí.

Viendo mis opciones, decidí programar el algoritmo en Python, tanto como práctica como para seguir dándome de topes por lo de las string unicode vs byte strings (quienes saben python entienden a lo que me refiero).

En sí, el algoritmo es sencillo, así que no tomó mucho tiempo:

# -*- coding: utf-8 -*-

import sys

def searchDifferentKanji(strseq):
    utf8Str = unicode(strseq,"utf-8")
    difstr = list(set(utf8Str))

    for c in difstr:
        if utf8Str.count(c) == 1:
            return c.encode("utf-8"), utf8Str.index(c) + 1

    return '',-1

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print "Error: Need a string to check"
        exit(1)
    else:
        difchar, pos = searchDifferentKanji(sys.argv[1])
        if pos != -1:
            print "Different char: " + unicode(difchar,"utf-8") + " in position " + str(pos)
        else:
            print "All characters are the same"

Lo que hago es simple: creo un set a partir de la cadena, haciendo con esto que todos los elementos repetidos se esfumen, y lo convierto a lista, la cual contiene exactamente un carácter por cada carácter diferente en la cadena original. Después recorro esa lista buscando en la cadena si el elemento actual aparece una sola vez; de ser así, es el carácter que estoy buscando, por lo que lo regreso, junto con la posición en la que está.

Existen problemas similares que contienen más de una diferencia, es decir: entre un mar de repeticiones del mismo carácter se encuentran varios diferentes. Para resolverlos, el algoritmo arriba expuesto puede ser sencillamente modificado para que no rompa el ciclo con el primer carácter diferente que encuentre, y agregue la tupla de (carácter,posición) a una lista, que sería el valor que la función “searchDifferentKanji” regresaría.

Como nota adicional, el kanji de ese problema es , que se lee 「しゅ」(shu), y conlleva el significado de “ciervo grande”. El kanji diferente es , con varias lecturas, entre ellas las más comúnes 「ちり」 (chiri), que significa “polvo”, “basura” y 「ごみ」(gomi), que también significa “basura”.

Sí: me queda de tarea hacerlo en Haskell.

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)