8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. #define SWAP(a,b) {a^=b; b^=a; a^=b;}. Branchless check to see if not equal: #define SWAP(a,b) {a^=(b*(a!=b)); b^=(a*(a!=b)); a^=(b*(a!=b));} \$\endgroup\$ – AnnoyinC Nov 26 '20 at 15:54
  • \$\begingroup\$ Oops, just noticed shuffle supposedly returns an int. It doesn't. Should be void shuffle() \$\endgroup\$ – AnnoyinC Nov 26 '20 at 17:45
9
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I tested the interval by running (10, 20) a couple million times which produces 15 avg. And you are right, without the +1 -1 it produced slightly under or above 15, can't remember. ### My logic was that any remainder of the division would cause the bias, so choose larger than the remainder. ### The reason I went with both-inclusive, as well as such a verbose name is because such details always leave me wondering (is this random function inclusive? tail inclusive?). Thanks for clearing that up for me. ### I also like your assert suggestions. \$\endgroup\$ – AnnoyinC Nov 26 '20 at 16:24
  • \$\begingroup\$ Link to char const *argv[] is about a function lacking a size parameter and in that case, helper(char *mcs_mask) is a good idea. Here, main() has a leading argc. C spec uses the idiomatic int main(int argc, char *argv[]), so until the spec changes its style, main() coded as [] remains the clearer choice. \$\endgroup\$ – chux - Reinstate Monica Nov 29 '20 at 3:08
  • \$\begingroup\$ @chux-ReinstateMonica: Strong disagree, for the reasons stated in Linus's rant. The function takes a parameter of type "pointer to pointer to char," which is idiomatically spelled char **argv. You physically can spell it char *argv[], or even char *argv[argc] or char *argv[47] — they're all physically synonymous in this specific position, because the language spec has special cases to make them synonymous — but logically you should spell it char **argv so that the spelling matches the actual pointer-to-pointer type. Reserve the [] declaration syntax for array declarations. \$\endgroup\$ – Quuxplusone Nov 29 '20 at 17:09
  • \$\begingroup\$ @Quuxplusone The proposed new C principle for C2x 15. Application Programming Interfaces (APIs) should be self-documenting when possible promotes VLA notation. As with such style issues, best to follow your group's style guide vs. personal preference. \$\endgroup\$ – chux - Reinstate Monica Nov 29 '20 at 20:38
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Interesting. I thought the xor operator would just take whatever size data and xor the literal bits. Not so, then? Also, thank you for suggesting the Mersenne Twister. \$\endgroup\$ – AnnoyinC Nov 26 '20 at 16:40
  • 2
    \$\begingroup\$ No, for example 3.14 ^ 2.72 simply doesn't compile. Also, just as a practical matter, on hardware XOR-swap is going to be much slower than your naïve swap, because the former involves ALU operations whereas the latter is a simple register-rename that introduces no dependencies. Remember that the world is optimized for "ordinary" code; the more "extraordinary" your code looks, the less you'll benefit from the optimizations everyone else is getting. \$\endgroup\$ – Quuxplusone Nov 26 '20 at 17:14
1
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ This is a good note, I overlooked that. \$\endgroup\$ – AnnoyinC Nov 29 '20 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.