#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 number of hits is stored
            int curr;                     // index of current item being worked on
            int last;                     // index of last item in our work queue
            int games_played;             // keep track of how many games we have played
            int stat[10];                 // Keeps track of number of hits to win a game 
            int work[1000][31];           // Work queue (DFS will never 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 to play a board
            last = 1;

            while (last > 0) {
                int possible[30];         // maximum number of possible hits
                int last_idx;             // index of last possible hit for "this" board
                int temp;                 // used for Fisher-Yates shuffle

                /* 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 perfect
                    temp = possible[i];
                    possible[i] = possible[j];
                    possible[j] = temp;
                }

                // Loop over all possible hits on the board, hitting each 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;
        }
    }
}