Solving riddles

My first is in deans but not in slats
My second is in persona but not in perusing
My third is neither in veiled nor in seized
My fourth is in cleat but not in octet
My last is in curtsied but not in curbed

Solution: Earls

This is the first of a trio of posts looking at the word riddles like the one above. In this post, I'll build a solver for this type of riddle. In the next post, I'll build a tool that generates these riddles. In the third post, I'll show how to make riddle generation fast.

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.

How these riddles work

Just in case you need a reminder, the riddle defines a particular word you have to guess. Each line of the riddle gives some constraints on a particular letter in that word. The combination of the constraints should, ideally, mean there is only one word that fits.

In the example at the top of this post, the first line says that the first letter is one of d, e, or n (the letters of deans that are not also present in slats). The second line says the second letter is one of a or 0. The third line gives a bunch of letters that can't be in the third position of the word. And so on.

Overall plan

My overall plan is three steps.

Read the riddle text into some form that's easier to work with than strings of words.
Transform that parsed riddle into a form that's easy to generate solutions.
Solve the puzzle.

The idea is that work in the first two stages will produce a representation that's easy to use in a solver.

Representing riddles

As with many of these puzzles, the first step is working out how to represent the problem. (This is also my excuse to use the type hinting and checking system that recently came into Python.)

In this case, I need to think about whether a clue (or part of a clue) is about including or excluding letters. Each line of a puzzle turns into two "clues" about the letter in a particular position. The whole text is a set of these clue-pairs, indexed by position.

class RiddleValence(Enum):
  Include = auto()
  Exclude = auto()
 
@dataclass
class RiddleClue:
  valence : RiddleValence
  word : str
  
Riddle = Dict[int, Tuple[RiddleClue, RiddleClue]]

That's enough to get started with the parsing.

Parsing the riddle

This is the process of getting the text into the representation above.

If we start with a line like:

My first is in deans but not in slats

I notice that only the four words in bold ("first", "deans", "not", "slats") carry any information for the puzzle. One tells me which letter this is a clue for, one tells me the valence of the half-line, and two are the clue words themselves. I can happily drop the rest of the words.

The first step is to split the text into words. I do that with re.split to split on non-word characters.

def tokenise(phrase: str) -> List[str]:
  return [w.lower() for w in re.split(r'\W+', phrase) if w]

I then define the words I want dropped. Stop words are the general filler or functional words. Negative words are the words that show a clue is about excluding letters.

stop_words = set('my is in within lies and also always you will find the found'.split())
negative_words = set('but not never neither nor'.split())

The ordinals connect number words to numbers.

ordinals : Dict[str, int] =  { 'last': -1
            , 'first': 1
            , 'second': 2
            , 'third': 3
            , 'fourth': 4
            , 'fifth': 5
            , 'sixth': 6
            , 'seventh': 7
            , 'eighth': 8
            , 'ninth': 9
            , 'tenth': 10
            , 'eleventh': 11
            , 'twelfth': 12
            }

reverse_ordinals : Dict[int, str] = {n: w for w, n in ordinals.items()}

I can now read a line. I strip out all the stop words then identify the locations of the position word, any negatives, and what's left are the clue words.

def parse_line(tokens: List[str]) -> Tuple[int, Tuple[RiddleClue, RiddleClue]]:
  stripped_tokens = [t for t in tokens if t not in stop_words]
  
  position_word = [t for t in stripped_tokens if t in ordinals][0]
  pos = from_ordinal(position_word)
  
  indexed_words = [(i, t) for i, t in enumerate(stripped_tokens)
                            if t not in ordinals 
                            if t not in negative_words]
  
  first_index, first_word = indexed_words[0]
  second_index, second_word = indexed_words[1]
  
  neg_indices = [i for i, t in enumerate(stripped_tokens) if t in negative_words]
  
  ...

From there, I need to do some jiggery-pokery to build the two clues, taking in account any negative words that could be there. The basic logic is that if a negative word occurs before a clue word, that clue is excluding letters; otherwise, the clue is including letters. There could be zero, one, or two negative words.

The logic I end up with isn't watertight, but it's enough to deal with the stylised formatting of lines in this sort of riddle.

  ...
  
  first_clue = None
  second_clue = None
  
  if neg_indices:
    if neg_indices[0] < first_index:
      first_clue = RiddleClue(valence = RiddleValence.Exclude,
                             word = first_word)
      if len(neg_indices) > 1:
          second_clue = RiddleClue(valence = RiddleValence.Exclude,
                             word = second_word)
    elif neg_indices[0] < second_index:
      second_clue = RiddleClue(valence = RiddleValence.Exclude,
                             word = second_word)
  
  if first_clue is None:
    first_clue = RiddleClue(valence = RiddleValence.Include,
                             word = first_word)
  
  if second_clue is None:
    second_clue = RiddleClue(valence = RiddleValence.Include,
                             word = second_word)

  return (pos, (first_clue, second_clue))

