Forever Functional: Algorithms, Computer Science, and Cards
Published: 2023-08-25 20:38:57

by [Federico Kereki](https://blog.openreplay.com/authors/federico-kereki)

<blockquote><em>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.</em></blockquote>



In our [previous article](https://blog.openreplay.com/forever-functional-poker-and-typescript/) 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.

```typescript
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](https://www.htmlsymbols.xyz/games-symbols/playing-cards); take it up as an exercise!

```typescript
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.

```typescript 
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.

![-](https://blog.openreplay.com/images/forever-functional-algorithms-computer-science-and-cards/images/image1.png)

Creating a deck is just a couple of loops:

```typescript
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](https://en.wikipedia.org/wiki/Fisher-Yates_shuffle) 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?)

![-](https://blog.openreplay.com/images/forever-functional-algorithms-computer-science-and-cards/images/image2.png)

We'll need a random function that returns a random positive integer less than a given limit `K`, and the following will do.

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

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

The shuffling algorithm is now:

```typescript
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.

```typescript
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?

![-](https://blog.openreplay.com/images/forever-functional-algorithms-computer-science-and-cards/images/image3.png)

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.)

```typescript
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.


<div style="background-color:#efefef; border-radius:8px; padding:10px; display:block;">
<hr/>
<h3><em>Session Replay for Developers</em></h3> 
<p><em>Uncover frustrations, understand bugs and fix slowdowns like never before with <strong><a href="https://github.com/openreplay/openreplay" target="_blank">OpenReplay</a></strong> — an open-source session replay suite for developers. It can be <strong>self-hosted</strong> in minutes, giving you complete control over your customer data.</em></p>
<img alt="OpenReplay" style="margin-top:5px; margin-bottom:5px;" width="768" height="400" src="https://raw.githubusercontent.com/openreplay/openreplay/main/static/openreplay-git-hero.svg" class="astro-UXNKDZ4E" loading="lazy" decoding="async">
<p><em>Happy debugging! <a href="https://openreplay.com" target="_blank">Try using OpenReplay today.</a></em><p>
<hr/>
</div>


## Deal 'em!

Imagine you are dealing [Poker](https://en.wikipedia.org/wiki/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.

![-](https://blog.openreplay.com/images/forever-functional-algorithms-computer-science-and-cards/images/image4.png)

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.

```typescript
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:

```typescript
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()`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice) method.

```typescript
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:

```typescript
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.

```typescript
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](https://blog.openreplay.com/forever-functional-sorting-recipes-for-js/), and we'll use some techniques there for our case.


![-](https://blog.openreplay.com/images/forever-functional-algorithms-computer-science-and-cards/images/image5.png)


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.

```typescript
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](https://blog.openreplay.com/forever-functional-pointfree-style-programming/) in the series. If you prefer, you could alternatively write:

```typescript
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.

```typescript 
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](https://en.wikipedia.org/wiki/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!