Shuffle a deck of cards and draw 2

Question

I recently came across a coding challenge on some sort of technological basket weaving forum, where you had to pick 2 cards from a shuffled deck. I believe the challenge can be interpreted 2 ways:

1. Generate random deck, pick first 2
2. Generate sequential (or any) deck, pick 2 random cards

I went for option one. I believe I have used a good shuffling algorithm and accounted for modulo bias.

My main priorities:

1. correctness
2. code easy to handle and read

cards.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
    
#define SWAP_INT(a,b) {int tmp=a; a=b; b=tmp;}
    
const char const* suits[4] = {"Diamonds","Clubs","Hearts","Spades"};
const char const* ranks[13] = {"Ace","2","3","4","5","6","7","8","9","10","Jack","Queen","King"};
    
// from min inclusive to max inclusive
int rand_ranged_inclusive(int min, int max)
{
    if (min > max)
        SWAP_INT(min, max);

    if (min == max)
        return min;

    int range = max-min+1;
    int biased_interval = RAND_MAX%(range-1);
    int x;

    // prevent modulo bias by choosing a number outside biased interval
    do {
        x = rand();
    } while (x < biased_interval); 

    return x%range + min;
}

// Fisher-Yates (Durstenfield)
int shuffle(int arr[], int len)
{
    for (int i = 0; i < len; ++i) {
        int j = rand_ranged_inclusive(i, len-1);
        SWAP_INT(arr[i], arr[j]);
    }
}

void print_card(int c)
{
    if (c < 0 || c > 52)
        printf("Joker\n");

    const char const* suit = suits[c/13];
    const char const* rank = ranks[c%13];

    printf("%s of %s\n", rank, suit);
}

int main(int argc, char const *argv[])
{
    srand(time(NULL));

    int cards[52] = {0};

    for (int i = 0; i < 52; ++i)
        cards[i] = i;

    shuffle(cards, 52);

    print_card(cards[0]);
    print_card(cards[1]);

    return 0;
}

I feel like it can be optimized some more, especially picking random numbers, but reading from dev/urandom seems overall slower, when the modulo bias is so small and easily overcome.

Answer 1

rand_ranged_inclusive(a, b) is a surprisingly long function name, for how little information it communicates to the reader. I have frequently seen versions of this function named randint(a, b) or randint0(b) — but where the possible outputs are between 0 inclusive and b exclusive!

Using "half-open ranges" like this has huge advantages in C, because C uses half-open ranges for everything else. To pick a random element from an array, you want randint0(NELEM(a)). To pick a random character from a string, you want randint0(strlen(s)). And so on.

if (min > max)
    SWAP_INT(min, max);

Here and throughout, I strongly recommend curly-bracing all your control flow, including if and for bodies which are currently only one line long. These braces may one day save you from a goto fail bug.

Also, I think it's un-idiomatic that you are going out of your way to produce well-defined behavior for rand_ranged_inclusive(6, 1). I claim that that kind of input clearly indicates a bug in the caller, and you should be using assert(min <= max) here. (Or, if you switch to half-open ranges, assert(min < max).)

Your choice to handle rand_ranged_inclusive(6, 1) becomes even weirder when you consider that you do not handle seemingly valid parameters such as rand_ranged_inclusive(-10, INT_MAX). (The caller who tries that gets integer overflow and undefined behavior.)

int range = max-min+1;
int biased_interval = RAND_MAX%(range-1);

The use of RAND_MAX % ... instead of (RAND_MAX+1) % ... is an immediate red flag for me, after our discussion of half-open ranges. (RAND_MAX is an endpoint-which-is-included, similar to INT_MAX.) All these +1 and -1 would go away if you switched to half-open ranges. I bet they're hiding some off-by-one errors. Let's trace through a sample input.

Suppose min=1, max=6, RAND_MAX=10. (This is legitimately the first input I traced.) Then range=6, biased_interval=0... so the do-while loop runs only once before dropping out... but you end up choosing 1-4 twice as often as 5-6.

Did you test this code at all? How did you test it?

I think the algorithm you want here is more like

int range = max - min + 1;
int discard_top_k = ((RAND_MAX % range) + 1) % range;
int real_max = RAND_MAX - discard_top_k;
do {
    x = rand();
} while (x > real_max);

---

int j = rand_ranged_inclusive(i, len-1);

Your Fisher-Yates shuffle looks correct; but notice again that you're having to add a -1 to fix up the lack of half-open ranges in your random-number code.

---

if (c < 0 || c > 52)
    printf("Joker\n");

Is this situation possible? If it's supposed to be impossible, you should assert(0 <= c && c < 52) (hey look! half-open ranges!)

Also notice the off-by-one error in your code because of (say it with me) the lack of half-open ranges.

---

char const *argv[]

I agree with Linus on this one. Prefer

const char **argv

Answer 2

Premature optimization

I just noticed that I can do an XOR-swap instead of a temp variable. This would also allow the SWAP_INT macro to remain untyped

That's unfortunately incorrect - xor-swapping in fact has a reliance on type. Aside from your declared int type, the "naive" implementation of your swap would work with (for example) struct instances where xor cannot.

Unless you're on a microcontroller that has a poor compiler and every nanosecond is precious, do not bother writing out a xor-swap yourself. An optimizing compiler will either do this, or better (with an actual swap instruction where applicable) for you. Your existing swap macro is fine, and if you want this to be type-parametric, you can always accept the variable type as another macro parameter.

Parameter validation

if (min > max)
    SWAP_INT(min, max);

seems risky to me. If the application gets into a state where the min is greater than the max, I would consider this fairly surprising and erroneous behaviour, and would want to call that out as an error instead of silently fixing it.

Given that C of course does not have exception handling, your options to do this are somewhat constrained - you can have an output parameter separate from your return value, where the former receives the random result and the latter indicates success or failure. An assert would also be appropriate.

Likewise,

if (c < 0 || c > 52)
    printf("Joker\n");

seems too permissive. You should choose one well-defined value for a joker, and consider all others out-of-range to be erroneous.

Random sources

Cryptographic-quality randomness is not important for this application, so I consider the /dev approach to be overkill. Something like the Mersenne Twister would work well because it has better numerical characteristics while remaining extremely fast.

Answer 3

Limited range

For this application, shuffling 52 cards, rand_ranged_inclusive() limitations are not an issue, yet should be noted.

rand_ranged_inclusive() has trouble when:

1. max-min+1 overflows (UB)

2. RAND_MAX < range - 1. (Note even some 32/64 bit systems have RAND_MAX = 32767)