// Arup Guha
// 11/22/2025
// Solution to 2025 Fall COP 3502 Program 6: Wordle Candidate Ranking

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

#define MAXGUESSES 5
#define LEN 5

/*** For scoring ***/
const int freq[26] = {
    /* a  b  c  d  e  f  g  h  i  j  k  l  m */
       8, 2, 3, 4, 13,3, 2, 6, 7, 0, 1, 4, 2,
    /* n  o  p  q  r  s  t  u  v  w  x  y  z */
       7, 7, 2, 0, 6, 6, 9, 3, 1, 2, 0, 2, 0
};

typedef struct Entry{
    char word[6];
    int score;
} Entry;

typedef struct HeapStruct {
    Entry** heaparray;
    int capacity;
    int size;
} HeapStruct;

// To store a guess and its feedback.
typedef struct Guess {
    char word[LEN+1];
    char feedback[LEN+1];
} Guess;

char** getValidWords(int* numWordPtr);

char* feedback(char* guess, char* correct);
void init(int arr[], int size, int val);
void initString(char arr[], int size, char ch);

Entry* makeEntry(char* word);
int consistent(char* word, Guess guesses[], int numGuesses);
void print(Entry* ptr);

// Functions to support heap.
int compare(Entry* ptr1, Entry* ptr2);
HeapStruct* makeHeapFromArray(Entry** words, int len);
void swap(Entry** ptr1, Entry** ptr2);
void heapify(HeapStruct* heapPtr);
void percolateUp(HeapStruct* heapPtr, int idx);
void percolateDown(HeapStruct* heapPtr, int idx);
Entry* deleteMin(HeapStruct* heapPtr);

int main() {

    // Read in the dictionary of words.
    int numWords;
    char** wordlist = getValidWords(&numWords);

    // Read in the feedback.
    int numFeed;
    scanf("%d", &numFeed);
    Guess guesses[MAXGUESSES];
    for (int i=0; i<numFeed; i++)
        scanf("%s%s", guesses[i].word, guesses[i].feedback);

    // First store the consistent guesses here. We'll resize later.
    Entry** viable = calloc(numWords, sizeof(Entry*));

    // Index into consistent.
    int idx = 0;

    // Go through each dictionary word.
    for (int i=0; i<numWords; i++)

        // Just add if it's consistent with these guesses.
        if (consistent(wordlist[i], guesses, numFeed))
            viable[idx++] = makeEntry(wordlist[i]);

    // Resize so we're the right space.
    viable = realloc(viable, idx*sizeof(Entry*));

    // Make the heap.
    HeapStruct* mine = makeHeapFromArray(viable, idx);

    // We can just print as soon as we extract, effectively sorting as we print.
    for (int i=0; i<idx; i++) {
        Entry* tmp = deleteMin(mine);
        printf("%d %s\n", tmp->score, tmp->word);
        free(tmp);
    }

    // Special case.
    if (idx == 0)
        printf("No candidates found.\n");

    // Clean up.
    free(mine->heaparray);
    free(mine);
    free(viable);
    for (int i=0; i<numWords; i++)
        free(wordlist[i]);
    free(wordlist);

    return 0;
}

// Read in the number of words into the int pointed to by numWordPtr and return a pointer to the array of
// strings storing those words.
char** getValidWords(int* numWordPtr) {

    // Read in the number of words.
    scanf("%d", numWordPtr);

    // Allocate pointers for each word.
    char** res = calloc(*numWordPtr, sizeof(char*));

    // Read the words.
    for (int i=0; i<(*numWordPtr); i++) {

        // Allocate space and read in the word.
        res[i] = calloc( (LEN+1), sizeof(char));
        scanf("%s", res[i]);
    }

    // Return the array.
    return res;
}

// Pre-condition: guess and correct are strings of lowercase letters of the same length.
// Post-condition: Returns the Wordle Feedback for guess assuming that the correct
//                 solution is correct.
char* feedback(char* guess, char* correct) {

    // Set up return string.
    char* res = calloc(LEN+1, sizeof(char));
    initString(res, LEN, 'B');

    // Set up used arrays.
    int usedGuess[LEN];
    int usedSol[LEN];
    init(usedGuess, LEN, 0);
    init(usedSol, LEN, 0);

    // Step one: mark green (could be a function but I was lazy)
    for (int i=0; i<LEN; i++) {
        if (guess[i] == correct[i]) {
            usedGuess[i] = 1;
            usedSol[i] = 1;
            res[i] = 'G';
        }
    }

    // Step two: mark yellow left to right.
    // i = index into guess, j = index int correct
    for (int i=0; i<LEN; i++) {

        // Skip these.
        if (usedGuess[i]) continue;

        for (int j=0; j<LEN; j++) {

            // These aren't allowed.
            if (usedSol[j]) continue;

            // Matching yellow.
            if (guess[i] == correct[j]) {
                usedGuess[i] = 1;
                usedSol[j] = 1;
                res[i] = 'Y';

                // This is critical to get out!!!
                break;
            }
        }
    }

    // We're good now.
    return res;
}

