miércoles, marzo 06, 2013

var self=this is not lame!

A few weeks ago I came across this article: http://ngauthier.com/2012/04/var-self-equals-lame.html and then I thought: "OK, let's follow this stranger's advice, I don't want to be lame!".

But what was really lame was to change my coding style just because other person said so. After thinking a little bit about it and writing some code; I found that the reasons given in the aforementioned article weren't very good...
  • Intent. self is totally unambiguous, and when you see a self it's very clear that it refers to a lexically scoped variable rather than a variable that might change at runtime.
  • Self-completeness. Why is 'leaning on a well tested library' good, when you could be using a core language feature instead?
  • Brevity. Oh, a one liner. SLOC's is the most simplistic (and usually wrong) metric for code complexity. Let's take another approach and count levels of nested parens and braces instead! I prefer reading two lines containing simple statements over a complex expression almost every time, because our brain handles poorly deep nesting.
  • Dangling code. I have to agree in that, but that's a minor problem and cleaning up unused variables is a task that we all have to face when refactoring code.
And there are some very good reasons to prefer self=this over bind(this):
  • Debugging. What do you see if you inspect a callback function variable that has been bound? This: function () { [native code] }. You don't get any information about which function is it, because all you see is a native code wrapper.
  • Nested callbacks. You have to bind two functions, even if you just use this in the inner callback.
  • "this" as as part of the callback API. Some callbacks will set a useful value for "this" (like the receiver of an event, or the current element in $.forEach); what if you want to use it?
So, emotional statements (like "don't do that, it is lame!") don't really belong to science or programming, as they bias your criteria. Avoid them.

viernes, febrero 15, 2013

Functional pagination (or CPS iterator pattern)

I know that I promised to write about Javascript... Not yet, but I'm almost there.

I’ve been thinking about implementing a purely functional pagination scheme for a product picker I’m working on… The motivation is that writing asynchronous code that manipulates mutable state is not to my taste.

Instead of having around the current offset counter, I’ve thought that each callback can receive (besides the data) two extra functions: one that returns the previous page and another that returns the next page (if any).

The widget is written in Javascript, which is great because you don’t have declare recursive function signatures, but you still need to use them without making any mistakes. To be sure of what I’m going to implement is not nonsense, I wrote a toy example in Scala before diving in:

import scala.collection.immutable.Range

object sandbox {

  trait PaginatedCallback[T] {
    def apply(results: List[T],
      prev: Option[PaginatedCallback[T] => Unit],
      next: Option[PaginatedCallback[T] => Unit])
  }

  def feed(callback: PaginatedCallback[Int]) = {
    def page(p: Int)(cb: PaginatedCallback[Int]): Unit = {
      val prev = if (p > 0) Some(page(p - 1)_) else None;
      val next = if (p < 10) Some(page(p + 1)_) else None;
      val results = Range(p * 10, (p + 1) * 10) toList;
      cb(results, prev, next)
    }
    page(0)(callback)
  }

  object printAll extends PaginatedCallback[Int] {
    def apply(results: List[Int],
          prev: Option[PaginatedCallback[Int] => Unit],
          next: Option[PaginatedCallback[Int] => Unit]) = {
      
      println(results);
      next match {
       case Some(cb) => cb(printAll)
       case None => println("finished")
      }
    }
  }
  
  feed(printAll)
  //> List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  //| List(10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
  //| List(20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
  //| List(30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
  //| List(40, 41, 42, 43, 44, 45, 46, 47, 48, 49)
  //| List(50, 51, 52, 53, 54, 55, 56, 57, 58, 59)
  //| List(60, 61, 62, 63, 64, 65, 66, 67, 68, 69)
  //| List(70, 71, 72, 73, 74, 75, 76, 77, 78, 79)
  //| List(80, 81, 82, 83, 84, 85, 86, 87, 88, 89)
  //| List(90, 91, 92, 93, 94, 95, 96, 97, 98, 99)
  //| List(100, 101, 102, 103, 104, 105, 106, 107, 108, 109)
  //| finished
}

I think it’s quite neat.

It took me a while to think, but once I wrote it, it just worked. I’m sure I wouldn’t have got it right in Javascript without a little trial and error.