That gives me something that works.

>>> parse_line(tokenise("My first is in apple, but not in pad."))
(1,
 (RiddleClue(valence=<RiddleValence.Include: 1>, word='apple'),
  RiddleClue(valence=<RiddleValence.Exclude: 2>, word='pad')))

>>> parse_line(tokenise("My second is in apple and also in banana."))
(2,
 (RiddleClue(valence=<RiddleValence.Include: 1>, word='apple'),
  RiddleClue(valence=<RiddleValence.Include: 1>, word='banana')))

>>> parse_line(tokenise('My seventh is neither in callus nor in calves'))
(7,
 (RiddleClue(valence=<RiddleValence.Exclude: 2>, word='callus'),
  RiddleClue(valence=<RiddleValence.Exclude: 2>, word='calves')))

The final stage is to convert this list of RiddleClues into a Riddle.

def parse_riddle(riddle_text: str) -> Riddle:
  return {i: elem 
          for i, elem in 
            [parse_line(tokenise(l)) 
             for l in riddle_text.split('\n')]}

Solving a riddle

The RiddleClues defined above are a good representation of the text of a riddle, but aren't the most useful for solving it. (But the are good for generating riddles, which I'll get to in the next post.) The clues tell us what's in a riddle, but not how those clues are interpreted.

The interpretation of each line in a riddle is that it defines what a particular letter in the solution could be (or could not be). For instance, the line my first is in deans but not in slats mean that the first letter is a member of the set {d, e, n}. Every line in the riddle defines one set of letters.

That suggests a new data structure to store them.

@dataclass
class RiddleElement:
  valence : RiddleValence
  letters : Set[str]

RiddleElems =  Dict[int, RiddleElement]

Now I need something that will combine the two clues on a line into a single set. There are three cases to consider, depending on the valence of the two clues.

Both clues are Include: the set is the intersection of the two words and the letter must be Included in it
Both clues are Exclude: the set is the union of the two words and the letter must be Excluded from it
The valences are different: the set is the set difference of the Include word "minus" the Exclude word.

The combine_clues function below handles these cases, and wraps them up in a comprehension to handle all the clues in a riddle.

def collapse_riddle_clues(elems : Riddle) -> RiddleElems:
  def combine_clues(a: RiddleClue, b: RiddleClue) -> RiddleElement:
    if a.valence == b.valence:
      if a.valence == RiddleValence.Include:
        return RiddleElement(letters = set(a.word) & set(b.word), 
                             valence = RiddleValence.Include)
      else:
        return RiddleElement(letters = set(a.word) | set(b.word), 
                             valence = RiddleValence.Exclude)
    else:
      if a.valence == RiddleValence.Include:
        p, q = a, b
      else:
        p, q = b, a
      return RiddleElement(letters = set(p.word) - set(q.word), 
                           valence = RiddleValence.Include)
  
  return {i: combine_clues(a, b) for i, (a, b) in elems.items()}

To solve a riddle, I go through all the words in the dictionary and check if it's consistent with the riddle; I return all the words that match.

def solve_riddle(riddle: RiddleElems) -> List[str]:
  return [w for w in dictionary 
          if len(w) == len(riddle)
          if matches_all_elements(riddle, w)]

That requires that I write the function matches_all_elements (which matches a word with a riddle) and match_one_element (which matches a letter with its corresponding element).

def matches_all_elements(riddle: RiddleElems, word: str) -> bool:
  if -1 in riddle:
    last_elem = riddle[-1]
    new_riddle = {p: e for p, e in riddle.items() if p != -1}
    new_riddle[len(word)] = last_elem
  else:
    new_riddle = riddle
  return all(matches_element(i, elem, word) for i, elem in new_riddle.items())
  
def matches_element(pos: int, elem: RiddleElement, word: str) -> bool:
  if len(word) < pos:
    return False
  if elem.valence == RiddleValence.Include:
    return word[pos-1] in elem.letters
  else:
    return word[pos-1] not in elem.letters

There's a little bit of fiddling in matches_all_elements to take account of clues of the form My last is in...

Finally, I put the three steps together in one function. This reads and parses a riddle text, collapses the clues into elements, then solves the riddle.

def parse_and_solve_riddle(riddle_text: str) -> List[str]:
  riddle = parse_riddle(riddle_text)
  elems = collapse_riddle_clues(riddle)
  return solve_riddle(elems)

And that's all that's needed to solve some riddles!

The next step is to generate my own riddles, covered in the next post.