Hangman Bot built with performance in mind

I’m working on a bot that can use a wordlist to play hangman optimally as fast as possible. With the current implementation, the simulateGame function, which plays a whole game against the bot, takes ~500-700 microseconds to execute for the words I’ve tested, like "fatherhood", "esoteric", "joyousnesses", etc.

Wordlist can be found here, and the SIMDStarterKit.h header can be found here.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <strings.h>
#include <sys/time.h>

#include "SIMDStarterKit.h"

typedef struct {
    char **buffer;
    int length;
    int capacity;
} StringArray;

StringArray newStringArray() {
    StringArray array;
    array.buffer = malloc(sizeof(char **));
    array.length = 0;
    array.capacity = 1;
    return array;
}

void appendToStringArray(StringArray *array, char *string) {
    if (array->length == array->capacity) {
        int newCapacity = array->capacity * 2;
        array->buffer = realloc(array->buffer, sizeof(char **) * newCapacity);
        array->capacity = newCapacity;
    }
    
    array->buffer[array->length++] = string;
}

typedef struct {
    StringArray *arrays;
    int *lengths;
} IndexedWordlist;

IndexedWordlist indexWordlist(StringArray wordlist) {
    int minLength = INT_MAX;
    int maxLength = INT_MIN;
    for (int i = 0; i < wordlist.length; i++) {
        int len = (int) strlen(wordlist.buffer[i]);
        if (len > maxLength)
            maxLength = len;
        else if (len < minLength)
            minLength = len;
    }
    
    int lists = (maxLength - minLength) + 1;
    StringArray *wordlists = malloc(sizeof(StringArray) * lists);
    for (int i = 0; i < lists; i++)
        wordlists[i] = newStringArray();
    for (int i = 0; i < wordlist.length; i++) {
        int len = (int) strlen(wordlist.buffer[i]);
        int lenIdx = len - minLength;
        appendToStringArray(wordlists + lenIdx, wordlist.buffer[i]);
    }
    
    IndexedWordlist indexedWordlist;
    indexedWordlist.arrays = wordlists;
    indexedWordlist.lengths = malloc(sizeof(int) * lists);
    for (int i = 0; i < lists; i++) {
        indexedWordlist.lengths[i] = i + minLength;
    }
    
    return indexedWordlist;
}

char mostLikelyCharacter(char *query, char *noCount, char *forbidden, StringArray wordlist) {
    int len = (int) strlen(query);
    int *globalCounts = aligned_alloc(MEMORY_ALIGNMENT, 128 * sizeof(int));
    int *localCounts = aligned_alloc(MEMORY_ALIGNMENT, 128 * sizeof(int));
    long *largeLocalCounts = (long *) localCounts;
    for (int i = 0; i < 128; i++) {
        globalCounts[i] = 0;
        localCounts[i] = 0;
    }
    for (int i = 0; i < wordlist.length; i++) {
        char *string = wordlist.buffer[i];
        for (int j = 0; j < len; j++) {
            char predCharacter = string[j];
            char realCharacter = query[j];
            if (realCharacter == '_') {
                if (forbidden[predCharacter] == 1)
                    goto forbiddenWord;
            } else {
                if (predCharacter != realCharacter)
                    goto forbiddenWord;
            }
            if (noCount[predCharacter] == 1)
                goto skipCount;
            localCounts[predCharacter] += 1;
        skipCount:;
        }
        for (int j = 0; j < 128; j += VECTOR_SIZE) {
            SIMDi global = Load(&globalCounts[j]);
            SIMDi local = Load(&localCounts[j]);
            SIMDi added = Add(global, local);
            Store(globalCounts + j, added);
        }
    forbiddenWord:
        for (int j = 0; j < 128 / 2; j++)
            largeLocalCounts[j] = 0;
    }
    char bestCharacter = '';
    int bestCount = 0;
    for (int i = 0; i < 128; i++) {
        if (globalCounts[i] > bestCount) {
            bestCount = globalCounts[i];
            bestCharacter = (char) i;
        }
    }
    free(globalCounts);
    free(localCounts);
    return bestCharacter;
}

char *fgetsCopy(char *src) {
    int len = (int) strlen(src);
    char *newBuffer = malloc(sizeof(char) * len);
    memcpy(newBuffer, src, len - 1);
    newBuffer[len - 1] = '';
    return newBuffer;
}

StringArray loadWordlist() {
    FILE* file = fopen("/Users/tanmaybakshi/wordlist.txt", "r");
    char line[256];
    StringArray words = newStringArray();
    while (fgets(line, sizeof(line), file)) {
        appendToStringArray(&words, fgetsCopy(line));
    }
    return words;
}

char stringsEqual(char *a, char *b) {
    for (int i = 0; i < strlen(a); i++)
        if (a[i] != b[i])
            return 0;
    return 1;
}

void simulateGame(char *word, IndexedWordlist indexedWordlist) {
    int i = 0;
    StringArray wordlist;
    while (1) {
        if (indexedWordlist.lengths[i] == strlen(word)) {
            wordlist = indexedWordlist.arrays[i];
            break;
        }
        i++;
    }
    
    char *forbidden = calloc(128, sizeof(char));
    char *noCount = calloc(128, sizeof(char));
    char *query = malloc(sizeof(char) * strlen(word) + 1);
    for (int i = 0; i < strlen(word); i++)
        query[i] = '_';
    query[strlen(word)] = '';
    
    while (stringsEqual(query, word) == 0) {
        char result = mostLikelyCharacter(query, noCount, forbidden, wordlist);
        char correct = 0;
        for (int i = 0; i < strlen(word); i++) {
            if (word[i] == result) {
                correct = 1;
                query[i] = result;
            }
        }
        if (correct == 0) {
            printf("Incorrect response! (%.1s)n", &result);
            forbidden[result] = 1;
        } else {
            printf("Correct response! (%.1s)n", &result);
            printf("%sn", query);
            noCount[result] = 1;
        }
    }
    
    free(forbidden);
    free(noCount);
    free(query);
}

long long timems() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return (tv.tv_sec) * 1000 + (tv.tv_usec) / 1000;
}

int main() {
    StringArray wordlist = loadWordlist();
    IndexedWordlist indexedWordlist = indexWordlist(wordlist);
    long long start = timems();
    for (int i = 0; i < 5000; i++)
        simulateGame("esoteric", indexedWordlist);
    long long end = timems();
    printf("Time: %lldn", end - start);
    for (int i = 0; i < wordlist.length; i++) {
        free(wordlist.buffer[i]);
    }
    free(wordlist.buffer);
    free(indexedWordlist.lengths);
    return 0;
}