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:
| Palabra | Longitud | Texto ordenado |
| follar | 6 | rollfa |
| mierda | 6 | rmieda |
| pis | 3 | spi |
| coño | 4 | ñooc |
| maldición | 9 | onmliidca |
| hijoputa | 8 | utpojiha |
| culo | 4 | uolc |
| pipí | 4 | ppii |
| popó | 4 | ppoo |
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.
- Como diría Forrest Gump: “Hay veces que no hay suficientes piedras…”. [↩]
- ¡Y de obtener en algún sitio un diccionario de palabras válidas, claro! [↩]
- 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. [↩]
- 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. [↩]
- 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. [↩]
- ¿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. [↩]
- Sí, ya sé que es evidente qué palabra se puede formar, pero sigamos el algoritmo por la cosa de la didáctica… [↩]
- O “Hagamos un análisis de requerimientos”, como se dice ahora. [↩]
- En realidad, ésa sería la aproximación de cualquier informático… [↩]
- 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”. [↩]
- Sí, es inválida. Recordad: estamos escribiendo en notación polaca inversa, no en infijo. [↩]
- 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”. [↩]
- 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. [↩]
- 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.
{ 44 } Comentarios
Buenas, muy buen artículo, como siempre.
Sobre como obtener el diccionario: no será el de la RAE, pero en linux los correctores ortográficos traen uno. La notación no es tan clara, habrá que realizar alguna transformación, pero yo creo que valdría.
Y, sobre todo: Seguramente Hyperion sea uno de los mejores libros de ciencia ficción de la historia, pero, al menos para mi gusto, la saga de Ender o Fundación son superiores.
Yo también veía ese programa, pero hace tiempo que no lo pillo. A mi la verdad es que se me daba bien, sobre todo los matemáticos nunca he tenido problemas para conseguir el resultado exacto, así que no veo por que deberían de hacer trampa, la verdad. Con una serie de trucos, que probablemente harás informaticamente se facilita mucho las cosas y eso el cerebro lo hace bastante bien. Los informaticos sois muy kajun, la verdad. Yo estoy haciendo simulación numérica y los ordenadores me parecen cafeteras, días duran simulaciones optimizadas, vamos, es toda una experiencia.
PD. (100+2)*8 es mas bonito. Que es una ilustración de un truco, nunca usar unos de los números mayores de 9 directamente, o operar sobre el objetivo, 45 segundos dan para mucho, la verdad.
@Brigo: Para gustos, los colores… La Fundación, si te refieres a los tres primeros (Fundación, Fundación e Imperio y Segunda Fundación), desde luego que es la mejor saga de toda la ciencia ficción. Pero si incluyes a las precuelas y secuelas escritas treinta años más tarde, ahí ya no. Y la saga de Ender tiene dos libros extraordinarios, los dos primeros (El juego de Ender y La Voz de los Muertos), uno pasable (Ender el Xenocida) y un rollo patatero (Hijos de la Mente), que le costó a Orson Scott Card como cinco años escribir, porque no le quedaba más remedio que escribirlo porque había dicho que era una Tetralogía, y que apañó como buenamente pudo para terminarlo y seguir con la saga de Bean… En cambio, el último libro de la saga de Hyperion (El ascenso de Endymion) es el mejor de toda la saga. Para mi gusto, claro.
Pero, vamos, son opiniones, claro.
@Sergio: Claro que (100+2)*8 es más corto y lo que todo humano normal encontraría. Si he puesto una forma un poco más enrevesada es precisamente para marcar el hecho de que hay (o puede haber) muchas formas de llegar al mismo resultado.
En lo que no estoy tan de acuerdo es en que siempre es sencillo para un humano entrenado encontrar la solución numérica en 45 segundos. Muchas veces, sí. Otras, difícilmente. Otras más, imposible. Ejemplos tengo. Si los encuentro, os pongo alguno en comentarios, a ver si sois capaces de “verlos” en 45 segundos (que igual sí, eh??)
Gracias por vuestros comentarios.
Bueno, yo quería mas bien referirme a formas de conseguirlo, estrategias. Ir acercándote a pasos, factorizar, ademas depende del numero que factorice… bueno, nunca me he parado a informarme, pero es algo de psicologia de las matemáticas. Si nos fijamos en los números primos menores de 10 el 2 es lo mas familiar, el 3 en cambio es bastante mas ajeno, el 5 es también de lo mas común y el 7 en cambio es el mas extraño de todos. Y luego la verdad es que el 6 aunque no sea primo tiene para nosotros mas significado que el de ser 2*3, no como el 4, el 8 o el 9. Tenemos 2 de cada y 5 dedos, para el 3 ya tienes que mirar a los lados y al centro, algo bastante mas complejo, el 6 en cambio se cuenta con la mano también, usando 0 dedos, por eso se usan docenas digo yo, y en verdad dividiendo el 6 entre 2 puede que sea una forma mas natural de encontrar el 3. Pero el 7 es difícil encontrarlo, yo si tuviera que ponerle un numero al diablo seria ese jajaja. Nosotros multiplicamos por 10 añadiendo 0s lo que nos lo pone muy fácil, ventaja de no usar el sistema binario, pero vamos, las tablas de multiplicar las tenemos en memoria, creo que los ordenadores también las tenían, así que eso no seria una gran ventaja… Vamos que no es por meterme con los ordenadores, pero nosotros tenemos una herramientas que aunque no conozcamos muy bien funcionan muy bien en estas cosas.
A mi me ha quedado una duda al respecto de las combinaciones de paréntesis en notación polaca inversa. Siempre pensé que este tipo de notación era para precisamente evitar los paréntesis, y hasta hice una práctica en la universidad años ha en la que se reordenaba una fórmula quitando los paréntesis y metiéndola en una pila en notación polaca inversa. Pero en fin, mi duda: Creo (si no me he equivocado) que la fórmula (6x(((4+2)x5)÷3))-1 que tu escribes como 642+5×3÷x1- se puede escribir también como 42+5×3÷6×1-, manera que encuentro más ordenada, con dos cifras en un principio y después va todo con operador-cifra-operador… y que todas las fórmulas de este estilo pueden escribirse así. ¿No es posible que en esas 42 combinaciones de paréntesis ya estuvieran incluidas fórmulas dadas con anterioridad? A mi entender sólo habría las 720 permutaciones de cifras con las 1024 combinaciones de operadores binarios, en total las 737.280 combinaciones que dices al principio, pero seguro que hay algún detalle que se me escapa…
Me contesto a mi mismo
Creo que lo que se me escapaba eran las agrupaciones de operaciones tales como ((a+b)x(c+d))÷(e-f), que se escribiría como ab+cd+xef-÷ o lo que es lo mismo como OO·OO··OO··, abcdef, ++x-÷
Aun así sigo sin ver que todas las combinaciones de OO y ·· sean válidas (que no estén repetidas). A no ser que en esas 42 que comentas ya se hayan quitado las repetidas, claro.
@Sergio B: Tienes razón, claro. Hay estrategias que ayudan a resolver estos problemas de cifras a los humanos. Pero hay muchos problemas donde es realmente complicado encontrar la solución. ¡En 45 segundos, OJO! ¡Imaginaos, encima, hacerlo con la cámara grabando…!
Como prometí, aquí dejo unos cuantos problemas de esos que son difíciles de encontrar en 45 segundos. Intentad resolverlos… en 45 segundos, o si quieréis en un minuto completo, incluso en dos, y luego me decís qué tal os ha ido… Todos tienen solución, por cierto.
Primero pongo los números separados por guiones y luego el objetivo, separado por dos barras. Suerte!
2-8-10-9-10-8 // 956
3-25-9-1-9-5 // 781
75-5-75-1-7-6 // 922
5-4-6-2-7-3 // 959
4-25-50-4-5-1 // 687
75-10-1-8-9-1 // 351
4-1-7-6-4-8 // 958
9-4-3-5-3-2 // 323
Saludos
Ya está Macluskey, tirao.
Te paso solo mis resultados para que no sirvan de spoiler pa los demás, ahora, que me ha resultado muy sencillo obtenerlos eh? Esperaba yo un poco mas de “chicha”.
En el primero, debido al efecto ¡¡¡aaaghhhh se me acaba el tiempo!! he alcanzado como resultado “borrón-borrón”.
En el segundo he llegado al 675, podría haber atinado más, pero cambié de estrategia cuando ya era tarde.
En el tercero he alcanzado un honorable 912.3, que en su momento me pareció poca cosa, pero ahora estoy orgulloso.
En el 4 he logrado un 1003
En el quinto tengo otro borrón
Sexto: Borrón, borrón, 225 (a la desesperada y ahora no se si lo he sacado de verdad o si he confundido algún número).
Septimo:1000 clavaos (muy redondo).
Octavo: Un honroso 347 y además es e único en el que tengo las operaciones un poco claras.
A todo esto, me daba 45 segundos pero cuando el tiempo acababa me dejaba acabar la operación en curso (lo que posiblemente sea trampa) y una duda: ¿estas seguro de que no se pueden usar potencias? hay numeros que sin potencias me parecen imposibilisimos de la muerte.
Por cierto, me tienes que decir como lo has hecho, yo una vez puse en un artículo la palabra “hostia” y se lió, tu pones 7 malsonantes y no pasa na… igual el truco está en hacer referencia a algún libro…
¡¡Un saludo!! y gracias por le divertimento mental
.
Muy buen articulo!! Hablando de palabras malsonantes y de cifras y letras no puedo evitar enlazar el siguiente video: http://www.youtube.com/watch?v=c9_9K-9wI9U
Hola, recuerdo bien la notación polaca y las malas noches en la universidad.
Supongo, este mismo método puede aplicarse para juegos tipo Scrabble?
Saludos
@Eduardo: Sí, te aseguro que en las 42 que salen ya están quitadas todas las redundantes. De todos modos, en el ejemplo de tu primer comentario, ¿qué pasaría si en vez de (6x(((4+2)x5)÷3))-1 fuera algo casi igual: (6/(((4+2)x5)÷3))-1, donde el primer operador es una división? Pues que ya no podrías reordenar la fórmula como lo has hecho… Piénsalo bien y lo verás claro.
@Rantamplan: ¡¡¡Lo que me he reído con tu comentario…!!! Sí, estoy seguro que no se pueden usar potencias, al menos en las diferentes versiones que he visto del programa a lo largo de los años…
No te desesperes, es normal que no hayas encontrado ni una, son combinaciones difíciles de encontrar… en un par de días doy las soluciones (encontradas por un programa, claro, que si no…).
Y, ejem, yo no he usado ninguna palabra malsonante… Ha sido Martin Silenus!!. Y a un poeta que ha vendido 5.000 millones de copias de su “Tierra Moribunda” no se le discute ni una coma (como pasó con Camilo José Cela en su día, hace como 35 años, y si no, que se lo pregunten a Mercedes Milá, cuando todavía era una reportera seria).
@Todos: Gracias por vuestros comentarios.
Sí, caí en la cuenta después de que la propiedad conmutativa no aplica ni a la división ni a la resta, y que lo de poder cambiar el 6 de sitio era por dicha propiedad de la multiplicación. Además como puse en mi otro comentario hace falta tener en cuenta las operaciones que se realizan en paralelo, no sólo reordenar la precedencia de los operadores. Vale, si tu me dices que ya están quitadas las repeticiones me lo creo
P.D.: mandé tu artículo sobre los mainframes a mi padre y logré emocionarle
Una vez gané la calculadora estando en el público de cifras y letras
No faltan las combinaciones en las que no se usan todos los operandos?
@Mòni: No, no faltan. En realidad las combinaciones en que no son necesarios todos los operandos dados no son más que subconjuntos de las combinaciones completas que usan todos ellos… únicamente el programa debe verificar si ha alcanzado el objetivo después de realizar cada cálculo individual, y no al final.
Si el objetivo fuera el 125 y tuviéramos un 100 y un 25… no harían falta el resto. Lo que pasaría en este caso es que habría mucha redundancia, pues todas las combinaciones que en algún momento sumen esos dos términos serían válidas… pero eso nos da igual, una vez hemos encontrado solución, ¿no?
Saludos
Este Mac, siempre sorprendiendo. ¿Tú estabas ya jubilado o sigues en activo? Gente como tú no debería retirarse nunca. Si los docentes actuales fueran como tú, todo el mundo estaría interesado en aprender. En fin.
¿Cómo llegas a la conclusión de las 42 combinaciones “matemáticamente”?
No, no estoy jubilado. Aún.
Aunque, eso sí, una buena parte de mis neuronas ya se hayan jubilado anticipadamente…
Lo de las 42 combinaciones es combinatoria pura. Debido a las restricciones de las posibles combinaciones de O y ·, cualquier combinación tiene que empezar obligatoriamente por ‘OO’ y terminar por ‘·’ ; además la distribución interna debe ser tal que todo operador · tenga “algo” sobre lo que operar, es decir, al menos dos operandos…
No quería ponerlas, porque me parece un poco rollo, pero… ¡vosotros lo habéis querido!!. Las 42 combinaciones posibles son:
OO·O·O·O·O· OO·O·O·OO·· OO·O·OO··O· OO·O·OO·O·· OO·O·OOO··· OO·OO··O·O· OO·OO··OO·· OO·OO·O··O· OO·OO·O·O·· OO·OO·OO··· OO·OOO···O· OO·OOO··O·· OO·OOO·O··· OO·OOOO···· OOO··O·O·O· OOO··O·OO·· OOO··OO··O· OOO··OO·O·· OOO··OOO··· OOO·O··O·O· OOO·O··OO·· OOO·O·O··O· OOO·O·O·O·· OOO·O·OO··· OOO·OO···O· OOO·OO··O·· OOO·OO·O··· OOO·OOO···· OOOO···O·O· OOOO···OO·· OOOO··O··O· OOOO··O·O·· OOOO··OO··· OOOO·O···O· OOOO·O··O·· OOOO·O·O··· OOOO·OO···· OOOOO····O· OOOOO···O·· OOOOO··O··· OOOOO·O···· OOOOOO·····
Que os aprovechen!!
Sí sí, las 42 combinaciones están muy bonitas, pero has hecho la cuenta de la vieja o salen de alguna “fórmula matemática combinatoria” tal como las otras (combinaciones con repetición, factoriales, etc.).
Pues, Eagle, ya que preguntas, las calculé tipo “cuenta de la vieja”, como tú dices, pero aplicando la técnica usual para el cálculo de “tablas de verdad” en lógica.
La verdad es que han salido un poco feas en el comentario, pero comenzando en la primera (OO·O·O·O·O·) basta con ir intercambiando de forma sistemática, de derecha a izquierda, operandos y operadores. Por tanto, la primera es OO·O·O·OO·· (se intercambian los O y · finales: ojo, que el último · es fijo); la siguiente es la OO·O·OO··O·, luego la OO·O·OO·O··, y así hasta llegar a la OOOOOO·····, donde ya no podemos seguir intercambiando O’s y ·’s.
Podría haber construido un programa para calcularlas, pero hacerlo a mano me llevó diez minutos, así que no merecía la pena.
Y no sé lo suficiente de combinatoria como para llegar a calcular analíticamente el númerito… ¡Sólo soy un viejo informático!!
Okis, es que yo tampoco sé mucho de combinatoria (aprobé estadística en la carrera con un 5 pelao y en segunda convocatoria) y tenía curiosidad por si había “una fórmula” (como siempre hay una, pues eso).
Ya quisieran muchos jóvenes de hoy saber la mitad que el “viejo informático”.
Me parece que por combinatoria no puede calcularse, lo más parecido que hay serían las permutaciones de 8 elementos donde 5 son . repetidos y 3 son O repetidos, (dado que tiene que empezar por OO y acabar por . eso no entran en la película).
Eso se denota como P(subindice)8(superindice)5,3 y da de resultado (8 !)/(5!x3!) pero me parece que no es correcto por que contempla opciones como OO…..OOOO. es decir habría que introducir en la ecuación alguna forma de eliminar todas aquellas opciones en las que aparezcan los . demasiado rápido impidiéndoles tener operando y creo que no se puede.
Bueno, yo he intentado hacerlo, si las primeras son siempre dos OO y la ultima un . pues tendriamos ordenar 4 .’s y 4 o’s. Si dividimos en grupos de 4 mirando los primeros 4 4 .’s o 4 o’s y lo contrario en la siguientes, como solo hay una forma de ordenar 4 iguales 1x1x2=2 3 .’s y 1 o’s o inversa y lo contrario en las 4 siguientes. Como hay 4 formas de ordenar 3 figuras iguales y una distinta 4x4x2=32 2.’s o 2 o’s y lo mismo en las otras. como hay 6 formas de ordenar 2 figuras distintas de cada 6×6=36
Vamos, que me salen 70, así que en algo me habré equivocado, pero no se en que. Ahora tendré que pensarme lo de la matemáticas polacas para ver que significa “además la distribución interna debe ser tal que todo operador · tenga “algo” sobre lo que operar, es decir, al menos dos operandos…”
Repampanos, tienes razón, serían permutaciones de 8 elementos donde 4 O se repiten y 4. se repiten (me he columpiao al contar Os y .s) y da 70, e s verdad.
No, no puede dar 70 porque no valen todas las combinaciones de O y .
Por ejemplo, es imposible OO….OOOO.
Una cosa que he estado pensando es que en realidad no todas las combinaciones propuestas de operadores y operandos son válidas. Creo que tendríamos muchos resultados repetidos por la conmutatividad de la multiplicación y de la suma, lo que nos permitiría ahorrarnos un buen número de cálculos. También con la división, si ordenásemos siempre los operandos de mayor a menor por ejemplo, podríamos ahorrarnos un montón de operaciones en las que supiéramos que íbamos a dividir directamente un número pequeño por otro mayor, pues las fracciones no están permitidas en el juego (siempre divisiones enteras).
Pero seguro que todos estos cálculos iniciales son una montaña comparados con la reducción que nos propondrá en el siguiente capítulo
Pues sí… En el siguiente artículo os contaré todas las vueltas que a mi pobre cerebro se le han ocurrido para no tener que revisar cada vez más de treinta millones de combinaciones con más de 150 millones de operaciones artiméticas… que ya son operaciones.
¡¡Y ahí sí que váis a disfrutar/acordarse de mis ancestros, según!! Y es muy posible que se os ocurran más formas de eliminar combinaciones o de refutar alguna que se me ha ocurrido a mí… Interesante debate tendremos la semana que viene, espero!
Para los que buscáis la formula combinatoria: si tenemos n operadores binarios y (n+1) números, el número de maneras distintas de poner los paréntesis es: numero de formas= (2n)!/((n+1)!*n!) Se trata del n-ésimo número de Catalán: http://es.wikipedia.org/wiki/N%C3%BAmeros_de_catalan
¡¡Atiza!! ¡Los números de Catalan!
Y… ¿eso qué es lo que es? Uff, evidentemente es la solución: para n=6, (2n)!/((n+1)!*n!), o sea, 10!/6!·5! da 42 exactamente…
darkdead, si te digo que no tenía ni la más remota idea de qué rayos era eso de los “números de Catalan”, ni mucho menso que fueran la solución a nuestro problema de las combinaciones, seguro que me crees a pies juntillas…
Gracias por la indicación!!! Seguramente lo añadiré al artículo para dejarlo “niquelao”.
Esto de El Cedazo es tremendo, eh?; lo que uno no sabe otro lo enseña. Pedro: Menudo invento tuviste, amigo.
Pues muy interesante que existan con nombre y todo.
Ni números de Catalan ni leches fritas. Todo el mundo digno de escribir en este foro debería saber que sale 42 porque es “the Ultimate Answer to the Ultimate Question of Life, The Universe, and Everything” (Douglas Adams dixit).
@J: ¡¡Se te ha olvidado el smiley!!
Hay una nota al pié en el artículo, gentileza de J, con el link wikipedístico a “the Ultimate Answer to the Ultimate Question of Life, The Universe, and Everything”, para aquellos que, como a mí me pasaba, no teníamos fresco por qué 42 es la respuesta final a todo…
Joer, la que lié preguntando de donde salía el 42. Pero mira tu, al final, como te decía, siempre hay una fórmula (lo que pasa es que yo nunca me la sabía en el examen y tenía que improvisar…)
Oh, vaya. Si es que me repito mucho…
Han pasado dos días y, tal como prometí, os doy las soluciones de los problemas que enuncié en el comentario 7 (es para que veáis que efectivamente sí que había solución):
2-8-10-9-10-8 // 956. Una única forma de resolverlo: (((10×10)+8)x9)-(2×8). Fácil, no?
3-25-9-1-9-5 // 781. Una forma: (((9×9)+(3×25))x5)+1.
75-5-75-1-7-6 // 922. Una forma solamente: ((75+75+5)x6)-7-1. Psé, muy fácil.
5-4-6-2-7-3 // 959. Una única forma: ((((4×6)+3)x5)+2)x7.
4-25-50-4-5-1 // 687. Una sola forma: ((50×5)+4-25)x(4-1). Chupao.
75-10-1-8-9-1 // 351. Dos maneras de llegar al resultado. Forma 1: (75-((10+8)x(1+1)))x9, y Forma 2: (((75+1)/(10-8))+1)x9. Tirao.
4-1-7-6-4-8 // 958. Sólo una forma: ((4×4)+1)x(7×8)+6. Es facilísimo, 17×56+6, cualquiera llegaría en 45 segundos…
9-4-3-5-3-2 // 323. Una única manera: (((3x4x9)-2)x3)+5.
En fin, espero que os hayáis divertido un poquito… ¡sobre todo Rantamplan!!
Macluskey, he conseguido sacar el 5º y el ultimo en un tiempo razonable (el quinto en poco mas de un minuto y el ultimo en menos de los 45 segundos). Pero soy incapaz de ver los demas, incluso en un tiempo poco razonable (yo creo que con alguno me he pasado de los 10 minutos
). Como buen “mal alumno” he llegado a pensar que alguno estaba mal planteado 
.
Espero esas respuestas, ya me has dejado con el gusanillo
Maldicion, te me has adelantado mientras pensaba los resultados y escribia… Bueno, me alegra saber que los que supe, los hice bien, ahora me queda comprobar los demas y ver porque no era capaz ni de imaginarlo
Voy a plantear un par de problemas interesantes sobre cifras:
Con la combinación de cifras 100-75-50-25-10-9 se pueden conseguir todos los números del 100 al 999, ¿Cuántas combinaciones de cifras existen que den todos los números de dicho rango?
Por el contrario la combinación 1-1-1-1-1-1 da como máximo 9, la 2-2-2-2-2-2 da 64, solo a partir de la 3-3-3-3-3-3 se pueden obtener soluciones dentro del rango. ¿Cuál es la combinación de números iguales que ofrece mayor número de soluciones?
2-8-10-9-10-8 // 956. Una única forma de resolverlo: (((10×10)+8)x9)-(2×8) Este me había salido tal cual
3-25-9-1-9-5 // 781. Una forma: (((9×9)+(3×25))x5)+1. ((255)+(9-1))(9-3)=798
75-5-75-1-7-6 // 922. Una forma solamente: ((75+75+5)x6)-7-1. ((7+6)(75+1))-75+5=918
5-4-6-2-7-3 // 959. Una única forma: ((((4×6)+3)x5)+2)x7. Este pase de hacerlo, por que mucho tienen que odiarse los concursantes pa no elegir ni un misero numero de la cuarta columna.
4-25-50-4-5-1 // 687. Una sola forma: ((50×5)+4-25)x(4-1). Este casi (1+25+50)*(4+5)+4=688
75-10-1-8-9-1 // 351. Dos maneras de llegar al resultado. Forma 1: (75-((10+8)x(1+1)))x9, y Forma 2: (((75+1)/(10-8))+1)x9. La verdad es que si te das cuenta de que se divide entre 9, pos buscar el 39 tampoco es tan chungo, este es el otro que me salio
Los dos ultimos pase por lo mismo que el otro de numeritos pequeños.
Creo que estoy bastante desentrenado, pero vamos, te puedes defender, vamos pa mi es fácil acercarse y luego si puedes conseguir el exacto o no pos cuestión de suerte.
@Antonio Villena: Son acertijos muy interesantes, sin duda. Yo no he trabajado nada en este tipo de problemas, sino sólo en los orientados a resolver un problema dado; veo que tú has estudiado el problema desde el punto de vista contrario.
Mientras mi orientación al juego (consecuencia de mi natural idiosincrasia informática) es: Dado un problema que alguien pone, resolverlo lo antes posible;
La tuya (mucho más en el terreno de la matemática) es la opuesta: Qué tipo de problemas dan origen a un cierto tipo de soluciones. Yo de eso sé muy poco, la verdad, aunque seguro que entre nuestros lectores los hay que sí que sabrían mucho sobre el tema.
Te animo, si lo deseas, a escribir aquí, en El Cedazo, un artículo explicando cómo se resolvería este problema, tan interesante, o quizá más, que simplemente resolver un caso dado.
@Sergio B: Pues para estar “desentrenado”, te han salido unos resultados muy buenos. Yo, desde luego, ni me acerqué casi con ninguno. Bueno, sí, con el 4-25-50-4-5-1 // 687: ((50×5)+4-25)x(4-1), ése sí le pillé al darme cuenta que el objetivo era divisible por 3, y había que buscar el 229 dejando un 4 y el 1 aparte. Pero necesité más de 45 segundos (algo más de un minuto).
Mi intención no era poner ningún acertijo (bueno, un poquito, sí
), sino sólo poner algún caso que es realmente complicado de resolver… ¡en 45 segundos! A mí el de encontrar el resultado multiplicando 17 por 56 y luego sumando 6… ése me parece ya de libro, de tan irresoluble que es. Y además, es la única forma de llegar al dichoso número. Mi programita encontró la solución en un par de segundos, que para eso es un trozo de silicio, pero para un humano “normal” es completamente imposible.
Gracias por tus comentarios. Te espero (y a todos los demás) la semana que viene para que destripéis la optimización…
Saludos
Mac
@Mac nunca viene mal entrenar el coco, pero el 17*56, intentar algo así trauma
Esperemos a ver el destripe del programa.
Yo tenia un juego numérico, vamos, es algo que suelo hacer cuando me aburro y tengo un papel y un boli. Busco los números que se repiten en las potencias. Ejemplo: 5*5=25 se ha repetido el 5 asi todas las potencias de 5 terminan en 5 *5=125 todas la segunda cifra sera 2 *5=625 *5=3125 repetido, tercera serie 1, 6 *5=15625 *5=78125 *5=390625 *5=..31.. *5=..56.. repe! luego la serie sera 5,8,0,3
Obvio?, la primera cifra las de 2 son 2,4,8,6, las de 3 son 3,9,7,1 las de 4 son 4,6 las del 6 solo el 6 (magico!) las de 7 son 7,9,3,1 las de 8 son 8,4,2,6 y las de 9 son 9,1 y bueno el resto de números pues dependerá de con que empiecen, pero un numero terminado en 7 solo puede ser potencia del 7, en cambio uno terminado en 6 puede ser potencia de cualquier numero par. Y bueno, ningún numero terminado en 5 puede ser potencia de otra cosa que de 5, obvio, pero esa propiedad no la tienen ningún otro numero, es curioso, ¿no? Ademas, descontando el 5, el 6 se nos queda mal colocado, vamos, lo de buscar reglas es lo mas divertido del juego
Bueno, es una forma rara de entretenerse, pero bueno, cada serie tiene un numero de combinaciones limitada, 10 por la cantidad de la anterior y según avanzas se va complicando y es mas entretenido.
@Macluskey los problemas que he propuesto son computacionales, pero vamos que si hay alguien que lo resuelve con la teoría matemática me quito el sombrero. En ambos lo complicado es implementar una función con 7 parámetros de entrada (el número a buscar y las seis pistas) y que dé una salida booleana de si se puede o no.
Si a alguien le interesan este tipo de problemas hay una página con 344 problemas de este estilo aquí: http://projecteuler.net
Gracias por animarme a escribir, igual me animo algún día pero no será para este problema. Lo he propuesto sin saber yo mismo la solución.
@Antonio Villena tienes razón http://projecteuler.net es un proyecto increíble, me he enviciado, lo más curioso es que vas avanzando y vas aprendiendo más porque los otros publican sus respuestas, y a veces ni requieren escribir una linea de código ó su código es tan eficiente que el mio da verguenza aunque se demore menos de un minuto.
Gran blog, me gustó bastante, por lo que lo he agregado a los Feeds
Si os gusta Cifras y letras y tenéis un Android, tenéis que bajaros Cerebritum. Existe una versión gratuita limitada a 3 niveles: CerebritumFree
Has tenido en cuenta que no siempre hay que usar los 6 numeros ? Las 720 combinaciones son para 6 numeros, o sea 6! como bien dices. Creo que hay que sumarle 5! y 4! y 3! y 2! Eso lo convierte en 720 + 120 + 24 + 6 + 2 = 872 Que convierte la cifra total de 30.965.760 en 37.502.976
Hola, Ramón Bacardi.
Desde luego que he tenido en cuenta que se puede encontrar el resultado usando menos de los seis números dados, pero eso se tiene en cuenta solamente en la fase de resolución: mientras se van calculando los diferentes resultados parciales se va comprobando que cada uno de los resultados parciales sea el objetivo (o una mejor aproximación que la mejor hasta el momento, que también).
Y si piensas un poco te darás cuenta de que no, no son 872 combinaciones las que dan combinar seis números, son 720 (6!), porque todo el resto de combinaciones de dos, tres, cuatro o cinco números son todas ellas subconjuntos de una o varias combinaciones de seis, y por tanto, ya están contenidas en el conjunto original de seis números.
Así, si la combinación 6345, de sólo cuatro números, es decir, usando los números número 6, 3, 4 y 5 de cierta manera, por ejemplo 6345+-, alcanza al objetivo, también lo harán todas aquellas combinaciones que comiencen con esa misma estructura, como la 6345+-12++, o la 6345+-21, etc). Incluso también encontrarán el objetivo aquellas combinaciones que incluyan esta estructura completa aunque no comience por ella, dado que su resultado parcial satisfará también el objetivo. Por ejemplo, la 12+6345+-*, etc.
En cualquier caso, te recuerdo que este artículo es el primero de una serie que desmenuza el problema de las Cifras. Son cuatro artículos. Te recomiendo que los leas todos ellos (puedes encontrarlos en el link “Series” de la cabecera, y allí buscar la serie “Resolviendo Cifras y Letras”) y, si tienes cualquier duda o piensas que algo está mal, no dudes en comentarlo.
Saludos
{ 1 } Trackback
[...] Resolviendo “Cifras y Letras” eltamiz.com/elcedazo/2011/06/27/resolviendo-cifras-y-letr… por guachindango hace 3 segundos [...]
Escribe un comentario