wordle/solver/src/greedy.ts

/**
 * Greedy position-masking Wordle solver.
 * Strategy: strictly respect known greens (lock positions).
 * For yellows, test words that have the letter in different positions.
 * For grays, eliminate words containing that letter.
 *
 * Simpler than entropy — models how many humans actually play.
 */

function getFeedback(target: string, guess: string): string {
  const tu = target.toLowerCase();
  const gu = guess.toLowerCase();
  const counts: Record<string, number> = {};
  for (const ch of tu) counts[ch] = (counts[ch] ?? 0) + 1;
  const result: string[] = Array(5).fill('x');
  for (let i = 0; i < 5; i++) {
    if (gu[i] === tu[i]) { result[i] = 'g'; counts[gu[i]]--; }
  }
  for (let i = 0; i < 5; i++) {
    if (result[i] === 'g') continue;
    if ((counts[gu[i]] ?? 0) > 0) { result[i] = 'y'; counts[gu[i]]--; }
  }
  return result.join('');
}

function matchesFeedback(candidate: string, guess: string, feedback: string): boolean {
  return getFeedback(candidate, guess) === feedback;
}

/**
 * Solve using greedy position-masking.
 * Pick any candidate — the filtering does the work.
 */
export function solveGreedy(target: string, allWords: string[], maxAttempts = 6): number {
  let candidates = [...allWords];

  // Good human-style starting word
  const starters = ['crane', 'slate', 'arise', 'stare'];
  const starter = starters.find((w) => allWords.includes(w)) ?? allWords[0];

  for (let attempt = 1; attempt <= maxAttempts; attempt++) {
    const guess = attempt === 1 ? starter : candidates[0];
    const fb = getFeedback(target, guess);

    if (fb === 'ggggg') return attempt;

    candidates = candidates.filter((c) => matchesFeedback(c, guess, fb));
    if (candidates.length === 0) return maxAttempts + 1;

    // Greedy: prefer candidates with letters in positions matching known greens
    if (attempt < maxAttempts) {
      const greenPositions: number[] = [];
      for (let i = 0; i < 5; i++) {
        if (fb[i] === 'g') greenPositions.push(i);
      }
      // Sort candidates by how many greens they match from previous feedback
      if (greenPositions.length > 0) {
        candidates.sort((a, b) => {
          let aMatch = 0, bMatch = 0;
          for (const pos of greenPositions) {
            if (a[pos] === guess[pos]) aMatch++;
            if (b[pos] === guess[pos]) bMatch++;
          }
          return bMatch - aMatch; // more matches first
        });
      }
    }
  }

  return maxAttempts + 1;
}