generate waffle puzzles

waffle.py

#!/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))

I wrote this because the wafflegame website is currently broken on mobile - the cookie dialog does not fit on screen and does not scroll.