javascript recursive dice combination and store the result in a matrix

what I'm trying to achieve is one of the classical results of the combination of the launch of N-dices,but saving the results in a matrix with M-N fields (where N is the number of dices and M is the total number of possible combinations - obtained by 6^N). So far I've written the following code:

function Dice (commonFace, singleFace){
    this.diceFaces = ["critical", commonFace, commonFace, singleFace, "support1", "support2"]
    this.numCases = function(){
        return Math.pow(this.diceFaces.length, numberDices)
    }
}
//create the attack dice
var attackDice = new Dice("smash", "fury");

//create the defence dice
var defenceDice =  new Dice("block", "dodge");



//create a function that rolls the dice results and returns the number of results results
function rollDiceResults(diceTypeRolled, numberDicesRolled) {

    //total possible results of the rolls of that number of dices
    var totalPossibilites = diceTypeRolled.numCases(numberDicesRolled);

    //store the dice results
    var diceResults = new Array;


    function rollDice(diceType, iteration, array) {
        if (iteration == 1) {
            //return the base case
            for (i = 0; i < diceType.diceFaces.length; i++) {
                array[i] = (diceType.diceFaces[i]);
            }
        } else {
            //continue
            for (i = 0; i < diceType.diceFaces.length; i++) {

                array[i] = diceType.diceFaces[i];
                rollDice(diceType, iteration - 1, tempResult);
            }

        }
    }


    for (i = 0; i < numberDicesRolled; i++) {
        rollDice(diceTypeRolled, numberDicesRolled, diceResults);
    }

}

what I'm getting is

  • an error in the declaration of the function
  • I'm missing how can I call the array inside the function, while maintaining the m-n structure

thanks for your help

Answers:

Answer

Fixed-length combinations

Recursion is a functional heritage and so using it with functional style will yield the best results. Recursion is all about breaking a large problem down into smaller sub problems until a base case is reached.

Below, we use the proposed Array.prototype.flatMap but include a polyfill for environments that don't support it yet. When n = 0 our base case has been reached and we return the empty result. The inductive case is n > 0 where choices will be added to the result of the smaller problem combination (choices, n - 1) – We say this problem is smaller here because n - 1 is closer to the base case of n = 0

Array.prototype.flatMap = function (f)
{
  return this.reduce ((acc, x) => acc.concat (f (x)), [])
}

const combinations = (choices, n = 1) =>
  n === 0
    ? [[]]
    : combinations (choices, n - 1) .flatMap (comb =>
        choices .map (c => [ c, ...comb ]))
        
const faces =
  [ 1, 2, 3 ]
  
// roll 2 dice
console.log (combinations (faces, 2))
// [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 1, 2 ], ..., [ 2, 3 ], [ 3, 3 ] ]

// roll 3 dice
console.log (combinations (faces, 3))
// [ [ 1, 1, 1 ], [ 2, 1, 1 ], [ 3, 1, 1 ], [ 1, 2, 1 ], ..., [ 2, 3, 3 ], [ 3, 3, 3 ] ]

Using combinations with your program

Writing rollDice would look something like this

const rollDice = (dice, numberOfDice) =>
  combinations (dice.diceFaces, numberOfDice)

console.log (rollDice (attackDice, 2))
// [ [ 'critical', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'fury', 'critical' ]
// , [ 'support1', 'critical' ]
// , [ 'support2', 'critical' ]
// , [ 'critical', 'smash' ]
// , [ 'smash', 'smash' ]
// , ...
// , [ 'critical', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'fury', 'support2' ]
// , [ 'support1', 'support2' ]
// , [ 'support2', 'support2' ]
// ]

Without dependencies

If you're curious how flatMap and map are working, we can implement them on our own. Pure recursion, through and through.

const None =
  Symbol ()

const map = (f, [ x = None, ...xs ]) =>
  x === None
    ? []
    : [ f (x), ...map (f, xs) ]
  
const flatMap = (f, [ x = None, ...xs ]) =>
  x === None
    ? []
    : [ ...f (x), ...flatMap (f, xs) ]

