Generate a specific number given X inputs of dice rolls

Question

I'm trying to come up with a solution where I need to roll a number of dice (all of the same size) and come to a specified number. Provided I have all the validation in place to make sure the numbers are valid and could theoretically arrive at the desired result, does anyone have a good algorithm for solving this? Note it should appear random, not just a straight divide.

Some examples

roll 3 d6 and get 14 -> so it could output 5,3,6 or 6,6,2

roll 4 d20 and get 66 -> so it could output 16,14,19,17

I need a generic function that can accept a dice of any size, any amount to be rolled and the desired result.

My initial attempt is below, though this doesn't produce the desired output (you can ignore the mod for now, this was to also allow modifiers). This example is also missing the validation that the desired output is achievable,but that's not part of the question.

let desired = 19
let mod = 0
let dm = desired - mod
let n = 5;// number of dice
let d = 6 // dice sides
let nums = []

for(i =0; i< n; i++) {
    nums.push(Math.round(Math.random() * Math.round(d)) + 1)
}

let sum = nums.reduce((acc,val) => acc + val)


nums = nums.map(a => Math.round((a/sum) * dm))

let diff = dm - (nums.reduce((acc,val) => acc + val))
function recursive(diff) {
    let ran = nums[Math.random() * Math.round(nums.length -1)]
    if(nums[ran] + diff > d || nums[ran] + diff < 1) {
        recursive(diff)
    } else {
        nums[ran] += diff
    }
}
while(diff != 0) {
    recursive(diff)
    diff += diff < 0 ? 1 : -1;
}

alert(nums)

Answer 1

recursive:

function foo(desired, rolls, sides, current) {
  if (rolls === 0) {
    return current.reduce((s, c) => s + c) === desired ? current : null;
  }
  
  const random = [];
  for (let i = 1; i <= sides; i++) {
    const randomIndex = Math.floor(Math.random() * (random.length + 1))
    random.splice(randomIndex, 0, i);
  }
  
  for (const n of random) {
    const result = foo(desired, rolls - 1, sides, [...current, n]);
    if (result) {
      return result;
    }
  }
}

console.log(foo(14, 3, 6, []))

non-recursive:

function foo(desired, rolls, sides) {
  const stack = [[]];
  while (stack.length) {
    const current = stack.pop();    
    const random = [];
    for (let i = 1; i <= sides; i++) {
      const randomIndex = Math.floor(Math.random() * (random.length + 1));
      random.splice(randomIndex, 0, i);
    }
  
    for (const n of random) {
      if (current.length === rolls - 1) {
        if (current.reduce((s, c) => s + c + n) === desired) {
          return [...current, n];
        }
      } else {
        stack.push([...current, n]);
      }
    }
  }   
}

console.log(foo(14, 3, 6));

non-recursive with minimum memory consumption:

function foo(desired, rolls, sides) {
  const currentIndexes = Array(rolls).fill(0);
  const randoms = Array.from({ length: rolls }, () => {
    const random = [];
    for (let i = 1; i <= sides; i++) {
      const randomIndex = Math.floor(Math.random() * (random.length + 1));
      random.splice(randomIndex, 0, i);
    }
    return random;
  })
  while (true) {
    if (currentIndexes.reduce((s, idx, i) => s + randoms[i][idx], 0) === desired) {
      return currentIndexes.map((idx, i) => randoms[i][idx]);
    }
    for (let i = currentIndexes.length - 1; i >= 0; i--) {
      if (currentIndexes[i] < sides - 1) {
        currentIndexes[i] += 1;
        break;
      }
      currentIndexes[i] = 0;
    }
  }
}

console.log(foo(14, 3, 6));

non-recursive solution with minimum memory consumption and increased performance by calculating the last roll based on previous rolls.

function foo(desired, rolls, sides) {
  const currentIndexes = Array(rolls - 1).fill(0);
  const randoms = Array.from({ length: rolls - 1 }, () => {
    const random = [];
    for (let i = 1; i <= sides; i++) {
      const randomIndex = Math.floor(Math.random() * (random.length + 1));
      random.splice(randomIndex, 0, i);
    }
    return random;
  })
  while (true) {
    const diff = desired - currentIndexes.reduce((s, idx, i) => s + randoms[i][idx], 0);
    if (diff > 0 && diff <= sides) {
      return [...currentIndexes.map((idx, i) => randoms[i][idx]), diff];
    }
    for (let i = currentIndexes.length - 1; i >= 0; i--) {
      if (currentIndexes[i] < sides - 1) {
        currentIndexes[i] += 1;
        break;
      }
      currentIndexes[i] = 0;
    }
  }
}

console.log(foo(66, 4, 20));

Answer 2

Soluton in ruby:

def foo(count, dim, desired, results = [])
  return results if count == 0
  raise ArgumentError if count > desired
  raise ArgumentError if count * dim < desired

  max_roll = (dim <= desired - count) ? dim : desired - count + 1
  min_roll = [(desired - (count-1) * dim), 1].max
  roll = (rand(min_roll..max_roll))
  results << roll

  foo(count - 1, dim, desired - roll, results)

  results
end

puts foo(3, 6, 11).inspect
puts foo(2, 6, 11).inspect
puts foo(4, 4, 11).inspect

Results:

[3, 4, 4]
[5, 6]
[2, 3, 4, 2]

So basically it is recursive function. For each step:

• roll a dice (within allowed range min_roll..max_roll)
• call same function but reduce count by already consumed number by dice and extend results array by value of roll

Note one thing: with this behaviour you may have larger numbers in the beginning of result. To avoid this just shuffle result of function in the end of it