Prove adversarial wordle has no 3-move solutions, based on work by zwegner

anti_wordle2.py

# A shorter version of zwegner's https://gist.github.com/zwegner/508cc183ab94dd27686a40384783ca4e

# Proof of optimality of 4-move solution to adversarial Wordle
# https://qntm.org/files/wordle/index.html
import collections

with open("wordle-words.txt") as f:
    normal_words = [word.strip() for word in f]

with open("wordle-fake-words.txt") as f:
    all_words = [word.strip() for word in f] + normal_words

# Get the colors for guessing the word <a> if the real word is guess <b>, as a
# 10-bit mask (5 green 5 yellow). Note that we only give as many yellow clues
# as there are matching letters (so guessing 'aabaa' against 'start' gives Y----)
def get_color_mask(a, b):
    g = y = 0
    c = collections.Counter(b)
    for i in range(5):
        if b[i] == a[i]:
            g |= 1 << i
            c[a[i]] -= 1
    for i in range(5):
        if b[i] != a[i] and c[a[i]] > 0:
            c[a[i]] -= 1
            y |= 1 << i
    return g << 5 | y


def full_search():
    # each guess splits the solution space `normal_words` into one or more
    # equivalence classes.
    # `maximum_num_equivalence_classes` tracks the largest number of
    # classes that any guess splits the space into. This is also the best
    # we can do on our second guess.
    maximum_num_equivalence_classes = 0
    # `minimax_equivalence_class_size` tracks the minimum (among all guesses)
    # size of the largest equivalent class for each guess (i.e. the number of
    # remaining candidates that Absurdle will leave us with)
    minimax_equivalence_class_size = float("inf")
    for guess in all_words:
        c = collections.Counter()
        for target in normal_words:
            s = get_color_mask(guess, target)
            c[s] += 1
        num_equivalence_classes = len(c)
        [(_, maximum_equivalence_class_size)] = c.most_common(1)
        if num_equivalence_classes > maximum_num_equivalence_classes:
            maximum_num_equivalence_classes = num_equivalence_classes
            print(
                f"Guessing '{guess}' splits the solution space into {num_equivalence_classes} equivalence classes."
            )
        if maximum_equivalence_class_size < minimax_equivalence_class_size:
            minimax_equivalence_class_size = maximum_equivalence_class_size
            print(
                f"Guessing '{guess}' leaves a largest equivalence class of size {maximum_equivalence_class_size}"
            )

    if maximum_num_equivalence_classes < minimax_equivalence_class_size:
        print(
            f"On the second guess, we can split the solution space into at most {maximum_num_equivalence_classes} equivalence classes, but the smallest maximum equivalence class among all words is of size {minimax_equivalence_class_size}"
        )


full_search()

Oh @genos I was more concerned that there would be a negative impact on performance: the a[i] in b code looked like code that someone might add to have an early return because defaultdict access was slower than searching for string membership (but it wasn't the case).