domingo, julio 22, 2012

Renombrando canciones 2.1

Venga, vamos a darnos otra chuta de Python antes de pasar a Javascript...

El otro disco que me bajé tenía las canciones sin los números. Seguramente estarían en los tags id3, pero es algo que me da mucha pereza, así que miré el orden de las pistas en Amazon y me hice otro script ^_^

Este recibe como argumentos dos ficheros, uno con el listado de pistas de Amazon (copiado de la tabla usando ctrl+seleccionar)

  1. Half Remembered Dream
  2. We Built Our Own World
  3. Dream Is Collapsing
  4. Radical Notion
  5. Old Souls
  6. 528491
  7. Mombasa
  8. One Simple Idea
  9. Dream Within A Dream
10. Waiting For A Train
11. Paradox
12. Time

y otro con el nombre de los archivos:

528491.mp3
Dream Is Collapsing.mp3
Dream Within A Dream.mp3
Half Remembered Dream.mp3
Inception Teaser Trailer.mp3
Mind Heist.mp3
Mombasa.mp3
Old Souls.mp3
One Simple Idea.mp3
Paradox.mp3
Projections (bonus track).mp3
Radical Notion.mp3
Time.mp3
Waiting For A Train.mp3
We Built Our Own World.mp3
y se encarga de emparejarlos según cuáles sean más parecidos usando el Longest Common Substring (por lo que debería ser robusto ante pequeños cambios).


#!/usr/bin/env python

import sys
import itertools
import functools
from collections import defaultdict

allchars = (chr(i) for i in range(256))
table = ''.join(x.lower() if x.isalnum() else ' ' for x in allchars)

def memoize(obj):
        cache = obj.cache = {}
        @functools.wraps(obj)
        def memoizer(*args, **kwargs):
                if args not in cache:
                        cache[args] = obj(*args, **kwargs)
                return cache[args]
        return memoizer

@memoize
def lcs(ra, rb):
        if not (ra and rb):
                return 0
        elif ra[0] == rb[0]:
                return 1 + lcs(ra[1:], rb[1:])
        else:
                return max(lcs(ra[1:], rb), lcs(ra, rb[1:]))


def make_all_pairs(group_a, group_b):
        def rank(a, b):
                h = lcs(a.translate(table), b.translate(table))
                return 2.0*h/(len(a) + len(b))

        for ia, a in enumerate(group_a):
                ib, b = max(enumerate(group_b), key=lambda (_, b): rank(a, b))
                yield ia, ib


def format_pairs(number_name, file_ext):
        numbers, track_names = zip(*number_name)
        numbers = map(int, numbers)
        track_names = map(str.strip, track_names)
        file_names, exts = zip(*file_ext)
        for t_i, f_i in make_all_pairs(track_names, file_names):
                print 'mv "%(fname)s.%(ext)s" "%(n)02d - %(tname)s.%(ext)s"' % {
                        'fname' : file_names[f_i],
                        'ext' : exts[f_i],
                        'tname' : track_names[t_i],
                        'n' : numbers[t_i]
                }

tracks, files = (map(str.strip, open(x).readlines()) for x in sys.argv[1:])

number_name = [x.split('.',1) for x in tracks]
file_ext = [x.rsplit('.', 1) for x in files]

format_pairs(number_name, file_ext)

sábado, julio 21, 2012

Renombrando canciones 2.0

Hoy necesitaba mi viejo script para renombrar canciones y el cabroncete me ha dejado un poco tirado, no borraba completamente el autor que estaba repetido en todos los nombres de los ficheros (era "Hans Zimmer & James New Howard" y sólo se cargaba el "Hans").

Como no me apetecía una puta mierda ponerme a depurarlo (el código tiene ya 7 años y los bits se van pudriendo), me he dicho, ¿a ver cómo lo reescribiría siendo un poco más viejo?

El resultado es este:


#!/usr/bin/env python
import sys

allchars = (chr(i) for i in range(256))
table = ''.join(x if x.isalnum() else ' ' for x in allchars)

