My JavaScript book is out! Don't miss the opportunity to upgrade your beginner or average dev skills.

Sunday, July 27, 2008

Mousetrap in C language

Just for fun, and performances are horribles as well in new C version, performances are great until 5000 cards, so I need to remove some dust from my good old ANSI C book :D

New version, compatible with gcc compiler.
To create and use the executable, gcc Mousetrap.c

Then call the file Mousetrap 5, for example, to obtain 1,3,2,5,4
Works quickly until 5000 results, requires a monster PC for 1000000 Google limit (algo is still not perfect, but this can generate an entire deck, instead of getting only that index, for each index)

#include <stdlib.h>

int *perfectDeck(int cards);

int main(int argc, char **argv){
if(--argc){
*argv++;
int i = 0,
cards = atoi(*argv);
if(cards > 0){
int *result = perfectDeck(cards);
printf("%i", result[i++]);
while(i < cards)
printf(" %i", result[i++]);
free(result);
}
}
return 0;
}

int *perfectDeck(int cards){
int card = cards,
move = 0,
i = 0;
int *deck = (int *)malloc(cards * sizeof(int)),
*result = (int *)malloc(cards * sizeof(int));
while(card--)
deck[card] = card;
while(cards){
move = (card++ % cards--) + 1;
while(move--){
i = deck[0];
memmove(deck, deck + 1, cards * sizeof(int));
deck[cards] = i;
}
result[deck[0]] = card + 1;
deck++;
}
free(deck);
return result;
}



This is the old version, bad practices everywherem and no movements optimizations (ok, ok, I wrote it too fast)

#include <stdlib.h>

typedef struct {
int length;
int *index;
} Array;

Array new_Array(int length);
Array shift(Array deck);
Array perfectDeck(int cards);
void move(Array deck);

Array new_Array(int length){
Array result;
int i = 0,
*stack = malloc(length * sizeof(int));
while(i < length)
stack[i] = i++;
result.length = length;
result.index = stack;
return result;
}

Array shift(Array deck){
Array result = new_Array(deck.length - 1);
int i = 0,
length = result.length,
*dindex = deck.index,
*rindex = result.index;
while(i < length)
rindex[i] = dindex[++i];
free(deck.index);
return result;
}

Array perfectDeck(int cards){
Array deck = new_Array(cards),
result = new_Array(cards);
int i = 0,
count = 0;
while(i < cards){
while(count++ != i)
move(deck);
result.index[deck.index[0]] = count;
deck = shift(deck);
count = 0;
++i;
}
free(deck.index);
return result;
}

void move(Array deck){
int *index = deck.index,
last = index[0],
i = 1,
length = deck.length;
while (i < length)
index[i - 1] = index[i++];
index[i - 1] = last;
}

/*
int main(){
Array result = perfectDeck(5);
printf("%i %i %i %i %i", result.index[0], result.index[1], result.index[2], result.index[3], result.index[4]);
scanf("%s");
free(result.index);
return 0;
}
*/

No comments: