wordle.c

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdarg.h>

#define MAX_WORDS 13000 // leave room for some tinkering
#define LENGTH 5
#define EVAL_RANGE 243 // 3^LENGTH

typedef uint8_t Eval_t;
char words[MAX_WORDS][LENGTH];
unsigned numWords;
Eval_t evalTable[MAX_WORDS][MAX_WORDS];
// evalTable[i][j] : evaluation of guessing i if j is the answer

#define RIGHT_LETTER_WRONG_PLACE  2
#define RIGHT_LETTER_RIGHT_PLACE  1
#define WRONG_LETTER              0

unsigned countOccurrences(char* word, char c) {
    unsigned n = 0;
    for(unsigned i=0;i<LENGTH;i++,word++) {
        if (*word == c)
            n++;
    }
    return n;        
}

Eval_t evaluate(char* word, char* guess) {
    uint8_t eval[LENGTH];
    for (unsigned i=0;i<LENGTH;i++) {
        char c = guess[i];
        if (word[i] == c) { 
            eval[i] = RIGHT_LETTER_RIGHT_PLACE;
        }
        else {
            eval[i] = 0;
        }
    }
    for (unsigned i=0;i<LENGTH;i++) {
        if (!eval[i]) {
            char c = guess[i];
            uint8_t count = countOccurrences(word, c);
            if (count) {
                uint8_t already = 0;
                for (uint8_t j=0;j<LENGTH;j++) {
                    if (eval[j] && guess[j] == c)
                        already++;
                }
                if (already < count) {
                    eval[i] = RIGHT_LETTER_WRONG_PLACE;
                }
            }            
        }
    }
    Eval_t e = 0;
    for (unsigned i=0;i<LENGTH;i++) {
        e = e*3 + eval[i];
    }
    return e;
}


void error(char* e, ...) {
    va_list args;
    va_start(args, e);
    vfprintf(stderr, e, args);
    fputc('\n', stderr);
    va_end(args);
    exit(1);
}

void load(void) {
    numWords = 0;
    FILE* f = fopen("full.txt", "r");
    if (f == NULL)
        error("Cannot open full.txt");
    while(numWords < MAX_WORDS) {
        char line[LENGTH+256];
        if (NULL == fgets(line, LENGTH+256, f))
            break;
        if (islower(line[0])) {
            memcpy(words[numWords],line,LENGTH);
            numWords++;
        }
    }
    printf("Loaded %d words\n", numWords);
}

void fillEvalTable(void) {
    puts("Filling eval table");
    for (unsigned i = 0 ; i < numWords ; i++) {
        for (unsigned j = 0 ; j < numWords ; j++)
            evalTable[i][j] = evaluate(words[j], words[i]);
        if (i%1000==999 || i == numWords-1) { printf("%d ",i+1); fflush(stdout); }
    }
    puts("\nEval table filled");
}

void dumpWord(unsigned i) {
    for (unsigned j = 0 ; j < LENGTH ; j++)
        putchar(words[i][j]);
}

void bestFirst(void) {
    unsigned bestI = 0;
    unsigned bestSize = numWords;
    for (unsigned i = 0 ; i < numWords ; i++) {
        uint16_t counts[EVAL_RANGE];
        memset(counts, 0, sizeof(counts));
        for (unsigned j = 0 ; j < numWords ; j++)
            counts[evalTable[i][j]]++;
        unsigned largest = 0;
        for (unsigned j = 0 ; j < EVAL_RANGE ; j++) 
            if (counts[j] > largest)
                largest = counts[j];
        if (largest < bestSize) {
            bestI = i;
            bestSize = largest;
        }
    }
    printf("%d ", bestSize);
    dumpWord(bestI);
    putchar('\n');
}

void bestPair(void) {
    unsigned bestI = 0;
    unsigned bestJ = 0;
    unsigned bestSize = numWords;
    for (unsigned i = 0 ; i < numWords ; i++) {
        if (i%100 == 0) {
            printf("%d ",i);
            fflush(stdout);
        }
        for (unsigned j = 0 ; j <= i ; j++) {
            uint32_t counts[EVAL_RANGE*EVAL_RANGE];
            memset(counts, 0, sizeof(counts));
            for (unsigned k = 0 ; k < numWords ; k++)
                counts[(unsigned)evalTable[i][k]*EVAL_RANGE+evalTable[j][k]]++;
            unsigned largest = 0;
            for (unsigned j = 0 ; j < EVAL_RANGE*EVAL_RANGE ; j++) 
                if (counts[j] > largest)
                    largest = counts[j];
            if (largest < bestSize) {
                bestI = i;
                bestJ = j;
                bestSize = largest;
            }
        }
    }
    printf("%d ", bestSize);
    dumpWord(bestI);
    putchar(' ');
    dumpWord(bestJ);
    putchar('\n');
}

int main(int argc, char** argv) {
    load();
    fillEvalTable();
    bestFirst();
    bestPair();
}