/// Yasmin Fakhoury
/// COP 3502 Honors
/// 2/14/17
/// Program #3
/// Outputs all the number of possible answer combinations for a partially
/// completed game of Mastermind

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/// Global variables
int n;          /// Number of slots to fill
int k;          /// Number of possible colors
int m;          /// Number of moves made
int b;          /// Number of black pegs
int w;          /// Number of white pegs
int total;      /// Number of possible combinations
int** combinations;
int combopos = 0;

void printgame(int** game);
void freegame(int** game);
//void allCombos(int perm[], int guess[], int place);
int black(int perm[], int guess[]);
int white(int perm[], int guess[]);
bool compare(int perm[], int guess[]);
void allCombos2(int perm[], int place);
void test(int** combinations, int** mm);

FILE* infile;


int main(){

    infile = fopen("test.in", "r");

    int numcases;   /// Total number of partially complete games to read in
    int h, i, j;    /// Counters

    /// Scan top of input for number of total cases
    fscanf(infile,"%d", &numcases);

    /// Read in each game
    for(h=0; h<numcases; h++){


        /// Read in number of slots per guess, the number of possible
        /// colors to pick from, and the number of moves so far in the game
        fscanf(infile,"%d %d %d", &n, &k, &m);

        combinations = (int**) malloc(pow(k,n)*sizeof(int*));

        combopos=0;

        for(i=0; i<pow(k,n); i++){
            combinations[i] = (int*) malloc(n*sizeof(int));
        }

        /// Allocate space for rows of the fame in a 2d array
        int** mm = (int**) malloc(m * sizeof(int*));
        /// Array to hold each possible combination of guesses
        int* combo = (int*) malloc(n*sizeof(int));
        allCombos2(combo, 0);
        free(combo);

        /// Loop through each move in the game
        for(i=0; i<m; i++){

            /// Allocate space for columns of 2d array
            mm[i] = (int*)malloc((n+2) * sizeof(int));

            /// Loop through n times
            for(j=0; j<n; j++){
                /// Scan in guesses from each turn in the game
                fscanf(infile,"%d", &mm[i][j]);
            }

            /// Scan in the number of black and white pegs after each line
            fscanf(infile,"%d %d", &mm[i][n], &mm[i][n+1]);

            /// Generate all the possible combinations for the game, and from
            /// there see which ones match the black and white peg values read in
            // allCombos(combo, mm[i], 0);


        }

        /// Initialize total viable combinations at 0 before incrementation
        total = pow(k,n);

        test(combinations, mm);

        printf("%d\n", total);
        //printgame(mm);

//        /// Free memory used to store game before moving on to the next one
        freegame(mm);

        for(i=0; i<pow(k,n); i++)
        {
            free(combinations[i]);
        }
        free(combinations);

    }

    fclose(infile);
    return 0;
}

/*
/// Prints out all possible guess combinations for the given values of k and n
void allCombos(int perm[], int guess[], int place){

    /// If the place in the array is equal to the number of slots,
    /// then call compare function
    if(place == n){
        compare(perm, guess);
    }

    /// Otherwise, keep going until an entire combination is filled in
    else{
        int i;
        for(i=0; i<k; i++){
            /// Set the slot in the array equal to one of the colors
            perm[place] = i;
            allCombos(perm, guess, place+1);
        }
    }
}
*/
bool compare(int perm[], int guess[]){

    /// If both black and white peg functions return true,
    /// increment the total by 1
    return ((black(perm, guess) == 1) && (white(perm, guess) == 1));
//        printf("compare total = %d \n", total);

}


int black(int perm[], int guess[]){

    /// "totalblack" is the number of black pegs yielded through
    /// comparison of the guess and given combination
    int i, totalblack = 0;

    for(i=0; i<n; i++){
        /// Each time slot i of the combination holds the same
        /// color as slot i of the guess, increase number of
        /// black pegs by 1
        if(perm[i] == guess[i])
            totalblack++;
    }

    /// If the total number of black pegs found equals that which
    /// was given in the input, the function returns true
    /// Otherwise, return false
    if(totalblack == guess[n]) return 1;
    else return 0;
}

int teststuff[4] = {0,1,2,1};
int white(int combo[], int guess[])
{


    int* freqguess = (int*)malloc(k*sizeof(int));   /// Frequency array for guess
    int* freqcombo = (int*)malloc(k*sizeof(int));   /// Frequency array for combination
    int i, j;           /// Counters
    int totalwhite = 0; /// Number of white pegs found through
    /// comparing the guess and the combination

    /// Initialize both frequency arrays at 0
    for(i=0; i<k; i++){
        freqguess[i] = 0;
        freqcombo[i] = 0;
    }

    for(i=0; i<n; i++){
        freqguess[guess[i]]++;
        freqcombo[combo[i]]++;
//
//        for(j=0; j<n; j++){
//            /// Each time that a slot in the guess or combo equals a particular color
//            /// increase the value in the slot of the frequency array for that
//            /// color by 1
//            if(guess[j] == i){
//                freqguess[i]++;
//            }
//            if(combo[j] == i){
//                freqcombo[i]++;
//            }
//        }
    }

    /*
    int loop;
    printf("freqcombo: ");
    for(loop=0; loop<4; loop++){
        printf("%d ", freqcombo[loop]);
    }
    printf("\n");

    printf("freqguess: ");
    for(loop=0; loop<4; loop++){
        printf("%d ", freqguess[loop]);
    }
    printf("\n");
    */

    for(i=0; i<k; i++){

        /// Compare the frequency array values of combo and guess
        /// for each color and increase the number of white pegs the
        /// lesser of the two values
        if(freqcombo[i] >= freqguess[i])
            totalwhite += freqguess[i];

        else
        {
            totalwhite+=freqcombo[i];
        }

    }

//    printf("totalwhite = %d \n", totalwhite);

    /// If the total number of white pegs calculated equals the number of
    /// white pegs given in the input, return true

    free(freqcombo);
    free(freqguess);
    if(totalwhite == guess[n+1] + guess[n]){
        return 1;
    }else return 0;
}


/// Frees 2d array storing game
void freegame(int** game){

    int i;
    for(i=0; i<m; i++)
        free(game[i]);

    free(game);
}


/*
/// For testing, delete
void printgame(int** game){

    int i, j;
    for(i=0; i<m; i++){
        for(j=0; j<n; j++){
            printf("%d ", game[i][j]);

        }
        printf("\n");
    }
}
*/


void test(int** combos, int** guesses){
    int i, j;
    int numpossible = pow(k,n);

    for(i=0; i<numpossible; i++){
        for(j=0; j<m; j++)
            if(!compare(combos[i], guesses[j])){
                total--;
                break;
            }
    }

}

/// In main
/// combos[i] = malloc(n*sizeof(int));

void allCombos2(int perm[], int place){

    /// If the place in the array is equal to the number of slots,
    /// then call compare function
    if(place == n){
        int loop;
        for(loop=0; loop<n; loop++){
            combinations[combopos][loop] = perm[loop];
        }
        combopos++;
    }

        /// Otherwise, keep going until an entire combination is filled in
    else{
        int i;
        for(i=0; i<k; i++){
            /// Set the slot in the array equal to one of the colors
            perm[place] = i;
            allCombos2(perm, place+1);
        }
    }


}