Dice Game Algorithm (Iterative Array Sum Matching)

avatar
Marshal Murphy
July 17, 2020 - 3 MIN READ

The Problem: Given an integer and an array of integers, write a function that will determine if there are two numbers in the array that equal the given integer.

In-Place String Reversals

You've just landed in Vegas for your first time and have discovered a dice game at the hotel casino that you've never heard of before.

Like Black Jack, it's you against the dealer.

  1. The dealer rolls a pair of dice by placing them in an opaque cup and turns it over.
  2. The dealer's dice remain hidden until the player chooses to stop rolling.
  3. The player can then roll their pair of dice as many as 3 times, winning the game if any combination of their combined rolls equal the sum of the dealer's roll.

When the player is finished rolling and ends their turn, the dealer reveals their dice and the winner is revealed.

(Naturally, with every consecutive roll by the player, the amount of money they win is drastically reduced, but we won't worry about that here.)


Context

We need to write a function that decides the winner at the end of the game.

This function will take in an integer (the dealer's roll) and an array of integers (the rolls of the player), returning a boolean indicating if the player won or not.

When building our function:

  • We must determine if the sum of any 2 of the player's rolls equals the sum of the dealer's roll.
  • Player can only roll 3 times for a max of 6 integers in the range of 1...6.
  • For performance, don't check the same roll combination twice.

Let's look at an example:

const dealerRoll = 10;
const playerRolls = [1, 5, 4, 5, 6, 2];

function diceGame(playerRolls, dealerRoll) {
  // do stuff
  return true;
}

In the above example, the function returns true because a match is found with 5 + 5.

Additionally, a second match of 4 + 6 would also result in returning true.


Approach

How could we go about solving this?

First off, let's keep in mind that we need a way to avoid duplicating our efforts when it comes to summing pairs of the player's rolls.

If we were to use a nested loop to iterate over the array, we would end up repeating identical checks of pairs for every position of the array.

const playerRolls = [1, 5, 4, 5, 6, 2];

playerRolls.forEach(item => {
  for (var i = 0; i < playerRolls.length; i++) {
    // ...
  }
});

In the nested loop above, after progressing through the array once with the inner for loop, we begin repeating our sums for every integer left of the one represented by item in the outer loop.

Can we make the inner loop more performant, or can we replace it with something else?

Perhaps we could make use of an index from the outer loop to prevent us from repeating ourselves.

Something like this:

const playerRolls = [1, 5, 4, 5, 6, 2];

playerRolls.forEach((item, index) => {
  for (let i = index + 1; i < movieLengths.length; i++) {
    // ...
  }
});

A Solution

  • We set match to false, then iterate over playerRolls.
  • For each item in playerRolls, we check if any value that comes after it in the array (let i = index + 1) equals the dealerRoll when summed.
  • If there is a match, we update match to true.

Improvements:

One thing we didn't do is shortcircuit the function on first match. After all, only one match is required to win the game.

Can you think of a way to break out of this nested loop on first match?

Marshal Murphy 2020