const combinations = (choices = [], n = 1) =>
  n === 0
    ? [[]]
    : flatMap ( comb => map (c => [ c, ...comb ], choices)
              , combinations (choices, n - 1)
              )
          
const faces =
  [ 1, 2, 3 ]
  
// roll 2 dice
console.log (combinations (faces, 2))
// [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 1, 2 ], ..., [ 2, 3 ], [ 3, 3 ] ]

// roll 3 dice
console.log (combinations (faces, 3))
// [ [ 1, 1, 1 ], [ 2, 1, 1 ], [ 3, 1, 1 ], [ 1, 2, 1 ], ..., [ 2, 3, 3 ], [ 3, 3, 3 ] ]

Nerfed

Ok, so combinations allows us to determine the possible combinations of a repeated, fixed set of choices. What if we had 2 unique dice and wanted to get the all the possible rolls?

const results = 
  rollDice (attackDice, defenceDice) ???

We could call rollDice (attackDice, 1) and then rollDice (defenceDice, 1) and then somehow combine the answers. But there's a better way; a way that allows for any number of unique dice, even with a varying number of sides on each die. Below, I show you the two versions of combinations we wrote alongside the necessary changes to access untapped potential

 // version 1: using JS natives
const combinations = (choices, n = 1) =>
const combinations = (choices = None, ...rest) =>
  n === 0
  choices === None
    ? [[]]
    : combinations (choices, n - 1) .flatMap (comb =>
    : combinations (...rest) .flatMap (comb =>
        choices .map (c => [ c, ...comb ]))

// version 2: without dependencies
const combinations = (choices = [], n = 1) =>
const combinations = (choices = None, ...rest) =>
  n === 0
  choices === None
    ? [[]]
    : flatMap ( comb => map (c => [ c, ...comb ], choices)
              , combinations (choices, n - 1)
              , combinations (...rest)
              )

With this new version of combinations, we can roll any number of dice of any size – even the physically impossible 3-sided die is possible in this program ^_^

// version 3: variadic dice
const combinations = (choices = None, ...rest) =>
  choices === None
    ? [[]]
    : flatMap ( comb => map (c => [ c, ...comb ], choices)
              , combinations (...rest)
              )

const d1 =
  [ 'J', 'Q', 'K' ]

const d2 =
  [ '?', '?', '?', '?' ]

console.log (combinations (d1, d2))
// [ [ 'J', '?' ], [ 'Q', '?' ], [ 'K', '?' ]
// , [ 'J', '?' ], [ 'Q', '?' ], [ 'K', '?' ]
// , [ 'J', '?' ], [ 'Q', '?' ], [ 'K', '?' ]
// , [ 'J', '?' ], [ 'Q', '?' ], [ 'K', '?' ]
// ]

And of course you can roll a collection of the same dice

console.log (combinations (d1, d1, d1))
// [ [ 'J', 'J', 'J' ]
// , [ 'Q', 'J', 'J' ]
// , [ 'K', 'J', 'J' ]
// , [ 'J', 'Q', 'J' ]
// , [ 'Q', 'Q', 'J' ]
// , [ 'K', 'Q', 'J' ]
// , [ 'J', 'K', 'J' ]
// , ...
// , [ 'K', 'Q', 'K' ]
// , [ 'J', 'K', 'K' ]
// , [ 'Q', 'K', 'K' ]
// , [ 'K', 'K', 'K' ]
// ]

Tapping into this potential with your program, you can write rollDice as

const rollDice = (...dice) =>
  combinations (...dice.map (d => d.diceFaces))

console.log (rollDice (attackDice, defenceDice))
// [ [ 'critical', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'fury', 'critical' ]
// , [ 'support1', 'critical' ]
// , [ 'support2', 'critical' ]
// , [ 'critical', 'block' ]
// , [ 'smash', 'block' ]
// , ...
// , [ 'support2', 'support1' ]
// , [ 'critical', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'fury', 'support2' ]
// , [ 'support1', 'support2' ]
// , [ 'support2', 'support2' ]
// ]

Or with all sorts of dice

const rollDice = (...dice) =>
  combinations (...dice.map (d => d.diceFaces))

console.log (rollDice (defenceDice, attackDice, attackDice, attackDice))
// [ [ 'critical', 'critical', 'critical', 'critical' ]
// , [ 'block', 'critical', 'critical', 'critical' ]
// , [ 'block', 'critical', 'critical', 'critical' ]
// , [ 'dodge', 'critical', 'critical', 'critical' ]
// , [ 'support1', 'critical', 'critical', 'critical' ]
// , [ 'support2', 'critical', 'critical', 'critical' ]
// , [ 'critical', 'smash', 'critical', 'critical' ]
// , [ 'block', 'smash', 'critical', 'critical' ]
// , [ 'block', 'smash', 'critical', 'critical' ]
// , [ 'dodge', 'smash', 'critical', 'critical' ]
// , [ 'support1', 'smash', 'critical', 'critical' ]
// , ...
// ]

Going high-level

It's cool to see how we can accomplish so much with just a few pure functions in JavaScript. However, the above implementation is slow af and severely limited in terms of how many combinations it could produce.

Below, we try to determine the combinations for seven 6-sided dice. We expect 6^7 to result in 279936 combinations

const dice =
  [ attackDice, attackDice, attackDice, attackDice, attackDice, attackDice, attackDice ]

rollDice (...dice)
// => ...

Depending on the implementation of combinations you picked above, if it doesn't cause your environment to hang indefinitely, it will result in a stack overflow error

To increase performance here, we reach for a high-level feature provided by Javascript: generators. Below, we rewrite combinations but this time using some imperative style required to interact with generators.

const None =
  Symbol ()

const combinations = function* (...all)
{
  const loop = function* (comb, [ choices = None, ...rest ])
  {
    if (choices === None)
      return
    else if (rest.length === 0)
      for (const c of choices)
        yield [ ...comb, c ]
    else
      for (const c of choices)
        yield* loop ([ ...comb, c], rest)
  }
  yield* loop ([], all)
}

const d1 =
  [ 'J', 'Q', 'K', 'A' ]
  
const d2 =
  [ '?', '?', '?', '?' ]

const result =
  Array.from (combinations (d1, d2))

console.log (result)
// [ [ 'J', '?' ], [ 'J', '?' ], [ 'J', '?' ], [ 'J', '?' ]
// , [ 'Q', '?' ], [ 'Q', '?' ], [ 'Q', '?' ], [ 'Q', '?' ]
// , [ 'K', '?' ], [ 'K', '?' ], [ 'K', '?' ], [ 'K', '?' ]
// , [ 'A', '?' ], [ 'A', '?' ], [ 'A', '?' ], [ 'A', '?' ]
// ]

Above, we use Array.from to eagerly collect all the combinations into a single result. This is often not necessary when working with generators. Instead, we can use the values as they're being generated

Below, we use for...of to interact with each combination directly as it comes out of the generator. In this example, we show any combination that includes a J or a ?

const d1 =
  [ 'J', 'Q', 'K', 'A' ]

const d2 =
  [ '?', '?', '?', '?' ]

for (const [ rank, suit ] of combinations (d1, d2))
{
  if (rank === 'J' || suit === '?' )
    console.log (rank, suit)
}
// J ? <-- all Jacks
// J ?
// J ?
// J ?
// Q ? <-- or non-Jacks with Hearts
// K ?
// A ?

But of course there's more potential here. We can write whatever we want in the for block. Below, we add an additional condition to skip Queens Q using continue

const d1 =
  [ 'J', 'Q', 'K', 'A' ]

const d2 =
  [ '?', '?', '?', '?' ]

for (const [ rank, suit ] of combinations (d1, d2))
{
  if (rank === 'Q')
    continue
  if (rank === 'J' || suit === '?' )
    console.log (rank, suit)
}
// J ?
// J ?
// J ?
// J ?
// K ? <--- Queens dropped from the output
// A ?

And perhaps the most powerful thing here is we can stop generating combinations with break. Below, if a King K is encountered, we halt the generator immediately

const d1 =
  [ 'J', 'Q', 'K', 'A' ]

const d2 =
  [ '?', '?', '?', '?' ]

for (const [ rank, suit ] of combinations (d1, d2))
{
  if (rank === 'K')
    break
  if (rank === 'J' || suit === '?' )
    console.log (rank, suit)
}
// J ?
// J ?
// J ?
// J ?
// Q ? <-- no Kings or Aces; generator stopped at K

You can get pretty creative with the conditions. How about all the combinations that begin or end in a Heart

for (const [ a, b, c, d, e ] of combinations (d2, d2, d2, d2, d2))
{
  if (a === '?' && e === '?')
    console.log (a, b, c, d, e)
}

// ? ? ? ? ?
// ? ? ? ? ?
// ? ? ? ? ?
// ...
// ? ? ? ? ?
// ? ? ? ? ?
// ? ? ? ? ?

And to show you generators work for large data sets

const d1 =
  [ 1, 2, 3, 4, 5, 6 ]

Array.from (combinations (d1, d1, d1, d1, d1, d1, d1)) .length
// 6^7 = 279936

Array.from (combinations (d1, d1, d1, d1, d1, d1, d1, d1)) .length
// 6^8 = 1679616

We can even write higher-order functions to work with generators such as our own filter function. Below, we find all combinations of three 20-sided dice that form a Pythagorean triple - 3 whole numbers that make up the side lengths of a valid right triangle

const filter = function* (f, iterable)
{
  for (const x of iterable)
    if (f (x))
      yield x
}

const d20 =
  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]

