Regístrate | Conectar
El Tamiz Libros Recursos Series Únete 9 Users Online
Skip to content

Resolviendo “Cifras y Letras” (y II)




En el artículo anterior os había introducido mi fascinación antigua por el veterano concurso televisivo Cifras y Letras, había descrito su funcionamiento y cómo construir un programa que pudiera resolver tanto las pruebas de letras como las de cifras. Sobre cómo resolver los problemas de letras (construir una palabra válida cuanto más larga mejor con una serie de letras más o menos aleatorias que se dan en cada prueba), había simplemente pergeñado cómo se podía resolver, sin entrar en demasiado detalle (dije entonces que me parecía un problema informáticamente sencillo… pero largo).

En cambio, sobre cómo resolver las pruebas de cifras (obtener un cierto número objetivo realizando operaciones elementales –suma, resta, multiplicación y división- sobre una serie de seis números más o menos aleatorios dados), sí que me había detenido bastante más, explicando cómo atacar el problema por fuerza bruta, lo que obligaba a comprobar todas y cada una de las 30.965.760 fórmulas distintas posibles que pueden darse, o al menos hasta encontrar una solución válida. En este punto, si el tema te interesa y no has leído ese artículo anterior, quizá deberías hacerlo ahora….

Por cierto, en ese tan citado artículo enlacé unos programas para la Palm que nuestro amigo J había realizado años atrás, así como el intérprete de SmallBasic que servía para ejecutarlo en un Linux, Windows y demás… Pues J se ha superado, amigos, y ha reprogramado el juego para Android, así que todo aquél que tenga un dispositivo que funcione con ese sistema operativo (teléfono, tablet, etc) lo puede disfrutar… gratis. Os lo podéis descargar de aquí. ¡Muchas gracias, J!

.

Volviendo a lo nuestro, el problema del ataque por fuerza bruta es que comprobar casi 31 millones de fórmulas puede ser largo… de hecho es largo. En este artículo de hoy vamos a ver cómo es posible ir aplicando más y más trucos para resolver el problema en muchísimo menos tiempo que el necesario para hacerlo por fuerza bruta.

Optimizar, optimizar...

Hoy en día, con PCs cuya potencia se mide en Gigaflops y tienen Gigas y Gigas de RAM, puede parecer que esta optimización es innecesaria. Pero si estuviéramos trabajando en un ordenador limitado (como un teléfono móvil, un sistema empotrado, etc) o tuviéramos que resolver miles de estas peticiones cada segundo (como un servicio web o algo así) mejorar el rendimiento puede ser crítico. O también puede ocurrir que los datos de entrada de nuestro algoritmo sean muchos. Antaño, lo que la gente consideraba mucho podía ser analizar quizá un millón de registros, algo imposible de hacer a mano. Hoy seguramente un millón de registros podemos atacarlo por fuerza bruta y listo… pero es que con el avance de la informática nos encontramos con que ya nos gustaría poder automatizar tareas que impliquen tratar con un billón de registros… y a lo mejor ahí ya no sirve la fuerza bruta. Este artículo servirá para ejemplificar una optimización de este estilo.

Primero un breve recordatorio de cómo representar el problema. Los operandos se representaban por su número relativo de presentación, de 1 a 6, y había 720 formas posibles de ordenarlos, pues sólo se puede tomar como máximo una vez cada número (aunque se podía dejar algún número sin usar). En cuanto a los operadores, son las cuatro operaciones elementales (+, -, x, ÷), y había 1.024 maneras diferentes de ordenarlos (4 elevado a 5, que es el número de operadores necesarios para tratar seis operandos). Por fin, había 42 formas diferentes de colocar paréntesis para ordenar las operaciones,[1] que se escribían en notación polaca inversa, lo que eliminaba la necesidad de codificar los propios paréntesis, y se representaban utilizando una “O” para representar un operando, es decir, una cifra, y un “·” para representar un operador.

Así, para cada representación en polaca inversa se probaba cada combinación de operandos, y para cada una de ella, cada posible combinación de operadores. De la mezcla de las tres combinaciones (números, operadores y paréntesis) se obtenía cada fórmula individual a comprobar, por ejemplo, de [OOO·OO··O··;451623;+÷ -x+] se obtiene “451+62÷-3x+”.[2] En total hay casi 31 millones de éstas, ya digo.

Insisto. Si no has leído el artículo anterior o no te acuerdas, mejor lo lees antes de seguir. Y sí. Soy pesado, qué se le va a hacer.

Mejoras en el proceso de comprobación de fórmulas

Lo primero que se le ocurre a cualquiera es si es posible buscar atajos en el propio proceso de comprobación de fórmulas, que exige realizar cinco operaciones con cada una de las casi 31 millones de combinaciones posibles (o sea, cerca de 155 millones de operaciones para cada problema individual). Y sí, se puede. Un atajo bien grande.

Mirando la descripción del problema (seis números de partida enteros y positivos, y un objetivo entero y positivo), y teniendo en cuenta que se van a comprobar todas y cada una de las formas posibles de combinar estos seis números con las cuatro operaciones elementales, la primera acción es descartar la fórmula en cuanto cualquier resultado parcial dé como resultado un número negativo o no entero (obviamente, como los datos iniciales del problema son enteros y positivos, sólo una resta puede dar como resultado un número negativo, y sólo una división puede dar como resultado un número no entero).

La justificación es sencilla. Efectivamente es posible encontrar una solución que implique números intermedios negativos o con decimales… por ejemplo, la fórmula (3-7)x(25-100) da como resultado 300 (es decir: (-4)x(-75), que da eso: 300); si fuera precisamente 300 el número buscado, es, desde luego, una solución válida. Pero podemos descartarla alegremente en cuanto vemos el -4 (o el -75, igual da) por el simple hecho de que estamos completamente seguros de que la fórmula (7-3)x(100-25) también forma parte de los 31 millones de combinaciones, por tanto será probada tarde o temprano y dará también un resultado válido… y sin números negativos. Esto es cierto para cualquier situación en que aparezcan números negativos como resultado de cualquier operación. De hecho, también puede procederse de la misma manera si un resultado cualquiera es cero. Y como un razonamiento idéntico sirve para aquellas fórmulas con divisiones que den resultados no enteros… me ahorro la explicación.

De esta forma eliminamos un montón de operaciones inútiles, ya que en cuanto detectamos un resultado no válido al operar (bien menor que 1, bien no entero), detenemos el cálculo de la fórmula y la descartamos, evitando realizar las operaciones restantes. ¿Cuánto nos ahorramos con este truco? Pues depende… depende de los números dados; hay veces que nos ahorramos muchas operaciones y otras, no tantas… incluso hay un caso hipotético en que no nos ahorraríamos prácticamente ninguna (por ejemplo, si los seis números son todos “1”). Puede parecer una tontería, pero, empíricamente,[3] puedo asegurar que nos ahorramos, en media, ¡un 47% de operaciones!, casi la mitad (de las casi 155 millones de operaciones resultantes ahorramos cerca de 73 millones, nada menos), lo que supone un ahorro importantísimo de tiempo de proceso.

.

Pero no basta. Para un informático de pro, y si encima es de la Edad del Bronce, no. Hay que seguir optimizando nuestro programa… veamos cómo.

1- Eliminar combinaciones inservibles o redundantes a priori

Si nos fijamos en las condiciones del concurso, los números que se dan están comprendidos entre 1 y 100, mientras que el objetivo está comprendido entre 101 y 999. Como estos límites son los que son, podemos reducir el número de combinaciones a comprobar eliminando todas aquellas combinaciones en que las operaciones sean exclusivamente restas o divisiones. La justificación es también sencilla: estas dos operaciones disminuyen el valor del primer operando (el minuendo o el dividendo: recordad que sabemos que toda operación que dé como resultado un numero negativo o no entero implica eliminar la fórmula completa), por lo que aplicando sólo este tipo de operaciones (restas o divisiones) a números menores o iguales que 100, nunca vamos a conseguir obtener un número mayor que 100. En una palabra, para poder obtener cualquier objetivo con cualquier combinación de números de las características dadas es necesario que la fórmula contenga al menos una suma o una multiplicación.

¿Está claro? Esto nos permite eliminar algunas (no muchas) de las posibles combinaciones de operadores, que inicialmente eran 4 elevado a 5, o sea, 1.024. Las combinaciones que no contienen ninguna suma ni multiplicación son exactamente 48,[4] lo que deja 976 combinaciones de operadores válidas. Esto reduce el número de fórmulas posibles a algo menos de 30 millones (en concreto, 29.514.240). Algo es algo…

También podemos evitar la comprobación de ciertas fórmulas que sabemos con antelación que van a dar el mismo resultado. Por ejemplo, cuando en la combinación de operadores sean todos ellos sumas o todos ellos multiplicaciones, es indiferente tanto el orden a la hora de aplicar los operandos como la forma de colocar los paréntesis… el resultado será siempre el mismo: la suma o el producto de todos los números dados. Por ello, para estas combinaciones de operadores basta con comprobar la fórmula una única vez, evitando en cada una comprobar (720×42)–1 fórmulas (30.239) que sabemos de antemano que darán todas ellas el mismo resultado. Eso elimina otras 60.478 fórmulas más, dejando 29.453.762 fórmulas a comprobar. De esta forma, nos hemos quitado de encima millón y medio de combinaciones. Vale, no es mucha la ganancia, pero, nuevamente, algo es algo…

Existen otras maneras de eliminar fórmulas redundantes a priori, pero la comprobación de si la fórmula se debe o no eliminar es en general más costosa en términos de tiempo de proceso que lo que ahorramos, por lo que creo que es preferible dejarlo aquí.

Sólo 29.453.762 fórmulas, es decir, teniendo en cuenta el ahorro obtenido por desechar números negativos o cero o no enteros, alrededor de un 47%, implica realizar una media de sólo unas 78.100.000 operaciones para cada problema…

Puff! Siguen siendo muchas. Algo habrá que inventar.

Hay que tomar una determinación más radical… Aviso: Es ahora cuando viene lo realmente divertido de resolver este problema. ;)

2- Eliminar combinaciones redundantes aplicando las reglas del álgebra

Es muy evidente que con esta orientación de ataque por fuerza bruta estamos haciendo las mismas operaciones una y otra, y otra vez… por ejemplo, 7+3 es lo mismo que 3+7. O 100-5+3 es lo mismo que 100+3-5, o que 3-5+100. O bien ( (5×3)x4) es lo mismo que (5x(3×4) ). Hay mucha redundancia en el sistema, es evidente, debida sobre todo a la propiedad conmutativa de suma y multiplicación, pero no sólo. Lo que hay que hacer ahora es verificar qué fórmula es en realidad idéntica a otra, pues aunque sus operandos, paréntesis u operaciones estén en orden distinto, implica en realidad hacer lo mismo y de la misma manera con los números originales, y naturalmente obtiene el mismo resultado.

Aplicando el álgebra...

El procedimiento informático general es relativamente sencillo: Se genera un fichero inicial con todas las fórmulas posibles (las 29.453.762 obtenidas en el paso anterior), y entonces se pasa un astuto programa que, para cada fórmula del fichero, obtiene su, por así decirlo, “forma canónica”, fórmula equivalente a la original en que ésta se ha transformado. Y estas transformaciones deben hacerse de forma que todas las fórmulas equivalentes dejen como resultado la misma fórmula canónica; si no, de poco serviría la transformación. Entonces se eliminan todas las que son iguales,[5] dejando una única vez cada fórmula distinta.

Atención: No estamos tratando con problemas concretos, sino con fórmulas genéricas y aplicables a cualquier conjunto de números, esto es importante. En todo este proceso los operandos serán siempre 1,2,3,4,5,6, que representan en realidad al primero, segundo… y sexto número de los entregados en cada problema, que serán distintos cada vez. Es decir, algún lector podría pensar aquí “Hombre, una forma sencilla de eliminar cálculos es que si tengo dos números iguales, por ejemplo, dos 25’s, puedo intercambiar uno por el otro… Por ejemplo, si los números dados son 7, 3, 25, 8, 25, 9, puedo intercambiar el operando 3 por el 5, puesto que ambos son un 25, y por tanto la fórmula en polaca inversa (31+5x) es idéntica a la (51+3x), pues ambas son (25+7)x25”. Pues no. Eso no se puede hacer aquí… ¿qué pasaría en otro problema distinto donde los operandos 3 y 5 sean distintos, digamos 7 y 10, por ejemplo? Pues que en este caso las fórmulas anteriores son claramente distintas entre sí, y no se pueden asociar. ¿Queda claro?

Bien, el resultado del proceso será un fichero con el mismo formato que el original, pero sólo con las formas canónicas sin repeticiones, que serán muchas menos. Para resolver un problema concreto bastaría con leer el fichero final obtenido y comprobar exclusivamente las fórmulas contenidas en él, sin comprobar fórmulas redundantes, y ahorrando así muchísimo tiempo.

Sólo queda definir las transformaciones… Fácil, ¿no?

.

Vale, no, no tanto, tenéis razón. Veamos paso a paso qué transformaciones es posible hacer para obtener las dichosas fórmulas canónicas. A partir de aquí denotaré los operandos con letras mayúsculas A,B,C…F, letras que harán referencia a cualquier operando del 1 a 6. De esta manera quedarán más claras, o eso espero, las transformaciones a realizar en la fórmula.

.

Transformación 1 (Propiedad conmutativa)

En el caso de fórmulas con el patrón AB·, donde el operador (·) es + ó x, entonces ordenar de menor a mayor los dos operadores AB. Por ejemplo, ante un patrón “41+”, se cambiará a “14+”. Obviamente, el patrón “14+” no sufre cambio, pues está ya ordenado (1 es menor que 4). Ahora las dos fórmulas tienen la misma forma canónica, y una de ellas puede ser eliminada.

Variaciones de la transformación 1: Por la misma razón, en caso de fórmulas con los patrones ABC··, ABCD···, ABCDE···· ó ABCDEF····· siendo todos los operadores (·) iguales entre sí, y o bien son sumas (+) o multiplicaciones (x), ordenar de menor a mayor el conjunto de operandos ABC… Por ejemplo, los patrones 4153xxx y 5314xxx quedarían ambos como 1345xxx, lo que es obviamente equivalente.

Aplicando exclusivamente esta sencilla transformación con todas sus variantes al fichero original se eliminan 12.005.348 fórmulas… ¡un 40,7% de todas las fórmulas! Esto marcha… Sigamos aplicando transformaciones…

.

Transformación 2 (Propiedad conmutativa, continuación)

En el caso de fórmulas con el patrón AB·C·, siendo ambos operadores iguales y o bien sumas (+) o bien multiplicaciones (x), entonces convertir el patrón a ABC··. Si es, por ejemplo, 12+3+ (es decir, (1+2)+3), se convierte a 123++ (o sea, 1+(2+3)), lo que es obviamente lo mismo.

Variaciones de la transformación 2: De forma similar, en caso de fórmulas con los patrones AB·C·D·, AB·C·D·E· ó AB·C·D·E·F·, siempre con los operadores iguales, siendo sumas o multiplicaciones, se convierten respectivamente a ABCD···, ABCDE···· y ABCDEF·····.

Si aplicamos exclusivamente esta transformación al fichero original eliminamos 1.942.560 fórmulas, que es apenas un 6,5%… pero ¡fijaos en que estas fórmulas transformadas son ahora susceptibles de ser re-transformadas por la Transformación 1! Ésta es la clave de todo el asunto: una fórmula cambiada por una transformación es susceptible de ser a su vez cambiada por otra diferente, reduciendo cada vez el número de fórmulas a comprobar… En una palabra, será preciso realizar un proceso iterativo repitiendo el mismo proceso una y otra vez, para dejar que cada transformación pueda actuar sobre el resultado cambiado por otra transformación anterior. Y esto sirve también para todas las transformaciones que siguen.

.

Transformación 3 (Propiedad conmutativa, caso general)

Viendo el buen resultado que obtenemos simplemente ordenando los operandos de las operaciones sencillas que gozan de la propiedad conmutativa, el paso siguiente es obvio: Ampliar el procedimiento de ordenación a todas las operaciones de suma o multiplicación… En una palabra, para cada operador + ó x, localizar cuáles son los dos términos a los que aplica y ordenarlos de menor a mayor según el primer operando de cada término. Esta transformación no es tan sencilla de realizar como las anteriores, pues requiere de un sagaz algoritmo que busque primero cuáles son ambos términos de la operación concreta y, de ser necesario, que los intercambie. Es evidente que esta transformación 3 incluye a la transformación 1, pero mantenemos esta primera transformación primero, por claridad de exposición, y segundo, por un tema de puro rendimiento (es mucho más rápido en tiempo de ejecución comprobar y cambiar las fórmulas según la forma 1 que la 3).

Un ejemplo ayudará a clarificar el quid de esta transformación. Sea, en polaca inversa como siempre, la fórmula [453-÷26x+1+] (es decir, [ ( (3-5)÷4)+(2x6)+1 ] en notación infijo).[6] Según el razonamiento de esta transformación 3, para cada signo + ó x se verifica si sus términos están en orden de menor a mayor según su primer operando… Hay tres signos + ó x en la fórmula. El primero de izquierda a derecha, una multiplicación (x), actúa sobre los operandos 2 y 6, que están ya debidamente ordenados (2 es menor que 6), luego no se cambia nada. El segundo, una suma (+), actúa por un lado sobre el término 453-÷, y por el otro, sobre el término 26x. Están desordenados, ya que 4 es mayor que 2, así que se intercambian entre sí, quedando 26×453-÷+. Es obvio que este cambio no altera el resultado final. Por fin, el tercer operador conmutativo, otra suma (+), actúa por un lado sobre el término anterior, 26×453-÷+, y por el otro sobre el operando 1. Están también desordenados (2 es mayor que 1), así que nuevamente los intercambiamos. La fórmula original queda por fin así: [ 126x453-÷++ ]. Os reto a comprobar que es idéntica a la original.

Esta transformación es realmente muy poderosa, y permite eliminar muchas fórmulas originales. Si aplicamos exclusivamente esta transformación a los 29 millones y medio de combinaciones originales, elimina, al resultar duplicadas, nada menos que 23.249.970 fórmulas, ¡un 79% del total! Quedarían apenas 6.200.000 fórmulas a comprobar.

Pero… somos informáticos viejos, y además, tozudos, así que no nos vamos a conformar con tan poca cosa… Así que, agotadas las posibilidades de darle vueltas a la propiedad conmutativa, hay que buscar cómo podemos seguir rebajando el número de fórmulas, y una forma evidente es intentar convertir operaciones no conmutativas (-, ÷) en otras que sí lo sean… vamos allá.

.

Hay que tratar las ecuaciones con mimo

Transformación 4 (Porque menos por menos es más…)

En el caso de fórmulas con el patrón ABC··, siendo ambos operadores iguales y o bien son restas (-) o bien divisiones (÷), cambiarlas por AB·C·, donde el segundo operador es el mismo, pero el primero es el complementario (+ si originalmente es -; x si es ÷). Un ejemplo lo aclara: sea 123–, es decir, (3-2)-1, que se cambia a 12+3-, que es 3-(2+1), que es claramente lo mismo. Si fuera 123÷÷, quedaría 12×3÷; haced la prueba y veréis que es también lo mismo. El objetivo de esta transformación es no sólo eliminar fórmulas, sino que, al introducir en la fórmula signos + o x que antes no estaban, signos que sí admiten la propiedad conmutativa, vuelven la fórmula susceptible de ser reducida ulteriormente por las transformaciones 1 a 3.

Variaciones de la transformación 4: De forma similar, en caso de patrones ABCD··· ó ABCDE····, con todos los operadores iguales siendo o restas o divisiones, cambiarlas por ABC··D· ó ABCD···E·, siendo siempre el último operador el original (-,÷), y los dos o tres iniciales, el contrario (+,x, respectivamente).

Aplicando exclusivamente esta transformación con sus variaciones se eliminan 1.409.760 fórmulas, o un 4,7% de las fórmulas iniciales. Pero, además, ahora hemos cambiado una serie de operaciones no conmutativas (-,÷), por otras que sí lo son (+, x) y por ello susceptibles de ser reducidas por los pasos anteriores.

.

Transformación 5 (Ordenar operaciones del mismo rango)

En el caso de fórmulas con el patrón ·O·, siempre que los dos operadores sean de la misma “familia”[7] (sumas y restas, o bien multiplicaciones y divisiones, es decir, una de las configuraciones siguientes: +O+, +O-, -O+, -O-, y lo mismo cambiando + por x y – por ÷), entonces sustituir este patrón por un patrón O··, donde los operadores varían de la siguiente forma: ++ queda igual, +– queda ––, –+ queda +– y por fin –– queda –+ (y los equivalentes de sustituir suma por multiplicación y resta por división en la definición anterior).

Nuevamente un ejemplo para comprender la transformación. Sea el patrón -4+. Esto quiere decir que el primer operador (una resta) aplica sobre dos términos anteriores de la fórmula, que nos da lo mismo cuáles sean, digamos X e Y (pueden ser ambos operandos sencillos o bien el resultado de cualquier cálculo sobre ellos, no importa), y al resultado se le suma el operando 4. Por tanto, la fórmula original será, de alguna manera, XY-4+, lo que traducido a notación infijo sería [ (Y-X)+4 ]. Con el cambio, queda XY4+–, traducido a infijo: [ Y+4–X ], que es, naturalmente, lo mismo. Con el resto de combinaciones el razonamiento es similar.

Esta sencilla transformación (bueno, quizá no tan sencilla, pero indudablemente práctica), si la aplicamos ella sola al conjunto inicial de 29 millones y pico de fórmulas, elimina nada menos que 11.570.400 fórmulas, un 39% del total. Y además, al introducir sumas y/o multiplicaciones donde antes eran restas o divisiones, nuevamente habilitan a las transformaciones anteriores para seguir eliminando fórmulas.

.

Transformación 6 (Ordenar operaciones del mismo rango, continuación)

Siguiendo el razonamiento anterior, podemos buscar ahora patrones del tipo ·X·, donde X sea una fórmula completa en sí misma en lugar de un único operando como en la transformación anterior (por ejemplo OO·, o bien OOO··, OO·O·, etc, es decir, todo conjunto válido de operandos y operadores que den como resultado un único valor), y aplicar los mismos criterios de la transformación 5. Es decir, se cambia la fórmula a X·· (y esta vez X no es un operando sencillo, sino una fórmula más o menos larga), y a los operadores se les aplica los mismos cambios que en la transformación 5, así que no los detallo nuevamente.

Aplicando exclusivamente esta transformación 6 sobre el conjunto de fórmulas originales se eliminan 8.025.840 fórmulas, un 27% de las fórmulas originales. Si aplicamos conjuntamente las transformaciones 5 y 6 una detrás de otra, el número de fórmulas eliminadas es de 17.060.400, es decir, un 58% del total. Cada vez quedan menos…

.

En este punto igual alguno de vosotros ha ido sumando mentalmente cuántas fórmulas se eliminan en cada caso, y habrá llegado a la conclusión de que hemos eliminado más fórmulas de las que había originalmente, así que habrá que resolver el problema con magia… pues no. En realidad muchas de las eliminaciones que realizan unas y otras transformaciones o se cancelan entre sí o son realizadas por más de una transformación, así que aún quedan muchas, pero muchas fórmulas redundantes que eliminar. Esas fórmulas redundantes son, no lo olvidemos, las que estamos eliminando con tanta transformación y tanta gaita.

.

Transformación 7 (Ordenar operaciones del mismo rango, caso general)

Por fin, terminando con el razonamiento de ordenar operaciones de la misma familia, siempre que se encuentren dos operadores consecutivos (··) de la misma familia (suma/resta o multiplicación/división), transformarlos de la forma que ahora contaré. La presencia de dos operadores consecutivos implica la existencia de tres términos en la pila; el primer operando aplica sobre los dos últimos, y el segundo opera sobre el primero de los tres y el resultado de la operación anterior. Es decir, si los tres términos en la pila son X,Y,Z y los operadores son, por ejemplo, +- (en este caso podríamos representarlo como XYZ+-), la suma opera sobre Y y Z, y la resta sobre el resultado anterior (Y+Z) y X, haciendo (Y+Z)-X.

La transformación implica cambiar de lugar los términos X,Y,Z y los operadores en la fórmula, teniendo en cuenta en este caso que X,Y y Z son términos genéricos, y por tanto puede cualquiera de ellos ser una fórmula completa (como 123+x, por ejemplo).

Las transformaciones son: XYZ++ queda XY+Z+. XYZ+– queda XY–Z+. XYZ–– queda XY+Z–. Y por fin, XYZ–+ queda YXZ+–, ojo, que no es una errata. Es YXZ+–, con la X y la Y cambiadas de lugar y los dos operadores juntos. Naturalmente, lo mismo ocurre con multiplicaciones y divisiones, cambiando + por x y – por ÷. Por ejemplo, en este último caso, XYZ÷x es, en infijo, [ (Z÷Y)xX ]. Su transformación, YXZx÷ es en infijo [ (XxZ) ÷Y ]… que es lo mismo, lógicamente. Podéis comprobar el resto… si no os fiáis de mí.

Aplicando exclusivamente esta transformación al conjunto original se eliminan nada menos que 14.439.600 combinaciones redundantes, ¡un 49% de todas las combinaciones, casi la mitad!

.

Es posible que existan más transformaciones que permitan eliminar más tipos de combinaciones redundantes… yo no las he encontrado, así que nos conformaremos con éstas, que ya son bastantes. Algunos pensaréis que se podría aplicar también la propiedad distributiva de la multiplicación respecto de la suma, es decir, aprovechar que Xx(Y+Z) es igual a (XxY)+(XxZ)… Pues no, no se puede, porque esto implicaría usar dos veces el término X, lo que las normas del concurso prohíben: sólo es posible usar una única vez cada número dado.

.

Bien, tenemos definida una serie de cambios que van eliminando fórmulas redundantes, pero hemos visto que algunas son complementarias entre sí y otras tienden a cambiar operadores no conmutativos por otros que sí lo son, para que sea posible que actúen otras transformaciones. Es decir, se deben ejecutar la transformaciones de forma iterativa, permitiendo que se vayan complementando unas con otras y eliminando, en cada paso, más y más redundancias. ¿Hasta cuándo? Hasta que ya no se eliminan más tras varias iteraciones.

Así que esto es lo que he hecho en mis ratos libres… Primero generar todas las combinaciones posibles, luego aplicar las transformaciones sobre ellas, y luego pasar una y otra vez el mismo programa, pero esta vez sobre el resultado de la eliminación anterior… la primera pasada igual eliminaba 25 millones de combinaciones, la segunda medio millón más, la tercera trescientas mil… y así, una y otra vez, cambiando el orden de las transformaciones, haciendo unas veces unas y otras, otras… Y otra vez, y otra…

Por cierto, a la hora de implementar estas transformaciones en el programita de reducción hay que pensar cuidadosamente en qué orden se van comprobando. Y el orden óptimo no es, desde luego, el mismo en que las he ido explicando. Algunas de las transformaciones son “ordenadoras”, en el sentido de que no cambian la fórmula en sí, sino que sólo ordenan los términos de la misma (son las transformaciones 1 y 3), mientras que el resto de transformaciones sí modifican la fórmula original, bien cambiando signos, bien modificando el orden de ejecución (los paréntesis, para entendernos). Lo correcto es comprobar en primer lugar estas últimas, que modifican la fórmula en sí, y al final aplicar la ordenación de términos a la fórmula resultante. Así aseguramos la máxima reducción de fórmulas en cada paso.

El orden general que yo he usado para aplicar las transformaciones (que no tiene por qué ser el mejor) es: 2, 4, 5, 6, 7, 1, 3. Pero cuando este orden no obtenía ya más reducción he ido modificando el orden, poniendo las de abajo arriba, eliminando unas veces unas y otras, otras, etc, y así he conseguido más y más reducciones… hasta que ya no hubo forma de reducir más, hiciera lo que hiciera.

El resultado final es un fichero de sólo 1.025.472 fórmulas diferentes, apenas un 3,5% de las combinaciones originales, fichero que, en el hipotético e improbable caso de que os interese para algo, podéis encontrar aquí, libre de derechos de autor. En él sigue vigente, si se desea, la norma de parar el cálculo de la fórmula cuando se detecte un resultado menor o igual que cero o no entero, por lo que el número medio de operaciones a realizar es de unas 2.715.000 en cada problema.[8]

Si tenéis curiosidad (y si habéis llegado hasta aquí es seguro que sí), el número de sumas y multiplicaciones que hay en ese fichero es de 1.096.936, mientras que el número de restas y divisiones  es de 1.466.744.[9] Lógicamente, por el modo simétrico en que se han realizado las transformaciones, deben coincidir el número de restas con el de divisiones y el de sumas con el de productos. Y es lógico que haya más restas que sumas: al no ser la resta conmutativa, no es posible hacer un gran número de reducciones que sí son posibles con las sumas.

.

Creo que resulta evidente que el proceso de obtención del dichoso ficherito de poco más de un millón de fórmulas es largo, tedioso y algo complicado. De hecho, no sólo se debe ejecutar recursivamente bastantes veces (decenas de ellas) para permitirle que unas transformaciones reduzcan el resultado de otras en la iteración anterior, sino que además exige ir variando la disposición de las transformaciones en los programas, porque se van generando “bucles” de combinaciones que impiden que se reduzcan. Explicaré esto un poco: Puede haber (y, de hecho, las hay) tres combinaciones a, b y c que en realidad son la misma fórmula, pero que el conjunto de transformaciones en cascada las hace “circular” entre sí, de la forma a => b => c => a. Entonces una pasada del programa cambia la fórmula a a b, la b a c, y la c a a. Clasificamos el fichero resultante y… ¡Estamos igual que el principio! Para romper esta simetría que, insisto, se da en la realidad, hay que ir variando las transformaciones, cambiándolas de lugar, quitando algunas y luego, otras, etc. Yo he necesitado muchas iteraciones, como cincuenta o quizá más, para obtener el fichero final, pero es que lo he hecho por puro ensayo y error… si yo fuera más listo podría seguramente haber diseñado una estrategia óptima, pero no lo soy, qué le vamos a hacer.

Por ejemplo, la fórmula [ 25614-÷xx3- ] queda, tras todas la transformaciones anteriores, como [ 614-5x2x÷3- ]; ésta, a su vez, queda como [ 5614-2x/x3- ], que a su vez es transformada en [ 25614-÷xx3- ]… que es la misma fórmula original. Si en el fichero de fórmulas  estuvieran dos (o tres) de éstas, no seríamos capaces de reducirlas… a eso me refiero. Por cierto, no las busquéis en el fichero, porque ninguna de esas tres fórmulas está. En su lugar está una sola, equivalente a todas ellas: la [ 614-25xx÷3- ].

Entonces algunos de vosotros pensaréis: “¡Pues vaya optimización! Seguro que resolver el problema por fuerza bruta es más rápido. ¡Y más sencillo!, desde luego“.  Y claro que es así… siempre que sólo vayáis a resolver un único problema en vuestra vida. Si lo que queréis es tener cientos y cientos de ediciones del concurso en todo el mundo, con cuatro o seis pruebas de cifras cada edición, y encima vender centenares de miles de cacharritos baratos que sepan jugar, o millones de juegos para el PC o para el móvil que lo hagan, jueguecitos que sus usuarios jugarán cienes y cienes de veces… entonces el tiempo de respuesta del programa es crítico. Necesitáis optimizar sí o sí. Para que os hagáis una idea, atacar un problema que no tiene solución (es decir, que no hay forma de llegar al objetivo con los números dados), lo que exige revisar la totalidad de las fórmulas posibles, tarda en mi PC antediluviano, por fuerza bruta, unos 55 segundos, mientras que el mismo problema revisando el fichero optimizado tarda unos 3 segundos… el 6% del tiempo, aproximadamente. ¡Y eso que tiene que leer el fichero de un millón de registros!, mientras que atacando el mismo problema por fuerza bruta sólo requiere el uso de CPU (de toda la CPU… no veáis cómo se pone al 100% mientras piensa…).

.

Atención: No tengo la seguridad de que este fichero sea óptimo, que conste. Para que el fichero fuera óptimo debería cumplir dos condiciones: en primer lugar, que no haya fórmulas redundantes (que haya dos o más fórmulas que realicen el mismo cálculo, aunque variando el orden de los cálculos intermedios), y en segundo, que no haya ningún problema que, no teniendo solución mediante la aplicación de las fórmulas contenidas en el fichero, sí la tenga atacándolo por fuerza bruta. Y no, no tengo la seguridad absoluta de que esto sea así.

En el primer caso, es decir, que no haya fórmulas redundantes (lo que ocurriría cuando dos o más fórmulas del fichero son en realidad la misma) no puedo estar seguro de que no queden combinaciones redundantes, sobre todo porque tras mucho pensar (bueno, pensar un poco) no se me han ocurrido más formas de simplificar fórmulas… Sin embargo, he hecho muchas pruebas, pero muchas, centenares de ellas, en que he obtenido todas las diferentes formas en que, usando el famoso fichero, se pueda resolver el problema, y luego me he dedicado a la tediosa labor de comprobar una por una si, en realidad, es la misma que alguna otra con diferente orden o lo que sea… nunca he encontrado ninguna redundancia, así que, aburrido, lo he dejado. Me rindo. Además, si esta primera condición no se cumple no es algo muy pernicioso; si existieran, por ejemplo, un 5% de fórmulas redundantes (que va a ser que no), el proceso tardaría quizá un 5% más de tiempo, pero seguiría encontrando solución a los problemas que la tienen; más de una, vale, pero se sigue cumpliendo el objetivo fundamental del programa, que es encontrar soluciones a los problemas.

En cuanto al segundo caso, que no haya ningún problema que, no teniendo solución mediante la aplicación de las fórmulas contenidas en el fichero, sí la tenga atacándolo por fuerza bruta… quizá os extrañe que incluso pueda existir el hecho de que haya problemas concretos que no tengan solución vía el fichero pero sí por fuerza bruta. Aparentemente, si las transformaciones están bien hechas (y lo están, palabrita de Macluskey) este caso es imposible… y efectivamente es imposible siempre que sea necesario usar los seis operandos para lograr el resultado. Pero ¿qué ocurre si sólo son precisos, por ejemplo, cuatro o cinco operandos para obtener la solución, es decir, que sea un resultado intermedio el que resuelva el problema? Recordad que no es obligatorio usar los seis números para obtener la respuesta correcta. Podría entonces ocurrir que, debido a las transformaciones realizadas, no se obtengan los mismos resultados intermedios (de hecho, ocurre) y, por tanto, que usando el fichero no encontremos solución para algún problema cuando sí la tendría en un ataque por fuerza bruta. Además, recordad que en cuanto una resta obtiene un número menor que 1, o bien cuando una división obtiene un resultado no entero, se desecha inmediatamente la fórmula. Por tanto, podría ocurrir que la fórmula concreta que pudiera resolver un problema dado haya sido transformada finalmente a una que obtenga un resultado intermedio no válido, y por tanto, se deseche.

Este razonamiento quizá sea difícil de entender… un ejemplo quizá ayude.

Sea el siguiente problema: Números: 100, 50, 1, 7, 6, 8. Objetivo: 974.

Si lo resolvemos por fuerza bruta, obtenemos 32 soluciones, 32 formas distintas de resolverlo. Pero todas ellas son, en realidad, la misma, cambiando de diferentes formas el orden de los cálculos. O sea, sólo hay una única manera de obtener el 974 con esos seis números, y es la siguiente:  [( ( 7 x 8 ) x ( 100 - 1 ) ) ÷ 6) + 50]. No hay otro modo.

Efectivamente, si intentamos resolver este problema mirando las fórmulas del fichero, encontramos una única combinación exitosa, que es la [ 2531-46xx÷+ ]. Si traducimos las fórmula a infijo, y sustituímos los operandos 1, 2… 6 por sus valores, la fórmula que queda es [50 + ( ( 100 - 1 ) x ( 7 x 8 ) ) ÷ 6 ], que es, obviamente, equivalente a la primera que yo he puesto. El desarrollo pormenorizado de los cálculos para llegar a la solución es:  100 – 1 = 99; 7 x 8 = 56; 99 x 56 = 5544; 5544 ÷ 6 = 924; 50 + 924 = 974.

Entonces hay una sola forma de resolver ese problema concreto, pero muchas maneras diferentes de ordenar los cálculos. Supongamos, por ejemplo, que la fórmula canónica final, la que queda en el fichero tras tanta transformación, no es la [ 2531-46xx÷+ ], sino la [ 231-546x÷x+ ], que es una fórmula equivalente. En infijo esta fórmula sería [50 + ( 100 - 1 ) x ( ( 7 x 8 ) ÷ 6) ) ], que podéis comprobar que es equivalente. En realidad la única diferencia es que se divide por el operando 5 (el “6″ del problema) antes de multiplicar por el 99 (resultado de restar el 1 al 100)… total, en una serie consecutiva de multiplicaciones y divisiones, da igual hacer las operaciones en un orden u otro… ¿o no? Pues no, en este caso, no. Realicemos de nuevo los cálculos intermedios de esta nueva fórmula:

100 – 1 = 99; 7 x 8 = 56; 56 ÷ 6 = 9,3333….. ¡Un momento! Este resultado no es entero, así que… ¡descartamos la fórmula! Pero es que tras la reducción ésta es la única fórmula que tenemos que podría resolver nuestro problema concreto… así que decidimos que no hay solución. ¡Y sí la tiene! Si siguiéramos operando con decimales  y todo, veríamos que 99 x 9,333333… = 924; y 50 + 924 = 974. Una posible solución sería no parar el cálculo de la fórmula al detectar un número negativo o no entero… pero eso duplicaría inmediatamente el tiempo necesario para resolver cualquier problema… Interesante dilema. Porque yo no acepto tardar el doble de lo que podría tardar ni consumir el doble de recursos de los que podría consumir. Es mi mentalidad de informático curtido en la escasez…

Así que, para evitar en lo posible esta circunstancia, en los pasos finales de obtención del fichero tan sólo ejecuté aquellas transformaciones que desplazaran lo más hacia atrás posible restas y divisiones; esto debería asegurar que los resultados intermedios sean lo más válidos posible. Esto está garantizado en el fichero. Si lo veis en el ejemplo de hace tres o cuatro párrafos, el de las tres fórmulas equivalentes, la fórmula que definitivamente quedó en el fichero sólo divide cuando ya ha multiplicado todos los términos que ha podido multiplicar. Esto no es casualidad, está buscado así.

Pero no es suficiente… sigo sin estar seguro, y además no sé cómo podría estarlo (uno sabe de Teoría de Números lo que sabe, es decir, poco). Además, podría ser que el resultado se obtuviera precisamente con un resultado intermedio. En el ejemplo anterior, supongamos que el número buscado fuera el 792 en vez del 974. 792 saldría, por ejemplo, de multiplicar 99 por 8, es decir, de la fórmula (100 – 1) x 8. Pues bien, la fórmula que finalmente quedó en el fichero, la que vimos antes, no llegaría nunca a obtener ese 792, ya que multiplica el 8 por el 7 (dando 56) antes de multiplicar por el 99. Esta fórmula concreta no encontraría solución para el 792, cuando alguna de las fórmulas originales que han sido agrupadas en ella sí que hubieran obtenido eventualmente ese 792. En este ejemplo tan tonto sí hay otras fórmulas en el fichero que obtienen ese resultado de 792 (en concreto, por si os lo estabais preguntando, 1.332, nada menos) pero… ¿qué ocurriría en el caso de que la única fórmula que obtuviera ese 792 intermedio hubiera sido convertida, por mor de las transformaciones, a una que no lo obtiene? Pues que no encontaríamos solución a un problema que, en realidad, sí que la tiene. Dudas, dudas

En fin, decidí entonces realizar un largo y tedioso proceso para intentar al menos hallar una contradicción, es decir, encontrar un problema dado (pues con uno basta) que, teniendo solución por fuerza bruta, no la tenga utilizando el fichero. O, más fácil, al revés: que no teniendo solución comprobando el millón y pico de fórmulas del fichero, sí la tuviera en un ataque por fuerza bruta.

Dicho y hecho. He ejecutado muchas veces, centenares de ellas, un proceso que hacía lo siguiente: generaba decenas de miles de problemas aleatorios y los intentaba resolver revisando el fichero (lo que es rapidísimo, como supongo suponéis); todas aquellas combinaciones que no tenían solución exacta eran apuntadas cuidadosamente, y luego se las atacaba por fuerza bruta (lo que no es tan rápido, ni mucho menos), para ver si efectivamente tenían o no solución… He generado, por tanto, millones de problemas, encontrando centenares de miles de ellos que no tenían solución, y todos, absolutamente todos los problemas que no tenían solución revisando las fórmulas del fichero tampoco la tenían atacándolos por fuerza bruta… Por cierto, tras este tedioso proceso puedo deciros de forma empírica que aproximadamente el 9% de los problemas aleatorios generados no tienen solución, por si este dato puede ayudaros a fardar delante de algún contertulio. Si alguien quiere (y sabe) calcular analíticamente cuántas exactamente serían, adelante, pero yo no sé hacer tal cosa.

Leonhard Euler en 1753, retrato de Emanuel Handmann

Formalmente no es suficiente, bien que lo sé, y sé también que hablando de conjeturas sobre números pasan cosas muy extrañas. Por ejemplo, el llamado “Último Teorema de Fermat” (el que asegura que no existen soluciones para la ecuación  x^n + y^n = z^n, siendo x, y, z y n enteros y n mayor que 2) sólo ha podido ser demostrado hace unos pocos años, tras dos siglos y medio de denodados intentos para, bien demostrarlo analíticamente, (lo que consiguió finalmente Andrew Wiles en 1995 con una elegante y completamente incomprensible demostración de ciento y pico páginas bien llenas de símbolos matemáticos) bien refutarlo encontrando un contraejemplo. Pues bien, resulta que la así llamada conjetura de Euler, de configuración muy parecida a la de Fermat, que preconiza que no existen soluciones a la ecuación x^4 + y^4 + z^4 = w^4, siendo x, y, z y w números enteros, fue finalmente refutada cuando alguien (supongo que sería un ordenador) encontró un contraejemplo…

Resulta que 2682440^4 + 15365639^4 + 187960^4 = 20615673^4.  ¡¿Quién lo iba a decir?!

Repito, pues: formalmente no es suficiente, lo sé, pero para mí, viejo informático gruñón, sí lo es. Además, el número final de fórmulas que contiene el fichero es “extraño”, o al menos para mí lo es: descomponiéndolo en factores primos, resulta que esos factores primos de 1.025.472 son 2,2,2,2,2,2,3,7,7 y 109. No sé interpretarlo, claro, pero raro es, ¿no? Sobre todo ese enigmático “109“… Y no, no es mi edad. Todavía. ;)

Hasta aquí la diversión… o el tostón, según se mire. Igual a algún lector le ha dado alguna información sobre cómo funciona… no, funcionaba el cerebro de un informático viejo y tozudo enfrentado a un problema difícil. Y espero que algo hayáis aprendido de la importancia de conseguir algoritmos que no sólo hagan lo que tienen que hacer, sino que lo hagan eficentemente.

Y ojo, y para acabar con esta “Loa a la Optimización“: no siempre es bueno optimizar todo lo posible. Que quede claro que hacer las cosas ”eficientemente” no quiere decir “automatizarlo-todo-siempre”.

Me explico: hay veces que tenemos un problema que, seguramente, se da una única vez en la vida, por ejemplo, una fusión de dos Cajas de Ahorros impelidas por las circunstancias… Para conseguir que la Caja (o Banco, o lo que sea) resultante sea eso: Una, y no dos mitades de Caja cada una con su propio sistema incompatible, habrá que unificar los sistemas y los datos de una y otra (clientes, cuentas, etc) en un solo sistema (o eso hacíamos en nuestros tiempos; ahora… ¡quién sabe!). Esto podemos hacerlo con un maravilloso programa que tenga en cuenta todos y cada uno de los casos, posibilidades, excepciones y tontadas varias propias de cada entidad, o bien hacer un programa mucho más sencillo y barato que arregle sólo el 98% de los datos, los casos sencillos, los  ”normales”, y arreglar luego a mano lo que quede, las excepciones. Haciendo bien las cuentas, es muy probable que sea más rápido, eficaz y barato hacerlo de la segunda manera… aunque nos quedemos con las ganas de hacerlo todo, todo y todo mediante nuestros programas. Ya sabemos que “lo mejor es enemigo de lo bueno“.

.

Y ahora sí, esto se ha terminado.  Disfrutad de la vida, mientras podáis.

  1. 42 es el quinto número de Catalan, números combinatorios que definen, entre otras cosas, de cuántas formas distintas se pueden colocar paréntesis en fórmulas de n operadores y n+1 operandos. []
  2. 451+62÷-3x+, que traducido a notación “infijo” sería: [ 4+(((5+1)-(6÷2) )x3) ], recordando siempre que 1, 2, etc en realidad hacen referencia al primer operando dado, al segundo, etc. []
  3. Ejecutando miles y miles de veces el proceso de resolución con números aleatorios, y contando cuántas operaciones nos ahorramos. []
  4. Dejo la demostración para quien quiera ejercitarse en combinatoria básica. []
  5. Para ello, lo sencillo y rápido es clasificar el fichero de las fórmulas resultantes (las ”formas canónicas”) de menor a mayor, lo que dejará juntas a las fórmulas iguales, y luego eliminar todas las duplicadas. []
  6. Recordad siempre que el 1, 2, etc representan al primer número dado, el segundo, etc, y se sustituirán por ellos al hacer los cálculos; no son estrictamente 1,2, etc. []
  7. Del mismo rango, para ser precisos. []
  8. Ésas serían las operaciones precisas para revisar el fichero completo, es decir, para comprobar que no hay solución. Si sí que hay solución, el número de operaciones necesarias lógicamente puede, y suele, disminuir mucho. []
  9. Sumando los cuatro números da 5.127.360, que es el resultado de multiplicar el número de fórmulas del fichero por 5 operaciones en cada una. Naturalmente. []

