Create a gist now

Instantly share code, notes, and snippets.

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 <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