fork(35) download
copy 
  1. // Fritz Ammon
  2. // March 7, 2014
  3. // Shuffle Interview Problem
  4.  
  5. /*
  6. 	The exercise solves a coding problem that involves shuffling a deck of cards. 
  7. 	The problem description is as follows:
  8.  
  9. 	You are given a deck containing 313 cards. While holding the deck: 
  10. 		1. Take the top card off the deck and set it on the table 
  11. 		2. Take the next card off the top and put it on the bottom of the deck in 
  12. 			your hand. 
  13. 		3. Continue steps 1 and 2 until all cards are on the table. This is a round. 
  14. 		4. Pick up the deck from the table and repeat steps 1-3 until the deck is in 
  15. 			the original order. 
  16.  
  17. 	Write a program to determine how many rounds it will take to put the deck back 
  18. into the original order. This will involve creating a data structure to represent the 
  19. order of the cards. This program should be written in C. It should take a number 
  20. of cards in the deck as a command line argument and write the result to stdout.
  21. */
  22.  
  23. // Explanation of my solution:
  24. //
  25. //		Trying to solve this problem without realizing the benefit of a simple mathematical concept
  26. // and the use of a poor solution could result in an extremely large number of simulations of
  27. // card shuffling for a deck with 313 cards. Thus, it would take too long to compute and I must
  28. // find another way to solve this by finding a pattern which I have illustrated in the image below:
  29. // http://f...content-available-to-author-only...l.ly/items/223e2u063C3k0o460P3r/shuffling.png
  30. // It takes 12 rounds to return 12 cards back to order; feel free to try that as input yourself as verification.
  31. //
  32. // 		You might also notice something about what happens when a card returns to its position.
  33. // Its numbers for the card, or the numbers in that card's column, would repeat. We were lucky that
  34. // all the numbers returned to their original position after 12 rounds, but that may not always happen.
  35. // Thus, we count how many rounds each card takes, then calculate the LCM which tells us how many rounds
  36. // are required by the cards altogether to get the deck back in order at the same time.
  37.  
  38. #include <stdio.h>
  39. #include <stdlib.h>
  40.  
  41. typedef enum {FALSE, TRUE} BOOL;
  42.  
  43. typedef struct Card
  44. {
  45. 	unsigned short int n; // card number
  46. 	struct Card *p; // next card in deck
  47. 	unsigned int r; // loop length
  48. } cardType;
  49.  
  50. void createDeck(cardType **d, cardType **b, unsigned short s);
  51. void destroyDeck(cardType **d);
  52. void removeTop(cardType **d, cardType **t);
  53. void shiftDeck(cardType **d, cardType **b);
  54. BOOL checkDeck(cardType* d, unsigned int r);
  55. void makeKey(cardType* d, unsigned short *k, unsigned short *c, unsigned short s);
  56. void adjustDeck(cardType* d, unsigned short *k, unsigned short *c, unsigned short s);
  57. unsigned int gcd(unsigned int a, unsigned int b);
  58. unsigned int lcm(unsigned int a, unsigned int b);
  59. unsigned int lcmLoop(cardType* d);
  60.  
  61. int main()//int argc, char **argv)
  62. {
  63. 	cardType *topDeck = NULL, *bottomDeck = NULL, *topTable = NULL;
  64. 	cardType *nextBottom = NULL; // the topDeck
  65. 	unsigned int rounds = 0;
  66. 	BOOL done = FALSE;
  67. 	unsigned short deckSize = 0;
  68. 	unsigned short *key;
  69. 	unsigned short *copy;
  70.  
  71. 	/*if (argc != 2)
  72. 		return 0;
  73.  
  74. 	sscanf_s(argv[1], "%d", &deckSize);*/
  75.  
  76. 	scanf("%d", &deckSize);
  77.  
  78. 	key = (unsigned short*) malloc(sizeof(unsigned short) * deckSize);
  79. 	copy = (unsigned short*) malloc(sizeof(unsigned short) * deckSize);
  80.  
  81. 	createDeck(&topDeck, &bottomDeck, deckSize);
  82. 	nextBottom = topDeck; // we know our current top will be the bottom of our next deck
  83.  
  84. 	// keep removing and shifting until deck is empty
  85. 	do
  86. 	{
  87. 		removeTop(&topDeck, &topTable);
  88.  
  89. 		if (topDeck)
  90. 		{
  91. 			if (topDeck != bottomDeck) // cannot shift if already bottom
  92. 				shiftDeck(&topDeck, &bottomDeck);
  93. 		}
  94. 		else
  95. 		{
  96. 			rounds++; // all cards on table
  97. 			topDeck = topTable; // table deck becomes our new deck
  98. 			topTable = NULL;
  99.  
  100. 			bottomDeck = nextBottom;
  101. 			nextBottom = topDeck;
  102.  
  103. 			done = TRUE;
  104. 		}
  105. 	} while (!done);
  106.  
  107.     // We only needed to analyze how cards moved around once to create a key
  108.  	// of indexes which lets us get the next position of a card in O(1).
  109. 	makeKey(topDeck, key, copy, deckSize);
  110.  
  111. 	// Next we keep adjusting the deck following the key until cards are back in place.
  112. 	while (!checkDeck(topDeck, rounds))
  113. 	{
  114. 		adjustDeck(topDeck, key, copy, deckSize);
  115. 		rounds++;
  116. 	}
  117.  
  118. 	// find the lcm of all the r's
  119. 	rounds = lcmLoop(topDeck);
  120.  
  121. 	destroyDeck(&topDeck);
  122.  
  123. 	free(copy);
  124. 	free(key);
  125.  
  126. 	printf("rounds for %d numbers = %d\n", deckSize, rounds);
  127.  
  128. 	return 0;
  129. }
  130.  
  131. void createDeck(cardType **d, cardType **b, unsigned short s)
  132. // d is a pointer to the top of our deck (which is a pointer to a node).
  133. // b is a pointer to the bottom of our deck (which is also a pointer to a node).
  134. // s is the size of the deck.
  135. // We will create the deck and save the corresponding node pointers.
  136. {
  137. 	cardType *newCard, *t;
  138. 	unsigned short c;
  139.  
  140. 	(*d) = (cardType*) malloc(sizeof(cardType));
  141. 	(*d)->n = 0;
  142. 	(*d)->r = 0;
  143. 	(*d)->p = NULL;
  144. 	t = (*b) = (*d); // copy of top, and bottom is deck top right now
  145.  
  146. 	for (c = 1; c < s; c++)
  147. 	{
  148. 		newCard = (cardType*) malloc(sizeof(cardType));
  149. 		newCard->n = c;
  150. 		newCard->r = 0;
  151. 		newCard->p = NULL;
  152. 		(*d)->p = newCard;
  153. 		(*b) = (*d) = newCard;
  154. 	}
  155.  
  156. 	(*d) = t; // return to top
  157. }
  158.  
  159. void destroyDeck(cardType **d)
  160. // d is the top of our deck.
  161. // Where we create, we must destroy.
  162. {
  163. 	cardType *nextCard;
  164.  
  165. 	while ((*d))
  166. 	{
  167. 		nextCard = (*d)->p;
  168. 		free((*d));
  169. 		(*d) = nextCard;
  170. 	}
  171. }
  172.  
  173. void removeTop(cardType **d, cardType **t)
  174. // d is the top of our deck.
  175. // t is the top of our table deck.
  176. // We will remove the top of our deck and place at the top of our table deck.
  177. {
  178. 	cardType *tempCard;
  179.  
  180. 	// d becomes top next
  181. 	// make deck top next point to table top
  182. 	tempCard = (*d);
  183. 	(*d) = (*d)->p;
  184.  
  185. 	tempCard->p = (*t);
  186. 	(*t) = tempCard;
  187. }
  188.  
  189. void shiftDeck(cardType **d, cardType **b)
  190. // d is the top of our deck.
  191. // b is the bottom of our deck.
  192. // We remove the top card and place it underneath the deck.
  193. {
  194. 	cardType* tempCard;
  195.  
  196. 	// top becomes next card
  197. 	tempCard = (*d);
  198. 	(*d) = (*d)->p;
  199.  
  200. 	// bottom is updated with old top
  201. 	// new bottom points to null
  202. 	(*b)->p = tempCard;
  203. 	(*b) = (*b)->p;
  204. 	(*b)->p = NULL;
  205. }
  206.  
  207. BOOL checkDeck(cardType* d, unsigned int r)
  208. // d is the top of our deck.
  209. // r is the number of rounds it took for a card to get back into its original position in the deck.
  210. // We check each card to see if it its position n matches our index i which tells us it is back in the
  211. // right position. Then we save the number of rounds r.
  212. // We only return TRUE when all of the cards are back in place.
  213. {
  214. 	unsigned short i = 0;
  215. 	BOOL done = TRUE;
  216.  
  217. 	while (d)
  218. 	{
  219. 		if (d->n == i)
  220. 			d->r = r; // if back in original place then cycle finished, keep round count
  221. 		else if (d->r == 0) // if never reached original place and not equal to original place
  222. 			done = FALSE;
  223.  
  224. 		d = d->p;
  225. 		i++;
  226. 	}
  227.  
  228. 	return done; // done when all r's are not 0
  229. }
  230.  
  231. void makeKey(cardType* d, unsigned short *k, unsigned short *c, unsigned short s)
  232. // d is the top of our deck.
  233. // k is the key.
  234. // c is a copy of the key.
  235. // Makes a key of indexes to use when adjusting our deck (simulate a round).
  236. {
  237. 	unsigned short i;
  238.  
  239. 	// we keep the positions the numbers came from
  240. 	// so that now we don't have to calculate them
  241. 	// and simply adjust future decks
  242. 	for (i = 0; i < s; i++)
  243. 	{
  244. 		c[i] = k[i] = d->n; // remember, this is after we've shifted (i = 0 does not => n = 0)
  245. 		d = d->p;
  246. 	}
  247. }
  248.  
  249. void adjustDeck(cardType* d, unsigned short *k, unsigned short *c, unsigned short s)
  250. // d is the top of our deck.
  251. // k is our key.
  252. // c is a copy of our key.
  253. // s is the size of the deck.
  254. // Simulate a round.
  255. {
  256. 	unsigned short *newCopy = (unsigned short*) malloc(sizeof(unsigned short) * s);
  257. 	unsigned short i;
  258.  
  259. 	// based on key, find next deck order
  260. 	for (i = 0; i < s; i++)
  261. 	{
  262. 		newCopy[i] = d->n = c[k[i]]; // Get new positions.
  263. 		d = d->p;
  264. 	}
  265.  
  266. 	// make a copy of this new order for next order
  267. 	for (i = 0; i < s; i++)
  268. 		c[i] = newCopy[i];
  269.  
  270. 	free(newCopy);
  271. }
  272.  
  273. unsigned int gcd(unsigned int a, unsigned int b)
  274. // a and b are operands.
  275. // Calculates the greatest common divider.
  276. {
  277. 	while (b)
  278. 	{
  279. 		// euclid's
  280. 		a %= b;
  281. 		b ^= a;
  282. 		a ^= b;
  283. 		b ^= a;
  284. 	}
  285.  
  286. 	return a;
  287. }
  288.  
  289. unsigned int lcm(unsigned int a, unsigned int b)
  290. // a and b are operands.
  291. // Calculates the lowest common multiple.
  292. {
  293. 	return ((unsigned long long) a * b) / gcd(a, b);
  294. }
  295.  
  296. unsigned int lcmLoop(cardType* d)
  297. // d is the top of our deck.
  298. // Recursively calculates the lowest common multiple of all the cards' rounds.
  299. {
  300. 	if (d)
  301. 		return lcm(d->r, lcmLoop(d->p)); // recursively get lcm of all r's
  302. 	else
  303. 		return 1;
  304. }
Success #stdin #stdout 0s 2428KB
comments (?)
stdin
copy 
313
stdout
copy 
rounds for 313 numbers = 1575169365
https://ideone.com/yuMVIt
deck shuffle
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!