Activa las notificaciones para estar al tanto de lo más nuevo en tecnología.

Programación lúdica: ¿Cuántas palabras diferentes tiene “El Quijote”?

Una obra monumental de la literatura española es el Quijote, escrito por Miguel de Cervantes hace ya muchos años. Se tienen versiones impresas en rústica,...

quijote00

Una obra monumental de la literatura española es el Quijote, escrito por Miguel de Cervantes hace ya muchos años. Se tienen versiones impresas en rústica, en pasta dura, en ediciones de lujo, etcétera. Desde luego que en formato electrónico hace rato que está y el Quijote puede leerse en formatos PDF, ePub y en textos normal, sin formato especial, pues.

Después del reto pasado, el de contar palabras, en donde se usaron dos libros unidos (Los Miserables y el Quijote), para hacer un archivo relativamente grande (unos 5 MBytes), se me ocurre ahora plantear el siguiente problema: Tomemos el archivo del Quijote (el cual puede descargarse de este sitio), y la tarea a resolver, es la de hacer una lista de todas las palabras diferentes que tiene la obra de Cervantes y la frecuencia de las mismas (ordenado alfabéticamente). ¿Cuál será la palabra más veces escrita por el manco de Lepanto? ¿Cuál será la palabra que solamente se escribió una sola vez? Estas dudas no me dejan dormir.

Aquí tomaremos en cuenta dos criterios: el primero será el de la velocidad, es decir, qué programa llega a hacer esta lista (que se debe guardar en un archivo de texto) de manera más rápida y el segundo, que dé la frecuencia de cada palabra usada. El resultado debe entregarse mostrando por línea la palabra hallada y al lado, la frecuencia de la misma, es decir, las veces que ocurrió en el texto. Los criterios se toman en cuenta de forma indistinta. Por ejemplo, alguien puede entregar un programa que halla todas las palabras y sus frecuencias, y se tarda 2 minutos (por decir algo), mientras que otro entrega un programa que es muy veloz, pero que no entrega todas las palabras o que el conteo está mal. Evidentemente el ganador será aquí el que entregue el resultado más cercano al que debe ser.

Las restricciones usuales en el reto son: No se vale usar una biblioteca para hacer búsquedas, ordenar, o cualquier otra labor que sea parte del reto, es decir, solamente puede usarse el lenguaje tal cual viene definido con las bibliotecas de entrada/salida, por ejemplo.

Cabe señalar que el reto no es sencillo, porque antes de empezar hay que discurrir qué estructura de datos vamos a usar. De acuerdo a Word (e incluyendo los anuncios legales del Proyecto Gutenberg), el Quijote contiene unas 384,262 palabras. Pensemos, solamente para ilustrarlo, que todas ellas fuesen diferentes (que no es cierto), y que cada palabra ocupa unos 10 caracteres en promedio (suena razonable asumir eso), tendríamos que tener una estructura que conteniera  unos 4 MBytes, cosa que no es muy complicada. A eso hay que añadirle el conteo de las palabras, lo cual debe ponerse de alguna manera. Por favor, no se les ocurra hacer un arreglo de 4 MBytes para contener palabras y números. Eso, aunque s epueda hacer y el compilador no proteste, no es una técnica aceptable de programación. En mi opinión, hay que hacer un árbol de registros que contengan, las palabras y la frecuencia hallada. La ventaja de esta estructura es que el ordenamiento se puede hacer simplemente recorriendo el árbol de una manera en particular. No se requiere pues ordenarlo directamente. Pero estos son sólo tips, no tienen que seguirse si no se desea.

Quienes programan en Python, Ruby on Rails o cualquier lenguaje interpretado, la parte de procesar más rápido que los demás la tienen perdida. Esto no quiere decir que ya no puedan ganar el reto, pero claramente quedan en desventaja ante los programas compilados a código nativo x86.

¿El premio? Una taza con el logotipo de la Morsa a la mejor solución. Además hay una libretita y una gorra, cortesía de los buenos amigos de Qualcomm que se añade al premio. Pudiese ser que se incorporaran más premios pequeños (estamos trabajando en eso), como pudiesen ser camisetas, etcétera. Esto solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de al menos 8 GBytes y se les enviará por correo certificado. Y sí, sé que no son los grandes premios pero esto es lo que hay por el momento. Evidentemente quien gane será anunciado aquí y hasta tendrá sus quince minutos de fama.

Los resultados finales son inapelables. Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto. Programas copiados de la web o que tengan ese sabor sospechoso de plagio podrán ser eliminados sin mayores consideraciones. El chiste de estos retos es que los programadores se animen a resolverlos, no que busquen la manera de hacer trampa. ¡Así que a afilar sus habilidades de programación y pasar un buen rato intentando resolver el problema propuesto!

Comentarios