4 formats: ipynb,md,py:percent
9 jupytext_version: 1.15.0
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 but'.split())
32 negative_words = set('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 dictionary_neighbours = {
130 w: [o for o in dictionary
131 if edit_distance(w, o) <= 5
132 if not set(w) <= set(o)
133 if not set(o) <= set(w)]
136 dictionary_neighbours = {w: ns
137 for w, ns in dictionary_neighbours.items()
142 def collapse_riddle_clues(elems : Riddle) -> RiddleElems:
143 """Combine the two parts of a riddle line into one element for solving.
144 This takes account of the valence of the two parts."""
145 def combine_clues(a: RiddleClue, b: RiddleClue) -> RiddleElement:
146 if a.valence == b.valence:
147 if a.valence == RiddleValence.Include:
148 return RiddleElement(letters = set(a.word) & set(b.word),
149 valence = RiddleValence.Include)
151 return RiddleElement(letters = set(a.word) | set(b.word),
152 valence = RiddleValence.Exclude)
154 if a.valence == RiddleValence.Include:
158 return RiddleElement(letters = set(p.word) - set(q.word),
159 valence = RiddleValence.Include)
161 return {i: combine_clues(a, b) for i, (a, b) in elems.items()}
165 def matches_element(pos: int, elem: RiddleElement, word: str) -> bool:
166 """Does this element match this position of the the word?
167 Note that positions are one-based, as in the numbering system of the
171 if elem.valence == RiddleValence.Include:
172 return word[pos-1] in elem.letters
174 return word[pos-1] not in elem.letters
178 def matches_all_elements(riddle: RiddleElems, word: str) -> bool:
179 """Do all the elements of a riddle match the appropriate parts of a word?"""
181 last_elem = riddle[-1]
182 new_riddle = {p: e for p, e in riddle.items() if p != -1}
183 new_riddle[len(word)] = last_elem
186 return all(matches_element(i, elem, word) for i, elem in new_riddle.items())
190 def solve_riddle(riddle: RiddleElems) -> List[str]:
191 """Find all words that match this riddle"""
192 return [w for w in dictionary
193 if len(w) == len(riddle)
194 if matches_all_elements(riddle, w)]