Progress Report
My take on: #1 Generate a Unique Randomly Shuffled Array

My take on: #1 Generate a Unique Randomly Shuffled Array

Hamza Husein's photo
Hamza Husein
·

5 min read

"An article about how to shuffle an array? Isn't that something everyone knows?", I hear you say. Well yes, but there's a right way, and I'm about to show you an even righter way!😎

The Backstory

Here's the scoop🍧: I've been working on a learning project (A card memory game, maybe I should post about that in the future?). The gist of it is that a user sees 3 random images from Rick & Morty, and the user clicks on images that they haven't seen before. The goal of the game is to get through all the rounds of the game without clicking on a seen card twice.

If you've never heard of Rick & Morty, drop everything right now & watch it. Of course, don't forget to come back here and finish reading!😁

Alright, now in order to obtain the cards, I first have to fetch the JSON of the characters from the API (Check it out: Rick&Morty API. To get the JSON of a specific character, I would have to pass on the character ID inside the fetch statement, by using template literals.

async function fetchData(){
     for(let card of generatedCards){
          const response = await fetch(`https://rickandmortyapi.com/api/character/${card}`);
          const data = await response.json();
          {...}
     }
}

If the words "async", "await", "fetch" seem foreign to you, check out this article. Don't worry, I'll wait for you right here!

Still with me? Good!

Now, I would need to pass a character number to the fetch command, such that the number has only been generated once for each round. Of course, the first thing that came to my mind was to use the inbuilt Math.random() method to generate the numbers, store them in an array, then shuffle the array using Array.sort() method, and finally update the state by pushing the array to it.

For this example, we'll assume the card deck size to be 10.

const generateRandomCards = () =>{
   let newCards = [];
   for (let i=0; i<3; i++) {

         // Generate random card numbers
         let randomCardNumber = Math.floor(Math.random() * 10) + 1;
         newCards.push(randomCardNumber);
    }

    // Shuffle array randomly
    newCards.sort((a, b) => 0.5 - Math.random());
}

Now let's see what arrays we get if we run the above code 10 times (to simulate 10 rounds).

image.png

Try it on CodePen.

The Problem

As you can clearly see, we run into a major issue. The numbers inside the arrays underlined green are getting repeated. This means that the user would see more than one card of a character, effectively ruining the game. Now, a quick and easy fix would be to iterate through a for-loop and check if a number repeats in the array. But this would not be ideal for a large-scale application, as it would require additional processing time and slow down the overall program/game.

Okay Hamza, but how do we fix this!?

Patience grasshopper. Since whatever I could come up with were basically variations of the same problem, I turned to good ol'Google! While searching endless StackOverflow topics and Youtube videos, I came across a different approach to this problem. I have to give a shoutout to CSDojo, who explained the solution to this problem so eloquently (Check it out here).

Based on what the video relays, we can first generate the numbers required for our application (ie, the total character card deck size) and then shuffle the array, by using the Fisher-Yates shuffle algorithm. This would be guaranteed to give us a uniquely randomly shuffled array for each round!

Implementing the new solution

Let's now see how we can solve this:

Step 1:

To be able to use the Fisher-Yates shuffle algorithm, we first require a pre-generated array of all numbers we need (in our case, an array containing all the character numbers available based on the card deck size).

I had previously come across Geoffrey's post on StackOverflow. Here, he shows how to generate an array of numbers by creating an array using the spread operator and passing its size, and using .map() to iterate through each index and store its value inside the array.

const cardDeckSize = 10;
const cardsIndexArray = cardDeckSize => [...Array(cardDeckSize)].map((_, index) => index + 1);

// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Step 2:

Now we finally get to the fun part, implementing the Fisher-Yates shuffle algorithm!

for (let i = cardsIndexArray.length - 1; i>0; i--){
            let j = Math.floor(Math.random() * i);
            let k =cardsIndexArray[i]
            cardsIndexArray[i] = cardsIndexArray[j]
            cardsIndexArray[j] = k
        }

// [2, 8, 6, 3, 4, 10, 9, 5, 1 ,7]

Try it on CodePen.

Step 3:

And voila! You now have a randomly generated shuffled array! Now go and implement it in your own application or game.

Wrapping up! 😊

"WAIT!", I hear you say.

"You mentioned Rick and Morty characters, card decks, and rounds. Where do I get to see the game?"

Glad to hear you're keen on it. Check out my Github Repo to see how and why I have implemented this algorithm, which also resulted in the very article your reading right now!🤭🤭. Definetly give your reaction and feedback, and of course, share this article with someone who needs to read this!

  • For similar but short content, follow me over at Twitter 🐤 here.
  • Check out what I'm currently working on over at Github 🐱 here

Till next time, take care and cheers!🥂

ReactJavaScriptWeb Development