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