Javascript Recursive Dice Combination And Store The Result In A Matrix
Solution 1:
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)
{
returnthis.reduce ((acc, x) => acc.concat (f (x)), [])
}
constcombinations = (choices, n = 1) =>
n === 0
? [[]]
: combinations (choices, n - 1) .flatMap (comb =>
choices .map (c => [ c, ...comb ]))
const faces =
[ 1, 2, 3 ]
// roll 2 diceconsole.log (combinations (faces, 2))
// [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 1, 2 ], ..., [ 2, 3 ], [ 3, 3 ] ]// roll 3 diceconsole.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.
constNone =
Symbol ()
constmap = (f, [ x = None, ...xs ]) =>
x === None
? []
: [ f (x), ...map (f, xs) ]
constflatMap = (f, [ x = None, ...xs ]) =>
x === None
? []
: [ ...f (x), ...flatMap (f, xs) ]
constcombinations = (choices = [], n = 1) =>
n === 0
? [[]]
: flatMap ( comb => map (c => [ c, ...comb ], choices)
, combinations (choices, n - 1)
)
const faces =
[ 1, 2, 3 ]
// roll 2 diceconsole.log (combinations (faces, 2))
// [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 1, 2 ], ..., [ 2, 3 ], [ 3, 3 ] ]// roll 3 diceconsole.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 nativesconstcombinations = (choices, n = 1) =>
constcombinations = (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 dependenciesconstcombinations = (choices = [], n = 1) =>
constcombinations = (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.
constNone =
Symbol ()
const combinations = function* (...all)
{
const loop = function* (comb, [ choices = None, ...rest ])
{
if (choices === None)
returnelseif (rest.length === 0)
for (const c of choices)
yield [ ...comb, c ]
elsefor (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')
continueif (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')
breakif (rank === 'J' || suit === '♡' )
console.log (rank, suit)
}
// J ♤// J ♡// J ♧// J ♢// Q ♡ <-- no Kings or Aces; generator stopped at KYou 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 = 279936Array.from (combinations (d1, d1, d1, d1, d1, d1, d1, d1)) .length
// 6^8 = 1679616We 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!
constNone =
Symbol ()
// Array ApplicativeArray.prototype.ap = function (args)
{
constloop = (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 = functionchain (f)
{
returnthis.reduce ((acc, x) => [ ...acc, ...f (x) ], [])
}
// Identity functionconstidentity = x =>
x
// math is programming is math is ...constcombinations = (...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', '♢' ]// ]
Post a Comment for "Javascript Recursive Dice Combination And Store The Result In A Matrix"