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.

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.

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á.

.

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.

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  , 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 , 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 .  ¡¿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. [↩]