4
\$\begingroup\$

I have written a Wordle solver in JavaScript.

The solver generates a decision tree. For each word, it generates all possible feedbacks patterns for that word, it then selects for each pattern the word that on average, given all possible feedbacks, reduces the size of remaning words the most.

The algorithm is taken from 3Blue1Browns Solving Wordle using information theory

Almost all the cpu time is spent in calculateAndAppendBestGuessesForAllPatterns. For a given node, this function generates a list of all possible feedback patterns for that node. Then for each feedback pattern, if the list of possible remaning words is more than 2, it loops through all words in "ALL_WORDS" (which is 7680 words long) and picks the word that on average reduces the size of the list the most.

This piece of code is the critical piece as its executed so many times:

/////////////////////////////////////////
// This is where all the time is spent //
/////////////////////////////////////////
for (let word of ALL_WORDS) {
    results_for_specific_pattern_of_all_words.push({
        "word": word,
        "expected_information": expected_information(word, REMAINING_WORDS)
    });

    bar.tick();
}

Generating the entire tree takes about an hour on my pc. I would like to look 2 guesses ahead in the future, but with this speed, its not viable.

The findPossibleWords function may be the main bottleneck as its called so many times, but I havent been able to find any ways to optimize it.

Any suggestions to improve this code, especially in terms of speed, is greatly appreciated.

Program:

const fs = require('fs');
const path = require('path');
const cliProgress = require('cli-progress');


/**
 * Loads a set of words from a CSV file and returns them as an array.
 * Only words with 5 letters and containing only letters from the Danish alphabet are included.
 * @returns {string[]} An array of words.
 */
