miércoles, 6 de enero de 2010

Algoritmos ayudados

En un comentario a una entrada anterior de este blog, Claudio nos proponía lo siguiente:

Te envío un problema que mandó Rodolfo Kurchan a la lista de Snark :

Este simpático acertijo me lo envió Michael Reid de EEUU: Colocar los dígitos 0, 1, .... , 9, sin repetir en la expresión a^b + c^d + e^f + g^h + i^j para obtener el año actual.

Pensé en aplicar esta idea al 2010. Como estábamos en días navideños, no me apetecía pensarlo mucho. Por otra parte, si intentaba un algoritmo sin preparación, me podía encontrar con 1010 pasos, lo que era demasiado para cualquier hoja de cálculo.

Así que pensé en ayudar un poco al algoritmo, para ver si entre la máquina y yo lo encontrábamos sin gran esfuerzo. La primera idea fue la de un algoritmo voraz, pero también había que diseñar bastante, y mi cabeza estaba con los villancicos.

Después de cavilar se me ocurrió elaborar una lista de potencias desde 00 hasta 99 eliminando las mayores de 2010 y casi todas las triviales: 13, 14,...08…La lista estaba compuesta por 1296, 1024, 729, 625, 512,…5, 4, 3, 2, 1, 0 (29 en total)

De esta forma, el algoritmo podía traducirse a “Descomponer 2010 en sumandos tomados de una lista”. Aún así, los cálculos tardaban demasiado (295 pasos) y los compromisos sociales me esperaban. Lo dejé para otro día.

Reanudada la tarea, impuse la condición de que los sumandos fueran no crecientes, lo que simplificaba la búsqueda, y como 2010/5 = 402 debería haber algún sumando superior a esa cantidad. De esta forma puede seguir recortando pasos.

Al final obtuve una lista de sumandos que comenzaba con

1296+625+81+8+0
1296+625+81+7+1
1296+625+81+6+2

y terminaba con

625+625+625+128+7
625+625+512+243+5
625+625+512+216+32

Ya tenía algo con lo que trabajar. Añadí a cada sumando los dígitos que lo formaban como una potencia:

1296 6 y 4 625 5 y 4 81 9 y 2 3 y 4 8 8 y 1 2 y 3 0

Ya sólo quedaba elegir las posibilidades en las que no se repitieran los dígitos. Encontré cuatro:

45+28+93+17+06=2010
45+28+93+16+07=2010
45+28+36+18+07=2010
45+28+36+17+09=2010

De esta forma la hoja de cálculo aportó una base para soslayar mi pereza mental, y yo le ayudé con mi sentido común.

¿Habrá más soluciones? Ya digo que esto me cogió con la mente dispersa. Si alguien los encuentra, aquí le esperamos.

Feliz año 2010

No hay comentarios: