Cifras y Letras es un veterano concurso de televisión de origen francés (Des chiffres et des lettres), que, con mínimas diferencias, se ha emitido a lo largo de los años en muchísimos países del mundo (el autor ha visto el concurso en bastantes lugares del mundo, zapeando en la tele de esos hoteles del mundo mundial al que una vez le llevaron sus andanzas de “Viejo Informático”). En España se empezó a emitir en 1991, y, con algunas lagunas y cambios de emisora, se viene emitiendo desde entonces con asiduidad.

Imagen (Screenshot) de la versión inglesa del programa (Wikipedia)

Hace años estuve yo una buena temporada no diré que obsesionado, pero sí interesado en el programa, que como se emitía a las tres y pico de la tarde, o sea, cuando yo estaba trabajando en la oficina o donde fuera, lo grababa cada día y lo veía luego grabado por la noche siempre que podía, intentando ponerme en la piel de los concursantes. Pensar en acertijos de cifras y letras me relajaba mucho después de mi ardua tarea…

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.

El objetivo de este artículo no es tanto investigar la forma matemáticamente óptima de atacar un problema concreto como puede ser éste, sino más bien mostrar un ejemplo de cómo desmenuzar paso a paso el ataque a un problema dado, para resolverlo de la forma más eficiente que nos sea posible, en este caso mediante un programa informático, pero en otros quizá mediante técnicas de ingeniería, matemáticas o del tipo que sean. Y he dicho eficiente, es decir, que obtiene los resultados deseados con el mínimo uso de recursos posible.

En nuestros atareados tiempos de Teras de disco, Gigas de RAM, GHz de velocidad de procesador y procesadores de no-sé-cuántos núcleos, y todo ello barato, barato, nos hemos acostumbrado (mal-acostumbrado) a resolver todos nuestros problemas informáticos a base de aumentar los recursos todo lo aumentable. ¿Que va lento…? ¡Métele más Gigas, leñe! ¡Y más rápidas! Y hay veces que, por más recursos que le eches, sigue sin ir bien…^[1]

Yo empecé a trabajar, a mediados de los setenta, con un ordenador con memoria de ferritas de unos 400KHz (sí, K, no M, ni mucho menos G), con 32 KB de RAM (efectivamente, K, no M, ni mucho menos G) y discos duros removibles de 4 MB (M, ni G ni T ni ná de ná). En estas condiciones había que ser un auténtico artista para conseguir escribir una liquidación de cuentas o de préstamos que funcionara como es debido en ese ordenador del Jurásico. Y lo lográbamos. No penséis, sin embargo, que ese problema de la asfixiante escasez de recursos de máquina ha desaparecido hace años… Hoy en día sigue habiendo problemas donde la optimización es absolutamente necesaria, bien porque requieren tratar con muchísimos millones de datos, o porque necesitan gestionar miles de transacciones por segundo, o simplemente porque deben funcionar en dispositivos móviles, empotrados o de escasa capacidad. De eso va en realidad esta historia, tomando como excusa al inocente “Cifras y Letras”…

Además, para que el artículo no quede en pura investigación para optimización, aprovecharemos para contar un par de las herramientas que los informáticos, ingenieros y otra ralea similar utilizamos para resolver algunos problemas: los diccionarios (en este caso, diccionario inverso) y la notación polaca inversa (o notación postfija). Vamos allá.

Descripción del juego

Primero de todo, una breve descripción del mecanismo del juego, para aquellos que no lo conozcan.

Cada programa enfrenta a dos concursantes (aunque nada impediría que fueran tres, cuatro o cualquier número), y consta de dos tipos de pruebas, según indica el propio nombre del concurso: Pruebas de Cifras y Pruebas de Letras. Típicamente hay seis u ocho pruebas de letras y cuatro de cifras, pero supongo que cualquier otra combinación es posible. En cada una de las pruebas se obtienen puntos y gana el concurso quien más puntos obtiene: eso le da una cierta cantidad de dinero, no mucho, y el derecho a volver al día siguiente a enfrentarse a un nuevo concursante. Y a quedar como chico listo en el barrio, claro.

Para cada prueba, sea de cifras o de letras, se dispone de 45 segundos de tiempo para obtener la solución. 45 segundos suele ser un tiempo muy ajustado para estos menesteres, por lo que “ver” la solución de antemano es vital para llegar a buen puerto.

Las pruebas de “Letras” consisten en que aparece un cierto número de letras (normalmente, nueve), con un cierto número mínimo de vocales y consonantes (creo que, de hecho, los participantes piden una vocal o una consonante, por turno), y luego los concursantes intentan componer con dichas letras palabras válidas en español; gana cada prueba el que consigue la palabra válida más larga, y en caso de empate no recuerdo si se repartían los puntos o ganaba quien tuviera la mano, que iba pasando sucesivamente de uno a otro concursante.

Ejemplo: Imaginemos que las nueve letras que aparecen son: P, A, O, H, C, I, E, A, L. Los concursantes piensan durante los 45 segundos de que disponen. Al acabarse el tiempo, uno dice: “7 letras” (porque había encontrado “CHAPELA”, típica boina vasca); el otro dice: “Yo, de 8“. Entonces se le da la opción a contestar al que más letras ha juntado en su palabra, el de 8 letras. Que dice: “ALOPECIA” (seguramente porque el hombre es calvo y conoce bien la palabra). Como la palabra “alopecia” sí existe en el diccionario, se lleva los puntos de esa prueba, y se pasa a la siguiente. Si la palabra que hubiera encontrado no fuera correcta, se le da la oportunidad al otro concursante, y así.

.

En cuanto a las pruebas de “Cifras”, aparece una serie aleatoria de seis números y un cierto número objetivo de tres cifras. Los números base para calcular la solución están limitados a los números del 1 al 10, el 25, el 50, el 75 y el 100. Catorce valores posibles, pues, y creo, además, que existían ciertas limitaciones en el concurso, como que no pudiera haber más de dos números superiores a 9 en la serie de números dados, aunque esta restricción es irrelevante para la resolución del problema. Por otra parte, los números se pueden repetir, es decir, puede que haya dos cincos, o tres sietes o cuatro unos entre los seis números dados. En cuanto al número objetivo, debe estar comprendido entre 101 y 999, lo que garantiza que al menos se necesite operar con dos números de los dados para componer cualquier solución acertada, puesto que el mayor número que puede aparecer es el 100.

Gana la prueba el concursante que consiga obtener el número objetivo exacto utilizando los números dados, sin repetir ninguno y combinándolos entre sí usando sólo las cuatro operaciones elementales (suma, resta, multiplicación y división). No es necesario usar obligatoriamente los seis números, sino los necesarios para obtener el número objetivo. Por ejemplo, si el objetivo es el 108 y entre los números dados tenemos un 100 y un 8, basta sumarlos para obtener el resultado exacto, ignorando los otros cuatro. En caso de que ninguno de los concursantes consiga el número exacto, gana la prueba quien más se aproxime, y en caso de empate rige el mismo criterio, sea cual sea, que en la parte de Letras.

Ejemplo: Supongamos que los seis números que aparecen son los siguientes: 100, 8, 2, 5, 75, 7, y el número objetivo es 816. 45 segundos. Tic-tac-tic-tac… Uno de los concursantes dice: “El 817“; el otro dice: “El exacto“. Éste último tiene la oportunidad de explicar cómo ha llegado al número exacto, y dice: “100 por 8; 800. Por otro lado: 75 más 2, 77, que dividido por 7 da 11. 800 más 11, 811, más el 5 que queda, 816“. Si se hubiera equivocado en sus cálculos, entonces el otro concursante podría explicar cómo ha llegado al 817 y ganar así la prueba, etc.

El Diccionario de la Real Academia de la Lengua

Parte importante del concurso son los dos expertos, uno de letras y el otro de cifras, que validan si la solución dada por el concursante es o no válida, y proponen, en su caso, una mejor alternativa. En el caso de Letras, la validez o no de la palabra la dicta el diccionario de la RAE; en el de Cifras, la ejecución de las operaciones elementales en el orden dado por el concursante comprobando que no se ha cometido error alguno y se llega al número dicho por él. Esto no es muy complicado, y no hace falta ser experto de ningún tipo para ello.

Luego, los expertos proponen una mejor solución, si la hay, que para eso son expertos. Si la palabra ganadora encontrada por el concursante tenía seis letras, el experto propone otra válida de siete u ocho, o, raramente, de nueve, si es que existe y la encuentra (ha habido alguna ocasión en que yo, espectador, encontré una palabra válida de ocho y el experto no la vio, lo que considero perfectamente normal, dado que lo habitual era que ocurriera exactamente lo contrario).

En cambio, en la parte de Cifras, si no se ha encontrado por los concursantes cómo llegar al número exacto, el experto interviene y dice, ufano: “Muy buena aproximación (en realidad esto lo dice siempre, aunque se haya quedado a cuatrocientos ochenta números del buscado); esta vez no hay forma de conseguir el exacto”, o bien dice: “Para conseguir el número exacto hay que…”, y entonces explica el procedimiento para obtener la solución. Hay veces que, aunque los concursantes no encuentren la solución, es factible para alguien con práctica hallarla… pero otras… Veamos: “Tomamos el 75, le sumamos el 8, que da 83 y le restamos el 10, que da 73. Por otro lado multiplicamos el 7 por el 2, que da 14, multiplicamos el 14 por el 73 de antes, lo que da 1022. A ese 1022 le restamos el 25 y obtenemos el 997 que buscábamos… Fácil, ¿no?”

¿Fácil? ¿En 45 segundos? ¡Venga ya! Por muy experto que sea el experto, no me lo creo. Siempre pensé que seguro, seguro, que usa un programa… luego vemos cómo puede escribirse tal programa, y espero que gracias a mi… ejem, fluida prosa, los no informáticos podáis entender también los entresijos de la solución.

Letras y Cifras para la Palm en SmallBASIC (ejecutado sobre Windows, por eso se ve feo)

El amigo J, otro frikazo de talla mundial donde los haya, se implementó tiempo ha una versión de Cifras y Letras en la Palm… no es sólo que se ejecutara en la Palm, es que lo programó en la propia Palm, con el miniteclado virtual táctil, una pantalla de 4 pulgadas y toda la parafernalia. Para los afortunados que aún posean una Palm, podéis encontrar el programa aquí, el código fuente aquí, y el intérprete de SmallBASIC aquí. También hay un intérprete para Windows o Linux en la misma página, pero sabed que se ve un poco más feo que en la Palm.

.

Resolviendo la parte de “Letras”

El programa informático que resuelva este problema no es muy complicado: compone palabras con las letras dadas (es un típico y sencillo problema combinatorio) y las compara con un diccionario para ver si son válidas o no… es más un problema de tiempo de respuesta,^[2] pues pueden formarse muchísimas palabras con esas nueve letras o un subconjunto de ellas. Informáticamente hablando es largo, tedioso y pesado, pero no es de mucha dificultad.

Existen, naturalmente, técnicas para agilizar el proceso. La más sencilla es capturar todas las palabras posibles y válidas del diccionario, es decir, las de nueve letras o menos,^[3] ordenar sus letras de mayor a menor y almacenar en una base de datos para cada una de ellas una fila (registro) con tres campos. Los tres campos indican, respectivamente, la longitud de la palabra, su valor ordenado y la palabra correcta equivalente.^[4] Por ejemplo, la palabra “ordenado” se almacenará como: longitud de la palabra: 8; “roonedda”, que es su valor ordenado de mayor a menor, y la palabra origen correcta, “ordenado”.

Luego, en tiempo de resolución, dadas las nueve letras del problema, se van haciendo subconjuntos con ellas; primero de nueve letras, luego de ocho, de siete, etc. Para cada una de estas combinaciones, se ordenan las letras que la componen de mayor a menor^[5] y se comprueba en la base de datos si esa combinación existe (por longitud y valor ordenado). La primera combinación que exista en la base de datos es una palabra válida de la máxima longitud posible para esa combinación de letras (puede haber más, claro, pero no otra válida de mayor longitud). Insisto, puede ser largo, pero no difícil.

Siguiendo el ejemplo anterior, si las letras del problema fueran por ejemplo: “daondexro”, primero se comprobaría la palabra de nueve letras, ordenándolas de mayor a menor, lo que dejaría “xroonedda”, palabra que seguramente no existiría en nuestra buena base de datos. A continuación se prueban las nueve combinaciones de ocho letras, descartando una letra cada vez. Eventualmente se descartará la “x”, y al probar el resto, “roonedda” con longitud 8, se encontrará que esa entrada sí que existe en nuestra base de datos, y se obtendría la solución: “ordenado”. Claro que también sería una solución válida “rodeando” (infinitivos, participios y gerundios son los únicos tiempos verbales que son admitidos como correctos según las normas del concurso), que tiene las mismas ocho letras en distinto orden; en cualquier caso, ambas soluciones son correctas y valdría con dar con una de ellas para “ganar” la prueba, aunque el programa podría dar todas la palabras encontradas con la misma clave (longitud-valor ordenado) para que el experto elija la que más le guste.

Y no hay mucho más que hacer en esta parte. Es un sencillo programa… una vez se dispone de la Base de Datos con todas las palabras posibles.

Ejemplo: Supongamos que, tras décadas de viaje en fuga criogénica, estamos en Puertas del Cielo, donde sufrimos una apoplejía por envenenamiento cuando trabajábamos cavando canales de ácido más allá del perímetro… lo mismito que le ocurrió a Martin Silenus, el poeta de “Los Cantos de Hyperion“, de Dan Simmons,^[6] y, lo mismo que le ocurrió a él, todo nuestro vocabulario quedó reducido a tan sólo nueve palabras, todas ellas del hemisferio derecho del cerebro. Esas nueve palabras, que componen nuestro diccionario completo, son:   “follar”, “mierda”, “pis”, “coño”, “maldición”, “hijoputa”, “culo”, “pipí” y “popó”. Si son palabras malsonantes, lo siento, pero son exactamente las mismas de que dispuso Martin Silenus cuando escribió sus afamados “Cantos de la Tierra Moribunda”, de los que se vendieron cinco mil millones de copias, así que no será tan malo, digo yo…

Sí, son pocas palabras. Es lo que tienen las apoplejías por envenenamiento, que no miran lo que se llevan por delante: siete sustantivos ciertamente escatológicos, una interjección, un único verbo y ningún adjetivo ni adverbio. Además, para colmo, dos de las palabras (pipí y popó) están repetidas y son eufemismos infantiles… Poca cosa. Bastaba.Y hasta aquí puedo leer... El que quiera más, ya sabe: Hyperion, de Dan Simmons.

Muy bien, sigamos con lo nuestro y apliquemos el proceso a las dichosas nueve palabras:

Como veis, en “Texto ordenado” están las mismas letras de la palabra original, pero ordenadas de mayor a menor, y hemos apuntado cuidadosamente su longitud. La clave de búsqueda será la suma de este texto ordenado más la longitud.

Supongamos que las nueve letras que nos dan son: “PHJUSAOTI“.^[7]. Primero ordenamos las letras de mayor a menor, y nos queda: “UTSPOJIHA“. Entramos en el algoritmo de búsqueda en sí:

1) Intentamos con la palabra de 9, buscando en nuestra base de datos de malsonantes términos “UTSPOJIHA”,”9″. No existe, así que seguimos en el paso 2.

2) Intentamos ahora las palabras de 8 letras. Para ello, vamos eliminando sucesivamente una letra cada vez, y comparamos con el resto.

2.1) Quitamos la “U”, y buscamos con ”TSPOJIHA”,”8″. No existe. Sigamos.

2.2) Quitamos la “T”, y buscamos con ”USPOJIHA”,”8″. Tampoco existe. Sigamos.

2.3) Quitamos la “S”, y buscamos con ”UTPOJIHA”,”8″. ¡Bingo! Hemos encontrado una de ocho, y aquí podemos parar: el mejor resultado posible es “hijoputa”, de 8 letras.

Si por lo que fuera la fea palabrita de 8 letras no estuviera en nuestro diccionario, seguiríamos buscando, primero las de siete letras en el paso 3 (eliminando de todas las formas posibles dos letras de las nueve), luego las de seis, etc, hasta que eventualmente encontremos por fin una de tres letras que sí existe: “spi”, que nos da “pis”. En fin, ésta es la manera de utilizar un diccionario inverso para resolver un problema informático. Espero que se haya entendido.

Resolviendo la parte de “Cifras”

No nos engañemos: la auténtica gracia reside en las pruebas de Cifras, al menos para los que no somos de Letras (aunque, con el paso de los años, no estoy yo nada seguro de que un informático del Pleistoceno sea más de Ciencias que de Letras…).

Analicemos primero el problema. Tenemos a nuestra disposición seis números base (que pueden ser todos distintos o puede haber alguno de ellos repetido; de hecho lo raro es que no haya ninguno repetido) y las cuatro operaciones elementales, suma, resta, multiplicación y división, para alcanzar un cierto número objetivo de tres cifras; los números base sólo podemos tomarlos una única vez, y no es necesario utilizar todos ellos para alcanzar el objetivo. Las bases del problema son, pues, claras.

Desmenucemos un poco más el asunto.^[8]

La primera aproximación de buen informático experto es atacar el problema por fuerza bruta.^[9] Es decir, calcular todas y cada una de las posibles combinaciones operando con los seis números y las cuatro operaciones elementales. ¿Cuántas formas posibles hay de combinar números y operaciones? Muchas, sí, pero… ¿cuántas? Vamos a contarlas.

Primero: ¿Cuántas formas tenemos de tomar los números? Como tenemos seis números, que rotularemos como “1”, “2”… “6” (lo que representa al primero de los números dados, el segundo, etc, y no al número 1, al 2, y así), podemos tomarlos, independientemente de las operaciones que hagamos con ellos, de 720 maneras diferentes. 720 es el resultado de calcular el factorial de 6 (6!), que es el número de permutaciones que podemos obtener con seis elementos, es decir, 6! = 6x5x4x3x2x1 = 720. ¿Sí?

123456, 536142 ó 654321 son, por ejemplo, tres de las 720 combinaciones de números válidas.

Segundo: ¿Cuántas formas posibles hay de operar con dichas combinaciones? En cada combinación de seis números, es decir, una vez fijada cada manera posible de ordenar los seis números dados, podemos operar hasta un máximo de cinco veces, es decir, usar cinco operadores de cuatro clases diferentes, admitiéndose cualquier operador tantas veces como sea necesario. Eso son 1.024 formas diferentes de operar, pues 1.024 es el resultado de 4 elevado a 5, donde 4 es el número de operadores diferentes y 5, cuántos operadores son necesarios, es decir, las variaciones con repetición de cuatro elementos tomados de cinco en cinco.

Por ejemplo, “+++++”, “+-x-x” ó “÷÷÷÷÷” son tres de las 1.024 combinaciones válidas.

Combinando ahora las posibles maneras de tomar los números y las posibles maneras de operar con ellos vemos que hay 720×1024 = 737.280 formas diferentes de realizar los cálculos, puesto que a cada una de las 720 combinaciones posibles de números se le pueden realizar operaciones de 1.024 maneras distintas, todas las maneras posibles de ordenar los cuatro operadores elementales.

¿Ya está? Pues no. Hay más, naturalmente. Sigamos.

Tercero: Ahora hay que ver de cuántas maneras posibles se pueden agrupar los números ante los cálculos, es decir, de cuántas formas diferentes se pueden colocar paréntesis en la fórmula. Por ejemplo, si tenemos la combinación de números 135246 y la combinación de operadores “+x+-÷”, una posible manera de combinarlos es [ (1+(3x5)+2-4)÷6 ],^[10] y otra manera posible, que dará un resultado completamente diferente, sería [ (1+3)x(5+2)-(4÷6) ], por ejemplo, y otra más sería [ 1+(3x(5+2-4)÷6) ], etcétera, etcétera.

Calcular cuántas formas posibles de colocar paréntesis es ya algo más complicado, así que los informáticos, para facilitarnos la vida, en estos casos decidimos cambiar la representación de la fórmula, es decir, su notación. Las fórmulas, en nuestra vida cotidiana, las representamos en una notación llamada “infijo” (o infix, en inglés). Todas las fórmulas que han aparecido hasta ahora (y todas las que os habéis encontrado seguramente en vuestra vida) están en notación infix. En esta notación necesitamos los paréntesis para especificar la preferencia (o prioridad) de las operaciones entre los operandos. Existen, sin embargo, otras notaciones que no necesitan de paréntesis para describir dicha preferencia. Una de ellas es la notación “postfijo” (postfix en inglés), aunque nadie en la profesión la llama así, sino “Notación Polaca Inversa”, en honor al matemático polaco Jan Lukasiewicz que la introdujo en los años veinte del siglo pasado, cuando ni existían los ordenadores ni siquiera se podía pensar que fueran a existir alguna vez…

Cómo funciona una Pila (LIFO o Data Stack)

Para resolver una fórmula escrita en Polaca Inversa es preciso usar una Pila (traducción al inglés: Stack o LIFO, éste último acrónimo de “Last Input-First Output”, es decir, el primer elemento en salir de la pila es el último en entrar), y el algoritmo es muy sencillo: si se tiene un operando, introducirlo en la cabeza de la pila (push); si se tiene un operador, operar con los dos elementos de la cabeza de la pila, descabezarla (pop) y dejar el resultado en su lugar. Y yastá. Durante los años setenta y ochenta, las mejores calculadoras programables de Hewlett-Packard funcionaban en polaca inversa, por lo que es muy familiar para ingenieros, matemáticos e informáticos de cierta edad… Por ejemplo, la fórmula infix (la forma habitual de representar fórmulas): (1+2)x3 se representaría como 12+3x, mientras que 1+(2×3) se representaría como 123x+. No es muy complicado con una mínima práctica.

Entonces, dadas dos combinaciones determinadas, la una con el orden de los seis operandos y la otra describiendo los operadores a utilizar, debemos, usando la notación polaca inversa, representar las diferentes agrupaciones de los operandos y operadores independientemente de cuáles sean estos, es decir, los modelos de operación posibles. Para definir nuestros modelos deberemos usar una cierta representación, por ejemplo una O mayúscula para representar un Operando y un punto (·) para representar un Operador. En cada combinación concreta las Oes se sustituirán sucesivamente por los operandos y en su orden, y los puntos, por los operadores también en su orden, es decir, la primera O por el primer operando, la segunda por el segundo, etc, y lo mismo con los operadores.

Por ejemplo, dada la combinación [ OOO·O·O··O·, 642531, +x÷x- ], la fórmula resultante será, en polaca inversa: 642+5×3÷x1-, o, lo que es lo mismo en infix, [ (6x(((4+2)x5)÷3))-1 ]. Recuerda: 1,2, etc no son los números 1,2… en sí, sino que hacen referencia al primer número dado, al segundo, etc, sean cuales fueran estos números.

Si no lo has entendido vuelve a leerlo detenidamente; no es difícil, pero es la base de todo lo que viene ahora…

.

Volvamos ahora a la pregunta de hace cuatro o cinco o seis párrafos: ¿Cuántas formas posibles de colocar paréntesis hay?, o lo que es lo mismo: ¿Cuántas combinaciones válidas de seis Operandos (Oes) y cinco Operadores (·) existen en notación Polaca Inversa? Hay que tener en cuenta que no toda combinación de seis Operandos y cinco Operadores es válida, pues para serlo es necesario que cuando aparezca un Operador (un ·) tiene que haber al menos dos Operandos (O) en la Pila de Cálculo. El motivo es sencillo: un operador cualquiera (suma, resta, etc) es binario, pues requiere de dos operandos para que tenga sentido, para que pueda ejecutarse; por ello una fórmula como “1+2” escrita en polaca inversa es inválida,^[11] porque la suma no tiene más que un único operando definido (el 1) y la suma (como el resto de operaciones elementales) necesitan dos operandos.

¿No lo ves? Claro, tus ojos te engañan. Esta fórmula de antes, “1+2”, en la notación que normalmente empleamos en nuestra vida cotidiana (infix) es validísima, y da 3 como resultado. Pero si quieres representar la fórmula anterior “1+2” en polaca inversa, deberías hacerlo “12+”. Se toma el 1 y se introduce en la pila; se toma el 2 y se introduce también en la pila; por fin, al tratar el “+”, se opera, sumando en este caso, los dos operandos de la cabeza de la pila, el 1 y el 2, y ahora sí, da 3 (que dejamos en cabeza de la pila). Por lo tanto, “1+2” en polaca inversa sería incorrecto: Se toma el 1 y se introduce en la pila, y ahora… ¿qué hacemos con el “+”, cuando sólo hay un operando en la pila? Luego introducimos el 2 y ¿qué hacemos con él? ¿Cuál es el resultado final de la fórmula? En fin, espero que ahora haya quedado claro.

Por ello, serán válidas todas aquellas fórmulas, o mejor, modelos de fórmula, que cumplan que, teniendo seis Operandos y cinco Operadores, para cualquier Operador (·) situado en el lugar n de la fórmula (para n comprendido entre 1 y 5, pues 5 es el número de operadores de la fórmula) tiene que haber al menos n+1 Operandos (O) situados a su izquierda.

Si no lo has entendido no te preocupes; es decir en términos finolis lo que es de sentido común: que para poder operar con dos números tiene que haber al menos… eso: dos números para poder operar el uno con el otro… Sí, de Perogrullo, pero es así.

El caso es que hay exactamente 42 combinaciones posibles,^[12] comenzando por la OO·O·O·O·O· y terminando por la OOOOOO·····. No me molesto en escribirlas, es largo y tedioso, y con pensar un poco se obtiene la lista fácilmente.

Actualización: darkdead, en un comentario, nos ilustra sobre cómo calcular el número total de formas de colocar paréntesis en una fórmula de n operadores y n+1 operandos. Es ni más ni menos que el quinto número de Catalan, que se calcula de la forma (2n)!/[(n+1)!(n)!]. Para n=5, el resultado es 42, al que empíricamente había yo llegado. ¡Nunca te acostarás sin saber una cosa más! ¡Gracias, darkdead!

.

El caso es que si hay 720 formas de ordenar los operandos; 1.024 maneras de operar con ellos; y 42 combinaciones posibles de colocar paréntesis, y todas ellas son compatibles con todas las demás, el número de fórmulas a probar es el producto de las tres cifras de marras, es decir, 30.965.760 fórmulas distintas.

¿Pocas? ¿Muchas? Depende…