def remove_common_tokens(tokenized_lines):
        common = reduce(set.__and__, map(set, tokenized_lines))
        is_unique = lambda x: x not in common
        return [filter(is_unique, line) for line in tokenized_lines]

originals = map(str.strip, sys.stdin)
names, extensions = zip(*[x.rsplit('.',1) for x in originals])
tokenized_lines = [x.translate(table).title().split() for x in names]
unique_tokens = remove_common_tokens(tokenized_lines)
numbers = [str(int(x[0])).zfill(2) for x in unique_tokens]
new_names = [' '.join(x[1:]) for x in unique_tokens]

for original, number, new_name, extension in zip(originals, numbers, new_names, extensions):
        print 'mv "' + original + '" "' + number + ' - ' + new_name + '.' + extension + '"'

A tope. Lo que antes me llevaba 88 líneas ahora me lleva 21.  Soy un 25% más vago. Evidentemente tiene un bug (es el precio de ahorrar tanto), pero me la suda.

La mejora más aparente es que he eliminado toda la morralla de eliminar las partes iguales con un método más compacto y agresivo: cogemos todos los tokens comunes (independientemente de dónde estén) y nos los cargamos. El bug está ahí, si da la casualidad de que hay una palabra legítima que se repite en todos los títulos (como podría ser "of" por ejemplo), pues va a ir a tomar por culo también.

El resto sigue siendo más o menos igual, vamos aplicando transformaciones (tokenizar, sacar las extensiones y los números, eliminar partes repetidas, etc.) y al final componemos el resultado.

Algo gracioso que ha cambiado con la edad es que antes sólo usaba comillas dobles para los literales de strings (manías de Java, supongo), ahora suelo usar las simples.

Mi relación con map y filter es un poco de amor odio. Recuerdo que mi primera versión tiraba bastante de map, pero luego lo reescribí para usar list comprehensions. Ahora uso lo que sea más corto, si ya tengo la función definida, pues suelo tirar de map, si tengo que hacer un map y luego un filter seguramente use una comprehension que queda más clara, etc.

Sobre reduce la verdad es que no le suelo encontrar mucho uso, porque las reducciones típicas son sum y str.join y ya están los built-in, pero aquí por ejemplo tenía que encontrar la intersección de unos cuantos sets y me parecía mucho más elegante usar reduce que un bucle con acumulador.

En el próximo post (espero que en una semana o así) seguramente cuelgue algo de código en... ¡Javascript! quién me lo iba a decir a mí después de tantos años.

viernes, abril 13, 2012

Productos de mierda que triunfan: hoy Whatsapp

Siempre me ha fascinado qué es lo que hace que un producto de mierda tenga éxito, aún cuando existen alternativas claramente mejores en todos los aspectos mesurables.

Sin duda, los factores más determinantes son la inercia y la estupidez humana.

Recuerdo cuando hace tiempo hice jabber advocacy en este mismo blog. Ahora, más de 7 años después, me encuentro con algo parecido, pero en los móviles. El puto Whatsapp. ¿Por qué lo usamos (yo me incluyo)?

Mi razón es sencilla: porque es lo que usan mis amigos. Supongo que el 99% de la gente tiene el mismo motivo y habrá entre un 20% o 30% de personas que son conscientes de que es una mierda, pero se resignan.

El motivo más sangrante es que realmente es una aplicación de pago que te quieren hacer pasar como gratuita (durante el primer año lo es). Hacen que seas dependiente de su servicio, te agarran por los cojones y luego te lo cobran. Eso está muy feo.

Pero claro, ¿qué es lo que pasa cuando se lo intentas explicar a la gente? ¡Que te toman por un pirado de esos que años atrás mandaban correos en cadena diciendo que Andy y John iban a hacer de pago el MSN Messenger! Es un poco como el cuento de Pedro y el lobo, con la diferencia de que yo también era el imbécil que se molestaba en intentar educar a la gente en contra de los correos en cadena sin fundamento.

Si usted, querido lector, quiere estar seguro de que esto que digo es cierto, sólo tiene que ir a Settings/Account Info y leer lo que pone.

