Descifrando el Numble

Hace unos días escribía sobre el Wordle como acertijo. Hoy me ha dado por el Numble. Numble es un juego creado por @Rayoplateado e inspirado en una de las pruebas del programa de televisión Cifras y Letras. Cito de wikipedia:

El objetivo es obtener un número entero natural (del 101 al 999) con las operaciones aritméticas elementales (+,−,×,÷) con seis números (del 1 al 10, 25, 50, 75 y 100). No es obligatorio usar todos los números, pero no se puede repetir ninguno.

Aquí podéis ver un fragmento del programa. Pero vamos, es esto:

Siempre me pareció un juego divertido a nivel usuario pero me resulta más divertido aun pensar en el algoritmo para resolverlo. Eso es lo que vamos a hacer en este post. Aquí el simulador.

¿Cuántos pasos hay?

1. Empiezas con 6 números. 2 de ellos los fusionas usando una de las 4 operaciones permitidas (+,−,×,÷) y te quedan 5 números.

2. Repites la operación y te quedan 4 números.

3. Repites la operación y te quedan 3 números.

4. Repites la operación y te quedan 2 números.

5. Repites la operación y te queda 1 solo número.

Bien, vemos que como máximo pueden hacerse 5 operaciones.

¿Cuántas combinaciones hay?

Si tenemos 6 números iniciales y vamos a elegir 2 de ellos para fusionarlos, ¿cuántas parejas distintas podemos escoger?

• El 1 lo podemos fusionar con el 2, el 3, el 4, el 5 o el 6.

• El 2 con el 3, el 4, el 5 o el 6 (con el 1 ya lo habríamos contado).

• El 3 con el 4, el 5 o el 6.

• El 4 con el 5 o el 6.

• Y el 5 con el 6.

Paréntesis. El orden no importa. Fusionar el 1 y el 2 nos lleva al mismo estado, al mismo conjunto de números que fusionar el 2 y el 1. Solo hay una forma de sumar o multiplicar A y B. Y también, dado que no están permitidos los números negativos ni decimales, solo habrá una forma de restar o dividir A y B (el mayor de ellos delate).

En total con 6 números tendremos 15 (sumatorio de 5) posibles parejas distintas. Y con cada pareja podemos hacer 4 operaciones.

1. Es decir, que de los 6 números iniciales podemos pasar a 60 (4*sumatorio de 5) conjuntos distintos de 5 números.

2. Y si repetimos el cálculo, de cualquier conjunto de 5 números podremos ir a 40 (4*sumatorio de 4) posibles conjuntos de 4 números.

3. Y de cualquier conjunto de 4 números podremos ir a 24 (4*sumatorio de 3) posibles conjuntos de 3 números.

4. Y de cualquier conjunto de 3 números podremos ir a 12 (4*sumatorio de 2) posibles conjuntos de 2 números.

5. Y de cualquier conjunto de 2 números podremos ir a 4 (4*sumatorio de 1) posibles conjuntos de 1 número.

Y agregando todo esto tenemos que de un conjunto de 6 números existen 2.764.800 (60*40*24*12*4) caminos que nos llevan a un conjunto de 1 número.

Primer enfoque

2.764.800 me parece una cifra aceptable para conseguir un buen tiempo de ejecución. Pero resulta que google sheets no permite libros con más de 10 millones de celdas. Así que mi primera intención, que era hacer una tabla con 2 millones y pico de filas, una por cada camino posible, se ve frustrada.

En este punto me planteo un algoritmo recursivo que siempre me resultan entretenidos. Es decir, solo tendría que escribir las iteraciones de un paso y luego simplemente llamarse a sí mismo si el conjunto resultante aun tiene más de 1 número. Parece además que el problema se presta a ello: una estructura de árbol, no más de 5 pasos (no desbordará la pila)... Incluso me planteo hacer caso a los pesaos (ejem @1_pageknowledge, @Gsnchez, @rutrus) y tirar de google colab (python).

Pero lo descarto enseguida por 2 razones:

1. Dado que me interesa la solución en menos pasos, prefiero recorrer el árbol a lo ancho que a lo profundo. Ver primer minuto de este video de @BettaTech.

