Created
May 3, 2011 17:32
-
-
Save EmilHernvall/953786 to your computer and use it in GitHub Desktop.
Given a hand of n cards and k attempts, use recursion to shuffle the cards into a given order.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Emil Hernvall - 2007-12-15 | |
* Given a hand of n cards and k attempts, use recursion to shuffle the cards | |
* into a given order. | |
*/ | |
#include <stdio.h> | |
int compare(int* first, int* second, int size) | |
{ | |
int i; | |
for (i = 0; i < size; i++) { | |
if (first[i] != second[i]) { | |
return 0; | |
} | |
} | |
return 1; | |
} | |
void print(int* source, int size, int indent) | |
{ | |
int i; | |
for (i = 0; i < indent; i++) { | |
printf("\t"); | |
} | |
for (i = 0; i < size; i++) { | |
printf("%d ", source[i]); | |
} | |
printf("\n"); | |
} | |
int* move(int* source, int size, int pos, int range, int newpos) | |
{ | |
int* new = malloc(sizeof(int) * size); | |
memset(new, 0, sizeof(int) * size); | |
int move[range]; | |
int fixed[size-range]; | |
// separate the interval to move and the fixed cards | |
int i, j, k; | |
for (i = 0, j = 0, k = 0; i < size; i++) { | |
if (i >= pos && i < pos + range) { | |
move[j] = source[i]; | |
j++; | |
} else { | |
fixed[k] = source[i]; | |
k++; | |
} | |
} | |
// merge them again | |
for (i = 0, j = 0, k = 0; i < size; i++) { | |
if (i >= newpos && i < newpos + range) { | |
new[i] = move[j]; | |
j++; | |
} else { | |
new[i] = fixed[k]; | |
k++; | |
} | |
} | |
return new; | |
} | |
int recurse(int* cards, int* target, int size, int maxlevel, int curlevel) | |
{ | |
if (curlevel > maxlevel) { | |
return 0; | |
} | |
int i, j, n, match = 0; | |
// number of cards to move every time | |
for (n = 1; n < size; n++) { | |
// position to move the cards from | |
for (i = 0; i <= size - n; i++) { | |
// position to move the cards to | |
for (j = 0; j <= size - n; j++) { | |
int* cards2 = move(cards, size, i, n, j); | |
if (compare(cards2, target, size) == 1) { | |
match = 1; | |
print(cards2, size, curlevel); | |
} | |
else if (recurse(cards2, target, size, maxlevel, curlevel + 1) == 1) { | |
match = 1; | |
print(cards2, size, curlevel); | |
} | |
free(cards2); | |
} | |
} | |
} | |
return match; | |
} | |
int main(void) | |
{ | |
int size = 5; | |
int cards[] = { 1, 2, 3, 4, 5 }; | |
int target[] = { 5, 4, 3, 2, 1 }; | |
recurse(cards, target, size, 3, 1); | |
print(cards, size, 0); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment