From ce34915246926441c163272e09f1343db3fd1955 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Wed, 9 Aug 2023 10:36:20 +0100 Subject: [PATCH] Created separate library --- generated-riddles.txt | 97 ++++++++++++++++++ riddle-solver.md | 232 ------------------------------------------ riddle_creator.md | 214 ++++++++++++++++++++++++++++++++++++++ riddle_definitions.md | 171 +++++++++++++++++++++++++++++++ riddle_solver.md | 160 +++++++++++++++++++++++++++++ 5 files changed, 642 insertions(+), 232 deletions(-) create mode 100644 generated-riddles.txt delete mode 100644 riddle-solver.md create mode 100644 riddle_creator.md create mode 100644 riddle_definitions.md create mode 100644 riddle_solver.md diff --git a/generated-riddles.txt b/generated-riddles.txt new file mode 100644 index 0000000..ead93f6 --- /dev/null +++ b/generated-riddles.txt @@ -0,0 +1,97 @@ +My first is in upraising but not in reprising +My second is in inept and also in inapt +My third is neither in hopping nor in cooping +My fourth is in goody and also in bloody +My fifth is neither in gaffing nor in gauging +My sixth is in rouses but not in kluges +My seventh is in replies and also in repairs +My eighth is in slumps but not in blunts +My ninth is in tiller and also in billed +My tenth is in tainted but not in gritted +My eleventh is in waggled and also in fagged +Target: airdropping + +My first is in bared and also in babied +My second is in pilling but not in riffing +My third is in caning and also in weaning +My fourth is in waking but not in wackier +My fifth is in ranks and also in rocks +My sixth is in servos but not in sprays +My seventh is in clods but not in clang +My eighth is in fating but not in lining +Target: blankest + +My first is in corns but not in lorry +My second is in garaged but not in grudged +My third is in tunas but not in times +My fourth is in hoots but not in huffs +My fifth is in walked but not in wilder +My sixth is in coeval but not in commas +My seventh is in recovered but not in reversed +My eighth is in usually but not in salty +My ninth is in priest but not in evilest +My tenth is in abides but not in amigos +Target: cantaloupe + +My first is in aloes but not in dados +My second is in censures and also in tenures +My third is in extricating and also in extrication +My fourth is in cutlass but not in atlases +My fifth is in mortgagee but not in montage +My sixth is neither in dawns nor in darts +My seventh is in mooching but not in mucking +My eighth is in routing and also in shouting +My ninth is in flumes but not in flurry +Target: luxurious + +My first is in deans but not in slats +My second is in persona but not in perusing +My third is neither in veiled nor in seized +My fourth is in cleat but not in octet +My last is in curtsied but not in curbed +Target: earls + +My first is in loaned but not in limned +My second is in equals and also in quails +My third is in fitting and also in matting +My fourth is in creations but not in libations +My fifth is in goriest but not in iffiest +My sixth is in rooked and also in goosed +My last is in blips and also in slaps +Target: outcrop + +My first is neither in slide nor in slily +My second is in yocks but not in bricks +My third is in auras but not in crays +My fourth is in swing but not in going +My fifth is in drags but not in dealt +My sixth is in sexily but not in subtly +My last is in timeless and also in tireless +Target: mousses + +My first is in wiper but not in dimmer +My second is in faces but not in offices +My third is in climes but not in corms +My fourth is in razing but not in seeing +My fifth is in minnow but not in mingle +My sixth is in glided but not in flawed +My seventh is in cashed but not in vanned +My eighth is neither in dwarfs nor in swarms +Target: pairwise + +My first is in penes but not in linens +My second is in buried but not in mushed +My third is in curved and also in carved +My fourth is in recaps but not in scads +My fifth is neither in upending nor in unbending +My sixth is in surgery but not in surgeons +My seventh is in raves but not in framer +Target: prepays + +My first is in remit but not in resins +My second is in mingles but not in gingkos +My third is in suave and also in state +My fourth is in caned and also in cored +My fifth is in saucy but not in spacey +My sixth is in carps but not in saves +Target: teacup diff --git a/riddle-solver.md b/riddle-solver.md deleted file mode 100644 index 9aa58d7..0000000 --- a/riddle-solver.md +++ /dev/null @@ -1,232 +0,0 @@ ---- -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/riddle_creator.md b/riddle_creator.md new file mode 100644 index 0000000..36b939a --- /dev/null +++ b/riddle_creator.md @@ -0,0 +1,214 @@ +--- +jupyter: + jupytext: + formats: ipynb,md,py:percent + 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 +from riddle_definitions import * + +from typing import Dict, Tuple, List, Set +from enum import Enum, auto +import random +``` + +```python +def include_exclude_clue(letter: str, limit: int = 3) -> (RiddleClue, RiddleClue): + with_letter = [w for w in dictionary if letter in w] + without_letter = [w for w in dictionary if letter not in w] + + finished = False + while not finished: + a = random.choice(with_letter) + b = random.choice(without_letter) + finished = ((edit_distance(a, b) <= limit) and + not set(a) <= set(b) and + not set(a) >= set(b)) + return (RiddleClue(word=a, valence=RiddleValence.Include), + RiddleClue(word=b, valence=RiddleValence.Exclude)) + +a, b = include_exclude_clue('s') +a, b, set(a.word) - set(b.word), edit_distance(a.word, b.word) +``` + +```python +def include_include_clue(letter: str, limit: int = 3) -> (RiddleClue, RiddleClue): + with_letter = [w for w in dictionary if letter in w] + + finished = False + while not finished: + a = random.choice(with_letter) + b = random.choice(with_letter) + finished = ((a != b) and + (edit_distance(a, b) <= limit) and + not set(a) <= set(b) and + not set(a) >= set(b)) + return (RiddleClue(word=a, valence=RiddleValence.Include), + RiddleClue(word=b, valence=RiddleValence.Include)) + +a, b = include_include_clue('s') +a, b, set(a.word) | set(b.word), edit_distance(a.word, b.word) +``` + +```python +def exclude_exclude_clue(letter: str, limit: int = 3) -> (RiddleClue, RiddleClue): + without_letter = [w for w in dictionary if letter not in w] + + finished = False + while not finished: + a = random.choice(without_letter) + b = random.choice(without_letter) + finished = ((a != b) and + (edit_distance(a, b) <= limit) and + not set(a) <= set(b) and + not set(a) >= set(b)) + return (RiddleClue(word=a, valence=RiddleValence.Exclude), + RiddleClue(word=b, valence=RiddleValence.Exclude)) + +a, b = exclude_exclude_clue('s') +a, b, set(a.word) | set(b.word), edit_distance(a.word, b.word) +``` + +```python +def random_clue( letter: str + , ie_limit: int = 3 + , ii_limit: int = 2 + , ee_limit: int = 2) -> (RiddleClue, RiddleClue): + r = random.random() + if r <= 0.7: + return include_exclude_clue(letter, limit=ie_limit) + elif r <= 0.9: + return include_include_clue(letter, limit=ii_limit) + else: + return exclude_exclude_clue(letter, limit=ee_limit) +``` + +```python +def random_riddle(word: str, limit: int = 3) -> Riddle: + return {i+1 : random_clue(l, ie_limit=limit) + for i, l in enumerate(word)} +``` + +```python +sample_riddle = random_riddle('sonnet') +sample_riddle +``` + +```python + +``` + +```python +sample_riddle = random_riddle('sonnet', limit=4) +sample_riddle +``` + +```python +sample_riddle +``` + +```python +collapse_riddle_clues(sample_riddle) +``` + +```python +solve_riddle(collapse_riddle_clues(sample_riddle)) +``` + +```python +def valid_random_riddle(word: str) -> Riddle: + finished = False + while not finished: + riddle = random_riddle(word) + solns = solve_riddle(collapse_riddle_clues(riddle)) + finished = (len(solns) == 1) + return riddle +``` + +```python +def write_include_exclude_line(clue_a: RiddleClue, clue_b: RiddleClue) -> str: + line = f"is in {clue_a.word} but not in {clue_b.word}" + return line +``` + +```python +def write_include_include_line(clue_a: RiddleClue, clue_b: RiddleClue) -> str: + line = f"is in {clue_a.word} and also in {clue_b.word}" + return line +``` + +```python +def write_exclude_exclude_line(clue_a: RiddleClue, clue_b: RiddleClue) -> str: + line = f"is neither in {clue_a.word} nor in {clue_b.word}" + return line +``` + +```python +def write_line(a: RiddleClue, b: RiddleClue) -> str: + if a.valence == RiddleValence.Include and b.valence == RiddleValence.Include: + return write_include_include_line(a, b) + elif a.valence == RiddleValence.Include and b.valence == RiddleValence.Exclude: + return write_include_exclude_line(a, b) + elif a.valence == RiddleValence.Exclude and b.valence == RiddleValence.Exclude: + return write_exclude_exclude_line(a, b) + else: + return "illegal line" +``` + +```python +def write_riddle(riddle: Riddle) -> List[str]: + output = [] + for i, (clue_a, clue_b) in sorted(riddle.items()): + pos = reverse_ordinals[i] + if i == len(riddle) and random.random() <= 0.3: + pos = reverse_ordinals[-1] + line = write_line(clue_a, clue_b) + full_line = f"My {pos} {line}" + output.append(full_line) + return output +``` + +```python + +``` + +```python +sample_riddle = valid_random_riddle("elephant") +sample_riddle +``` + +```python +write_riddle(sample_riddle) +``` + +```python +solve_riddle(collapse_riddle_clues(sample_riddle)) +``` + +```python +with open("generated-riddles.txt", 'w') as file: + between = False + for _ in range(10): + if between: + file.write('\n') + between = True + target = random.choice(dictionary) + riddle = valid_random_riddle(target) + lines = write_riddle(riddle) + file.writelines(l + '\n' for l in lines) + file.write(f'Target: {target}\n') + +``` + +```python + +``` diff --git a/riddle_definitions.md b/riddle_definitions.md new file mode 100644 index 0000000..fb025c4 --- /dev/null +++ b/riddle_definitions.md @@ -0,0 +1,171 @@ +--- +jupyter: + jupytext: + formats: ipynb,md,py:percent + 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 +--- + +# Definitions generally useful for the riddle solver + +```python +import unicodedata +import re +from dataclasses import dataclass +from typing import Dict, Tuple, List, Set +from enum import Enum, auto +import functools +import random +``` + +```python +stop_words = set('my is in within lies and also always you will find the found'.split()) +negative_words = set('but not never neither nor'.split()) +``` + +```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] +``` + +These are the words that can be the solution to a riddle, and used as the clue for a riddle. + +```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() + if len(w.strip()) >= 5 + if w not in stop_words + if w not in negative_words + if w not in ordinals + ] +``` + +Some types that will be used throughout the library + +```python +class RiddleValence(Enum): + Include = auto() + Exclude = auto() + +@dataclass +class RiddleClue: + valence : RiddleValence + word : str + +@dataclass +class RiddleElement: + valence : RiddleValence + letters : Set[str] + +Riddle = Dict[int, Tuple[RiddleClue, RiddleClue]] +RiddleElems = Dict[int, RiddleElement] +``` + +```python +@functools.lru_cache +def edit_distance(s: str, t: str) -> int: + if s == "": + return len(t) + if t == "": + return len(s) + if s[-1] == t[-1]: + cost = 0 + else: + cost = 1 + + res = min( + [ edit_distance(s[:-1], t)+1 + , edit_distance(s, t[:-1])+1 + , edit_distance(s[:-1], t[:-1]) + cost + ]) + + return res +``` + +```python +def collapse_riddle_clues(elems : Dict[int, Tuple[RiddleClue, RiddleClue]]) -> RiddleElems: + def combine_clues(a: RiddleClue, b: RiddleClue) -> RiddleElement: + if a.valence == b.valence: + if a.valence == RiddleValence.Include: + return RiddleElement(letters = set(a.word) & set(b.word), + valence = RiddleValence.Include) + else: + return RiddleElement(letters = set(a.word) | set(b.word), + valence = RiddleValence.Exclude) + else: + if a.valence == RiddleValence.Include: + p, q = a, b + else: + p, q = b, a + return RiddleElement(letters = set(p.word) - set(q.word), + valence = RiddleValence.Include) + + return {i: combine_clues(a, b) for i, (a, b) in elems.items()} +``` + +```python + +``` + +```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: RiddleElems, 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: RiddleElems) -> List[str]: + return [w for w in dictionary + if len(w) == len(riddle) + if matches_all_elements(riddle, w)] +``` + +```python + +``` diff --git a/riddle_solver.md b/riddle_solver.md new file mode 100644 index 0000000..a9e3064 --- /dev/null +++ b/riddle_solver.md @@ -0,0 +1,160 @@ +--- +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 +from riddle_definitions import * + +import re +from typing import Dict, Tuple, List, Set +from enum import Enum, auto +``` + +```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 +def parse_line(tokens: List[str]) -> Tuple[int, Tuple[RiddleClue, RiddleClue]]: + 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 = RiddleClue(valence = RiddleValence.Exclude, + word = first_word) + if len(neg_indices) > 1: + second_clue = RiddleClue(valence = RiddleValence.Exclude, + word = second_word) + elif neg_indices[0] < second_index: + second_clue = RiddleClue(valence = RiddleValence.Exclude, + word = second_word) + + if first_clue is None: + first_clue = RiddleClue(valence = RiddleValence.Include, + word = first_word) + + if second_clue is None: + second_clue = RiddleClue(valence = RiddleValence.Include, + word = 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 +e3 = parse_line(tokenise('My seventh is neither in callus nor in calves')) +e3 +``` + +```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 = {i: elem + for i, elem in + [parse_line(tokenise(l)) + for l in sample_riddle_text.split('\n')]} +sample_riddle_lines +``` + +```python +sample_riddle = collapse_riddle_clues(sample_riddle_lines) +sample_riddle +``` + +```python +def parse_riddle(riddle_text: str) -> Riddle: + riddle_lines = {i: elem + for i, elem in + [parse_line(tokenise(l)) for l in riddle_text.split('\n')]} + return collapse_riddle_clues(riddle_lines) +``` + +```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 +sample_riddles = open('generated-riddles.txt').read().split('\n\n') +sample_riddles = [riddle.split('\nTarget: ') for riddle in sample_riddles] +sample_riddles = [(r, s.strip()) for r, s in sample_riddles] +sample_riddles +``` + +```python +for r, s in sample_riddles: + found_solns = parse_and_solve_riddle(r) + correct = len(found_solns) == 1 and found_solns[0] == s + print(found_solns, s, correct) +``` + +```python +# [parse_line(tokenise(line)) for line in sample_riddles[4][0]] +[parse_line(tokenise(line)) for line in sample_riddles[4][0].split('\n')] +``` + +```python +parse_riddle(sample_riddles[4][0]) +``` + +```python + +``` -- 2.34.1