Por @Alvy — 7 de Julio de 2011

Cifras-Y-Letras-2Pt

El Cedazo ha publicado el que tal vez sea el más exhaustivo análisis de la posible solución definitiva al popular concurso Cifras y letras, en dos partes:

El análisis incluye un buen número de cálculos sobre todas las combinaciones posibles letras y palabras, números y soluciones, especialmente en la parte de Cifras, que es la que permite una aproximación más matemática. Uno de los datos es que con los números que se ofrecen para buscar el valor en cada prueba de Cifras se pueden realizar 31 millones de fórmulas diferentes de cara a encontrar la solución.

Anotaciones relacionadas:

Compartir en Flipboard  Compartir en Facebook  Tuitear

4 comentarios

#1 — miguel

En el primer artículo habla de que un experto en informatica emplearía fuerza bruta para la prueba de cifras... realmente creo que sería más rápido aplicar algún algoritmo de búsqueda con retroceso.

#2 — Alvy

Curiosamente a mi me pareció que ~30 millones de operaciones posibles es razonablemente poco y «barato» (en cuando a tiempo, etc) como para estar de acuerdo en que la fuerza bruta es la solución más práctica – que no la más eficiente, tal vez, pero los ciclos de CPU van baratos y 30 millones de cálculos no parecen muchos…

#3 — cruzki

@miguel y @ Alvy

Un apunte: La "búsqueda con retroceso" no es más que una forma "ordenada" (y burda) de usar la fuerza bruta aka "probar con todas".

La idea de Mac es bastante más "elaborada" y posiblemente más eficiente pues no "prueba con todas" sino con "todas las que son distintas".

Otra cosa es si planteas algún esquema de "ramificación y poda" pero a mi no se me ocurre ninguno.

#4 — dalet

#3 Se puede hacer branch and bound si vamos guardando soluciones parciales y contamos lo lejos que estamos de nuestro objetivo. P.ej, si tenemos 1,2,4,9,25,100 y vamos por un lado por 9*100*25 = 22500, ya podemos podar todas las operaciones en las que sumamos, restamos o multiplicamos cualquier combinación de los otros números, que siempre será peor que algún otro resultado.
Ayuda partir de los números ordenados, lo que viene a resolver para cada caso particular lo que propone el autor de no intentar diferencias o cocientes contra las reglas (a la vez que no se descartan soluciones); e ir guardando soluciones parciales para evitar muchas duplicidades por conmutatividad, etc.