La fascinante búsqueda de algoritmos

La fascinante búsqueda de algoritmos
Facebook Twitter Flipboard E-mail

Hay cierto tipo de pasatiempos que, siendo pasatiempos, producen en quien los practican gratificantes emociones. Cuando se consigue un equilibrio entre dificultad y éxito es cuando más fuertes son las emociones. Preguntarle la hora a alguien enfrascado en resolver un Sudoku, es como preguntársela a una farola. ¿Cuantas veces os han tenido que repetir vuestras madres la frase "¡a cenaaaaaar!", mientras repetís (nivel tras nivel) "¡que ya voy!"?. No es casualidad que juegos como el Tetris con suaves curvas de dificultad sean tan populares, mantienen al sujeto en ese preciso equilibrio de dificultad (reto) y éxito (progreso). En la mayoría de los casos da igual si "ganas" o no, de hecho, no "ganar" es un aliciente para intentarlo de nuevo (mientras se mantenga el equilibrio de éxito).

Una de las principales cosas que hacemos los programadores es buscar algoritmos, soluciones eficientes a los problemas del día a día, esa búsqueda de mejorar nuestros procesos es normalmente un aliciente para muchos (y me incluyo). Pero igual que en el Counter-Strike, si el desafío se produce ante otros, toma mayor relevancia (así es el ser humano, que le vamos a hacer).

La fascinante búsqueda de algoritmos

La fascinante búsqueda de algoritmos tiene diferentes y variados modos de juego; podemos conocer la dificultad del problema o no, saber si hay solución, tener una definición estricta o que admite ajustes, en un lenguaje concreto, etc... pero dos de los que a mí más me gustan son:

  • Problemas con una definición muy muy sencilla pero que son muy muy difíciles.

  • Problemas para los que hay una solución eficiente y encontrar una variante más eficiente todavía.

Del primer tipo, es muy muy (pero que muy) improbable que encontremos una solución (para mí, al menos), pero su sencilla definición permite que le demos muchas vueltas al problema y encontremos montones de estrategias interesantes que luego podemos aplicar en otros algoritmos. Un ejemplo típico sería (nada más y nada menos) que buscar un algoritmo eficiente para un problema NP-completo, si no recuerdas cuales son, aquí tienes dos:

  • Dado un conjunto de números C = {n1, n2, ..., nM} responder o NO (nada más) a la pregunta "¿Existe un subconjunto de C que sume K?". Por ejemplo, si es C = {1, 7, 3} y K = 4 la respuesta es SI.

  • Dado un mapa de carreteras y una lista de ciudades, responder o NO (nada más) a la pregunta "¿Existe una ruta que pase por cada ciudad una sola vez?". Por ejemplo, en la imagen:

    Hamiltoniano

Del segundo tipo la dificultad depende de quien haya indicado la solución, es común en foros o en sitios como Solveet que los "participantes" vayan refinando las soluciones (incluso sus propias soluciones) en tal caso será frecuente que podamos aportar soluciones mejores refinando unos las soluciones de otros (en una especie de brainstorm informal). Otras veces sin embargo, las soluciones son "oficialmente las mejores" en cuyo caso será muy difícil que las podamos mejorar, pero siempre queda la posibilidad de mejorar casos concretos.

Quizás un ejemplo representativo de esto último podría ser el problema de triangular un polígono simple (como los que se estudian en el cole), es un problema abierto el obtener un algoritmo más sencillo que el de Bernard Chazelle (de coste lineal). Obtenerlo está (casi seguro) muy lejos de nuestro alcance, pero tomado como un juego, es emocionante darle vueltas y descubrir propiedades y estrategias que no se te habían ocurrido antes.

Así, existen infinidad de problemas de algorítmica de diversos temas y dificultades que podemos resolver (o intentar) con el fin de matar el tiempo, practicar un determinado lenguaje, aprender y pensar en nuevas estrategias, retar a los demás para saciar nuestra innata sed de competitividad, etc...

Lugares donde encontrar desafíos

En mi opinión los mejores sitios para obtener desafíos son la documentación universitaria (y biblioteca técnica y científica asociada), en ella se encuentran desafíos de todo tipo, mostrados con rigor, por personas que saben mucho sobre lo que escriben y cuyas soluciones, hayamos dado o no con ella, seguro que nos aportarán una información valiosa.

No tienen porqué ser libros cargados de teoremas y análisis extensos; muchos se centran en aspectos prácticos como al estilo de "Gráficas por computadora en Basic" que contienen montones de ejemplos. Hay bastantes y muy buenos cuyos títulos suelen ser "Algoritmos de ..." que contienen un buen puñado de retos por resolver (con sus soluciones, claro).

En OpenLibra (comentado frecuentemente en GenBeta Dev) hay multitud de libros similares a los que puedes acceder gratuitamente.

Pero si no queremos seguir un método ni horario, también podemos recurrir a Internet por supuesto, aquí una pequeña lista de sitios que se me ocurren (seguro que hay muchísimos más):

  • List of algorithm general topics en Wikipedia es un buen punto de partida, podemos navegar por las materias que más nos interesen (IA, gráficas, cálculo numérico, etc...).

  • Solveet, que Juan ya nos presentó En su día y que contiene problemas y soluciones en múltiples lenguajes.

  • Rosetta Code, que contiene multitud de algoritmos resueltos en multitud de lenguajes.

  • Programming praxis, sitio que lleva tiempo presentando periódicamente problemas y que la gente resuelve de manera informal (sin rankings ni nada parecido).

  • Project Euler, que se centra en problemas de tipo numérico aunque no de forma estricta (eg. también de combinatoria).

  • 4 Clojure, específico para Clojure, guardando las versiones con tus progresos y validación automática sobre los test definidos en cada problema.

  • Code Chef, que promueve la cooperación y competitividad.

  • Top Coder, sitio muy famoso y con muy elaboradas herramientas que a mí personalmente no me gusta porque tiene demasiado control sobre los programadores (y se trata de pasar un buen rato, no de sentirte observado).

Pero recuerda, se trata de pasar un buen rato, encuentra aquellos problemas que están dentro de tu "zona de juego" (difíciles pero divertidos y asequibles a tu skill) y un consejo, nunca te tomes demasiado en serio los retos con que te encuentres.

Más información | Brainstorming.
Más información | OpenLibra libros técnicos en donde seguro encontrarás retos interesantes.
Más información | Polygon triangulation.

Comentarios cerrados
Inicio