People learning to program often struggle with how to decompose a problem into the steps necessary to write a program to solve that problem. This is one of a series of posts in which I take a problem and go through my decision-making process that leads to a program.

Background: I once attended a presentation by an amateur magician in which he stated that performing 8 perfect shuffles in a row on a deck of 52 cards returned the deck to the original order. A perfect shuffle is where you divide the deck into two, evenly sized stacks and when merging the stacks you are able to do so such that every other card comes from the same stack.

Problem: Write a program to determine if 8 perfect shuffles in a row return a deck of 52 cards to the original order. I assume that you understand statements, conditionals, loops, arrays, and functions.

You can find a video with more details at https://www.youtube.com/watch?v=6H02Wxa5VOs .

Design:

I start by thinking how to represent the cards. The claim above simply states that for whatever order the deck of cards is initially in, after 8 perfect shuffles it will return to its original order. It says nothing about the suits and values of the cards, so we don’t need to keep track of this information. Therefore, I will use an array consisting of the integers 1 to 52 as my cards. In the discussion below, this array is “cards”.

Each time I shuffle, I need to simulate dividing the deck into two stacks of 26 cards each followed by merging them such that one card comes from each stack during the merging. That is, when merging I get the first card from stack #1, the first card from stack #2, the second card from stack #1, the second card from stack #2, and so forth.

Each time I shuffle, I need to simulate dividing the deck into two stacks of 26 cards each followed by merging them such that one card comes from each stack during the merging. That is, when merging I get the first card from stack #1, the first card from stack #2, the second card from stack #1, the second card from stack #2, and so forth.

Representing the two smaller stacks is simple–the “left” stack will consist of the first 26 cards from the deck and the “right” stack will consist of the last 26 cards. That is

left[0] = cards[0]
left[1] = cards[1]
    .
    .
    .
left[25] = cards[25]

with a pattern of

left[i]= cards[i]

For producing the “right” stack, we can see that

right[0] = cards[26]
right[1] = cards[27]
    .
    .
    .
right[25] = cards[51]

with a pattern of

right[i] = cards[i + 26]

Merging is more of a challenge. I will print the current state of the loop after each shuffle and don’t care about the order before that, so I can re-use “cards” when merging. As for the merged values, cards[0] = left[0], cards[1] = right[0], cards[2] = left[1], cards[3] – right[1], and so forth. I can see that the indices of “cards” increments by one each time, but I use “left” and right” in pairs with the same index. That is, I use left[0] and right[0], then left[1] and right[1], and so on. This means that I need one indexing variable for “cards” and another for “left” and “right” so that I can increment them by different step sizes (for this approach).

Final Program:

#include <stdio.h>

void printCards(int card[], int len);
void shuffle(int c[]);

int main(void) {
    int cards[52];
    int i;

    /*  initializing the deck of cards  */
    for(i = 0; i < 52; i++)
        cards[i] = i+1;

    printf("original deck\n");
    printCards(cards, 52);

    for(i = 0; i < 8; i++) {
        shuffle(cards);
        printf("shuffle #%d\n", i+1);
        printCards(cards, 52);
    }
}

void shuffle(int c[]) {
    int i, k;
    int left[26];
    int right[26];

    /* divide into two subsets */
    for(i = 0; i < 26; i++) {
        left[i]  = c[i];
        right[i] = c[i+26];
    }

    /* merge two subsets */
    for(i = 0, k = 0; i < 52; i += 2, k++) {
        c[i]   = left[k];
        c[i+1] = right[k];
    }
}


void printCards(int card[], int len) {
    int i;

    for(i = 0; i < len; i++)
        printf("%d  ", card[i]);

    printf("\n\n");
}