in reply to
Re^2: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty

in thread Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty

All,

I have ported the code to C (figured out how to avoid a dynamically managed array) and am making it available here for your critique/suggestions. I have never been a C programmer so there are probably a number of ways to write this more elegantly and efficiently.

`#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int won_game(int *copy);
void hit(int *copy, int pos);
int n_neighbor(int *copy, int pos);
int s_neighbor(int *copy, int pos);
int e_neighbor(int *copy, int pos);
int w_neighbor(int *copy, int pos);
int main (void) {
static const char filename[] = "games.dat";
FILE *file = fopen (filename, "r");
if (file != NULL) {
char line[32];
srand(time(NULL));
while (fgets(line, sizeof line, file) != NULL) {
int i; // looping variable
int j; // looping variable
int hits; // index where the current n
+umber of hits is stored
int curr; // index of current item bei
+ng worked on
int last; // index of last item in our
+ work queue
int games_played; // keep track of how many ga
+mes we have played
int stat[10]; // Keeps track of number of
+hits to win a game
int work[1000][31]; // Work queue (DFS will neve
+r need more than 1000)
games_played = 0;
hits = 30;
// Populate stats to all be 0
for (i = 0; i < 10; i++) {
stat[i] = 0;
}
// Populate first item on work queue
for (i = 0; i < 30; i++) {
work[0][i] = ((int) line[i]) - 48;
}
work[0][hits] = 9; // number of hits allowed t
+o play a board
last = 1;
while (last > 0) {
int possible[30]; // maximum number of possibl
+e hits
int last_idx; // index of last possible hi
+t for "this" board
int temp; // used for Fisher-Yates shu
+ffle
/* Takes too long to play games exhaustively, even in
+C */
if (games_played > 500000) {
break;
}
--last;
curr = last;
--work[curr][hits]; // drop the number of hits
// populate possible hits for "this board"
last_idx = -1;
for (i = 0; i < 30; i++) {
if (work[curr][i] > 0) {
++last_idx;
possible[last_idx] = i;
}
}
// Fisher-Yates shuffle them so that games played are
+all distinct but random
for (i = last_idx; i > 0; i--) {
j = rand() % (i + 1); // yes, I know this isn't pe
+rfect
temp = possible[i];
possible[i] = possible[j];
possible[j] = temp;
}
// Loop over all possible hits on the board, hitting e
+ach one
for (i = 0; i <= last_idx; i++) {
// copy of the board to manipulate
int copy[31];
for (j = 0; j < 31; j++) {
copy[j] = work[curr][j];
}
hit(copy, possible[i]);
// Game won
if (won_game(copy) == 1) {
++games_played;
++stat[work[curr][hits]];
}
// Game lost
else if (work[curr][hits] == 0) {
++games_played;
++stat[9];
}
// Still playing so put it back on the work queue
else {
++last;
for (j = 0; j < 31; j++) {
work[last][j] = copy[j];
}
}
}
}
for (i = 0; i < 30; i++) {
printf("%c", line[i]);
}
for (i = 0; i < 10; i++) {
printf(",%i", stat[i]);
}
printf("\n");
}
fclose (file);
}
else {
perror(filename);
}
return 0;
}
int won_game(int *copy) {
int i;
for (i = 0; i < 30; i++) {
if (copy[i] > 0) {
return 0;
}
}
return 1;
}
void hit(int *copy, int pos) {
if (pos < 0 || copy[pos] == 0) {
return;
}
--copy[pos];
// If we exploded, we have to hit our neighbors
if (copy[pos] == 0) {
hit(copy, n_neighbor(copy, pos));
hit(copy, s_neighbor(copy, pos));
hit(copy, e_neighbor(copy, pos));
hit(copy, w_neighbor(copy, pos));
}
return;
}
int n_neighbor(int *copy, int pos) {
while (1) {
pos = pos - 5;
if (pos < 0) {
return -1;
}
if (copy[pos] > 0) {
return pos;
}
}
}
int s_neighbor(int *copy, int pos) {
while (1) {
pos = pos + 5;
if (pos > 29) {
return -1;
}
if (copy[pos] > 0) {
return pos;
}
}
}
int e_neighbor(int *copy, int pos) {
int min_val;
min_val = (pos / 5) * 5;
while (1) {
--pos;
if (pos < min_val) {
return -1;
}
if (copy[pos] > 0) {
return pos;
}
}
}
int w_neighbor(int *copy, int pos) {
int max_val;
max_val = ((pos / 5) * 5) + 4;
while (1) {
++pos;
if (pos > max_val) {
return -1;
}
if (copy[pos] > 0) {
return pos;
}
}
}
`

Even in my neophyte C, I have realized an enormous performance increase. Even in C, it still takes too long to exhaustively play all possible games for a board when you allow the player to use up to 9 hits. For this reason, I duplicated the same changes I did to the original Perl (play a limited number of distinct but random games). The difference is that I am now able to use up to 9 hits and play 500K games in less time then it was taking me to play 6 hits for 40K games.