riddle_definitions.md

   1 ---
   2 jupyter:
   3   jupytext:
   4     formats: ipynb,md,py:percent
   5     text_representation:
   6       extension: .md
   7       format_name: markdown
   8       format_version: '1.3'
   9       jupytext_version: 1.15.0
  10   kernelspec:
  11     display_name: Python 3 (ipykernel)
  12     language: python
  13     name: python3
  14 ---
  15
  16 # Definitions generally useful for the riddle solver
  17
  18 While this file is here as a Markdown file, it's intended that Jupytext will save this file as a "percent" Python file, so that it can be imported by other notebooks here.
  19
  20 ```python
  21 import unicodedata
  22 import re
  23 from dataclasses import dataclass
  24 from typing import Dict, Tuple, List, Set
  25 from enum import Enum, auto
  26 import functools
  27 import random
  28 ```
  29
  30 ```python
  31 stop_words = set('my is in within lies and also always you will find the found but'.split())
  32 negative_words = set('not never neither nor'.split())
  33 ```
  34
  35 ```python
  36 ordinals : Dict[str, int] =  { 'last': -1
  37             , 'first': 1
  38             , 'second': 2
  39             , 'third': 3
  40             , 'fourth': 4
  41             , 'fifth': 5
  42             , 'sixth': 6
  43             , 'seventh': 7
  44             , 'eighth': 8
  45             , 'ninth': 9
  46             , 'tenth': 10
  47             , 'eleventh': 11
  48             , 'twelfth': 12
  49             }
  50
  51 reverse_ordinals : Dict[int, str] = {n: w for w, n in ordinals.items()}
  52
  53 def from_ordinal(word: str) -> int:
  54   return ordinals[word]
  55
  56 def to_ordinal(number: int) -> str:
  57   return reverse_ordinals[number]
  58 ```
  59
  60 These are the words that can be the solution to a riddle, and used as the clue for a riddle.
  61
  62 ```python
  63 dictionary : List[str] = [unicodedata.normalize('NFKD', w.strip()).\
  64                  encode('ascii', 'ignore').\
  65                  decode('utf-8')
  66               for w in open('/usr/share/dict/british-english').readlines()
  67               if w.strip().islower()
  68               if w.strip().isalpha()
  69               if len(w.strip()) >= 5
  70               if len(w.strip()) <= 12
  71               if w not in stop_words
  72               if w not in negative_words
  73               if w not in ordinals
  74              ]
  75 ```
  76
  77 Some types that will be used throughout the library
  78
  79 ```python
  80 class RiddleValence(Enum):
  81   """Does this part of the riddle include or exclude letters?"""
  82   Include = auto()
  83   Exclude = auto()
  84
  85 @dataclass
  86 class RiddleClue:
  87   """A half line of a riddle, like 'is in dreams' or 'not in octet'"""
  88   valence : RiddleValence
  89   word : str
  90
  91 @dataclass
  92 class RiddleElement:
  93   """A representation of the constraints that come from a whole line of
  94   a riddle"""
  95   valence : RiddleValence
  96   letters : Set[str]
  97
  98 # A riddle that's been read and parsed.
  99 # Note that the numbering is one-based, as per the numbers in the riddle text
 100 Riddle = Dict[int, Tuple[RiddleClue, RiddleClue]]
 101
 102 # A riddle that's been processed ready for solving
 103 # Note that the numbering is one-based, as per the numbers in the riddle text
 104 RiddleElems =  Dict[int, RiddleElement]
 105 ```
 106
 107 ```python
 108 @functools.lru_cache
 109 def edit_distance(s: str, t: str) -> int:
 110   if s == "":
 111     return len(t)
 112   if t == "":
 113     return len(s)
 114   if s[0] == t[0]:
 115     cost = 0
 116   else:
 117     cost = 1
 118
 119   res = min(
 120     [ edit_distance(s[1:], t) + 1
 121     , edit_distance(s, t[1:]) + 1
 122     , edit_distance(s[1:], t[1:]) + cost
 123     ])
 124
 125   return res
 126 ```
 127
 128 ```python
 129 dictionary_neighbours = {
 130   w: [o for o in dictionary
 131       if edit_distance(w, o) <= 5
 132       if not set(w) <= set(o)
 133       if not set(o) <= set(w)]
 134   for w in dictionary}
 135
 136 dictionary_neighbours = {w: ns
 137                          for w, ns in dictionary_neighbours.items()
 138                          if ns}
 139 ```
 140
 141 ```python
 142 def collapse_riddle_clues(elems : Riddle) -> RiddleElems:
 143   """Combine the two parts of a riddle line into one element for solving.
 144   This takes account of the valence of the two parts."""
 145   def combine_clues(a: RiddleClue, b: RiddleClue) -> RiddleElement:
 146     if a.valence == b.valence:
 147       if a.valence == RiddleValence.Include:
 148         return RiddleElement(letters = set(a.word) & set(b.word),
 149                              valence = RiddleValence.Include)
 150       else:
 151         return RiddleElement(letters = set(a.word) | set(b.word),
 152                              valence = RiddleValence.Exclude)
 153     else:
 154       if a.valence == RiddleValence.Include:
 155         p, q = a, b
 156       else:
 157         p, q = b, a
 158       return RiddleElement(letters = set(p.word) - set(q.word),
 159                            valence = RiddleValence.Include)
 160
 161   return {i: combine_clues(a, b) for i, (a, b) in elems.items()}
 162 ```
 163
 164 ```python
 165 def matches_element(pos: int, elem: RiddleElement, word: str) -> bool:
 166   """Does this element match this position of the the word?
 167   Note that positions are one-based, as in the numbering system of the
 168   puzzle."""
 169   if len(word) < pos:
 170     return False
 171   if elem.valence == RiddleValence.Include:
 172     return word[pos-1] in elem.letters
 173   else:
 174     return word[pos-1] not in elem.letters
 175 ```
 176
 177 ```python
 178 def matches_all_elements(riddle: RiddleElems, word: str) -> bool:
 179   """Do all the elements of a riddle match the appropriate parts of a word?"""
 180   if -1 in riddle:
 181     last_elem = riddle[-1]
 182     new_riddle = {p: e for p, e in riddle.items() if p != -1}
 183     new_riddle[len(word)] = last_elem
 184   else:
 185     new_riddle = riddle
 186   return all(matches_element(i, elem, word) for i, elem in new_riddle.items())
 187 ```
 188
 189 ```python
 190 def solve_riddle(riddle: RiddleElems) -> List[str]:
 191   """Find all words that match this riddle"""
 192   return [w for w in dictionary
 193           if len(w) == len(riddle)
 194           if matches_all_elements(riddle, w)]
 195 ```
 196
 197 ```python
 198
 199 ```