¿De cuántas formas pueden sumarse 20 dados (1 cara de cada dado en cada suma) para obtener el número 70?

Aclaración previa: Esta respuesta toma una orientación algorítmica a la resolución del problema… para una aproximación estadística o una resolución basada en combinatoria, aconsejo la fantástica respuesta de

Ahora sí :-)

¿Orden de complejidad?

El algoritmo más simple que podemos usar evaluaría todas las configuraciones de 20 dados (Variaciones con Repetición de 6 elementos tomados de 20 en 20)

Se trata, por lo tanto, de un un orden de complejidad O(n⋅6n)O(n·6n)pues:

• Tenemos 6n6n configuraciones de dados distintas.
• Tenemos que sumar los n dados de cada configuración (n−1n−1 sumas).

Esto es demasiado para mi CPU, ya que para 20 dados debería…

• …evaluar 3.656.158.440.062.976 configuraciones de dados
• …sumar 20 dados en cada una de ellas: 69.467.010.361.196.544 sumas

Pero no debemos desanimarnos

Para empezar, una definición:

Definimos count( S, D) como "cuántas configuraciones de D dados suman S"

Si el número de dados D es 1, encontraríamos que

count(s,1)=⎧⎩⎨010s<11≤s≤66<scount(s,1)={0s<111≤s≤606

Es decir:

• Para toda suma que esté entre 1 y 6, existe una única configuracion posible: elegir el dado cuyo valor es la suma.
• Ninguna otra suma (mayor de 6 o menor de 1) tendría solución

Si usamos D = 2 (2 dados) encontramos que

count(s,2)=⎧⎩⎨⎪⎪0∑6ncount(s−n,1)0s<22≤s≤1212<scount(s,2)={0s<2∑n6count(s−n,1)2≤s≤12012

Es decir:

• Para toda suma que sea menor a 2 o mayor a 12 no habrá solución posible.
• Para toda suma que esté entre 2 y 12, podemos expresar la solución en función de 6 elecciones de dado y, para cada una de ellas, contar cuántas soluciones hay para la cantidad restante (suma - cara elegida) usando un único dado.

La forma general para D > 1 sería esta:

count(s,d>1)=⎧⎩⎨⎪⎪0∑6ncount(s−n,d−1)0s<dd≤s≤6d6d<scount(s,d>1)={0s

Esta expresión recursiva podría representarse en javascript fusionando los casos d=1 y d>1 como:

function count(s, d) { 
  if (s < d || d * 6 < s) 
    return 0 
  else if (d === 1) 
    return 1 
  else 
    return [1, 2, 3, 4, 5, 6].reduce( 
      (total,n)=> 
        total + count(s - n, d - 1), 
      0 
    ) 
} 

(Ver codigo completo)

Podemos usarla para calcular count(35,10) (de cuántas formas podemos sumar 35 usando 10 dados) y obtendremos:

4395456

Pero, CUIDADO, no lo intentes con count(70, 20).

Este algoritmo recursivo sigue siendo O(n∗6n)O(n∗6n) y el incremento para cada dado adicional crece significativamente

{ sum: 7, dice: 2, result: 6 } 
time: 4.617ms 
 
{ sum: 14, dice: 4, result: 146 } 
time: 0.174ms 
 
{ sum: 21, dice: 6, result: 4332 } 
time: 3.574ms 
 
{ sum: 28, dice: 8, result: 135954 } 
time: 7.158ms 
 
{ sum: 35, dice: 10, result: 4395456 } 
time: 131.758ms 
 
{ sum: 42, dice: 12, result: 144840476 } 
time: 4587.074ms 
 
{ sum: 49, dice: 14, result: 4836766584 } 
time: 156494.069ms 

Número de nodos vs Número de valores

La definición de count(70, 20) es recursiva, y si la desplegase obtendríamos un árbol 6-ario de profundidad 20, es decir 6^20 nodos cada uno de los cuales utiliza a todos sus nodos hijos para calcular su propio valor.

Sin embargo, como máximo encontraremos 70 * 20 = 1400 valores de count(s,d) ya que los parámetros s y d están acotados:

• Solo tenemos 70 posibles sumas: 1, 2, …, 70
• Para cada suma, count(s,d) solo puede ser expresada de 20 maneras: count(s,1), count(s,2), …, count(s,20)

Como conclusión

El algoritmo recursivo es extremadamente ineficiente porque calcula una y otra vez los mismos valores sin "recordar" que ya lo hizo anteriormente.

Ejemplo: count(7,2) será llamado múltiples veces:

• count(8,3) = count(7,2) + count(6,2) + … + count(2,2)
• count(9,3) = count(8,2) + count(7,2) + … + count(3,2)
• count(10,3) = count(9,2) + count(8,2) + count(7,2) + …

"Memoization" al rescate

Cuando los nodos teóricos de un algoritmo recursivo producen muy pocos valores (comparados con el número de nodos) la técnica de "memoization" es ideal.

Esta técnica "recuerda" el valor que se obtuvo al llamar a una función con unos parámetros (Ej: recordaría que el resultado de count( 21, 6 ) es 4332 ), así que solo la calcularía 1 vez.

El algoritmo anterior podría ser reescrito de esta manera:

function count(s, d) { 
 const countWithMemoization = memoizate((s, d) => { 
   if (s < d || d * 6 < s) 
     return 0 
   else if (d === 1) 
     return 1 
   else 
     return [1, 2, 3, 4, 5, 6]. 
       reduce((total,n) =>  
         total+countWithMemoization(s - n, d - 1), 
     0). 
     
 }); 
 return countWithMemoization(s, d) 
} 

Nota: Puedes ver el código completo aquí

Un análisis detallado para count(35,20) arroja estos resultados

{ 
  sum: 70, 
  dice: 20, 
  result: 189456975899496, 
  totalCalls: 3085, 
  totalMemoized: 610 
} 
time: 1.164ms 

• Se han memorizado 610 estados diferentes
• La función "countWithMemoization" se ha evaluado 3085 veces que resulta una mejora "muy significativa" respecto a las 3.656.158.440.062.976 veces de la versión sin memorización.

Lo mejor de todo: hemos obtenido la respuesta a la pregunta:

Existen 189456975899496 configuraciones de 20 dados que suman 70

Un saludo

Antonio

… Espera, ¿sabes? creo que aún podemos seguir un poco más… si te apetece, claro :-p .

¿Hay otra forma de solucionar el problema que no sea recursiva?

Sí, mediante una versión "iterativa"

• El algoritmo recursivo plantea la resolución como un gran árbol que se resuelve en post-orden (primero se resuelven las hojas, luego los padres de las hojas …).
• La estructura real es la de un grafo donde los nodos que tienen el mismo valor aparecen una única vez.
• El grafo tiene, de hecho, 1400 nodos y podría representarse en una matriz de 20 columnas (el número de dados) y 70 filas (las sumas del 70 al 1).
• El grafo conectaría cada nodo con los hasta 6 nodos que se usan para calcularlo a él.

La "memoización" consigue "engañar" a la percepción del desarrollador:

• Nos hace creer que estamos recorriendo el árbol.
• En realidad está recorriendo un grafo!!!.

El punto aquí, es que la realidad "subyacente" puede ser explotada de una forma diferente "rompiendo" las limitaciones que impone la recursividad (tamaño de pila, por ejemplo).

Solución iterativa

En otros problemas recursivos "similares" (ej: cálculo de la función de fibonacci) el paso de recursivo a iterativo se realiza pasando por una versión intermedia que cumple las restricciones de "tail recursion"

En nuestro caso, la dependencia entre estados es más compleja: cada nuevo estado count(s,d) depende de hasta 6 subestados (y 2 variables!!!9, así que escribir la versión usando "tail recursion" no es tarea fácil.

Un posible algoritmo iterativo: generar todos los "count" desde count(1,1) hasta count(S,D) teniendo en cuenta que cada estado count(s,d) depende de 6 estados que están a una distancia máxima (respecto a s) de 6: count(s-6, d-1)

Mi propuesta:

function count(totalSums, totalDice) { 
  let counts = Counts(totalDice); 
  for (let sum = 1; sum <= totalSums; sum++) 
    for (let dice = 1; dice <= totalDice; dice++) 
      if (sum < dice || dice * 6 < sum) 
        counts.set(sum, dice, 0); 
      else if (dice === 1) 
        counts.set(sum, dice, 1); 
      else 
        counts.set(sum, dice, 
          [1, 2, 3, 4, 5, 6]. 
          reduce( (t, side) =>  
            (sum - side > 0) ?  
              t+counts.get(sum - side, dice - 1) :  
              t, 
            0 
          ) 
        ) 
 
  return counts.get(totalSums, totalDice); 
} 

Nota: Puedes ver el código completo aquí

El objeto "counts" de esta solución nos permite almacenar los estados previamente calculados pero de una forma eficiente: solo nos interesa mantener una "ventana" con los counts resueltos de las 6 sumas anteriores (s-1, s-2, …, s-6). En la solución propuesta se usa una array "circular".

Incluyo el código completo de los ejemplos aquí

Ahora sí: Un saludo

Antonio