Generating riddles

My first is in remit but not in resins
My second is in mingles but not in gingkos
My third is in suave and also in state
My fourth is in caned and also in cored
My fifth is in saucy but not in spacey
My sixth is in carps but not in save

Solution: Teacup

In my last post, I showed now I solved puzzles of the form above. In this post, I'll show how I can generate these puzzles. (You should read the previous post for an explanation of how these riddles work.) The next post shows how to make this generation faster.

Code

Below, I describe my approach to this problem and show some Python code that solves it. You can find the full code on my Git server, or over at Gitlab. Note that I developed this with Jupyter and Jupytext, so only Markdown files are in version control. Jupyter + Jupytext will convert these into Notebook files and Python scripts when they're opened.

Random generation

The basic idea for riddle generation is simple: pick a word, then generate clues for each letter so that the combination of clues uniquely identifies the target word. The problem is with how to do that, in a way that only takes a short time and generates riddles that are "sensible."

In a riddle, each clue (line) has a pair of clue words. Human-crafted riddles tend to have clue words that are either very close in spelling or, more commonly, close in meaning. Each clue tends to suggest a few candidates for each letter in the target word. That gives me two problems to address.

1. How to balance allowing several candidates for each letter, against ensuring the whole riddle has just one solution
2. How to find suitable pairs of clue words, to give some form of coherence to the puzzle.

Ensuring unique solutions

One question that exercised me a lot was how to build puzzles with unique solutions but a range of letters for each clue. One approach was to ensure that each clue yielded just a single letter. That made the overall puzzle easy, but I wasn't satisfied with that approach. First, it limited the types of clues I could give (it would be hard to find clues of the form "is neither in X nor Y") as well as removing some of the challenge of the riddle itself.

Without a good solution coming to mind, I decided to pass the buck and get the machine to do the work. Rather than coming up with a clever solution, I decided to just generate clues somehow and check that the combination of clues would give a unique solution. If the random clue generation gave multiple solutions, I'd just try a different collection of clues.

If this worked in a reasonable time, that would be good enough. If it took too long, I'd at least have something to attempt to optimise.

Finding clue pairs

First off, looking for words based on meaning is likely to be difficult. I could use something like a pre-trained Word2Vec model to find connected words, but I don't have one of those to hand and I don't think this post is the sort of place to go through the use of one. That leaves finding words with similar letters.

One approach is to pre-compute sample pairs of clue words that will result in the candidate letters we want. However, this is expensive. If we consider just the letter 's', there are about 32,000 words that contain 's' and about 24,000 that don't. That gives over 10⁸ pairs of words to consider when pre-computing the lists. (As the clues are all about sets of letters, it's tempting to reduce the dictionary to distinct sets of letters. But that only roughly halves the size of the dictionary, leaving the pre-computed lists unfeasibly large.)

I could reduce the problem by reducing the size of the dictionary for clue words. But I didn't want to do that.

Instead, I decided that if I was generating riddles randomly, I might as well generate clues randomly too. I could just pick two clue words which, when combined, would include the desired letter as one of the possible letters.

Exploration: random generation

My first attempt at a clue-generator was for the include-exclude type clues ("My first is in remits but not in resins."). I could just pick a random word that contained 't' and a random word that didn't, and that was the clue.

def include_exclude_clue(letter: str) -> (RiddleClue, RiddleClue):
  with_letter = [w for w in dictionary if letter in w]
  without_letter = [w for w in dictionary if letter not in w]
  
  a = random.choice(with_letter)
  b = random.choice(without_letter)

  return (RiddleClue(word=a, valence=RiddleValence.Include),
          RiddleClue(word=b, valence=RiddleValence.Exclude))

Refining random generation

That worked, in that it generated clue pairs that led to the desired letter. But it didn't work in that the clue pairs used wildly different words, like "is in encountered but not in preyed" as a clue for 't'.  

Using edit distance (or Levenshtein distance) is one way to measuring the distance between words. I would pick two random clue words until their edit distance was less than some limit (I picked a distance of 3). An additional edge case that sometimes occurred was when one word's letters were a subset of the other's; this most commonly occurred when the words were the singular and plural of each other.

That meant a couple of additional tests in the function, which I placed in a loop to keep generating clue pairs until I got something that met the conditions.

def include_exclude_clue(letter: str, limit: int = 3) -> (RiddleClue, RiddleClue):
  with_letter = [w for w in dictionary if letter in w]
  without_letter = [w for w in dictionary if letter not in w]
  
  finished = False
  while not finished:
    a = random.choice(with_letter)
    b = random.choice(without_letter)
    finished = ((edit_distance(a, b) <= limit) and
                not set(a) <= set(b) and 
                not set(a) >= set(b))
  return (RiddleClue(word=a, valence=RiddleValence.Include),
          RiddleClue(word=b, valence=RiddleValence.Exclude))

Alongside this, I cribbed some code for edit distance from somewhere. It's often cited as an example where dynamic programming is useful, but I decided to memoise it with Python's built-in caching function decorator.

@functools.lru_cache
def edit_distance(s: str, t: str) -> int:
  if s == "":
    return len(t)
  if t == "":
    return len(s)
  if s[0] == t[0]:
    cost = 0
  else:
    cost = 1
       
  res = min(
    [ edit_distance(s[1:], t) + 1
    , edit_distance(s, t[1:]) + 1
    , edit_distance(s[1:], t[1:]) + cost
    ])

  return res

