Hrm. There's a
wikipedia article, but it's dense reading even for a native speaker who's familiar with the subject already.
Schlemiel the Painter's algorithm is easier going: "Schlemiel has a job painting the dotted lines down the middle of a road. Each day, Schlemiel paints less than he painted the day before. When he is asked why, Schlemiel complains that it is because each day he gets farther away from the paint can."
(And it's actually n³ now that I look at it closer.)
What it boils down to is that this will seem to work ok when used against a "reasonably"-sized library with, say, 25 cards left in it - it'll take on the order of 25*25*25, or 15,625, instructions. If it gets used against a
Battle of Wits deck or the Shandalar Arzakon deck or the challenge mode all-
Mountain deck with 400 cards left, it'll take on the order of 64
million instructions (400*400*400), or 4096 times as long as the 25-card deck instead of just 8 times. Done properly, the first deck should take 25 constant-time operations and the second 400.
The problematic code is:
- Code: Select all
while( count_deck(p) > 0 ){
rfg_top_card_of_deck(p);
}
with rfg_top_card_of_deck() in relevant part as
- Code: Select all
for(i=0;i<count_deck(player);i++){
deck[i] = deck[i+1];
}
rfg[ count_rfg(player) ] = id;
What's making them blow up is that count_deck() (and count_rfg(), which uses the same underlying code) are sort of like strlen() - it's not instant, it goes through the entire deck[] (or rfg[]) array, element by element, checking each position to see if there's a card in it.
The loop in rfg_top_card_of_deck() calls count_deck() once for each card in the deck, and then count_rfg() once. So it takes on the order of (deck_size * deck_size) + rfg_size instructions to execute. (This is the easiest part to fix - just store count_deck() in a local var once before the loop, and compare against that in the loop condition instead.)
The loop in card_jace_the_mind_sculptor() calls count_deck() and rfg_top_card_of_deck() once for each card in the deck. So
it in turn takes on the order of deck_size * (deck_size + (deck_size * deck_size) + rfg_size) instructions.
Since it doesn't matter what order the cards in the deck should be exiled, this shouldn't ever take more than 500 iterations even in the very worst case (500 total cards in the library and exile zone at start of execution), using something like
- Code: Select all
void rfg_entire_deck(int player, int* deck){
// deck can be either a library or graveyard, but must be at the start of the array
int* rfg = rfg_ptr[player];
int deck_pos, rfg_pos = 0, any_exiled = 0;
for (deck_pos = 0; deck_pos < 500; ++deck_pos){
if (deck[deck_pos] != -1){
while (rfg[rfg_pos] != -1){
++rfg_pos;
}
rfg[rfg_pos] = deck[deck_pos];
deck[deck_pos] = -1;
any_exiled = 1;
}
}
if (any_exiled){
play_sound_effect(WAV_DESTROY); // The exile sound effect, despite its name
}
}
Posted: 11 Nov 2013, 11:13