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 # Definitions generally useful for the riddle solver
  17
  18 ```python
  19 import unicodedata
  20 import re
  21 from dataclasses import dataclass
  22 from typing import Dict, Tuple, List, Set
  23 from enum import Enum, auto
  24 import functools
  25 import random
  26 ```
  27
  28 ```python
  29 stop_words = set('my is in within lies and also always you will find the found'.split())
  30 negative_words = set('but not never neither nor'.split())
  31 ```
  32
  33 ```python
  34 ordinals : Dict[str, int] =  { 'last': -1
  35             , 'first': 1
  36             , 'second': 2
  37             , 'third': 3
  38             , 'fourth': 4
  39             , 'fifth': 5
  40             , 'sixth': 6
  41             , 'seventh': 7
  42             , 'eighth': 8
  43             , 'ninth': 9
  44             , 'tenth': 10
  45             , 'eleventh': 11
  46             , 'twelfth': 12
  47             }
  48
  49 reverse_ordinals : Dict[int, str] = {n: w for w, n in ordinals.items()}
  50
  51 def from_ordinal(word: str) -> int:
  52   return ordinals[word]
  53
  54 def to_ordinal(number: int) -> str:
  55   return reverse_ordinals[number]
  56 ```
  57
  58 These are the words that can be the solution to a riddle, and used as the clue for a riddle.
  59
  60 ```python
  61 dictionary : List[str] = [unicodedata.normalize('NFKD', w.strip()).\
  62                  encode('ascii', 'ignore').\
  63                  decode('utf-8')
  64               for w in open('/usr/share/dict/british-english').readlines()
  65               if w.strip().islower()
  66               if w.strip().isalpha()
  67               if len(w.strip()) >= 5
  68               if w not in stop_words
  69               if w not in negative_words
  70               if w not in ordinals
  71              ]
  72 ```
  73
  74 Some types that will be used throughout the library
  75
  76 ```python
  77 class RiddleValence(Enum):
  78   Include = auto()
  79   Exclude = auto()
  80
  81 @dataclass
  82 class RiddleClue:
  83   valence : RiddleValence
  84   word : str
  85
  86 @dataclass
  87 class RiddleElement:
  88   valence : RiddleValence
  89   letters : Set[str]
  90
  91 Riddle = Dict[int, Tuple[RiddleClue, RiddleClue]]
  92 RiddleElems =  Dict[int, RiddleElement]
  93 ```
  94
  95 ```python
  96 @functools.lru_cache
  97 def edit_distance(s: str, t: str) -> int:
  98   if s == "":
  99     return len(t)
 100   if t == "":
 101     return len(s)
 102   if s[-1] == t[-1]:
 103     cost = 0
 104   else:
 105     cost = 1
 106
 107   res = min(
 108     [ edit_distance(s[:-1], t)+1
 109     , edit_distance(s, t[:-1])+1
 110     , edit_distance(s[:-1], t[:-1]) + cost
 111     ])
 112
 113   return res
 114 ```
 115
 116 ```python
 117 def collapse_riddle_clues(elems : Dict[int, Tuple[RiddleClue, RiddleClue]]) -> RiddleElems:
 118   def combine_clues(a: RiddleClue, b: RiddleClue) -> RiddleElement:
 119     if a.valence == b.valence:
 120       if a.valence == RiddleValence.Include:
 121         return RiddleElement(letters = set(a.word) & set(b.word),
 122                              valence = RiddleValence.Include)
 123       else:
 124         return RiddleElement(letters = set(a.word) | set(b.word),
 125                              valence = RiddleValence.Exclude)
 126     else:
 127       if a.valence == RiddleValence.Include:
 128         p, q = a, b
 129       else:
 130         p, q = b, a
 131       return RiddleElement(letters = set(p.word) - set(q.word),
 132                            valence = RiddleValence.Include)
 133
 134   return {i: combine_clues(a, b) for i, (a, b) in elems.items()}
 135 ```
 136
 137 ```python
 138
 139 ```
 140
 141 ```python
 142 def matches_element(pos: int, elem: RiddleElement, word: str) -> bool:
 143   if len(word) < pos:
 144     return False
 145   if elem.valence == RiddleValence.Include:
 146     return word[pos-1] in elem.letters
 147   else:
 148     return word[pos-1] not in elem.letters
 149 ```
 150
 151 ```python
 152 def matches_all_elements(riddle: RiddleElems, word: str) -> bool:
 153   if -1 in riddle:
 154     last_elem = riddle[-1]
 155     new_riddle = {p: e for p, e in riddle.items() if p != -1}
 156     new_riddle[len(word)] = last_elem
 157   else:
 158     new_riddle = riddle
 159   return all(matches_element(i, elem, word) for i, elem in new_riddle.items())
 160 ```
 161
 162 ```python
 163 def solve_riddle(riddle: RiddleElems) -> List[str]:
 164   return [w for w in dictionary
 165           if len(w) == len(riddle)
 166           if matches_all_elements(riddle, w)]
 167 ```
 168
 169 ```python
 170
 171 ```