2. Pero sobre todo porque en realidad no hay 2 millones y pico de rutas sino muchas menos.

¿Cómo que no hay 2.764.800 rutas? Cojamos el ejemplo del principio. Tenemos de estado inicial estos 6 números: 2,5,8,10,25,75.

Podemos hacer en el primer paso 2+5 y en el segundo 8+10.

O podemos hacer en el primer paso 8+10 y en el segundo 2+5.

Y ambas rutas nos llevan al mismo estado, al mismo conjunto de 4 números: 7,18,25,75. Por tanto no hay 2.400 (60*40) posibles conjuntos de 4 números sino muchos menos (estimo que la mitad o así).

Pero es que además podríamos llegar al mismo estado, no solo por hacer las mismas operaciones en distinto orden, también haciendo operaciones distintas. Por ejemplo, restar 4 y 2 o dividir 4 y 2 nos llevará al mismo estado.

Pivotando

De lo anterior concluyo que necesito calcular todos los estados de 5 números antes de pasar a los estados de 4 números. La idea es:

1. Calcular los 60 estados posibles de 5 números y quitar repetidos.

2. De los resultantes calcular para cada uno sus 40 posibles estados de 4 números y volver a quitar repetidos.

3. De los resultantes calcular para cada uno sus 24 posibles estados de 3 números y volver a quitar repetidos.

4. ...

Y así quedarían bastantes menos de 2 millones. Así que decido hacer una pequeña función que tome como input un estado (un conjunto de números), me itere todas las posibles combinaciones de 2 números con las 4 operaciones, y me devuelva todos los posibles estados finales.

Y esta función, combinada con la función UNIQUE para quitar duplicados (integrada en google sheets), es todo lo que necesito.

Cuando el usuario introduce los 6 números se calculan todos los posibles estados de 5 números. A estos estados se le quitan duplicados y se calculan todos los posibles estados de 4 números. Y así hasta estados de 1 número. Esto tarda unos 15 segundos pero el resto es inmediato.

Ya solo queda buscar vía REGEXMATCH aquellos estados que contengan el número objetivo y elegir alguna de las rutas más cortas para mostrar al usuario.

Input: celdas grises

Adicionalmente la hoja hace algunos cálculos extra que te invito a explorar (todas las rutas posibles al número objetivo, todos los posibles números objetivo que se podrían alcanzar...).

Qué he aprendido: REGEXMATCH

Un subtema interesante es cómo determinar si el string 2,5,8,10,25,75 contiene o no el número 10. No puedo pedirle que busque el 10 porque podría matchear con 100 o con 210. Tampoco puedo pedir que busque ,10, porque el 10 podría no ir precedido ni seguido por coma si está al principio o al final.

Las regular expressions nos permiten buscar un patrón. No fue sencillo encontrar el patrón que tenía que poner pero al final creo que me hizo click.

^([0-9]+,)*10(,[0-9]+)*$

• 10 en negrita sería el número que quiero buscar

• ^: Inicio del string

• $: Final del string

• *: Que se puede repetir 0 o más veces

• +: Que se puede repetir 1 o más veces

• [0-9]: 1 char entre 0 y 9

Es decir, que busco un 10 precedido por un conjunto que se puede repetir 0 o más veces. Ese conjunto es una coma (,) precedida por 1 o más chars numéricos.

Y lo mismo hacia delante. El 10 debe preceder a un conjunto que se puede repetir 0 o más veces. Ese conjunto es una coma (,) seguida de 1 o más chars numéricos.

Si todo esto se cumple el REGEXMATCH devolverá true.

Estaba pensando...

Ya voy a pasar página pero un tema interesante es el de la dificultad. ¿Cómo medir la dificultad de un camino, de una solución?

Pienso que cuando lo hacemos de cabeza solemos emplear la heurística de "más cerca del número objetivo, mejor". Pero ese "más cerca" no siempre nos ayuda. Si nuestro objetivo es el 100 y disponemos de un 10, "nos acerca" más el 1.000 que el 99.

Pienso que por aquí puede haber algo de cara a estimar la dificultad para un humano de encontrar una solución concreta.

Pero como digo, yo ya me voy. Animo a @Rayoplateado a seguir mejorando este juego tan chulo.

PD: El simulador