lunes, 13 de enero de 2014

Code Kata for fun and profit.

Code Kata es un término acuñado por Dave Thomas en analogía al concepto de kata en las artes marciales. Consiste en un ejercicio de programación para practicar que, en el mejor de los casos, puede ser resuelto de diferentes formas. Voy a proponer uno que me ha parecido muy interesante debido a la gran variedad de formas de resolverse que puede llegar a tener.


Dado un conjunto de enteros positivos únicos, encuentra todas las secuencias en el conjunto y múestralas ordenadas. Una secuencia es uno o más números consecutivos. 
Dado {1,59,12,43,4,58,5,13,46,3,6}, la salida debería ser: {1},{3,4,5,6},{12,13},{43},{46},{58,59}

 La resolución de este kata es bastante sencilla  y no parece que tenga muchas formas (medianamente óptimas) diferentes de solucionarse pero voy a introducir un punto que hará que el programador se replantee las cosas. Será este punto el que le de diversidad de soluciones a este problema.
Asume un conjunto muy grande de números. Sobre 10 millones aproximadamente.
 Yo todavía no he tenido tiempo para ponerme a ello pero mi intuición me dice que no existe una única manera óptima de resolución, si no que depende de si queremos consumir más memoria, más tiempo de CPU o un equilibrio entre los dos. Por otro lado, la distribución de ese consumo en el tiempo también puede ser importante. ¿Cómo cambiaría la solución si la secuencia de números nos llegase poco a poco a lo largo de varios minutos (o de manera indefinida) y queremos en cualquier momento recuperar las secuencias actuales del conjunto? ¿Cómo quedaría la solución si fuese mejor gastar tiempo de CPU recalculando cada vez que nos llega un número en vez de asumir que tenemos el conjunto de entrada completo desde el principio? Y con la memoria; ¿Y si necesitamos liberar la memoria que va ocupando el algoritmo cuanto antes (mientras se ejecuta el algoritmo)?

En resumen; este problema necesita que el programador se plantee diferentes contextos y con ellos desarrolle una solución óptima para cada uno.

Es por todo esto por lo que no sólo hay que encontrar una solución, si no explicar para que caso concreto esta solución es más o menos óptima.

Si terminas interesado en este kata acabarás aprendiendo sobre estructuras de datos, algoritmos de ordenación y búsqueda y sus costes computacionales y de memoria respectivos al insertar o buscar; por lo que aunque no encuentres solución a este problema la próxima vez que en el mundo real se te plantee un problema podrás evaluar de cabeza porque es mejor usar un árbol binario de búsqueda en vez de una tabla hash (o viceversa) en el contexto actual de tu problema.

No hay comentarios:

Publicar un comentario