vtjeng/anti_wordle2.py

## 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()
	# 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()