CODEWITHSUNDEEP
javascriptalgorithmnested-loops
ale10ander
ale10ander

Reputation: 986

Varying number of related nested for loops

I am attempting to determine all possible sums from rolling n dice, where n is not known at compile time.

For two dice, the solution is straightforward, just iterate through both dice and add each possible side to each other. If passing in 2 6-sided dice, the sorted results would be: [2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8,8,9,9,9,9,10,10,10,11,11,12]

I tried to expand this solution to any n dice, but I realized that I need n for loops. 

for(let i = 0; i < numDice; i++)
{
    dice.push(sides); 
}

for(let i = 0; i < numSides; i++)
{
    for(let j = 1; j < dice.length; j++)
    {
        for(let k = 0; k < numSides; k++)
        {
            results.add(dice[0][i] + dice[j][k]);
        }
    }
}

I also attempted a recursion-based approach as the first question below suggested. I believe it will loop the correct number of times, but I couldn't figure out how to define my summing function without introducing yet more loops.

function doCallMany(numDice, numSides, sumFunc)
{
    if(numDice == 0) 
    {
        sumfunc(numDice, numSides) //?
    }
    else
    {
        for(let i = 0; i < numSides; i++)
        {
            doCallMany(numDice--, numSides, sumFunc)
        }
    }
}

I looked at similar questions here and here but they do not answer my question. The first doesn't because the action I need to perform in the loops is not independent. The second is close, but the answers rely on Python-specific answers.

Upvotes: 2

Views: 167

Answers (2)

Mark
Mark

Reputation: 92440

The comment about the complexity of the solutions is correct. It gets big quickly. Having said that, to address your original question, you can do this with a fairly simple recursive function for small input. Basically you start with an array of dice, pop one off add it to a sum and recurse with that sum and the rest of the array.

For example:

function sums(dice, sum = 0, ans = []) {
  if (dice.length === 0) ans.push(sum) // edge case, no more dice
  else {
    let d = dice[0]
    for (let i = 1; i <= d; i++) {
      sums(dice.slice(1), sum + i, ans) // recurse with remaining dice
    }
    return ans
  }
}

// two six-sided dice
let ans = sums([6, 6]) 
console.log(JSON.stringify(ans.sort((a, b) => a - b)))

// three three-sided dice
ans = sums([3, 3, 3]) 
console.log(JSON.stringify(ans.sort((a, b) => a - b)))

Upvotes: 2

Sergiu Nistor
Sergiu Nistor

Reputation: 29

I suggest you use the backtracking method. It lets you vary the number of loops you want to execute. You can even execute a random number of loops, as the number of loops can be held in a variable.

Upvotes: -1

Related Questions