Otras cosas que me fastidian son las limitaciones absurdas:
  • El número de usuarios en un grupo. 10 es un número muy bajo y arbitrario, yo ya tengo 2 grupos llenos a los que colegas han pedido unirse tarde y se han tenido que quedar fuera.
  • El no poder usarlo en dos móviles distintos (tengo un número español y otro inglés y tengo que tener dos cuentas de la mierda esa)
  • Tampoco poder utilizarlo en algo que no sea un móvil. Me siento realmente estúpido cuando estoy delante del ordenador y tengo que contestar usando el móvil, tardando unas 10 veces más de lo que tardaría en escribirlo con el ordenador.
  • Tamaños de los archivos... Ten cuidado al grabar vídeos para enseñárselos a los colegas, porque a la mínima ya te dice que son demasiado grandes.
Por no hablar de que el servicio tampoco es que sea una maravilla de fiabilidad.

Así que voy a intentar tocarle los cojones todo lo posible a mis contactos para que usen Gtalk, o cualquier otra alternativa que sea mejor y encima gratis.

jueves, enero 19, 2012

a tomar por culo megaupload

Hace unos días estaba pensando en qué estúpidos fuimos los usuarios dejando morir los sistemas de intercambio de archivos p2p, por la comodidad que suponían los sitios de descarga directa.

Estoy pensando que incluso haya podido ser una buena jugada para los lobbies "anti-piratería" el éxito tan brutal que han tenido sitios como megaupload, fileshare, etc. Es mucho más fácil cerrarlos. Ahora a ver quién es el guapo que se vuelve a instalar el emule.

lunes, enero 16, 2012

Esta foto me intriga

sarkozy-rajoy.jpg

¿No os parece curioso el contraste entre las caras de Sarkozy y Rajoy? Yo creo que el franchute está pensando "Joder, ¿por qué tengo que ser el presidente más bajito de la Unión Europea?"... O algo peor.

jueves, enero 05, 2012

¿Por qué nos dicen que reiniciemos el ordenador cuando se queda colgado?

¡Feliz año nuevo!

Acabo de ver un vídeo de esos divulgativos (o mejor dicho: vulgarizantes) que "explica" por qué se cuelgan los ordenadores y por qué ctr+alt+del sirve para reiniciarlos :-|

Aquí lo tenéis para echaros unas risas http://www.elmundo.es/elmundo/2011/11/24/ciencia/1322158317.html

Como este blog siempre ha tenido vocación de culturizar al personal (aunque también me vanaglorio de que mis lectores son la hostia y no necesitan ser culturizados), vamos a proceder a intentar arreglar el desaguisado que comete este hombre con su "hesplicasion".

Lo más absurdo es empezar atribuyendo una única causa a los cuelgues y pensar que hay un único tipo de cuelgue. El cuelgue que parece preocupar a nuestro catedrático parece ser simplemente que el ordenador se ralentice cuando hay muchos programas abiertos, por lo visto este hombre nunca ha visto un BSOD (pantallazo azul de la muerte por sus siglas en inglés), o se le ha quedado el ordenador tan tostado que ni siquiera responde al sortilegio de ctrl+alt+del... Y también piensa que los Unix están hechos a prueba de bombas: no señor, también se cuelgan.

Vamos a identificar las barbaridades que dice el amigo:

Empecemos por la memoria caché, que parece que según este hombre es el origen de todos los males, la pobre. La caché es un tipo (conceptualmente) de memoria que sirve para guardar cosas que vas a usar más adelante.

La más famosa es la caché de los procesadores, que se suele dividir en dos tipos funcionales (de datos y de instrucciones); pero realmente podemos considerar que la RAM puede hacer de caché del disco duro (ya que es más rápida), o el disco duro puede hacer de caché de datos en la red, etc

El problema es que este señor está confundiendo "la caché" (como si sólo hubiese una) con varias cosas:
  • Memoria swap: este es el espacio de disco destinado para simular que tenemos más memoria RAM de la que físicamente disponemos.
  • Cola de eventos: es una estructura de datos donde se van guardando las acciones del usuario (pulsaciones de teclas, movimiento del ratón) para su posterior procesado.
El problema que describe en su segundo intento de aclarar las cosas (http://www.elmundo.es/elmundo/2011/11/26/ciencia/1322320450.html y por cierto, caché viene del francés, no del inglés) está relacionado con el swap y es lo que técnicamente se conoce como Hiperpaginación. Básicamente es que el working set (que es como se llama a la memoria que están usando los procesos activos) es mayor que la memoria física de la que disponemos, por lo que el sistema necesita mover páginas de memoria (una página es simplemente un cacho de un tamaño fijo) entre la RAM (que es rápida pero no muy grande) y el disco duro (que es muy grande pero no muy rápido).

Esto ocurre en todos los sistemas operativos con memoria virtual y swap si se "fuerzan". Ya sean Unix o Windows. Lo único que se puede hacer para evitarlo es:
  • Prescindir del swap y si el sistema se queda sin memoria matar procesos para liberarla.
  • Aumentar la RAM (pero no lo va a solucionar definitivamente, eventualmente podemos volver a llenarla si abrimos muchos procesos).
  • Usar una configuración del planificador del sistema menos interactiva, para que los cambios de proceso sean menos frecuentes (aunque esto causará que la sensación sea de que el ordenador responde peor ante cosas como movimientos del ratón)... Y tampoco es una solución definitiva, únicamente hace que el tiempo perdido moviendo páginas entre el disco y la RAM sea menor en proporción al tiempo útil de proceso.
Volvamos al tema de lo que es un verdadero cuelgue. Cuando el ordenador deja de responder de verdad, no hay ni siquiera huevos de que funcione el teclado y lo único que nos salvará es darle al botón de reset (o liarse a patadas con la caja e irnos a vivir a un monasterio).

Un ordenador es una de las creaciones más complejas jamás diseñadas por el ser humano. Para que nos hagamos una idea, la Torre Eiffel, una imponente obra de ingeniería, tiene unos 2.600.000 tornillos y unos 18.000 bloques de metal. El primer procesador Pentium (de 1993) ya tenía unos 3.000.000 de transistores, y ese número se ha ido doblando cada 18 meses aproximadamente (la llamada Ley de Moore). Actualmente un Xeon de 10 cores tiene unos 2.600.000.000 transistores.

Y al contrario que la Torre Eiffel, un procesador no es algo estático, tiene un comportamiento dependiente del tiempo (por eso llevan un reloj que va marcando el ritmo a altísimas velocidades, del orden de Gigahertzios=miles de millones de veces por segundo).

Así que es sencillo de comprender lo fácil que resulta que algo vaya mal en esa maraña electrónica miniaturizada. Por suerte los diseños de hardware suelen estar bastante acotados en lo que pueden hacer y se pueden hacer pruebas aisladas, por lo que si hay defectos no suelen ser de diseño (que también los puede haber), sino en el proceso de fabricación (es difícil que de una oblea no salga algún bicho defectuoso, por suerte, la mayor superficie suele estar destinada a memorias caché [esta vez sí], con lo que desactivando parte de ella se pueden salvar muchos micros pasándolos a una gama inferior).

Luego está el dichoso software. Aquí es donde empiezan los problemas serios. Porque al fin y al cabo, a pesar de que el nivel de integración del hardware es brutal, en gran parte se trata de bloques idénticos replicados (aunque también tiene su miga), es decir, que tener 1MiB de caché no hace el chip esencialmente más complejo que uno que sólo tenga 256KiB. Sin embargo, el software es distinto, porque no está acotado por una estructura física donde colocarlo; su única limitación es el pensamiento humano... Y el pensamiento humano puede ser muy enrevesado (y en muchas ocasiones defectuoso).

Espero que esto haya servido para hacernos una idea de la magnitud del asunto que tenemos entre manos.

Centrémonos ahora en el Sistema Operativo. En los tiempos del MS-DOS, el sistema operativo realmente no tenía mucho que hacer, puesto que como no había múltiples usuarios ni múltiples procesos simultáneos, cuando ejecutábamos un programa tenía prácticamente acceso total a todo el ordenador. Hoy en día no es así, el PC es un pequeño ecosistema donde conviven cientos (y hasta miles) de programas ejecutándose simultáneamente. Para que no se den de hostias entre ellos, el Sistema Operativo tiene que mediar entre ellos, para dar acceso ordenado a cada uno de los recursos.

Ahora vamos a analizar los 5 tipos de errores (bugs) típicos que hacen que un programa falle:

  • Acceso a una dirección de memoria incorrecta.
  • Desbordamiento de pila.
  • Intentar ejecutar una instrucción incorrecta.
  • Excepción no tratada (e.g. dividir entre cero).
  • Entrar en un bucle infinito.
Los cuatro primeros errores harán que el programa se detenga inesperadamente y que el Sistema Operativo le dé matarile sin más. En el último, el Sistema Operativo no tiene manera de saber si ese comportamiento es normal o anómalo (hay programas que están diseñados para no terminar nunca), así que es responsabilidad del usuario identificarlos y matarlos.

A esa lista podríamos añadir otro tipo de errores lógicos, que si bien no harán que el ordenador explote, harán que funcione de forma errática. Los más típicos son las race conditions, que son interacciones inesperadas entre software que se ejecuta de forma concurrente (esto está a la orden del día en cuanto intentas escribir código paralelo a no ser que te andes con pies de plomo).

Pues bien, el pobre Sistema Operativo no está exento de esos errores de programación. Quizá algo menos que el resto de programas, porque están diseñados y programados por los mejores profesionales del mundo; pero cualquier pequeño fallo es más evidente porque si el Sistema Operativo falla, el ordenador entero se suele colgar: no hay nadie más que tome las riendas.

Y por muy robustos que sean los sistemas operativos según vienen de fábrica, siempre hay algún driver chapucerillo que puede cargarse la integridad del mismo. Este es uno de los mayores puntos a favor de Linux (y MacOS) en cuanto a estabilidad frente a Windows. En Windows, cada vez que instalamos el driver de algún cacharrito que hemos comprado en los chinos (como una webcam, por ejemplo), estamos dejando que nuestro ordenador ejecute con todos los privilegios código escrito por vaya-usted-a-saber-quién, que si tiene algún bug es posible que nos fastidie el ordenador, porque los drivers se ejecutan (casi todos) en el mismo espacio de memoria que el sistema operativo y con sus mismos permisos. En el caso de Linux, la mayoría de los drivers están integrados en el código del propio kernel y están bastante bien auditados, por lo que las fuentes de fallos son menores. Para Mac, ni que decir queda que sólo hay drivers para el hardware que pasa por la caja de Cupertino y ya se encargan ellos de que funcione bien.

Hay algunas técnicas para incrementar la fiabilidad de los sistemas operativos, como ejecutarlos en máquinas virtuales o los basados en micro-kernels, pero desgraciadamente traen aumentos de complejidad en las interrelaciones entre componentes que pueden ser también fuentes de bugs.

Así que queridos lectores, como véis no es un tema sencillo ni mucho menos que se pueda explicar en un momento, de ser así los ordenadores seguramente no se colgarían tanto. Pero lo más importante es que no es lo mismo una degradación del rendimiento debido a un uso intensivo o excesivo que un error en el software o en el hardware. El primero se suele solucionar dejándole tiempo para que algunas tareas terminen o matándolas directamente con el task manager (no hace falta reinicar el ordenador normalmente), ante lo segundo lo único que podemos hacer es cruzar los dedos para que no nos toque o que saquen un parche lo antes posible.

lunes, noviembre 28, 2011

Leyendas urbanas sobre el JPEG

Una amiga me comentó hace poco que un profesor suyo le había dicho que la calidad de las imágenes guardadas en JPEG se degradaba cada vez que se abrían para visualizarlas.

Le expliqué que es cierto que las imágenes en JPEG pierden calidad, pero sólo cada vez que se escriben. Me quedé pensando un momento en mis días de la universidad, en la transformada del coseno y en su puta madre, y pensé que seguramente llegaría un punto en el que después de codificar y decodificar varias veces en cadena una imagen, se llegaría a un punto fijo, en el que no se perdería más calidad.

Me daba bastante pereza ponerme a probarlo, pero al final tiré de scripting en Python una vez más y he aquí los resultados:



import Image
import ImageMath
import sys

def main():
    prefix, suffix = sys.argv[1].split('.')

    prev = Image.open(sys.argv[1])
    go_on = True
    i = 0
    while go_on and i < 100:
        name = prefix + str(i) + '.' + suffix
        print 'name=',name
        prev.save(name)
        next = Image.open(name)
        diff = ImageMath.eval('abs(float(a) - float(b))', a=next, b=prev)
        go_on = tuple(next.getdata()) != tuple(prev.getdata())
        prev = next
        hist = diff.histogram()
        i += 1
        print hist


if __name__ == "__main__":
    sys.exit(main())

El programilla va imprimiendo el histograma de la diferencia entre dos imágenes consecutivas y se para cuando todos los píxels están a cero. Probando con un par de imágenes, parece que el punto fijo se alcanza tras unas cuantas iteraciones, entre 8 y 40. Así que no temáis demasiado por una degradación sin límites de vuestras fotos si las andáis retocando sobre los JPEGs, aunque nunca está de más guardar los originales en RAW, TIFF o PNG.

lunes, noviembre 21, 2011

Elecciones 2011

Son los mismos de siempre, nada va a cambiar.

domingo, noviembre 13, 2011

Otra de exploración de árboles de palabras

El lunes pasado se cayó Internet en el curro. Mientras yo estaba con mis pajas mentales, mis queridos compañeros nerds se empezaron a aglomerar en torno a un ordenador. Para no desentonar, me acerqué yo también y pregunté que qué regalaban.

Resultó que estaban jugando con un programita de consola (no me refiero a xbox ni ps3, sino a terminal de texto) que muestra una parrilla con letras y nosotros tenemos que introducir todas las palabras inglesas que se puedan formar con las letras siguiendo un camino de casilla en casilla.

Acordándome del mítico post sobre El Melenas de Cifras y Letras y de cómo le quité la gracia al juego del facebook de hacer anagramas, decidí que iba petarlo en cuanto volviese Internet y pudiese descargarme la lista de palabras inglesas...

Total, que como buen procrastinador, me puse a hacer mi script en Python, que ahora pasaré a explicar:

from itertools import product
import sys

# not much shorter, but much funnier to write than
# [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
# at first I used range(-1,2), but (-1,0,1) is cleaner and shorter
neighbours = [(i,j) for i,j in product(*[(-1,0,1)]*2) if i or j]
allow_repeat = True

def make_tree(words_list):
        base = {}
        for word in words_list:
                d = base
                for c in word:
                        if c not in d:
                                nd = {}
                                d[c] = nd
                                d = nd
                        else:
                                d = d[c]
                d[None] = None # complete word marker
        return base

def parse_matrix(text):
      return map(str.upper, filter(None, (filter(str.isalpha, line) for line in text)))

def is_valid_and_prefix(d, word):
        for c in word:
                if c not in d:
                        return False, False
                else:
                        d = d[c]
        valid = None in d
        prefix = len(d) > valid # more keys than None
        return (valid, prefix)

def successors(word, path, matrix):
        i,j = path[-1]
        for di, dj in neighbours:
                ni, nj = i+di, j+dj
                if (ni >= 0 and nj >= 0 and
                    ni < len(matrix) and nj < len(matrix[ni]) and
                    (allow_repeat or (ni,nj) not in path)):
                        successor = word + matrix[ni][nj], path + [(ni,nj)]
                        yield successor

def find_words(d, path, word, matrix):
        valid, prefix = is_valid_and_prefix(d, word)
        if valid:
                yield word
        if prefix:
                for nw, np in successors(word, path, matrix):
                        for x in find_words(d, np, nw, matrix):
                                yield x

if __name__ == '__main__':
        wordlist = sys.argv[1]
        tree = make_tree(x.upper().strip() for x in open(wordlist))
        matrix = parse_matrix(sys.stdin.readlines())
        words = set()
        for i,j in product(range(len(matrix)), range(len(matrix[0]))):
                c = matrix[i][j]
                words |= set(find_words(tree, [(i,j)], c, matrix))
        for w in sorted(words, key=len):
                print w

Para usarlo, recibe como primer y único argumento el nombre del fichero con el corpus de palabras válidas y lee por la entrada estándar la "sopa de letras" (de la cuál descartará cualquier caracter que no sea alfabético, así que puede estar formateada como os dé la gana).

¿Cómo funciona el jodío? Pues muy fácil, esta vez en lugar de construir un hash de las palabras que ignorase el orden de aparición de las letras, nuestra estructura de consulta es un arbolito (como bien indica el nombre de la función make_tree).

Este arbolito es básicamente un puñado de diccionarios (no en el sentido de RAE, sino tablas asociativas) anidados, en el cuál la clave es una letra y el valor, pues otro diccionaro. Hay un caso especial en el que algunos diccionarios tendrán una entrada None:None.

Para saber si una palabra está en el diccionario (esta vez sí, en el sentido de RAE, Collins, Oxford, etc.), tenemos que ver si podemos llegar a un nodo que tenga una clave None pegando saltitos por las ramas que tengan como clave cada letra de nuestra palabra de forma consecutiva. Esto es lo que hace la función is_valid_and_prefix, que además nos dice si la palabra es un prefijo de otras.

A partir de aquí es pan comido, sólo tenemos que hacer el típico backtracking por las casillas de la rejilla, podando cuando lleguemos a palabras que no son prefijo de ninguna y devolviendo aquellas que sean palabras completas. Los generadores de Python ayudan mucho para escribir este código de forma elegante.

Posibles optimizaciones:
  • Reemplazar los diccionarios por alguna otra estructura más compacta en memoria, ya que buscar linealmente entre un máximo de 28 caracteres seguramente sea más eficiente que un hash lookup.
  • Pasar sólo el sub-árbol con los sufijos de la palabra que estamos explorando en cada nivel de la búsqueda... No es que vaya a ser una gran diferencia, pero si ya estamos seguros de que vamos por un prefijo válido ¿para qué comprobarlo otra vez?
Lo más gracioso es la cantidad de palabras que se pueden formar con una matriz pequeñita si permitimos repetir casillas. Para probar, usé esta matriz de entrada (sí, ya sé que tiene algunas palabras muy obvias):

DONE
OIRT
PASS

¿Y a que no sabéis cuántas palabras había escondidas? 848.

martes, noviembre 08, 2011

Rock Estatal

Hace un buen puñado de años, cuando había una tienda Tipo en la C/Fuencarral a la que solía ir a mirar discos con algunos colegas; siempre me sorprendía ver la sección de "Rock Estatal", donde estaban todos los grupos chungos del país.

Aún a día de hoy podemos ver tamaña lerdez en su web:


¿Tanta es la aversión que tienen los guarros a palabras como español o nacional que llegan a utilizar otras que no vienen al caso?

Porque tampoco hace falta ser un erudito (basta con echarle un vistazo al diccionario o haber prestado un poquito de atención en clase cuando explicaban la diferencia entre país, nación y estado en lugar de estar fumando porros) para saber que el Estado es la estructura política y organizativa, el gobierno, la policía, los jueces y todas esas cositas que tanto les gustan nuestros amigos los punkis.

Ya me los imagino yendo a un bar, pidiendo un whisky y cuando el camarero pregunta ¿Nacional o importación? responden muy ufanos: Estatal. Pero como el Tito Fortran siempre ha tenido vocación didáctica, os voy a dar algunos sinónimos para que no os salgan sarpullidos y no hagáis el gilipollas: autóctono, local, de la tierra, patrio, vernáculo (qué grande sería pedir un güisqui vernáculo para que luego te pongan un puto DYC)...

Mientras tanto, tenemos a los panderetas de Rajoy y Rubalcaba diciendo más chorradas en la tele. La verdad es que no estoy viendo el debate, pero me la suda, porque sé de sobra de lo que están hablando, porque ya lo he visto cientos de veces. Estarán echándose mierda el uno al otro, Rajoy dirá que hay paro y estamos en crisis, Rubalcaba hablará de los años del gobierno de Aznar, Rajoy le hablará del gobierno de Zapatero, hablarán de ETA para intentar sumarse puntos, etc.

En fin, cuánta mierda por todas partes.