Sobre el autor:

Macluskey ( )

Macluskey es un informático de los tiempos heroicos, pero no ha dejado de trabajar en Informática y disfrutar con ella hasta la fecha. Y lo que el cuerpo aguante. Y además, le gusta la música...
 

{ 30 } Comentarios

  1. Gravatar cruzki | 07/07/2011 at 12:15 | Permalink

    @Macluskey

    Un apunte, no es que no seas suficientemente listo y no sepas comprobar que dos sucesiones de operación no son equivalentes, es que es un PROBLEMA HIPERJODIDO (NP-completo para los que sepan algo de complejidad algorítmica) de los que valen un millon de $.

    En tu caso posiblemente sea algo más simple por las condiciones de contorno (los 6 inputs que eliminan la distributiva y alguna cosilla más) y sea lo que te permite hacer un ataque de reducción por “fuerza bruta” (vamos, a base de pensar que transformaciones te llevan a una sucesión de operaciones canónico) pero en general no vas a poder hacerlo. De hecho ya has visto como se te ciclan tus optimizaciones y tienes que inventarte alguna heurística :P

    Otro apunte en la linea de lo que dices al final. En general las optimizaciones “complican” el código, pero es que muchas veces TAMBIÉN LO HACEN MÁS LENTO!!!!! Actualmente tanto los compiladores como los Sistemas Operativos como los Microprocesadores tienen “optimizadores” de código que pueden hacer que un código supuestamente optimizado colisione con alguno de estas estrategias y lo haga más lento.

    Para muestra un botón: en la última versión del kernel linux han decidido eliminar ciertas optimizaciones que realizaban en unas colas porque había detectado que iban en el mismo sentido que las optimizaciones que realizaban los procesadores x86 actuales y como resultado habían observado una reducción de velocidad del 6%!! (en procesadores antiguos y en otras arquitecturas dichas optimizaciones por lo visto si que tienen sentido y se van a conservar). Por eso una de las reglas básicas es COMPROBAR que la función optimizada REALMENTE es más rápida.

    De resto, chapó por otro de tus fantásticos artículos.

    PD: para los curiosos las sucesiones de operaciones se suelen llamar circuitos aritméticos o stright line programs y el problema que está intentando resolver Macluskey es el de isomorfismo de fórmulas (o de grafos o de circuitos).

  2. Gravatar J | 07/07/2011 at 07:40 | Permalink

    Cuando vi y edité el artículo de Mac, me daba miedo que alguien pensara que este tipo de optimización es imprescindible para cualquier problema… y no, no lo es. A menudo los técnicos nos dejamos llevar por el problema y su solución elegante, cuando hay soluciones no técnicas mejores.

    Ejemplo (está novelado, porque fue hace mucho tiempo y no recuerdo los detalles, pero en lo esencial es un hecho real): hace unos años un cliente nos pidió convertir unos gráficos de proyecto de un formato a otro (de autocad a microstation, si no recuerdo mal, pero no estoy seguro). El técnico vio que el propio importador de microstation era capaz de hacer el 90% de la conversión correctamente, y que vaya, con unos scripts podía pretratar los ficheros para que luego el importador los convirtiera bien. Después de una semana de trabajo, el script de pretratado no lograba funcionar del todo, pero estoy seguro de que nuestro aguerrido técnico hubiera terminado de hacerlo bien… de no ser por el hecho de que mientra tanto el jefe le había dado los mismos ficheros a la secretaria (con un coste/hora mucho menor que el de nuestro técnico), le había enseñado a hacer la importación que hacía bien el 90%, y le había enseñado a corregir manualmente el 10% restante… así que al acabar la semana, la automatización no estaba terminada, pero el trabajo hecho a mano sí.

    Ahora las malas noticias: el técnico era yo ;-)

    Un ejemplo similar, que me ha recordado cruzki. No lo he conocido personalmente, me lo contaron mis compañeros (una vez más, está novelado). Había un determinado algoritmo que era o(n^2), y alguien encontró la forma de convertirlo en o(n·log n). Lo de o(n^2) quiere decir que la complejidad del algoritmo crece con el cuadrado del número de entradas. Así que si tenemos que tratar 100 registros, tardará del orden de 100^2 = 10000 unidades de tiempo, mientras que si hay que tratar 1000000 de registros, tardará 1000000000000 unidades de tiempo.

    Por lo tanto, obviamente, nlogn es mejor que n^2, ¿no? Para 100 registros tardará 200 unidades de tiempo, que no es mucha ganancia, pero para 1000000 de registros tardará 6000000 unidades de tiempo, lo cual es una ganancia abrumadora.

    ¿Apuestas?

    Pues no. Sí, pero no.

    Curiosamente, cuando lo ponían a ejecutar, ¡tardaba más el nlogn!

    Después de mucho trabajo de investigación llegaron a la conclusión de que el primer algoritmo, el n^2 cabía entero en la caché del microprocesador, por lo que lo hacía a toda leche, mientras que el segundo no cabía, había que estar yendo a memoria principal (que es varios órdenes de magnitud más lenta que la caché) a por el código y los datos, y al final, para el conjunto de registros que tenían que tratar, tardaba más.

    Conclusión: optimizar está bien, pero no hay que hacerlo por que sí, hay que pensarlo.

    PS: me ha picado el gusanillo, y quizá algún día escriba algún artículo sobre esto de la complejidad de los algoritmos…

    PS2: venga, todos a bajarse mi juego de cifras y letras:

  3. Gravatar Macluskey | 07/07/2011 at 08:10 | Permalink

    @cruzki: Caramba, “Circuitos aritméticos”, qué bonito…

    La pena es que todo este asunto de complejidad de algoritmos y tal no se estudiaba en el Pleistoceno. Únicamente vi algo de esto de manera formal en los cursos de Doctorado, a principios de los ochenta, donde era una disciplina “nueva” y tal. Luego, ya en mi vida profesional, no he podido estudiar en detalle estos temas, así que no soy nada experto (hombre, algo sí sé, pero no mucho).

    De todos modos, con 32Kb de memoria no había mucho de qué preocuparse, con conseguir que tu programa cupiera en la memoria, ya habías hecho bastante!! ;)

    @J: Tienes más razón que un santo. Por las mismas razones que le digo a cruzki, no sabes cuánto me gustaría poder entender lo del NP-duro y el NP-completo a la “antes simplista…”.

    Y el programita es estupendo. Yo no tengo ningún android, pero he convencido a un amigo que sí tiene uno y estuvimos jugando un poquito el finde pasado… Es divertido y está muy bien hecho… lástima que no te dé la solución cuando tiene. Pero eso podrías implementarlo usando el ficherito que he colgado!! Mira tú por dónde, igual sirve para algo!!! Por supuesto, puedes usarlo a tu gusto (y cualquiera, también); lo he declarado de dominio público. Y funciona.

    Gracias por vuestros comentarios.

  4. Gravatar Eagle | 07/07/2011 at 11:05 | Permalink

    @Mac: casi me vuelvo loco con tanta transformación y tanta operación. Me he tenido que tomar una chocolatina para despejarme, jaja. El ejercicio de optimización que has hecho, estoy por apostar que no lo hacen hoy en el 99.99% de las “cárnicas” que hay. No ya por la tendencia a “que le metan más CPU”, sino por la aplicación de conceptos básicos de matemáticas que hoy ya casi nadie recuerda o es capaz de aplicar.

    Lo de J me hizo gracia pero claro, lo que él iba a hacer hubiera valido para “posteriores” migraciones futuras o incluso para otros clientes, mientras que lo de la secretaria fue puntual. Imagina que la secretaria pierde “los ficheros” con los cambios… a volver a hacer MANUALMENTE todo otra vez. Yo creo que casi siempre es bueno optimizar, raro es el caso donde solo uses una solución una única vez. Pasa como con los proyectitos que empiezan de pequeños: si total es para una chorrada… luego a alguien se le ocurre meter más funcionalidades y más… y al final sale la gestión completa de una empresa. Si desde “la tontería” del principio haces las cosas bien, el proyecto final funcionará mucho mejor.

  5. Gravatar Sergio B | 07/07/2011 at 11:20 | Permalink

    Es curioso que la lista no falle con las oportunidades que tiene para ello. Hombre no se si hace falta un generador aleatorio, al fin y al cabo dependiendo del juego, creo que no se podían repetir todos los números, pero supongamos que si, tenemos 7.529.536 combinaciones de números y 900 números, vamos 6.776.582.400 combinaciones posibles, son bastantes, pero no se si es imposible probarlas todas. aunque bueno, las 900 no pueden tocarse, pero a los 7 millones supongo que podremos quitarle muchas, solo con ordenarlas y quitar las repetidas, ¿no? Vamos, haciendo la comprobación para todos pues podremos estar seguros del todo.

    No entiendo por que la transformacion 6 no incluye a la 5 la verdad.

  6. Gravatar Macluskey | 07/07/2011 at 11:42 | Permalink

    @Eagle: ¡Espero que te haya aprovechado la chocolatina! ;)

    No. Evidentemente las “cárnicas” no van a hacer algo como esto. Primero porque dudo que los perfiles de profesionales que usan tengan los conocimientos como para poder atacar un cierto problema analíticamente de esta forma. Y segundo, porque, en caso de que los tuvieran, no lo harían porque consume tiempo. Y ellas facturan unas horas “x”, pero procuran por todos los medios gastar sólo “x/2″. Y si quieres algo más, te lo facturan como mejora. Así viven, es lícito, pero no se le pueden pedir virguerías…

    Estas cosas las hago yo por placer más que nada… si me pagaran por ello, también intentaría hacer lo menos posible por el mismo dinero. Es muy humano.

    @SergioB: Desde luego, la trasnformación 6 engloba a la 5. Si las he separado es (igual que la 1 y la 3) por claridad de exposición: entendida la 5, que es fácil, se entiende rápidamente la 6. Luego, a la hora de implementarlo, es mucho más sencillo y rápido de ejecución el tipo 5 que el 6, así que lo mantengo así.

    Y en cuanto a probar todas las posibles combinaciones posibles… Muy largo, ¿no? Quizá un día lo haga (tampocio es muy difícil de programar), pero no sé si me gustaría tener al ordenador un par de meses funcionando sin parar… Si alguna vez lo hago, escribo un artículo y lo cuento.

  7. Gravatar Sergio B | 07/07/2011 at 12:29 | Permalink

    @Macluskey lo que no tengo claro, que supongo que si, es si a la 6 le has quitado todos los que serian la 5, pero vamos expongo mi lio:

    “Aplicando exclusivamente esta transformación 6 sobre el conjunto de fórmulas originales se eliminan 8.025.840 fórmulas, un 27% de las fórmulas originales [menos que la transformación 5, ¿la has quitado de la 6?, ¿cuando dices x tienen que ser como mínimo dos?]. Si aplicamos conjuntamente las transformaciones 5 y 6 una detrás de otra, el número de fórmulas eliminadas es de 17.060.400, es decir, un 58% del total [¿Por que no es la suma de la 5 y la 6? ¿no debería de ser si acaso mas por que ha movido formulas?....¿o es menos por eso?..¿cuantas combinaciones eliminaría aplicar la 6 y después la 5?]. Cada vez quedan menos…”

  8. Gravatar Camarada Bakunin | 07/07/2011 at 01:18 | Permalink

    Fantástico análisis. Me ha llevado un rato leer las dos partes y los comentarios, pero merece la pena.

    Hace años que no veo el concurso, pero en tiempos había auténtico pique entre mi padre, mi madre y yo. Una táctica común que teníamos los tres a la hora de “atacar” las pruebas de números era la descomposición del número objetivo en factores primos. Te permite llegar de un vistazo (bueno, un vistazo entrenado, pero un vistazo) a muchas de esas soluciones “raras” que discutiáis en la primera parte. Y dentro de tiempo.

    ¿Habría forma de incorporar alguna de estas tácticas “humanas” al ataque mecánico? ¿O no merecería la pena?

    Gracias por los artículos.

  9. Gravatar cruzki | 07/07/2011 at 01:35 | Permalink

    @Mac

    Ya veremos que se puede hacer con lo de “complejidad algoritmica simplista” :P

  10. Gravatar Macluskey | 07/07/2011 at 02:40 | Permalink

    @Sergio: Tienes razón en que quizá no está muy bien explicado en el artículo. Contesto (tras haberlo verificado ;) ).

    Haciendo la transformación 5 sólo, se eliminan 8.025.840 combinaciones.

    Haciendo la transformación 6 sólo, se eliminan 17.060.400 combinaciones… las mismas que haciendo primero la 5 y luego la 6. En realidad la 5 es sólo un caso particular de la 6; si dejamos a la 6 solita, encuentra todos los de la 5 y, además, el resto que ella encuentra y la 5 no. Insisto: En realidad con la transformación 6 bastaba y se puede eliminar la 5 sin que pase nada. El motivo de mantenerlas es simplemente tiempo de proceso: es más rápido dejar que la 5 se elimine su parte y que luego la 6 elimine lo que quede, que dejar que la 6 haga sola el trabajo.

    Naturalmente, estamos cambiando tiempo de “materia gris” (programación) por tiempo de “silicio”, de CPU. Esto sólo tiene sentido cuando el programa se va a ejecutar muchas veces; para una única vez, o dos, no merece la pena. Lo que pasa es que en este caso he ejecutado muchísimas veces los programas de optimización, y al cabo, compensaba…

    Gracias por tus valoraciones y comentarios.

    @Camarada Bakunin: Si te das cuenta, con la solución final, comprobar poco más de un millón de fórmulas es rapidísimo en un PC normalito (unos tres segundos en verificar todo el millón de fórmulas; mucho menos si encuentra solución). Y eso, sin optimizar “en serio” lo que es el propio algoritmo en sí. Se podría paralelizar el proceso, precalcular operaciones, recodificar el fichero para hacerlo más compacto y, por tanto, más rápido de leer… en fin, ¡incluso usar un ordenador más potente!! :)

    Así que en este caso no creo que merezca la pena, pero puede haber problemas más complejos que sí se vean mejorados sensiblemente por una aproximación humana.

    En el siguiente comentario contaré una anécdota que ilustra esto.

    Saludos

  11. Gravatar Macluskey | 07/07/2011 at 02:52 | Permalink

    La anédota prometida.

    Como sabéis, clasificar cosas (registros, filas, datos…) por una clave es uno de los problemas más típicos y más consumidores de recursos con los que trata la informática. (Ver: http://eltamiz.com/elcedazo/2009/03/23/historia-de-un-viejo-informatico-el-sort-o-el-viejo-problema-de-ordenar-las-cosas/ )

    A mediados de los 90 ya se conocía todo acerca de los algoritmos de clasificación: burbuja, inserción… y quicksort. Hoare había demostrado que Quicksort era el algoritmo más rápido existente, sólo que no es muy intuitivo e implementarlo bien, con su recursividad y todo, no es nada sencillo, sobre todo si lo comparamos con la sencillísima burbuja, fácil en todos los sentidos… y lentísima.

    Así estaban las cosas (básicamente cerradas, pues ya no había nada que aprender al respecto) cuando se publicó en BYTE, revista de referencia de la época, un artículo que hablaba de una cosa llamada “Combsort”, que era básicamente la burbuja, sólo que en vez de comparar un elemento con el siguiente, comparaba un elemento con uno que estaba “un poco más allá”.

    Resultaba que codificar un “Combsort” era casi casi tan sencillo como hacerlo con la burbuja, pero su rendimiento era, en la mayoría de ocasiones, apenas un 30% más lento que un buen Quicksort… Es decir, más que suficiente para muchísimas aplicaciones.

    …Y la comunidad informática quedó conmocionada. ¿Dónde rayos estaríamos mirando tanto informático de pro para no habernos dado cuenta de que con esta sencilla modificación se ganaba tantísimo?? Hasta que a un iluminado se le ocurrió.. y nos iluminó a todos.

    Esas cosas pasan. A veces aplicar un poco de lógica “humana” puede mejorar sensíblemente un algoritmo. Lo díficil es… ¡saber cuándo (y dónde) hacerlo!

    Saludos

  12. Gravatar Pedro | 07/07/2011 at 04:06 | Permalink

    Mira que eres sexy cuando hablas de algoritmos y optimización, condenado :)

  13. Gravatar Antonio Villena | 08/07/2011 at 08:12 | Permalink

    @Macluskey me ha encantado el artículo, tanto que me ha dado por hacerlo en javascript, en mi caso uso algoritmo backtracking más sencillo.

    http://antoniovillena.es/2011/07/cifras-y-letras

    Como en el artículo anterior me animaste a escribir sobre el tema, aquí lo tienes, puedes subir el artículo al Cedazo si lo deseas. Aunque aviso que la implementación al estilo “Spaghetti code” no es para nada instructiva. Está más orientada al rendimiento: mi humilde netbook lo resuelve en milisegundos, y el caso peor (no encuentra solución) en alrededor de medio segundo.

  14. Gravatar Macluskey | 08/07/2011 at 08:45 | Permalink

    @Antonio Villena: ¡Estupenda solución, y estupenda página!

    Enhorabuena.

    Sí que es cierto que el código es un poco lioso, al menos para mí, pero la solución de adoptar un algoritmo de backtracking es muy elegante (de hecho, más que la mía, que es más de informático de la Edad de Piedra).

    Desde luego, no defiendo que “mi orientación” sea algorítmicamente la correcta para resolver este problema. El ánimo era más bien ilustrar un proceso de optimización sobre un problema de bases sencillas y comprensibles. Lo correcto en el caso de Cifras y Letras sería aplicar un algoritmo como el tuyo o el de Pedro Reina (cuya página, por cierto, no conocía, y me ha gustado mucho) y dejarse de zarandajas.

    Eso sí: ¡lo que me divertí en su día pensando en combinaciones y transformaciones!! ;)

    Gracias por tu comentario y por compartir tu trabajo.

  15. Gravatar helq | 10/07/2011 at 03:08 | Permalink

    @Macluskey encantadores tus artículos :D . Me has recordado en tu repuesta #11 uno de los principios que tiene Python y que creo que debería ser fundamental para todos: “Debería haber una — y preferiblemente sólo una — manera obvia de hacerlo.”, pero claro está única manera en muchas ocasiones es muy difícil de hallar y el caso del Comb Sort no lo demuestra. (Aunque claro, yo no reemplazaría a QuickSort por Comb Sort ya que la segunda es menos eficiente aunque algo enredada)

  16. Gravatar Antonio Villena | 10/07/2011 at 08:24 | Permalink

    @Macluskey Que va, lo elegante es lo tuyo, lo del backtracking es la solución “fácil”. Yo defiendo que “tu orientación” es algorítmicamente la más correcta, pero has “pecado” en la implementación. Optimizaciones que se me ocurren para tu programa:

    1. Restringir la entrada ordenando el array de mayor a menor. Así te podrías quitar las fórmulas en las que restas o divides un elemento con otro anterior (el anterior siempre es mayor o igual).

    2. Usar cálculos intermedios con todas las posibilidades que hay para 2 ó 3 elementos. El problema es que aplicas un millón de fórmulas pero repites los cálculos una y otra vez. Por ejemplo en lugar de hacer (a+b)c-(d-e)/f haces precalculadox-precalculadoy, con x=(a+b)c, y= (d-e)/f.

    3. Hacerlo todo en código. Ya sé que suena un poco bestia pero leer un fichero e interpretarlo va a ser siempre muy lento. Por supuesto el código lo generas automáticamente partiendo del archivo.

    4. También te puedes ahorrar muchas fórmulas testeando casos ilegales en los resultados de los cálculos intermedios como negativos, ceros, fraccionales.

    Para que te hagas una idea de los cálculos redundantes que hace el backtracking: un problema que se resuelve con una única fórmula (de los del artículo anterior) tiene 84 ramas solución.

    He visto tu archivo y las fórmulas siempre usan 6 operandos. Deberías añadir las de 5 o menos operandos (son muchas menos), porque hay casos que se pueden resolver con 5 y no hay forma de hacerlo con 6, ejemplo: 1-1-1-1-1-100 y número a hallar el 5.

  17. Gravatar Macluskey | 10/07/2011 at 12:50 | Permalink

    @Antonio: Gracias por tus notas.

    Sobre tu comentario, tengo a su vez bastante que contar…

    En primer lugar, hay que distinguir claramente entre resolver un problema concreto y resolver el modo en que se resuelven todos los problemas. Me explico con un ejemplo:

    Si te piden resolver la integral de cierta función entre dos puntos, digamos x=1 y x=2, puedes hacerlo de dos maneras:

    1) Analíticamente. Encuentras la función integral de la original, calculas su valor para x=1 y x=2, y la diferencia es la integral pedida. Pero así, en realidad, has hecho mucho más que resolver el caso particular para x=1, 2. Has resuelto cualquier caso que pudieran darte para calcular. Ahora te da igual qué valores de x te dan, los calculas y resuelves. Ésta es mi orientación, analítica. En realidad lo que he hecho es buscar un conjunto de fórmulas equivalentes a todas las dadas, eliminando, si no me he equivicado en algo, toda la redundancia existente (aunque no puedo demostrarlo, claro).

    2) Resolver la integral pedida por métodos heurísticos. Por ejemplo, defines un cuadrado entre x=1 y x=2, por un lado, y en las ordenadas, valores suficientemente altos o bajos para comprender todo valor de la curva (buscando antes máximos y mínimos y tal), y entonces “bombardeas” el cuadrado con millones de puntos (x,y) aleatorios. Para cada uno de ellos, calculas si pilla por encima o por debajo de la curva original, y lo apuntas. Si al final has bombardeado 10 millones de puntos, y cuatro millones estaban por por debajo de la curva, puedes decir con suficiente aproximación que la integral que te han pedido es un 40% del valor del área total del cuadrado. La ventaja es obvia: Sirve para cualquier función, aunque no haya forma de encontrar su función integral de forma analítica, a cambio de ser más lenta de ejecución. Ésa es tu aproximación: lidiar con cada problema concreto. Y es perfectamente válida, y posiblemente más rápida que hacerlo leyendo el ficherito…

    Una vez entendido esto, verás que no tiene demasiado sentido ni ordenar los argumentos previamente (si hay una sola forma de solucionar el problema, sólo vale un registro, estén como estén ordenados o desordenados los argumentos). Tampoco tiene sentido usar los cálculos intermedios para no repetir operaciones, siempre suponiendo que el fichero contiene fórmulas sin redundancia alguna, porque eso sólo sirve para un problema concreto; si los argumentos cambian, los resultados cambian. Hombre, meter todo en código… digamos que saldría un programa graaaaande; ;) y en cuanto a testear los casos ilegales, ya lo hace mi programa… en la parte de solución de problemas concretos. En cuanto calcula un valor menor o igual que cero o con decimales, aborta la fórmula. Pero eso es parte de la implementación del programa para resolver un problema concreto.

    Por otra parte, no hay que calcular las combinaciones que sólo usan dos o tres… o cinco números para hallar la solución; están contenidas en las fórmulas del fichero. El programa que busca soluciones comprueba que haya o no llegado a la solución al realizar cada cálculo válido, y devuelve como solución dos datos: la combinación “ganadora” y el número de operadores que ha tenido que usar para llegar a ella (de 1 a 5).

    Recuerda: lo que aquí expongo es un procedimiento para compactar fórmulas, de los 31 millones iniciales, al millón final, sólo a base de eliminar redundancia de fórmulas. Y el fichero aplica a cualquier conjunto de argumentos, tanto de números como de objetivos. Es decir, estoy intentando hallar la función integral para luego aplicar valores, no resolver la integral “a pelo”. Aunque me ponga pesado: El fichero de fórmulas no contiene redundancia ninguna (o al menos yo no las he detectado: ya sabes que no tengo argumentos para asegurarlo, pero bueno), pero al aplicar a una fórmula concreta sí puede haberlas: de hecho, siempre que basten cuatro o cinco operaciones para llegar a la solución, habrá redundancia (el resto de operadores que queden, que pueden ser sumas, restas,…), y desde luego que hay redundancia cuando se repite algún número, pero es redundancia “del problemas” no “de las fórmulas”.

    Desde luego, en este caso, y dada la potencia de los ordenadores actuales, quizá no compense tamaño esfuerzo (bueno, sí… ¡no sabéis cómo me divertí), y es mucho mejor implementar un buen backtracking, pero habrá otros en que sí compense.

    … Mmmmm. Ya he escrito otro tocho. ¡Si es que no se puede conmigo!!! :)

  18. Gravatar Antonio Villena | 10/07/2011 at 01:58 | Permalink

    @Macluskey guayyyy menudo tocho. Perdona hay cosas que he supuesto mal, porque no he visto tu código. Y otras que no me he explicado bien.

    He entendido que lo que explicas es un procedimiento general para reducir fórmulas. Y el proceso es totalmente correcto y muy brillante. Lo que te indicaba es que se pueden aplicar optimizaciones en la implementación, que no sé exactamente como está hecha pero me imagino por cómo lo cuentas en el artículo.

    Te pongo ejemplos concretos con fórmulas de tu fichero, usando los puntos que te indiqué en el comentario anterior:

    1. Ordenar de mayor a menor el array de entrada. Con esto puedes eliminar en torno a la mitad de las fórmulas, en tu fichero serían todas las fórmulas con cadenas 21/, 21-, 32/, 32-, 31/, 31-… 61/, 61- ya que analíticamente: 1>=2>=3>=4>=5>=6. Ejemplo línea 8871 fórmula 1234+++65-*.

    2. Cálculos intermedios. Ejemplo de uso en las dos primeras fórmulas: Sin optimización: (cambio números por letras) if ( total==a+b+c+d+e+f ) mostrar solución y salir if ( total==a+b-c-d-e-f ) mostrar solución y salir Con optimización: temp1= a+b; temp2= c+d+e+f; if ( total==temp1+temp2 ) mostrar solución y salir if ( total==temp1-temp2 ) mostrar solución y salir Hemos pasado de 10 a 6 sumas.

    3. Hacerlo en código. Con el ejemplo anterior se entiende, sería traducir las fórmulas a infijo y compararlas una a una con el número a hallar.

    4. Lo de comprobar valores ilegales yo lo haría pero en los datos intermedios (para descartar fórmulas enteras), una vez dentro de la fórmula creo que sería mejor aplicarla del tirón y comparar.

    Por último, las combinaciones de 5 o menos números las tratas bien, pero eso te obliga a comparar en cada operación. Creo que sería más óptimo quitar todas esas comparaciones intermedias (solo comparas una vez aplicada la fórmula completa) y añadir las fórmulas para dichos casos, que comparativamente son menos, y las pones al principio. Con esto te aseguras de encontrar una solución más corta, y puedes usar los cálculos de las combinaciones de 5 o menos números como datos intermedios para las de 6 (guardados en variables temporales).

    Bueno yo también estoy escribiendo un tochaco, espero no aburrirte. El esfuerzo de optimizar siempre compensa, aunque solo sea para sentirte bien por tí mismo de ver lo que se puede hacer.

  19. Gravatar Macluskey | 10/07/2011 at 09:08 | Permalink

    ¡¡Cómo me divierto!! Hacía tiempo que no mantenía una conversación tan interesante y productiva… :)

    En primer lugar, el método de comprobación no puede ser más sencillo: - Toma los argumentos del problema (6 números y un objetivo). - Abre el fichero de fórmulas. - Lee la primera fórmula. - Para cada registro del fichero de fórmulas, hacer: * Para cada carácter de la fórmula (son 11), proceder: . Si es un número, tomar el número equivalente e introducirlo en la pila. . Si es una operación, ejecutar dicha operación con los dos elementos de la cabeza de la pila, y dejarla en la cabeza de la pila. Si el resultado es igual al objetivo (o mejor que el mejor que tengamos), apuntarlo (o parar si es igual, según lo que se desee). Si el resultado es menor o igual que cero o tiene decimales, parar el cálculo de la fórmula.

    Y yastá. Dependiendo de lo que quieras hacer, puedes revisar todas las fórmulas siempre (si lo que quieres es saber cuántas soluciones hay) o directamente parar y mostrar resultado si se encuentra.

    Yo lo tengo implementado en Cobol, que para algo es el único lenguaje en el que me siento cómodo. Ni es un lenguaje muy eficaz ni mi ordenador es muy rápido, pero tarda unos 2,8 segundos de media en revisar todo el fichero, con todo y lectura. Haciéndolo en C o algo mejor, sería un tiro, o simplemente manteniendo en caché el fichero…

    Sobre tus apreciaciones. Voy una a una.

    Eliminar fórmulas con restas o divisiones, habría que hacer dos cosas: Una: variar el método de comprobación (el que he enumerado antes), ordenando previamente los números. Eso no es muy difícil y sería muy rápido. Una buena burbuja y listo. Entonces, con este criterio, podríamos eliminar algunas fórmulas del fichero.

    El inconveniente es que dejaría de ser un conjunto Universal de fórmulas: necesita que sus argumentos estén ordenados o no garantiza nada. Dependiendo de cuántas fórmulas eliminemos, compensa o no. Se podrían, efectivamente, eliminar las fórmulas en que se restara un argumento mayor de uno menor. No sé cuántas fórmulas se quitarían así. Si puedo, lo compruebo y os lo cuento mañana. Pero no puedo hacerlo con las divisiones. ¿Por qué no? Porque puede haber números repetidos entre los argumentos. Si hay números repetidos (y es, de lejos, lo normal, como un 90% de las veces), quedarían juntos al ordenar, y entonces “54/” no significaría siempre generar decimales: si los argumentos 4 y 5 fueran iguales, “54/” daría 1: un resultado perfectamente válido. A priori, pues, no se pueden eliminar divisiones. Quizá sí si hay varios números de diferencia, como en “51/”. Ya tendría que ser casualidad que todos los argumentos del 1 al 5 fueran iguales, pero lo importante es que la fórmula sería redundante en este caso, porque la “54/” ya daría 1. Aunque no lo he pensado del todo (lo estoy haciendo mientras escribo) seguramente se podrían eliminar las fórmulas del tipo “xy/” siempre que x fuera mayor que y en más de una unidad…

    Insisto: habría que saber cuántas fórmulas se eliminarían así (que seguro que no son la mitad ni mucho menos, pero ya veremos), y si compensa el hecho de comprometer al algoritmo de comprobación. Ya haré los cálculos y contaré los resultados…

    Cálculos intermedios. No me he puesto a hacer cuentas, pero me da la sensación, el olfato de viejo zorro informático del Medioevo me dice que si tengo que andar metiendo código para determinar si puedo o no hacer cálculos intermedios, seguramente no compense el hecho de ahorrase unas sumas o restas.

    Meter el fichero en código. Se puede meter en una tabla interna, claro. A ver quién se codifica eso ;) Si vamos a resolver muchos problemas, sí que es interesante primero leer el fichero y cargarlo en la tabla interna, y luego sólo recorrer la tabla. Si sólo vas a resolver un caso, o un caso cada vez, no creo que compense. Pero sí es una solución. De hecho, en los programas de comprobación que tengo para revisar miles de soluciones, lo hago así. Siguen tardando mucho… :=(

    Comparar datos ilegales. Con el algoritmo que he puesto arriba, verás que no tiene mucho sentido complicarlo mucho más. Es muy sencillo y rápido. Y lo mismo digo de las fórmulas que sólo necesitan con cuatro o cinco operadores. No creo que merezca la pena ampliar el número de fórmulas a comprobar para ganar algo de tiempo en cada fórmula, pero no he hecho los cálculos aún… puede que tengas razón y sea más rápido meter las fórmulas que no hacer las comprobaciones de número válido en cada operación. Serían en el pero de los casos algo más de cuatro millones de comprobaciones, al estar en el bucle interior (4 x 1.025.472); grosso modo (cálculo de cabeza) quedarían unas 325.000 combinaciones de cuatro operadores, unas 100.000 de tres, unas 35.000 de dos y unas pocas de uno solo… má-o-meno millón y medio de operaciones adicionales. ¿Qué sería mejor? 4 millones de comparaciones o millón y medio de operaciones. Las operaciones aritméticas consumen bastante más ciclos de reloj que las comparaciones… buff. Habría que probarlo, vaya.

    Y sí. Esto es divertido, realmente divertido. Es uno de los trabajos más divertidos que puede haber en esta profesión nuestra… ¡¡Mucho mejor que hacer informes!! :)

  20. Gravatar Antonio Villena | 10/07/2011 at 11:51 | Permalink

    Hola Macluskey

    Me alegra que te divierta la conversación. A ver no he comprobado personalmente ninguna sugerencia y por ejemplo si te digo que se pueden reducir a la mitad por ordenad igual me equivoco y solo puedes reducir un 25%.

    Si que es verdad que como lo tienes ahora es muy sencillo, y algunas cosas que te propongo requieren “complicar” bastante las cosas, como lo de los datos intermedios.

    En eliminar fórmulas con restas y divisiones, puedes eliminar las divisiones también porque la otra fórmula (la que tiene el orden inverso) también la tienes, por ejemplo en la línea 8911 (1234+++65/+) tendrías la recíproca en la línea 102 (1234+++56/+).

    Lo de cálculos intermedios posiblemente no compense. Yo lo probaría en un caso sencillo como todas las operaciones que involucren 2 elementos y ver que tal. Por ejemplo a+b, a-b, ab, a/b, a+c, a-c, ac, a/c… sigo solo con sumas para abreviar a+d, a+e, a+f, b+c..b+f, c+d..c+f, d+e, d+f y e+f. Un gran inconveniente es que tienes que crear nuevas variables y cambiar las fórmulas, que se volverían más crípticas. Por ejemplo la fórmula a+b+c+d+e+f se renombraría a algo como var25+var48+var99 siendo var25= a+b, etc…

    Meter el fichero en código. Hombre no lo vas a hacer a mano caso por caso, sería por generación automática de código. Y no te estoy hablando de meterlo en una tabla (en RAM) para que vaya más rápido, sino de transformar todo el fichero de fórmulas en una hiper-mega-función y luego compilar el archivo de un millón de líneas.

    Comparar datos ilegales. Claro que no tiene ningún sentido en el algoritmo que has puesto arriba. Tendría sentido sólo si implementas la tabla en código.

    Si quieres puedo ayudarte haciendo el generador de código para el caso más sencillo (sin cálculos intermedios, sin comparar datos ilegales y encontrando sólo las soluciones que usan los 6 operandos). ¿En qué lenguaje lo necesitas?

  21. Gravatar Macluskey | 11/07/2011 at 07:24 | Permalink

    @Antonio: Bueno, hoy no puede ser. :(

    A ver si mañana…

    Ah! No, no necesito que lo programes en ningún lenguaje, con mi antigualla de Cobol me apaño… salvo que quieras divertirte un poco, claro… :)

  22. Gravatar Macluskey | 13/07/2011 at 11:12 | Permalink

    @Antonio Villena:

    Estoy trabajando (más o menos) en el tema que nos ocupa. En principio, efectivamente tienes razón. Tomando como requisito que los números de partida estén ordenados de menor a mayor, si eliminamos directamente las combinaciones del tipo xy!, siendo x>y, y ! o bien una resta o una división, parece que se sigue funcionando bien. Eso quiere decir que los problemas con números ordenados para los que no hay solución revisando el fichero reducido, tampoco la tienen revisando el fichero original, el del millón de combinaciones.

    La reducción es de más de 300.000 combinaciones, quedando unas 640.000.

    El problema es que no estoy seguro de que se pueden eliminar tranquilamente las combinaciones cuando son divisiones.

    Pero es largo para un comentario. Estoy pensando en escribir un artículo corto explicando el proceso. Y en asegurarme de que se puede efectivamente cambiar todo. Y eso sólo puedo hacerlo generando todos los posibles problemas (!) y revisarlos. Sí, generar todas las combinaciones posibles y mezclarlas todas ellas con los 899 posibles objetivos (101 a 999)… Un puñao.

    Así que, si te parece, Antonio, nos emplazamos para dentro de unos días o semanas, cuando tenga todo masticado.

    Pero, vamos, que tenías razón y se puede acortar el proceso sensiblemente eliminando esas fórmulas “ilegales a priori” a cambio de ordenar los argumentos antes de procesar el fichero.

    Saludos

  23. Gravatar Antonio Villena | 14/07/2011 at 01:14 | Permalink

    @Macluskey genial, veo que no te rindes. Yo también le hice la reducción, usando un editor y con expresiones regulares y se me redujeron a 631.632 fórmulas, por lo que creo que lo hice bien (si quieres te mando el archivo resultado).

    Pero usando la misma idea (números ordenados) se pueden reducir aún más fórmulas, no se cuántas, pero en este caso la reducción es menor.

    Teniendo en cuenta que a+b>a, a+b>b, ab>=a, ab>=b y cosas similares, se pueden descartar más términos, en este caso de 3 o más elementos (no sólo los de 2 que ya hemos reducido). Por ejemplo si a>=b>=c, entonces c/(a+b)<1 por tanto se descarta.

    De acuerdo, lo dejamos para dentro de unas semanas.

    Por cierto he hecho el conteo cuando se usa el algoritmo generador que usaban el La2. Si no me he equivocado me sale: C(9,0)C(14,6)+C(9,1)C(13,4)+C(9,2)36C(12,2)+C(9,3)C(11,0)= 3003+9715+36*66+84= 11898

    Así que menos de 12 mil posibles entradas no son tantas como para probarlas todas. En este caso habría que ejecutar el programa 11898*899= 10.696.302 de veces. Esto serían 123.8 días a 1 por segundo. Pero claro si optimizas un poco y haces 20 por segundo, lo tendrías verificado en menos de una semana.

  24. Gravatar Macluskey | 14/07/2011 at 04:40 | Permalink

    @Antonio: Ayer no di las cifras exactas porque no las tenía a mano.

    La reducción de fórmulas con una resta/división elemental desordenada, en caso de estar ordenados los argumentos, es de 207.495 fórmulas con la resta y otras tantas con la división. Pero como hay fórmulas a las que aplican ambos casos, la reducción total es de 314.595 fórmulas. El fichero resultante es de, efectivamente, 631.632 registros. Ambos hemos coincidido, luego hemos debido hacerlo bien… :) Sin embargo, algo no me gusta del todo y estoy ligeramente mosqueado. Por eso comprobar millones de combinaciones…

    No veo muy bien de dónde te sale el número de posibles combinaciones de los seis argumentos ordenados, cada uno con 14 posible svalores: casi 12.000. Yo intenté brevemente calcularlo analíticamente… y no me salió, así que lo programé y listo (¿se nota que soy informático, no matemático?). ;)

    Salen 27.132 combinaciones posibles, sin contar con ninguna restricción, como la de que no haya más de dos valores superiores a 10, etc, que creo que sí hay en el programa. Es decir, desde la 1,1,1,1,1,1 hasta la 100,100,100,100,100,100.

    Ahí están comprendidas combinaciones que de ninguna manera tienen solución para cualquier objetivo dado, como la 1,1,1,1,2,2, por ejemplo y así con bastantes, pero no me merece la pena quitarlas, cuesta más el collar que el perro. Revisar el fichero completo de 631000 fórmulas se hace a razón de 45 por minuto en mi PC antediluviano, así que poco podría ganar eliminando cien o doscientas de antemano, las instrucciones de determinación para ver si la elimino o no seguramente costarían más que lo que ahorran.

    Estoy preparando la comprobación sistemática de todas las combinaciones. De momento lo he hecho para 101 a 102… poco, pero de momento no hay ninguna combinación que, no teniendo solución vía el fichero reducido, sí la tenga con el completo. O sea, parece que va bien.

    Ya me di cuenta de los casos que dices, de operaciones con tres o más operandos de tal modo que, estando ordenados, indefectiblemente den soluciones negativas o no enteras. Pero ni he estudiado en detalle cómo hacerlo, ni sé cuántas fórmulas elimina.

    En fin, de momento iré probando combinaciones contra objetivos, a ver si encuentro un contraejemplo. O no. Y seguiré dando vueltas al asunto… ¡Qué vicio!!

    Seguimos hablando…

    Mac

  25. Gravatar Antonio Villena | 15/07/2011 at 06:44 | Permalink

    Hola Macluskey Acabo de hacer el conteo para el caso que me dices, por el mismo método que antes y me sale una cifra un poco diferente, así que en algo me habré equivocado. La técnica es aplicar la fórmula de la combinatoria para todos los posibles casos de repeticiones. La cifra que te dí antes (11898) era para el caso de que solo se puede repetir, y una vez, los números del 1 al 9.

    sin repeticiones C(14,0)*C(14,6); 3003

    rep 2 +C(14,1)C(13,4); 14715= 10010 +C(14,2)C(12,2); 9166= 6006 +C(14,3)*C(11,0); 364

    rep 3 +C(14,1)C(13,3); 14286= 4004 +C(14,2)*C(12,0); 91

    rep 4 +C(14,1)C(13,2); 1478= 1092

    rep 5 +C(14,1)*C(13,1); 182

    rep 6 +C(14,1)*C(13,0); 14

    rep 2+rep 3 +C(14,2)C(13,1); 9113= 1183

    rep 2+rep 4 +C(14,2)*C(13,0); 91

    Total: 26040

  26. Gravatar Antonio Villena | 15/07/2011 at 07:37 | Permalink

    Ya he encontrado el fallo, aquí están los cálculos correctos. Nota: como en los comentarios desaparecen algunos asteriscos, ahora uso la letra x.

    sin repeticiones C(14,0)xC(14,6); 3003

    rep 2 +C(14,1)xC(13,4); 14×715= 10010 +C(14,2)xC(12,2); 91×66= 6006 +C(14,3)xC(11,0); 364

    rep 3 +C(14,1)xC(13,3); 14×286= 4004 +C(14,2)xC(12,0); 91

    rep 4 +C(14,1)xC(13,2); 14×78= 1092

    rep 5 +C(14,1)xC(13,1); 182

    rep 6 +C(14,1)xC(13,0); 14

    rep 2+rep 3 +C(14,1)xC(13,1)xC(12,1); 14x13x12= 2184

    rep 2+rep 4 +C(14,1)xC(13,1)xC(12,0); 14×13= 182

    Total: 27132

  27. Gravatar Macluskey | 15/07/2011 at 07:48 | Permalink

    @Antonio:

    ¡Cáscaras! Menudo trabajo de orfebrería… con razón no llegaba yo a ningún lado. Se ve que la combinatoria no es lo mío, pero entre los Números de Catalan del anterior artículo y esto, los artículos están quedando incluso “serios” :) y todo…

    En mis pruebas, voy por el 134 y todo parece ir bien… Pero tarda mucho, por más que he afinado lo indecible el programa para que no haga ni una instrucción de más… Seguramente en un ordenador moderno con cuatro núcleos y eso iría más deprisa, pero esto es lo que hay…

  28. Gravatar Eagle | 15/07/2011 at 10:23 | Permalink

    Madre mía, madre mía… ¿os he contado ya que ayer me aprendí la tabla del 7? A ver si mañana me aprendo la del 8 y en unas semanas os estoy haciendo sombra con las combinatorias… :P

  29. Gravatar Valero | 04/12/2016 at 10:32 | Permalink

    No sé por que has eliminado tan alegremente las operaciones donde un resultado intermedio es fraccionario. Hay respuestas que solo pueden obtenerse si se ha operado con números fraccionarios. Una cosa es que establezcas la convención de que no se pueden hacer divisiones si el resultado no es entero, y otra es que si se pueden hacer obtengas el mismo valor entero con otras operaciones sin divisiones no enteras. En la operación a[b+(c/d)] encontrarás miles de ejemplos donde si admites la división y continuas obtendrás un resultado final entero que si eliminas las divisiones no enteras no podrás conseguir. Por ejemplo con los números 2, 3, 5, 12 obtener 44. La forma es 12[2+(5/3)] = 12·(11/3) = 132/3 = 44 y con operaciones que solo involucren divisiones exactas es imposible conseguir 44.

  30. Gravatar Macluskey | 05/12/2016 at 09:10 | Permalink

    Querido Valero:

    Pueeessss….. la verdad es que tienes razón..

    Supongo que me confié con el caso de la resta, donde sí que parece evidente que siempre existe una fórmula equivalente que evita los números negativos, y lo hice extensible a la división porque, como todo el mundo puede ver, je, je, es para estos menesteres equivalente a la resta…. ¿no?

    ¡Y un cuerno! El contraejemplo que das es palmario; la pena es que no encontrara yo un contraejemplo similar cuando pensaba en estas cositas, hace ya una buena temporada…

    De todos modos, creo que todo el proceso de reducción de fórmulas, que es lo que yo creo que es interesante del artículo, sigue siendo válido; lo que habría que hacer es: en la comprobación de cada fórmula no descartar una combinación si da un resultado intermedio no entero, como proponía. Al hacerlo, seguramente, de eliminar alrededor de un 47% de operaciones, como decía en el artículo, igual se descarta sólo un 20% ó un 25% (dato inventado en estos momentos, pero que puede ser plausible). Algo es algo.

    Muchas gracias por la corrección. Lo que no voy a hacer es reprogramar nada ni revisar nada, más que nada porque ¡a saber dónde conservo yo los programas que me hice para escribir tanto desatino! ;)

    Un saludo.

{ 1 } Trackback

  1. [...] En este artículo voy a contaros cómo es posible resolver de forma óptima, o al menos lo suficientemente óptima, mediante programas informáticos, los acertijos de ambas partes del programa, la de “Letras” y la de “Cifras”, que es la que es realmente interesante… siempre desde la consabida óptica de antes simplista que incomprensible inherente a la casa en que estamos alojados. Segunda parte: eltamiz.com/elcedazo/2011/07/06/resolviendo-cifras-y-letras-ii/ [...]

Escribe un comentario

Tu dirección de correo no es mostrada. Los campos requeridos están marcados *

Al escribir un comentario aquí nos otorgas el permiso irrevocable de reproducir tus palabras y tu nombre/sitio web como atribución.