Learning Data Structures by Shuffling a Deck of Cards

Now that I’ve graduated out of the FlatIron School for Software Engineering, I have found that the job search requires more than just being able to program a good user interface in JavaScript and React with a nice API backend using Ruby on Rails. The technical interview portion of the hiring process assumes a good deal of computer science knowledge, specifically in the areas of data structures and algorithms. While getting into material to decipher this way of thinking about code, I realized that I needed to somehow make this knowledge my own. So, in order to practice understanding and solving problems with the different types of data structures, I decided to create a simple JavaScript app of shuffling a deck of cards. Here, I challenged myself to replicate the reality of the behavior of individual cards being shuffled in a standard 52 card deck, using the data structures stack and queue, as well as at least one recursive function.

The first step was to create the deck of cards. A standard deck of playing cards is made up of four suits (clubs, diamonds, hearts, and spades), and thirteen ranks/values ranging from the digits 2 through 10, and the court cards: Ace, King, Queen, and Jack. Once these terms were placed in two static-length arrays, a simple method to populate and array of objects would create the deck for us:

const createDeck = () => {
const ranks = [“Ace”, “King”, “Queen”, “Jack”, “10”, “9”, “8”, “7”, “6”, “5”, “4”, “3”, “2”]
const suits = [“Clubs”, “Diamonds”, “Hearts”, “Spades”]
let fullDeck = []
ranks.forEach(rank => {
suits.forEach(suit => {
let newCard = {}
newCard[rank]=suit
fullDeck.push(newCard)
})
});
return fullDeck
}

The return of this function will be one array of 52 objects, those objects having a key:value pair of rank:suit, such that the first card created would be the Ace of Club like this: {“Ace”:”Clubs”}. For a future blog on the development of this app, I may change the key:value pair to {“rank”: “Ace”, “suit”: “Clubs”} because it may make the code simpler to write when comparing winning card combinations for certain card games, but for now, we will leave it as is for demonstration purposes.

As a helper-method, I wrote a simple function to display each card in the deck in the console so that I could determine if the cards were being shuffled properly.

function showCards(cards) {
cards.forEach(card => {
console.log(card)
})
}

Now that the deck has been created, the first step to shuffling a deck is to cut it in “about” half. Although I’ve spent enough of my waking life at card tables to know that there are certain dealers who can instinctively split a deck exactly in half each time they pick one up, most of the time there is a little more on one split pile than the other. Therefore, I added a randomization as to where to split the array of objects. Since I anticipated certain card games to use more than one deck (Blackjack, for instance), a check is performed to make sure that the created deck(s) contain(s) a multiple of 52. The randomization is also set to cut any size deck almost in half.

Here is where our first test of stack vs queue comes in. It is also the place that seemed ripe for a recursion method. We could have used .splice() to create two separate arrays at the randomly generated index, but that would have missed the point of learning to use stack, queue, and recursion methods. When a deck of cards is cut roughly in half in real life, the cards deepest into the deck continue to remain in their original order in the new decks — they are just relatively at different points in the split decks. However, the bottom card (ie., first in) of the top pile that was pulled off will still be first in with the top deck, and the bottom-most cards of the deck that was pulled from will continue to be relatively first in for its new half. So to populate these two new decks of cards and keep their original order (like in a real-world situation), we could use a While Loop here (as in, “While there are still cards to be populated into the deck that was pulled off the original pile, continue to populate the new array.”) But here was also a good place to try a recursion method.

In any recursion method, which is defined as method that calls upon itself as part of the method, it is imperative to implement a line of code that represents the “base case” scenario in which the method must stop. Otherwise, the computer will call upon the method continuously into infinity or until your computer crashes. Here, we continually decrement the value of how deep into the original deck we cut it, represented by the variable depthOfCut. So long as the depthOfCut does not equal zero, we can safely continue to call the recursive method. Unless the deck was cut exactly in half (and it will often be the case that it won’t be), there will always be some cards remaining. Once we hit the base case, the remaining cards will be pushed in their original order into the right pile of cards, just like in a real-world scenario. Now, we have two piles of cards and are ready to merge them together.

const cutTheDeck = deck => {
// check that the deck(s) are a full 52 cards each
let amountOfDecks = deck.length / 52
if (deck.length % 52 != 0) {
return ("This is not a full legal deck")
} else {
console.log (`There is/are ${amountOfDecks} full deck(s) here.`)
}
// like in real life, the cut of the deck is never exactly half
let depthOfCut = Math.floor((Math.random() * 20) + (20)) * amountOfDecks
// create two piles of cards
let leftPile = []
let rightPile = []
const createTwoPiles = cc => {
if (depthOfCut !=0) {
leftPile.push(cc.shift())
depthOfCut--
return createTwoPiles(cc)
} else {
deck.forEach(d => {
rightPile.push(d)
})
}
let result = []
result.push(leftPile)
result.push(rightPile)
return result
}
return createTwoPiles(deck)
}

What is happening when two halves of a deck of cards are merged into one is that the cards on the bottom (ie., first in) will be merged into a new single pile of cards and continue to remain at the bottom. Therefore: The queue data structure again, and we will use .shift() to pull off the first card of each array. Each card will usually alternate between right pile/left pile into the new pile. However, not always. Therefore, we will add some more randomization here, with zero being the left pile of cards and one representing a card from the right pile going into the newly merging deck. Here is a good place to use a While Loop, since this process of alternating cards from the bottom (ie, first in) of the two decks into one deck will continue until one deck is empty. Then, the remaining cards will be pushed onto the top of the newly created card stack. Now that you can visualize that: The last of the cards (ie., last in) will be on the top of the deck. Therefore, when you deal them (unless you’re a card cheat and deal from the bottom of the deck), you deal from the top of the “stack”, as in: Last in/first out (stack data structure).

const combineHalfDecks = decks => {
let combinedDecks = []
while (decks[0].length !=0 && decks[1].length !=0) {
let side = Math.round(Math.random()) // when shuffling a deck, there is never an even insertion of left and right, replicating it here
combinedDecks.push(decks[side].shift())
}
return combinedDecks.concat(decks[0]).concat(decks[1])
}

In the next post, we will actually deal from the top (using the .pop() method) to pull the last card inserted into our shuffled deck of cards array to a player.