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