const combs =
  combinations (d20, d20, d20)

const pythagoreanTriple = ([ a, b, c ]) =>
  (a * a) + (b * b) === (c * c)

for (const c of filter (pythagoreanTriple, combs))
  console.log (c)

// [ 3, 4, 5 ]
// [ 4, 3, 5 ]
// [ 5, 12, 13 ]
// [ 6, 8, 10 ]
// [ 8, 6, 10 ]
// [ 8, 15, 17 ]
// [ 9, 12, 15 ]
// [ 12, 5, 13 ]
// [ 12, 9, 15 ]
// [ 12, 16, 20 ]
// [ 15, 8, 17 ]
// [ 16, 12, 20 ]

Or use Array.from with a mapping function to simultaneously transform each combination into a new result and collect all results in an array

const allResults =
  Array.from ( filter (pythagoreanTriple, combs)
             , ([ a, b, c ], index) => ({ result: index + 1, solution: `${a}² + ${b}² = ${c}²`})
             )

console.log (allResults)
// [ { result: 1, solution: '3² + 4² = 5²' }
// , { result: 2, solution: '4² + 3² = 5²' }
// , { result: 3, solution: '5² + 12² = 13²' }
// , ...
// , { result: 10, solution: '12² + 16² = 20²' }
// , { result: 11, solution: '15² + 8² = 17²' }
// , { result: 12, solution: '16² + 12² = 20²' }
// ]

What the func?

Functional programming is deep. Dive in!

const None =
  Symbol ()

// Array Applicative
Array.prototype.ap = function (args)
  {
    const loop = (acc, [ x = None, ...xs ]) =>
      x === None
        ? this.map (f => f (acc))
        : x.chain (a => loop ([ ...acc, a ], xs))
    return loop ([], args)
  }
 
// Array Monad (this is the same as flatMap above)
Array.prototype.chain = function chain (f)
  {
    return this.reduce ((acc, x) => [ ...acc, ...f (x) ], [])
  }

// Identity function
const identity = x =>
  x

// math is programming is math is ...
const combinations = (...arrs) =>
  [ identity ] .ap (arrs)

console.log (combinations ([ 0, 1 ], [ 'A', 'B' ], [ '?', '?' ]))
// [ [ 0, 'A', '?' ]
// , [ 0, 'A', '?' ]
// , [ 0, 'B', '?' ]
// , [ 0, 'B', '?' ]
// , [ 1, 'A', '?' ]
// , [ 1, 'A', '?' ]
// , [ 1, 'B', '?' ]
// , [ 1, 'B', '?' ]
// ]

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.