I don't see any obvious way to find out the lengths of the cyclic groups user3386109 mentioned, without using any arrays.
Besides, the "This is not a trick [interview] question" sounds to me like the interviewer just wanted you to simulate the deck operations in C using something other than an array.
The immediate solution that comes to mind is using singly or doubly linked lists. Personally, I'd use a singly-linked list for the cards, and a deck structure to hold the pointers for the first and last cards in the deck, as the shuffling operation moves cards to both top and bottom of decks:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
struct card {
struct card *next;
long face; /* Or index in the original order */
};
typedef struct deck {
struct card *top;
struct card *bottom;
} deck;
#define EMPTY_DECK { NULL, NULL }
The deck manipulation functions I'd use would be
static void add_top_card(deck *const d, struct card *const c)
{
if (d->top == NULL) {
c->next = NULL;
d->top = c;
d->bottom = c;
} else {
c->next = d->top;
d->top = c;
}
}
static void add_bottom_card(deck *const d, struct card *const c)
{
c->next = NULL;
if (d->top == NULL)
d->top = c;
else
d->bottom->next = c;
d->bottom = c;
}
static struct card *get_top_card(deck *const d)
{
struct card *const c = d->top;
if (c != NULL) {
d->top = c->next;
if (d->top == NULL)
d->bottom = NULL;
}
return c;
}
Since there is no get_bottom_card()
function, there is no need to use a doubly-linked list to describe the cards.
The shuffling operation itself is quite simple:
static void shuffle_deck(deck *const d)
{
deck hand = *d;
deck table = EMPTY_DECK;
struct card *topmost;
while (1) {
topmost = get_top_card(&hand);
if (topmost == NULL)
break;
/* Move topmost card from hand deck to top of table deck. */
add_top_card(&table, topmost);
topmost = get_top_card(&hand);
if (topmost == NULL)
break;
/* Move topmost card from hand deck to bottom of hand deck. */
add_bottom_card(&hand, topmost);
}
/* Pick up the table deck. */
*d = table;
}
The benefit of the deck
structure type with pointers to both ends of the card list, is avoiding the linear search in shuffle_deck()
to find the last card in the hand deck (for fast appending to the hand deck). Some quick tests I did indicates that linear search would otherwise have been the bottleneck, increasing runtime by about half.
Some results:
Cards Rounds
2 2
3 3
4 2
5 5
6 6
7 5
8 4
9 6
10 6
11 15
12 12
13 12
14 30
15 15
16 4
20 20
30 12
31 210
32 12
50 50
51 42
52 510 (one standard deck)
53 53
54 1680
55 120
56 1584
57 57
80 210
81 9690
82 55440
83 3465
84 1122
85 5040
99 780
100 120
101 3360
102 90
103 9690
104 1722 (two decks)
156 5040 (three decks)
208 4129650 (four decks)
However, using arrays, one can easily find out the cycle lengths, and use those to compute the number of rounds needed.
First, we create a graph or mapping how the card positions change during a full round:
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
size_t *mapping(const size_t cards)
{
size_t *deck, n;
if (cards < (size_t)1) {
errno = EINVAL;
return NULL;
}
deck = malloc(cards * sizeof *deck);
if (deck == NULL) {
errno = ENOMEM;
return NULL;
}
for (n = 0; n < cards; n++)
deck[n] = n;
n = cards;
while (n > 2) {
const size_t c0 = deck[0];
const size_t c1 = deck[1];
memmove(deck, deck + 2, (n - 2) * sizeof *deck);
deck[n-1] = c0;
deck[n-2] = c1;
n--;
}
if (n == 2) {
const size_t c = deck[0];
deck[0] = deck[1];
deck[1] = c;
}
return deck;
}
The above function returns an array of indexes, corresponding to where the card ends up after each full round. Because these indexes indicate card position, every round performs the exact same operation.
The function is not optimized or even terribly efficient; it uses memmove()
to keep the top of the deck at the start of the array. Instead, one could treat the initial part of the array as a cyclic buffer.
If you have difficulty comparing the function to the original instructions, the intent is to always take two topmost cards, and move the first to the top of the result deck, and the second to the bottom of the hand deck. If there are just two cards left, the first card goes to the result deck first, the second card last. If there is only one card left, it obviously goes to the result deck. In the function, the first n
entries in the array are the hand deck, and the last cards-n
entries are the table deck.
To find out the number of cycles, we simply need to traverse each cycle in the above graph or mapping:
size_t *cycle_lengths(size_t *graph, const size_t nodes)
{
size_t *len, i;
if (graph == NULL || nodes < 1) {
errno = EINVAL;
return NULL;
}
len = malloc(nodes * sizeof *len);
if (len == NULL) {
errno = ENOMEM;
return NULL;
}
for (i = 0; i < nodes; i++) {
size_t c = i;
size_t n = 1;
while (graph[c] != i) {
c = graph[c];
n++;
}
len[i] = n;
}
return len;
}
This function too could be enhanced quite a bit. This one traverses every cycle the number of positions in that cycle times, instead of just traversing each cycle only once, and assigning the cycle length to all participants in the cycle.
For the next steps, we need to know all primes up to and including the number of cards. (Including, because we might have only one cycle, so the largest length we might see is the number of cards in the deck.) One simple option is to use a bit map and Sieve of Eratosthenes:
#ifndef ULONG_BITS
#define ULONG_BITS (sizeof (unsigned long) * CHAR_BIT)
#endif
unsigned long *sieve(const size_t limit)
{
const size_t bytes = (limit / ULONG_BITS + 1) * sizeof (unsigned long);
unsigned long *prime;
size_t base;
prime = malloc(bytes);
if (prime == NULL) {
errno = ENOMEM;
return NULL;
}
memset(prime, ~0U, bytes);
/* 0 and 1 are not considered prime. */
prime[0] &= ~(3UL);
for (base = 2; base < limit; base++) {
size_t i = base + base;
while (i < limit) {
prime[i / ULONG_BITS] &= ~(1UL << (i % ULONG_BITS));
i += base;
}
}
return prime;
}
Since it is possible that there is only one cycle, covering all cards, you will want to supply the number of cards + 1 to the above function.
Let's see how the above would work. Let's define some array variables we need:
size_t cards; /* Number of cards in the deck */
unsigned long *prime; /* Bitmap of primes */
size_t *graph; /* Card position mapping */
size_t *length; /* Position cycle lengths, for each position */
size_t *power;
The last one, 'power', should be allocated and initialized to all zeros. We will be using only entries [2] to [cards], inclusive. The intent is to be able to calculate the result as ∏(p^power[p]), p=2..cards.
Start by generating the mapping, and calculating the cycle lengths:
graph = mapping(cards);
length = cycle_lengths(graph, cards);
To calculate the number of rounds, we need to factorize the cycle lengths, and calculate the product of the highest power of each factor in the lengths. (I'm not a mathematician, so if someone can explain this correctly/better, any and all help is appreciated.)
Perhaps actual code describes it better:
size_t p, i;
prime = sieve(cards + 1);
for (p = 2; p <= cards; p++)
if (prime[p / ULONG_BITS] & (1UL << (p % ULONG_BITS))) {
/* p is prime. */
for (i = 0; i < cards; i++)
if (length[i] > 1) {
size_t n = 0;
/* Divide out prime p from this length */
while (length[i] % p == 0) {
length[i] /= p;
n++;
}
/* Update highest power of prime p */
if (power[p] < n)
power[p] = n;
}
}
and the result, using floating-point math in case size_t
is not large enough,
double result = 1.0;
for (p = 2; p <= cards; p++) {
size_t n = power[p];
while (n-->0)
result *= (double)p;
}
I have verified that the two solutions produce exact same results for decks of up to 294 cards (the slow non-array solution just took too long for 295 cards for me to wait).
This latter approach works just fine for even huge decks. For example, it takes about 64 ms on this laptop to find out that using a 10,000-card deck, it takes 2^5*3^3*5^2*7^2*11*13*17*19*23*29*41*43*47*53*59*61 = 515,373,532,738,806,568,226,400 rounds to get to the original order.
(Printing the result with zero decimals using a double-precision floating-point number yields slightly smaller result, 515,373,532,738,806,565,830,656 due to the limited precision.)
It took almost 8 seconds to calculate that a deck with 100,000 cards the number of rounds is 2^7*3^3*5^3*7*11^2*13*17*19*23*31*41*43*61*73*83*101*113*137*139*269*271*277*367*379*541*547*557*569*1087*1091*1097*1103*1109 ≃ 6.5*10^70.
Note that for visualization purposes, I used the following snippet to describe the card position changes during one round:
printf("digraph {\n");
for (i = 0; i < cards; i++)
printf("\t\"%lu\" -> \"%lu\";\n", (unsigned long)i + 1UL, (unsigned long)graph[i] + 1UL);
printf("}\n");
Simply feed that output to e.g. dot
from Graphviz to draw a nice directed graph.