From ffbfb5b3117178a49a93946daed6c2689df3e1b8 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 7 Aug 2023 15:58:02 +0100 Subject: [PATCH] Initial commit: solves riddles --- .gitignore | 9 ++ riddle-solver.md | 232 +++++++++++++++++++++++++++++++++++++++++++++ sample-riddles.txt | 20 ++++ 3 files changed, 261 insertions(+) create mode 100644 .gitignore create mode 100644 riddle-solver.md create mode 100644 sample-riddles.txt diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..1e96007 --- /dev/null +++ b/.gitignore @@ -0,0 +1,9 @@ +*~ +*doc +*log +/tmp +/__pycache__/* +*pyc +.ipynb* +*.sublime-workspace +.directory/* \ No newline at end of file diff --git a/riddle-solver.md b/riddle-solver.md new file mode 100644 index 0000000..9aa58d7 --- /dev/null +++ b/riddle-solver.md @@ -0,0 +1,232 @@ +--- +jupyter: + jupytext: + formats: ipynb,md + text_representation: + extension: .md + format_name: markdown + format_version: '1.3' + jupytext_version: 1.14.5 + kernelspec: + display_name: Python 3 (ipykernel) + language: python + name: python3 +--- + +```python +import unicodedata +import re +from dataclasses import dataclass +from typing import Dict, Tuple, List, Set +from enum import Enum, auto +``` + +```python +dictionary : List[str] = [unicodedata.normalize('NFKD', w.strip()).\ + encode('ascii', 'ignore').\ + decode('utf-8') + for w in open('/usr/share/dict/british-english').readlines() + if w.strip().islower() + if w.strip().isalpha() + ] +dictionary[:5] +``` + +```python +ordinals : Dict[str, int] = { 'last': -1 + , 'first': 1 + , 'second': 2 + , 'third': 3 + , 'fourth': 4 + , 'fifth': 5 + , 'sixth': 6 + , 'seventh': 7 + , 'eighth': 8 + , 'ninth': 9 + , 'tenth': 10 + , 'eleventh': 11 + , 'twelfth': 12 + } + +# reverse_ordinals : Dict[int, str] = {n: w for w, n in ordinals.items()} + +def from_ordinal(word: str) -> int: + return ordinals[word] + +# def to_ordinal(number: int) -> str: +# return reverse_ordinals[number] +``` + +```python +from_ordinal('seventh') +``` + +```python +def tokenise(phrase: str) -> List[str]: + return [w.lower() for w in re.split(r'\W+', phrase) if w] +``` + +```python +tokenise("My first is in apple, but not in fish.") +``` + +```python +class RiddleValence(Enum): + Include = auto() + Exclude = auto() + +@dataclass +class RiddleElement: + valence : RiddleValence + letters : Set[str] + +Riddle = Dict[int, RiddleElement] +``` + +```python +stop_words = set('my is in within lies and also always you will find always the found'.split()) +negative_words = set('but not never'.split()) +``` + +```python +def parse_line(tokens: List[str]) -> Tuple[int, RiddleElement, RiddleElement]: + stripped_tokens = [t for t in tokens if t not in stop_words] + + position_word = [t for t in stripped_tokens if t in ordinals][0] + pos = from_ordinal(position_word) + + first_index, first_word = [(i, t) for i, t in enumerate(stripped_tokens) + if t not in ordinals + if t not in negative_words][0] + second_index, second_word = [(i, t) for i, t in enumerate(stripped_tokens) + if t not in ordinals + if t not in negative_words][1] + neg_indices = [i for i, t in enumerate(stripped_tokens) if t in negative_words] + + first_clue = None + second_clue = None + + if neg_indices: + if neg_indices[0] < first_index: + first_clue = RiddleElement(valence = RiddleValence.Exclude, + letters = set(first_word)) + if len(neg_indices) > 1: + second_clue = RiddleElement(valence = RiddleValence.Exclude, + letters = set(second_word)) + elif neg_indices[0] < second_index: + second_clue = RiddleElement(valence = RiddleValence.Exclude, + letters = set(second_word)) + + if first_clue is None: + first_clue = RiddleElement(valence = RiddleValence.Include, + letters = set(first_word)) + + if second_clue is None: + second_clue = RiddleElement(valence = RiddleValence.Include, + letters = set(second_word)) + + return (pos, first_clue, second_clue) +``` + +```python +e1 = parse_line(tokenise("My first is in apple, but not in pad.")) +e1 +``` + +```python +e2 = parse_line(tokenise("My second is in apple and also in banana.")) +e2 +``` + +```python +def collapse_riddle_elements(elems : List[Tuple[int, RiddleElement, RiddleElement]]) -> Dict[int, RiddleElement]: + def combine_elements(a: RiddleElement, b: RiddleElement) -> RiddleElement: + if a.valence == b.valence: + return RiddleElement(letters = a.letters | b.letters, valence = a.valence) + else: + if a.valence == RiddleValence.Include: + p, q = a, b + else: + p, q = b, a + return RiddleElement(letters = p.letters - q.letters, valence = RiddleValence.Include) + + return {i: combine_elements(a, b) for i, a, b in elems} +``` + +```python +collapse_riddle_elements([e1, e2]) +``` + +```python +sample_riddle_text = """My first is in shoat but not in oath +My second is in orate but not in ratter +My third is in preposition but not in osteoporosis +My fourth is in astern but not in taster +My fifth is in conscientiousness but not in suction +My sixth is in immorality but not in immorally""" + +sample_riddle_lines = [parse_line(tokenise(l)) for l in sample_riddle_text.split('\n')] +sample_riddle_lines +``` + +```python +sample_riddle = collapse_riddle_elements(sample_riddle_lines) +sample_riddle +``` + +```python +def parse_riddle(riddle_text: str) -> Dict[int, RiddleElement]: + riddle_lines = [parse_line(tokenise(l)) for l in riddle_text.split('\n')] + return collapse_riddle_elements(riddle_lines) +``` + +```python +def matches_element(pos: int, elem: RiddleElement, word: str) -> bool: + if len(word) < pos: + return False + if elem.valence == RiddleValence.Include: + return word[pos-1] in elem.letters + else: + return word[pos-1] not in elem.letters +``` + +```python +def matches_all_elements(riddle: Dict[int, RiddleElement], word: str) -> bool: + if -1 in riddle: + last_elem = riddle[-1] + new_riddle = {p: e for p, e in riddle.items() if p != -1} + new_riddle[len(word)] = last_elem + else: + new_riddle = riddle + return all(matches_element(i, elem, word) for i, elem in new_riddle.items()) +``` + +```python +def solve_riddle(riddle: Dict[int, RiddleElement]) -> str: + return [w for w in dictionary + if len(w) == len(riddle) + if matches_all_elements(riddle, w)] +``` + +```python +solve_riddle(sample_riddle) +``` + +```python +def parse_and_solve_riddle(riddle_text: str) -> List[str]: + riddle = parse_riddle(riddle_text) + return solve_riddle(riddle) +``` + +```python +sample_riddles = open('sample-riddles.txt').read().split('\n\n') +sample_riddles +``` + +```python +[parse_and_solve_riddle(r) for r in sample_riddles] +``` + +```python + +``` diff --git a/sample-riddles.txt b/sample-riddles.txt new file mode 100644 index 0000000..9e98b3b --- /dev/null +++ b/sample-riddles.txt @@ -0,0 +1,20 @@ +My first is in shoat but not in oath +My second is in orate but not in ratter +My third is in preposition but not in osteoporosis +My fourth is in astern but not in taster +My fifth is in conscientiousness but not in suction +My sixth is in immorality but not in immorally + +My first is in riddle, but not in little. +My second is in think, but not in brink. +My third is in thyme, but not in time. +My fourth is in mother, but not in brother. +My last is in time, but not in climb. + +My first is in spell, but not book. +My second is in fright and also shook. +My third is in cauldron, but never in pot. +My fourth is in net and also in knot. +My fifth is in bat, but never in vampire. +My sixth is in coal, but not found in fire. +My seventh is in moon, but not in night. \ No newline at end of file -- 2.34.1