Desde luego, hacer un programa que ataque el problema de los números por fuerza bruta es tan sencillo como que para cada combinación posible de operandos se prueban todas las posibles combinaciones de operadores, y para cada una de éstas, se prueban todas las posibles formas de ordenar los paréntesis. Cuando todos estos cálculos obtienen una solución exacta, se apunta y se acabó (salvo que queramos seguir buscando a ver si encontramos una solución que nos guste más); si no la obtiene, que será lo que ocurrirá casi siempre, se va apuntando el resultado más aproximado obtenido hasta el momento, y listo.^[13] Si hemos probado pacientemente los casi 31 millones de fórmulas y ninguna da el resultado correcto, es que no hay solución.

Fácil.

Pero si tenemos sólo 45 segundos para encontrar si existe o no solución para un problema dado, y teniendo en cuenta que calcular cada fórmula requiere hacer una serie de operaciones, comprobaciones, etc, 31 millones de combinaciones son bastantes, y dependiendo de lo fina que sea la implementación del programa y de la máquina en que se ejecute, puede no ser suficiente. Así que el buen informático experto no se queda ahí, sino que se pone a pensar cómo puede reducir el número de combinaciones a probar… y resulta que sí se puede reducir. Mucho… un montón, de hecho.

Pero el proceso de reducción, que es realmente divertido^[14] y didáctico, será objeto del próximo artículo, que éste ya va quedando largo…

Disfrutad de la vida, mientras podáis.

1. Como diría Forrest Gump: “Hay veces que no hay suficientes piedras…”. [↩]
2. ¡Y de obtener en algún sitio un diccionario de palabras válidas, claro! [↩]
3. Cómo y dónde obtener un fichero con todas las palabras españolas válidas es ya de por sí una tarea complicada o, al menos, pesada, en la que no voy a entrar. Parece que hay o ha habido en algún momento un CD editado por la RAE con todas las palabras del diccionario, pero ignoro dónde puede conseguirse… si es que puede conseguirse. [↩]
4. Para los expertos en Bases de Datos, el índice de la tabla será: longitud-valor ordenado. Será un índice no único, pues admite duplicados. Y sí, se podría ordenar perfectamente de menor a mayor, en lugar de mayor a menor, como yo propongo. Pero es mejor hacerlo de mayor a menor, es decir, descendentemente, porque así se reparten mucho mejor todas las palabras a lo largo de las diferentes letras; si lo hacemos de menor a mayor, imaginaos, por ejemplo, la gran cantidad de palabras que comenzarían por “a”: todas las que contuvieran al menos una “a” en cualquier lugar de la palabra. [↩]
5. Si se tiene la precaución de ordenar previamente las nueve letras del problema antes de comenzar el proceso de comprobación, evitamos tener que ordenar cada uno de los subconjuntos, lo que ahorra tiempo. [↩]
6. ¿De verdad es posible que no hayas leído todavía la mejor saga de ciencia ficción de fines del Siglo XX? Ya estás tardando. [↩]
7. Sí, ya sé que es evidente qué palabra se puede formar, pero sigamos el algoritmo por la cosa de la didáctica… [↩]
8. O “Hagamos un análisis de requerimientos”, como se dice ahora. [↩]
9. En realidad, ésa sería la aproximación de cualquier informático… [↩]
10. Recordad que aquí “1”, “2”, etc, no son los números 1, 2… en sí, sino que hacen referencia al primer número dado, al segundo, etc; es lo que los informáticos llamamos “direccionamiento indirecto”. [↩]
11. Sí, es inválida. Recordad: estamos escribiendo en notación polaca inversa, no en infijo. [↩]
12. Atención, chiste: no debería sorprendernos que diera precisamente 42, pues todo el mundo sabe que 42 es “Answer to the Ultimate Question of Life, The Universe, and Everything“, “La Respuesta Última a la Vida, el Universo y Todo”. [↩]
13. La comprobación de si el resultado obtenido es el número buscado o no debe hacerse no sólo al final, sino tras cada operación, puesto que también sirven los resultados intermedios. [↩]
14. O al menos así me lo parece a mí. [↩]

The Resolviendo “Cifras y Letras” (I) by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.