Forever Functional: Algorithms, Computer Science, and Cards

This article will show you several important Computer Science algorithms, such as sampling, shuffling, and sorting, using a simple deck of cards for the examples, so you can focus on the needed logic and study how to apply them to your own work.

In our previous article we developed code useful for a Poker game implementation, but it happens that card games are also useful to illustrate several important CS (Computer Science) algorithms that can be applied in many different contexts:

• Sampling is a procedure that lets you randomly pick some elements out of a set, giving every possible combination the same probability
• Shuffling allows you to randomize the order of a group of elements, again producing every possible permutation with equal odds
• Sorting is well known; given a group of elements, you want to put them in a specific order.

All these algorithms are common in Computer Science, but they also appear in card games!

• Dealing cards (or a magician’s “pick any card” routine that starts a magic trick) are examples of sampling.
• Every game starts by shuffling the deck (or decks) to provide random play
• Most players apply a sorting algorithm to arrange cards in their hands according to some rule

So, in this article, we’ll use the example of a deck of cards to provide examples of the algorithms we mentioned above. Testing for these algorithms is important, too, but we’ll realize this specific task is actually quite complex because of all the random aspects there are; more on this in a later article!

Some definitions

We’ll start by defining some types and constants that we’ll use throughout the article.

const RANKS = [
 'A', '2', '3' , '4', '5', '6', '7',
 '8', '9', '10', 'J', 'Q', 'K'
];

const SUITS = ['♥', '♦', '♠', '♣'];

type Card = { rank: number; suit: number };

type Deck = Card[];

Internally, the rank and suit of a card will correspond to positions in the RANKS and SUITS arrays. There are other possibilities; check the Enhancing the code section for an alternative and consider including Jokers in the deck. For a deck, we won’t need any complex data structure; a simple array will do.

We will want to list a hand or deck, but that’s just a loop. Of course, you could get more fancy and list card icons, images, or even HTML symbols; take it up as an exercise!

const listCards = (hand: Hand) => {
 hand.forEach((c) =>
   console.log(RANKS[c.rank] + SUITS[c.suit])
 );
};

For several algorithms, we’ll need a random function that returns a random non-negative integer, less than a given limit K, and the following will do.

const randomInt = (k: number): number =>
 Math.floor(k * Math.random());

(Question: Can you see why it works? As a hint, consider the range of values returned by Math.random() and the range of the multiplication result.)

We’re now set: let’s go on to the algorithms.

Generating a full deck of cards

Let’s start with the simplest algorithm: generating a deck of cards.

Creating a deck is just a couple of loops:

const makeDeck = (): Deck => {
 const deck: Deck = [];
 for (let s = 0; s < SUITS.length; s++) {
   for (let r = 0; r < RANKS.length; r++) {
     deck.push({ rank: r, suit: s });
   }
 }
 return deck;
};

We are essentially producing the deck suit by suit, and for each suit, we produce cards in ascending order, from ace to king. This logic is very straightforward and hard to get wrong. You may have to add Jokers to the deck; see the Enhancing the Code section for that.

The produced sequence isn’t very good for playing, though! (It’s equivalent to the deck you get when you open a new package.) So let’s directly jump into shuffling algorithms, so we’ll able to have interesting gameplay.

Shuffle the deck

How do you shuffle a deck? The Fisher-Yates is a simple but perfect way of randomly shuffling a deck. The basic algorithm can be described in pseudocode as follows:

• take the whole deck in your hand
• choose a random card
• put it away
• repeat the two previous steps until no cards are left

We could do this by using two arrays: one for the original deck and the other to put cards in. However, we can do better and not use an extra array. If the array is of dimension N, the following will do:

for I starting at N-1, going down to 1:
  let J be a random number between 0 and I, inclusive
  exchange the elements at positions I and J

(Question: why does the loop go down to 1, not 0? Would the algorithm still work if you let I become 0? What would happen at the last step?)

The shuffling algorithm is now:

function shuffle(deck: Deck): Deck {
 for (let i = deck.length - 1; i > 0; i--) {
   const j = randomInt(i + 1);
   [deck[i], deck[j]] = [deck[j], deck[i]];
 }
 return deck;
}

We may have a quick look at a random run.

const ddd = makeDeck();
shuffle(ddd);
listCards(ddd);

// Output, edited for clarity

9♦ 10♥  9♣  5♥  J♥  J♦  2♠  J♠  9♥  A♦  9♠  4♥  Q♥
Q♦  7♣  4♦  3♥ 10♣  7♠  3♠  7♦  3♣  4♠  K♣  8♠ 10♠
A♣  6♠  K♥  Q♣  8♣  5♣  6♥  6♣  5♠  Q♠  2♣  A♥  5♦
K♠ 10♦  2♦  2♥  4♣  3♦  6♦  7♥  8♥  K♦  8♦  J♣  A♠

OK, this seems random… but is it, really? Or is there some bug? How can we test if this algorithm really works? This is a quite interesting question we’ll follow up on in the next article in the series, I promise! For the time being, though, let’s move on to picking cards.

Pick a card, any card…

Suppose you want to generate a random card; how do you do it?

A first solution doesn’t even need a deck; we can randomly generate the card’s rank and suit. (A question to think about: what if the deck included Jokers? See the Enhancing the Code section for several questions.)

const randomRank = (): number => randomInt(RANKS.length);

const randomSuit = (): number => randomInt(SUITS.length);

const randomCard = (): Card => ({
 rank: randomRank(),
 suit: randomSuit()
});

This is a very computer-like way of working — not something you’d do in real life. A magician doesn’t tell you to figure out a random rank and suit pair; he would offer you a deck, and you either pick a random card from the deck or, otherwise, you could shuffle the whole deck and then just pick the top card. Let’s keep these ideas in mind because you may want to deal a hand, and then we have to be more careful.

Deal ‘em!

Imagine you are dealing Poker hands. Can you use the algorithm in the previous section? There’s an obvious problem: if you just use randomCard() five times in a row, by pure chance, you might get two Aces of Spades… and having duplicate cards may be detrimental to your health! So, we need something more.

The ideas at the end of the last section do work. Given a deck as input (it doesn’t matter whether it’s shuffled or not), we can pick a random card, remove it from the deck, deal it, and then repeat the process as many times as needed.

function randomCardFromDeck(deck: Deck): Card {
 const c = randomInt(deck.length);
 const l = deck.length - 1;
 [deck[c], deck[l]] = [deck[l], deck[c]];
 return deck.pop() as Card;
}

We pick a random card (at position c), we swap it to the deck’s last position, and we pop() to remove the card from the deck. Easy! Now we can write a function to deal a hand with a specified number of cards:

function randomHand(deck: Deck, cards: number): Hand {
 const hand = [] as Deck;
 while (cards > 0) {
   hand.push(randomCardFromDeck(deck));
   cards--;
 }
 return hand;
}

We can also do an alternative job by first shuffling the deck; that makes things simpler because we can then just pick cards from the start, taking advantage of the splice() method.

function randomHand2(deck: Deck, cards: number): Hand {
 shuffle(deck);
 return deck.splice(0, cards);
}

If you were dealing cards for a bridge game (in which four players, identified by the cardinal points, get 13 cards each) you could do the following:

const deck = makeDeck();
const handN: Hand = randomHand2(deck, 13);
const handE: Hand = randomHand2(deck, 13);
const handS: Hand = randomHand2(deck, 13);
const handW: Hand = randomHand2(deck, 13);

(Question: The deck would be emptied after dealing the last hand; can you see why?)

As an alternative, you could write a function that deals all hands at once, taking inspiration from the randomHand2() earlier code. Note how our dealBridgeHands() function returns a tuple.

function dealBridgeHands(): [Hand, Hand, Hand, Hand] {
 const deck = makeDeck();
 shuffle(deck);
 const handN: Hand = deck.splice(0, 13);
 const handE: Hand = deck.splice(0, 13);
 const handS: Hand = deck.splice(0, 13);
 const handW: Hand = deck; // the remaining 13 cards!
 return [handN, handE, handS, handW];
}

With this kind of logic, you can now deal a single card (as we also did in the previous section) or a complete hand. Again, we ask how we would test this random function; we’ll leave it to the next article, as we promised above.

Let’s finish the article by sorting cards in a couple of ways.

Sorting cards

We already saw some sorting recipes in a previous article, and we’ll use some techniques there for our case.

Sorting by just one field (say, by rank, as for many card games) is easy — we use the sortByRank() function in sortByRank() to sort by the appropriate field.

const sortByRank = (a: Card, b: Card): number =>  b.rank - a.rank;

function sortByRank(hand: Hand): Hand {
 hand.sort(sortByRank);
 return hand;
}

Note we wrote the sort in pointfree style, as in another article in the series. If you prefer, you could alternatively write:

function sortByRank(hand: Hand): Hand {
 hand.sort((a, b) => sortByRank(a, b);
 return hand;
}

What if we want to sort by rank and then by suit? We can also manage that in a single pass. We’ll need a function to compare by suit, too.

const sortBySuit = (a: Card, b: Card): number => b.suit - a.suit;

function sortByRankAndSuit(hand: Hand): Hand {
 hand.sort((a, b) => sortByRank(a, b) || sortBySuit(a, b));
 return hand;
}

How does this work? If two cards have equal rank, then sortByRank() returns zero, and the || operator then returns the result of the comparison by suits. If the two cards have different ranks, then sortByRank() returns a non-zero value, and sortBySuit() is not even called.

Testing sorting code is, fortunately, simple enough. You just provide a given hand with chosen cards, and you then check that the sorted output has the cards in the proper order. There’s no randomness at work here anywhere, so we don’t have to apply any “strange” solution, as we’ll be seeing in a future article.

Enhancing the code

We can consider some enhancements to the code to better provide support for some specific games.

• We used numbers (actually, integers ) for ranks and suits; what about using enum types?
• Many games include 1 or 2 Jokers; how would you modify your Card type definition to enable them? Make sure whatever you do also allows sorting a deck; do Jokers go before or after other cards?
• In our random card generation algorithm we only consider cards with rank and suit; how would you modify it to also generate Jokers?
• Canasta (a popular card game that was invented in my homeland, Uruguay!) uses a double deck and four Jokers; can you write a makeCanastaDeck() that will generate the needed cards?

Conclusion

In this article, we used cards to show several important CS algorithms with many applications beyond the obvious games. We used TypeScript and provided full data typing for all examples, just for clearer code. If you wanted to program some card-playing app, you should be on your way now; just start!

Hey… and what about Testing?

Unit testing for pure functions (those that, given the same arguments, always return the same result) is simple; you just provide some known arguments and check the expected result. But how do we work with all the functions we’ve seen above that purposefully return randomly varying results? (OK, let’s be fair; sorting isn’t like that, but shuffling, picking, and dealing are inherently random.) This happens to be a much harder question, so we’ll take it up in the next article in the series!

Understand every bug

Uncover frustrations, understand bugs and fix slowdowns like never before with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data. Check our GitHub repo and join the thousands of developers in our community.