Created
April 23, 2024 09:59
-
-
Save bazzargh/5551151dab75fe5e669f1017a20013c6 to your computer and use it in GitHub Desktop.
generate waffle puzzles
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
import fileinput | |
import random | |
# words contains the 5 letter wordle solution list | |
with fileinput.input(files=("words")) as f: | |
words = [line.strip() for line in f] | |
crossref = dict() | |
for word in words: | |
key = f"{word[0]}{word[2]}{word[4]}" | |
matches = crossref.setdefault(key, []) | |
matches.append(word) | |
# for generating boards, count the number of letters that | |
# should match but don't. | |
def board_score(waffle): | |
need = [[None]*3 for _ in range(0, 6)] | |
score = [0 for _ in range(0, 6)] | |
for i in range(3): | |
for j in range(3): | |
need[i][j] = waffle[3+j][2*i] | |
need[3+j][i] = waffle[i][2*j] | |
if waffle[i][2*j] != waffle[3+j][2*i]: | |
score[i] += 1 | |
score[3+j] += 1 | |
return score, need | |
# generate the solution by picking random words from the list then repairing | |
# the worst errors - similar to https://en.wikipedia.org/wiki/Min-conflicts_algorithm | |
# it does backtrack a little but finds solutions quickly so I didn't polish it further | |
def generate_board(words, crossref): | |
waffle = random.choices(words, k=6) | |
while True: | |
score, need = board_score(waffle) | |
if sum(score) == 0: | |
return [(waffle[i//2] if i%2==0 else ''.join([(waffle[3+(j//2)][i] if j%2==0 else ' ') for j in range(5)])) for i in range(5)] | |
pos = score.index(max(score)) | |
# try to improve the worst candidate | |
m = "".join(need[pos]) | |
candidates = crossref.get(m, []) | |
if candidates: | |
waffle[pos] = random.choice(candidates) | |
else: | |
# no candidates: reset | |
waffle = random.choices(words, k=6) | |
# we want to find a shuffle of the board that takes at least 10 swaps. | |
# selection sort takes the minimum number of swaps to sort a list; | |
# therefore we can generate a shuffle by driving selection sort in reverse. | |
# We pick 10 candidate letters that will be swapped, then starting with the | |
# lexically last of these, swap it with any swappable positions that contain | |
# a lexically higher letter where the position we're swapping to did not originally | |
# contain that same letter. | |
def shuffle_board(waffle): | |
swappable = sorted([(waffle[i][j],i,j) for i in range(5) for j in range(5) if i!=j and i+j!=4]) | |
orig = swappable[:] | |
moved = list(reversed(sorted(random.sample(range(len(swappable) - 1), k=10)))) | |
shuffled = [list(k) for k in waffle] | |
for p in moved: | |
ok = False | |
attempts = 0 | |
while not ok: | |
if attempts > 10: | |
raise Exception("No shuffle found in 10 attempts") | |
attempts += 1 | |
q = random.randrange(p + 1, 16) | |
ok = swappable[p][0] != swappable[q][0] and swappable[p][0] != orig[q][0] | |
temp = swappable[q] | |
swappable[q] = swappable[p] | |
swappable[p] = temp | |
shuffled[orig[p][1]][orig[p][2]] = swappable[p][0] | |
shuffled[orig[q][1]][orig[q][2]] = swappable[q][0] | |
shuffled = [''.join(k) for k in shuffled] | |
return shuffled | |
while True: | |
try: | |
board = generate_board(words, crossref) | |
shuffled = shuffle_board(board) | |
except: | |
continue | |
break | |
print("Puzzle:") | |
print('\n'.join(shuffled)) | |
print() | |
print("Solution:") | |
print('\n'.join(board)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I wrote this because the wafflegame website is currently broken on mobile - the cookie dialog does not fit on screen and does not scroll.