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 def collapse_riddle_clues(elems : Riddle) -> RiddleElems:
 126   """Combine the two parts of a riddle line into one element for solving.
 127   This takes account of the valence of the two parts."""
 128   def combine_clues(a: RiddleClue, b: RiddleClue) -> RiddleElement:
 129     if a.valence == b.valence:
 130       if a.valence == RiddleValence.Include:
 131         return RiddleElement(letters = set(a.word) & set(b.word),
 132                              valence = RiddleValence.Include)
 133       else:
 134         return RiddleElement(letters = set(a.word) | set(b.word),
 135                              valence = RiddleValence.Exclude)
 136     else:
 137       if a.valence == RiddleValence.Include:
 138         p, q = a, b
 139       else:
 140         p, q = b, a
 141       return RiddleElement(letters = set(p.word) - set(q.word),
 142                            valence = RiddleValence.Include)
 143
 144   return {i: combine_clues(a, b) for i, (a, b) in elems.items()}
 145 ```
 146
 147 ```python
 148 def matches_element(pos: int, elem: RiddleElement, word: str) -> bool:
 149   """Does this element match this position of the the word?
 150   Note that positions are one-based, as in the numbering system of the
 151   puzzle."""
 152   if len(word) < pos:
 153     return False
 154   if elem.valence == RiddleValence.Include:
 155     return word[pos-1] in elem.letters
 156   else:
 157     return word[pos-1] not in elem.letters
 158 ```
 159
 160 ```python
 161 def matches_all_elements(riddle: RiddleElems, word: str) -> bool:
 162   """Do all the elements of a riddle match the appropriate parts of a word?"""
 163   if -1 in riddle:
 164     last_elem = riddle[-1]
 165     new_riddle = {p: e for p, e in riddle.items() if p != -1}
 166     new_riddle[len(word)] = last_elem
 167   else:
 168     new_riddle = riddle
 169   return all(matches_element(i, elem, word) for i, elem in new_riddle.items())
 170 ```
 171
 172 ```python
 173 def solve_riddle(riddle: RiddleElems) -> List[str]:
 174   """Find all words that match this riddle"""
 175   return [w for w in dictionary
 176           if len(w) == len(riddle)
 177           if matches_all_elements(riddle, w)]
 178 ```
 179
 180 ```python
 181
 182 ```