function loadWords() {
    const wordSet = new Set();
    const data = fs.readFileSync("C:\\Users\\ldeir\\OneDrive\\Desktop\\LOCALTEST\\fuldformsliste.csv", 'utf8');
    const lines = data.split(/\r?\n/);

    lines.forEach(line => {
        const [ , word ] = line.split(';');
        if (word && word.match(/^[a-zæøå]{5}$/i) && !word.match(/[' -.,é]/)) {
            wordSet.add(word.toUpperCase());
        }
    });

    return [...wordSet];
}

let ALL_WORDS = loadWords();

/**
 * Adds all permutations to a feedback node. Called with result from generateAllFeedbackPatternsOnNode.
 * @param {Object} feedbackNode - The feedback node to add permutations to.
 * @param {Array} permutations - An array of permutations to add to the feedback node.
 * 
 * @see generateAllFeedbackPatternsOnNode
 */
function addAllPermutationsToFeedbackNode(feedbackNode, permutations) {
    for (const permutation of permutations) {
        feedbackNode[permutation] = {
            "word": undefined,
            "expected_information": -13.0,
            "type": "error"
        };
    }
}

/**
 * Converts feedback object to a simply string. Example form: 'ynmnn'
 * @param {Object} feedback - The feedback object.
 * @param {Array} feedback.correctlyPlacedLetters - The array of correctly placed letters.
 * @param {Array} feedback.misplacedLetters - The array of misplaced letters.
 * @returns {string} The Wordle formatted feedback.
 * 
 * @example convertFeedbackToWordleFormat({ correctlyPlacedLetters: [{ letter: 'A', position: 1 }], misplacedLetters: [{ letter: 'B', position: 2 }], absentLetters: ['C', 'E', 'R'] }) // 'yymnn'
 */
function convertFeedbackToWordleFormat(feedback) {
    let wordleFeedback = "";
    for (let i = 0; i < 5; ++i) {
        if (feedback.correctlyPlacedLetters.find(letter => letter.position === i + 1)) {
            wordleFeedback += "y";
        } else if (feedback.misplacedLetters.find(letter => letter.position === i + 1)) {
            wordleFeedback += "m";
        } else {
            wordleFeedback += "n";
        }
    }
    return wordleFeedback;
}

const WORD_PERMUTATIONS_CACHE = {}
/**
 * Generates all possible feedback permutations for a given word.
 * @param {string} word - The word to generate feedback permutations for.
 * @returns {Array} An array of objects representing all possible feedback permutations for the given word.
 */
function generateAllFeedbackPermutations(word) {
    if (WORD_PERMUTATIONS_CACHE[word]) {
        return WORD_PERMUTATIONS_CACHE[word];
    }

    const letters = word.toUpperCase().split('');

    // Generate all permutations of statuses only once.
    const allStatusPermutations = [];
    function generateStatusPermutation(permutation) {
        if (permutation.length === letters.length) {
            allStatusPermutations.push(permutation.slice());
        } else {
            ['y', 'm', 'n'].forEach(status => {
                generateStatusPermutation(permutation.concat([status]));
            });
        }
    }
    generateStatusPermutation([]);

    // Map the status permutations to the word's letters.
    const mapPermutationToWord = (permutation) => {
        const result = {
            correctlyPlacedLetters: [],
            misplacedLetters: [],
            absentLetters: []
        };
        permutation.forEach((status, index) => {
            switch (status) {
                case 'y':
                    result.correctlyPlacedLetters.push({ letter: letters[index], position: index + 1 });
                    break;
                case 'm':
                    result.misplacedLetters.push({ letter: letters[index], position: index + 1 });
                    break;
                case 'n':
                    result.absentLetters.push(letters[index]);
                    break;
            }
        });
        return result;
    };

    // Map each status permutation to the current word.
    let res = allStatusPermutations.map(mapPermutationToWord);

    WORD_PERMUTATIONS_CACHE[word] = res;
    return res;
}

/**
 * Filters a list of words based on the guesses made by the user.
 * @param {Object} inputData - The input data containing the guesses made by the user.
 * @param {Array} all_words - The list of all possible words to filter from. Defaults to ALL_WORDS. If only a subset of words should be used, pass that subset as this parameter.
 * @returns {Array} - The list of words that match the user's guesses.
 */
function findPossibleWords(inputData, all_words = ALL_WORDS) {
    const absentLetterCounts = new Map();


for (const guess of inputData.guesses) {
    for (const absentLetter of guess.absentLetters) {
      absentLetterCounts.set(
        absentLetter,
        (absentLetterCounts.get(absentLetter) || 0) + 1
      );
    }
  }

  // Filter words based on guesses
  return all_words.filter((word) => {
    for (const guessData of inputData.guesses) {
      // Check correctly placed letters
      for (const { letter, position } of guessData.correctlyPlacedLetters) {
        if (word[position - 1] !== letter) return false;
      }
      // Check misplaced letters
      for (const { letter, position } of guessData.misplacedLetters) {
        if (word[position - 1] === letter || word.indexOf(letter) === -1)
          return false;
      }
      // Check absent letters
      for (const absentLetter of guessData.absentLetters) {
        if (word.indexOf(absentLetter) !== -1) return false;
      }
    }

    // Additional optimization for absent letters count
    for (const [letter, count] of absentLetterCounts) {
      if (word.split(letter).length - 1 > count) return false;
    }

    return true;
  });
}

/**
 * Calculates the expected information of a given word and remaining words.
 * @param {string} word - The word to calculate the expected information for.
 * @param {string[]} remainingWords - An array of remaining words to consider.
 * @returns {number} The calculated expected information.
 */
function expected_information(word, remainingWords) {
    if (remainingWords.length === 0) {
        return 0;
    }

    const permutations = generateAllFeedbackPermutations(word);

    let sum = 0;
    for (const permutation of permutations) {
        const possibleWords = findPossibleWords({ guesses: [permutation] }, remainingWords);

        if (possibleWords.length === 0) {
            continue;
        }

        const p = possibleWords.length / remainingWords.length;
        if (p > 0) {
            sum += p * Math.log2(1 / p);
        }
    }

    return sum;
}

// Simply generates the following format:
// yyyyy
// yyyyn
// yyyym
// yyymy etc.
let ALL_PATTERNS_WOORDLE_FORMAT = null;
function generateAllFeedbackPatternsOnNode() {
    if (ALL_PATTERNS_WOORDLE_FORMAT) {
        return [...ALL_PATTERNS_WOORDLE_FORMAT];
    }

    let patterns = generateAllFeedbackPermutations("SARTE"); // word does not matter
    let feedbackPatterns = [];

    for (const pattern of patterns) {
        let feedbackPattern = convertFeedbackToWordleFormat(pattern);
        feedbackPatterns.push(feedbackPattern);
    }

    ALL_PATTERNS_WOORDLE_FORMAT = feedbackPatterns;

    return [...ALL_PATTERNS_WOORDLE_FORMAT];
}

/**
 * Converts a 'ynmmm' style feedback string to a Wordle formatted feedback object.
 * @param {string} woordleFeedback - The feedback string returned by Woordle game.
 * @param {string} word - The word that was guessed.
 * @returns {object} - An object containing the guess, correctly placed letters, absent letters, and misplaced letters.
 * 
 * @see convertFeedbackToWordleFormat
 */
function convertTreeToWordleFormat(woordleFeedback, word) {
    let guessEntry = {
        "guess": word,
        "correctlyPlacedLetters": [],
        "absentLetters": [],
        "misplacedLetters": []
    }

    for (let i = 0; i < woordleFeedback.length; ++i) {
        if (woordleFeedback[i] === 'y') {
            guessEntry["correctlyPlacedLetters"].push({
                "letter": word[i],
                "position": i + 1
            });
        } else if (woordleFeedback[i] === 'm') {
            guessEntry["misplacedLetters"].push({
                "letter": word[i],
                "position": i + 1
            });
        } else {
            guessEntry["absentLetters"].push(word[i]);
        }
    }

    return guessEntry;
}

const ProgressBar = require('progress');

let bar = new ProgressBar('Calculating feedback [:bar] :current / :total :rate', {
    complete: '=',
    incomplete: ' ',
    width: 20,
    total: 10000000
});


/**
 * Calculates and appends the best guesses for all patterns on a given node.
 * @param {Object} node - The node to calculate and append the best guesses for.
 * @returns {Object} - The feedback object with the best guesses for all patterns.
 */
function calculateAndAppendBestGuessesForAllPatterns(node) {
    // Append an empty feedback to the node
    node.node["feedback"] = {};

    let guesses = {
        "guesses": []
    };

    for (const path of node.path) {
        let guessEntry = convertTreeToWordleFormat(path.pattern, path.word);
        guesses.guesses.push(guessEntry);
    }

    let ALL_PATTERNS_JSON_FORMAT = generateAllFeedbackPatternsOnNode();

    let feedback = node.node["feedback"];

    addAllPermutationsToFeedbackNode(feedback, ALL_PATTERNS_JSON_FORMAT);

    for (let i = ALL_PATTERNS_JSON_FORMAT.length - 1; i >= 0; --i) {
        let results_for_specific_pattern_of_all_words = [];

        const CURRENT_PATTERN = ALL_PATTERNS_JSON_FORMAT[i];

        let CURRENT_GUESS_PERMUTATION_WITH_WORD = convertTreeToWordleFormat(CURRENT_PATTERN, node.node.word);
        guesses.guesses.push(CURRENT_GUESS_PERMUTATION_WITH_WORD);

        const REMAINING_WORDS = findPossibleWords({ guesses: guesses.guesses });

        if (REMAINING_WORDS.length === 0) {
            delete feedback[CURRENT_PATTERN];
        } else if (REMAINING_WORDS.length === 1) {
            feedback[CURRENT_PATTERN]["word"] = REMAINING_WORDS[0];
            feedback[CURRENT_PATTERN]["expected_information"] = 0.0;
            feedback[CURRENT_PATTERN]["type"] = "leaf";
        } else if (REMAINING_WORDS.length < 3) { 
            feedback[CURRENT_PATTERN]["word"] = REMAINING_WORDS[0];
            feedback[CURRENT_PATTERN]["expected_information"] = 1;
            feedback[CURRENT_PATTERN]["type"] = "node";
        } else {
            /////////////////////////////////////////
            // This is where all the time is spent //
            /////////////////////////////////////////
            for (let word of ALL_WORDS) {
                results_for_specific_pattern_of_all_words.push({
                    "word": word,
                    "expected_information": expected_information(word, REMAINING_WORDS)
                });

                bar.tick();
            }

            results_for_specific_pattern_of_all_words.sort((a, b) => b.expected_information - a.expected_information);

            const BEST_WORD = results_for_specific_pattern_of_all_words[0].word;
            const BEST_EXPECTED_INFO = results_for_specific_pattern_of_all_words[0].expected_information;

            feedback[CURRENT_PATTERN]["word"] = BEST_WORD;
            feedback[CURRENT_PATTERN]["expected_information"] = BEST_EXPECTED_INFO;
            feedback[CURRENT_PATTERN]["type"] = "node";
        }

        guesses.guesses.pop();
        if (i > 1) {
            break;
        }
    }

    return feedback;
}

/**
 * Finds all nodes matching a given predicate in breadth-first search order, along with their paths.
 * @param {Object} jsonObj - The JSON object to search.
 * @param {Function} predicate - The predicate function to use for matching nodes.
 * @param {number} [maxDepth=-1] - The maximum depth to search. If set to -1, there is no maximum depth.
 * @returns {Array} - An array of objects containing the matching nodes and their paths.
 */
function findAllNodesMatchingPredicateInBSFOrderWithPath(jsonObj, predicate, maxDepth = -1) {
    const queue = [{ node: jsonObj, depth: 0, path: [] }];
    const found = [];

    while (queue.length > 0) {
        const { node, depth, path } = queue.shift();

        if (depth > maxDepth && maxDepth !== -1) continue;

        if (predicate(node)) {
            found.push({ node, path });
        }

        for (let key in node.feedback) {
            queue.push({
                node: node.feedback[key],
                depth: depth + 1,
                path: [...path, { word: node.word, pattern: key }]
            });
        }
    }

    return found;
}

const jsonObj = JSON.parse(fs.readFileSync('C:\\Users\\ldeir\\OneDrive\\Desktop\\LOCALTEST\\initial_tree.json', 'utf8'));

function generate() {
    for (let depth = 0; depth < 6; ++depth) {
        let nodesToGenerateFeedbackFor = findAllNodesMatchingPredicateInBSFOrderWithPath(jsonObj, node => node.type === 'node' && (!node.feedback || Object.keys(node.feedback).length === 0), depth);

        let i = 0;
        for (const node of nodesToGenerateFeedbackFor) {
            calculateAndAppendBestGuessesForAllPatterns(node);
            ++i;
        }

        fs.writeFileSync('C:\\Users\\ldeir\\OneDrive\\Desktop\\LOCALTEST\\tree.json', JSON.stringify(jsonObj), 'utf8');
    }
}

generate();

// Initial speed 36

initial_tree.json

{
    "word": "SARTE",
    "expected_information": 6.153120935094769,
    "type": "node"
}

I am not allowed to share fuldformsliste.csv, but ALL_WORDS will contain something like:

let ALL_WORDS = [
    'ABBED',
    'ABENS',
    'ABERS',
    'ABEDE',
    'ABORT',
    'ACCES',
    7680 entries total
]
\$\endgroup\$
2
  • \$\begingroup\$ Here's a gist with all the words that Wordle accepts as valid: gist.github.com/dracos/dd0668f281e685bad51479e5acaadb93 -- This list is public, not sure why you can't share it. Also, the list of possible answers is much smaller (no plurals, no obscure words, etc), using the shorter list is probably advantageous. Finally, the Wordle Bot (requires NYT subscription) analyzes a played game, including offering the best choice at each step and a score for each possible choice, within a second. \$\endgroup\$ Nov 17, 2023 at 21:54
  • \$\begingroup\$ I am creating a tree for the Danish version of woordle. Ie. Using Danish 5 letter words. The reason I can't share the list is because it's under a license. The algorithm will work with any list though. \$\endgroup\$
    – Cortex
    Nov 18, 2023 at 7:19

0

Browse other questions tagged or ask your own question.