// Initializes arr[0..size-1] to val.
void init(int arr[], int size, int val) {
    for (int i=0; i<size; i++)
        arr[i] = val;
}

// Initializes arr to be a valid C strings with size copies of the character ch,
// null terminated.
void initString(char arr[], int size, char ch) {
    for (int i=0; i<size; i++)
        arr[i] = ch;
    arr[size] = '\0';
}

// Returns the corresponding entry for this word.
Entry* makeEntry(char* word) {

    // Create the struct and copy in the word.
    Entry* res = malloc(sizeof(Entry));
    strcpy(res->word, word);

    // Add up the score.
    res->score = 0;
    int len = strlen(word);
    for (int i=0; i<len; i++)
        res->score += freq[word[i]-'a'];

    // Return it!
    return res;
}

// Returns 1 iff word is consistent with every Guess struct
int consistent(char* word, Guess guesses[], int numGuesses) {

    // Go through each guess.
    for (int i=0; i<numGuesses; i++) {

        // Get the feedback this guess WOULD receive if word was correct.
        char* tmpFeed = feedback(guesses[i].word, word);

        // If the two strings aren't equal then this is a no go.
        if (strcmp(tmpFeed, guesses[i].feedback))
            return 0;
    }

    // If we make it here we are consistent.
    return 1;
}

// Returns a negative integer if the entry pointed to by ptr1 should come before
// the one pointed to by ptr2, 0 if equal, or a positive integer otherwise.
int compare(Entry* ptr1, Entry* ptr2) {

    // We need to sort from most points to least points.
    if (ptr1->score != ptr2->score)
        return ptr2->score - ptr1->score;

    // Otherwise, just regular alpha order.
    return strcmp(ptr1->word, ptr2->word);
}

// Prints the entry pointed to by ptr.
void print(Entry* ptr) {
    printf("%d %s\n", ptr->score, ptr->word);
}

/*** Heap Functions Below ***/

// Pre-condition: words is of length len storing pointers to Entry, starting at index 0.
// Post-condition: A pointer to a heap is returned storing these items.
HeapStruct* makeHeapFromArray(Entry** words, int len) {

    // Allocate space set up parameters.
    HeapStruct* res = malloc(sizeof(HeapStruct));
    res->heaparray = calloc(len+1, sizeof(Entry*));
    res->capacity = len;
    res->size = len;

    // We're doing the heap array indexing starting at 1.
    for (int i=0; i<len; i++)
        res->heaparray[i+1] = words[i];

    // Run heapify.
    heapify(res);

    // Now we are good.
    return res;
}

// Runs percolate up on the heap pointed to by heapPtr on index idx.
void percolateUp(HeapStruct* heapPtr, int idx) {

    // We're done.
    if (idx == 1) return;

    // If we beat our parent, then we swap and recurse, otherwise nothing.
    if (compare(heapPtr->heaparray[idx], heapPtr->heaparray[idx/2]) < 0) {
        swap(&heapPtr->heaparray[idx], &heapPtr->heaparray[idx/2]);
        percolateUp(heapPtr, idx/2);
    }
}

// Swaps where ptr1 and ptr2 point.
void swap(Entry** ptr1, Entry** ptr2) {
    Entry* tmp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = tmp;
}

// Runs percolate up on the heap pointed to by heapPtr on index idx.
void percolateDown(HeapStruct* heapPtr, int idx) {

   // printf("size is %d, idx is %d\n\n", heapPtr->size, idx);

    // We're done.
    if (2*idx > heapPtr->size) return;

    // Take care of this case separately.
    if (2*idx == heapPtr->size) {

        // Only swap if this is true.
        if (compare(heapPtr->heaparray[idx], heapPtr->heaparray[2*idx]) > 0)
            swap(&heapPtr->heaparray[idx], &heapPtr->heaparray[2*idx]);

        // We are done now.
        return;
    }

    // Do the comparison of the children.
    int cmp = compare(heapPtr->heaparray[2*idx], heapPtr->heaparray[2*idx+1]);

    // Index we might swap with.
    int nextIdx = cmp < 0 ? 2*idx : 2*idx+1;

    // If we lose to this child, we swap and recurse, otherwise nothing.
    if (compare(heapPtr->heaparray[idx], heapPtr->heaparray[nextIdx]) > 0) {
        swap(&heapPtr->heaparray[idx], &heapPtr->heaparray[nextIdx]);
        percolateDown(heapPtr, nextIdx);
    }
}

// Just run heapify on each item with children in reverse index order.
void heapify(HeapStruct* heapPtr) {
    for (int i=heapPtr->size/2; i>=1; i--)
        percolateDown(heapPtr, i);
}

// Deletes and returns the minimum value (first) from the heap pointed to by heapPtr.
Entry* deleteMin(HeapStruct* heapPtr) {

    // This is what we want to return.
    Entry* retval = heapPtr->heaparray[1];

    // Copy in the mailboy.
    heapPtr->heaparray[1] = heapPtr->heaparray[heapPtr->size];
    heapPtr->size--;

    // Just run percolate down here.
    percolateDown(heapPtr, 1);

    // Needs to be returned.
    return retval;
}