Different clues

With one clue type working, the others were essentially the same.

def include_include_clue(letter: str, limit: int = 3) -> (RiddleClue, RiddleClue):
  with_letter = [w for w in dictionary if letter in w]
  
  finished = False
  while not finished:
    a = random.choice(with_letter)
    b = random.choice(with_letter)
    finished = ((a != b) and 
                (edit_distance(a, b) <= limit) and
                not set(a) <= set(b) and 
                not set(a) >= set(b))
  return (RiddleClue(word=a, valence=RiddleValence.Include),
          RiddleClue(word=b, valence=RiddleValence.Include))

def exclude_exclude_clue(letter: str, limit: int = 3) -> (RiddleClue, RiddleClue):
  without_letter = [w for w in dictionary if letter not in w]
  
  finished = False
  while not finished:
    a = random.choice(without_letter)
    b = random.choice(without_letter)
    finished = ((a != b) and 
                (edit_distance(a, b) <= limit) and
                not set(a) <= set(b) and
                not set(a) >= set(b))                
  return (RiddleClue(word=a, valence=RiddleValence.Exclude),
          RiddleClue(word=b, valence=RiddleValence.Exclude))

Generating riddles

I can put these together in a function that generates a random clue (using random.choices to make a weighted random selection between the type) and from there make a random riddle (remembering to adjust for the one-based numbering of clues).

def random_clue( letter: str
               , ie_limit: int = 3
               , ii_limit: int = 2
               , ee_limit: int = 2) -> (RiddleClue, RiddleClue):
  clue_type = random.choices(['include_exclude', 'include_include', 'exclude_exclude'],
                             weights=[7, 2, 1],
                             k=1)[0]
  if clue_type == 'include_exclude':
    return include_exclude_clue(letter, limit=ie_limit)
  elif clue_type =='include_include':
    return include_include_clue(letter, limit=ii_limit)
  else:
    return exclude_exclude_clue(letter, limit=ee_limit)

def random_riddle( word: str
                 , ie_limit: int = 3
                 , ii_limit: int = 2
                 , ee_limit: int = 2
                 ) -> Riddle:
  return {i+1 : 
    random_clue(l, 
                ie_limit=ie_limit, ii_limit=ii_limit, ee_limit=ee_limit)
          for i, l in enumerate(word)} 

Unique-solution riddles

The approach above generates riddles that have the desired word as a solution. But the generated riddles can have more than one solution. Consider this riddle:

My first is neither in muses nor in mashes
My second is in gores but not in grist
My third is in angers but not in ledgers
My fourth is in ricing but not in dinning
My fifth is neither in blares nor in bakes
My last is in proofs but not in loafs

This is another riddle for "teacups", but "concur" is also a solution. That's easily solved with another cycle of generate-and-test, where I generate riddles then solve them, to ensure that the generated riddle has only one solution.

def valid_random_riddle(word: str) -> Riddle:
  finished = False
  while not finished:
    riddle = random_riddle(word)
    solns = solve_riddle(collapse_riddle_clues(riddle))
    finished = (len(solns) == 1)
  return riddle

Writing riddles

Now I can generate riddles in a sensible time, the final step is to write them in a human-readable form. This is fairly easy, as each clue type has a rigid structure for the text.

That means that each clue type has its own function for writing lines of that type.

def write_include_exclude_line(clue_a: RiddleClue, clue_b: RiddleClue) -> str:
  line = f"is in {clue_a.word} but not in {clue_b.word}"
  return line

def write_include_include_line(clue_a: RiddleClue, clue_b: RiddleClue) -> str:
  if random.randrange(2) == 0:
    line = f"is in {clue_a.word} and also in {clue_b.word}"
  else:
    line = f"is in both {clue_a.word} and {clue_b.word}"
  return line

def write_exclude_exclude_line(clue_a: RiddleClue, clue_b: RiddleClue) -> str:
  line = f"is neither in {clue_a.word} nor in {clue_b.word}"
  return line

Those get called by a function that selects the correct line function, based on the line type of the riddle.

def write_line(a: RiddleClue, b: RiddleClue) -> str:
  if a.valence == RiddleValence.Include and b.valence == RiddleValence.Include:
    return write_include_include_line(a, b)
  elif a.valence == RiddleValence.Include and b.valence == RiddleValence.Exclude:
    return write_include_exclude_line(a, b)
  elif a.valence == RiddleValence.Exclude and b.valence == RiddleValence.Exclude:
    return write_exclude_exclude_line(a, b)
  else:
    return "illegal line"

And finally, a function that writes a whole riddle, with a bit of faffing to choose between having the last line be written as either "My seventh..." or "My last...".

def write_riddle(riddle: Riddle) -> List[str]:
  output = []
  for i, (clue_a, clue_b) in sorted(riddle.items()):
    pos = reverse_ordinals[i]
    if i == len(riddle) and random.random() <= 0.3:
      pos = reverse_ordinals[-1]
    line = write_line(clue_a, clue_b)
    full_line = f"My {pos} {line}"
    output.append(full_line)
  return output  

Summary

And that's it! I can now generate as many riddles as I want and write them in a form that a person can read.

The problem is that the riddle generation is slow, taking about two seconds to generate a riddle. That's an issue I'll address in the next post.