4 formats: ipynb,md,py:percent
9 jupytext_version: 1.14.5
11 display_name: Python 3 (ipykernel)
16 # Definitions generally useful for the riddle solver
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.
23 from dataclasses import dataclass
24 from typing import Dict, Tuple, List, Set
25 from enum import Enum, auto
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())
36 ordinals : Dict[str, int] = { 'last': -1
51 reverse_ordinals : Dict[int, str] = {n: w for w, n in ordinals.items()}
53 def from_ordinal(word: str) -> int:
56 def to_ordinal(number: int) -> str:
57 return reverse_ordinals[number]
60 These are the words that can be the solution to a riddle, and used as the clue for a riddle.
63 dictionary : List[str] = [unicodedata.normalize('NFKD', w.strip()).\
64 encode('ascii', 'ignore').\
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
77 Some types that will be used throughout the library
80 class RiddleValence(Enum):
81 """Does this part of the riddle include or exclude letters?"""
87 """A half line of a riddle, like 'is in dreams' or 'not in octet'"""
88 valence : RiddleValence
93 """A representation of the constraints that come from a whole line of
95 valence : RiddleValence
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]]
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]
109 def edit_distance(s: str, t: str) -> int:
120 [ edit_distance(s[:-1], t)+1
121 , edit_distance(s, t[:-1])+1
122 , edit_distance(s[:-1], t[:-1]) + cost
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)
138 return RiddleElement(letters = set(a.word) | set(b.word),
139 valence = RiddleValence.Exclude)
141 if a.valence == RiddleValence.Include:
145 return RiddleElement(letters = set(p.word) - set(q.word),
146 valence = RiddleValence.Include)
148 return {i: combine_clues(a, b) for i, (a, b) in elems.items()}
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
158 if elem.valence == RiddleValence.Include:
159 return word[pos-1] in elem.letters
161 return word[pos-1] not in elem.letters
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?"""
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
173 return all(matches_element(i, elem, word) for i, elem in new_riddle.items())
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)]