Instantly share code, notes, and snippets.

# EmilHernvall/reorderhand.c Created May 3, 2011

What would you like to do?
Given a hand of n cards and k attempts, use recursion to shuffle the cards into a given order.
 /** * 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 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; }