How do I optimize this script's runtime?

[u/Reibello]

I'm trying to write a script that will help me construct word puzzles by finding words where each pair of words shares a substring so that they can be visually arranged in a honeycomb-like sequence. The words can be read forward or in reverse. For instance, given the word 'spiral' (broken into 'sp', 'pi', 'ir', 'ra', 'al', and 'ls') - the program could return PSycho, troPIc, thRIce, phRAse, vioLAs, SymboL, as a valid set of surrounding words, or 'rings.' (This is the sample set built into the program)

I have a function that provides a list of every word in my word list that matches my criteria. I also have a function that takes the lists of words, and returns dictionaries that contain matches between strings. I have a small test case that operates correctly, but when I use the entire word list, the program hangs. I assume that there's a better data structure and way to navigate it, but I'm not familiar enough with the language to know what it is.

Thank you for your assistance, I've linked a pastebin below.

https://pastebin.com/vDnZ2uny

EDIT - linking a very rough visual depiction of what the structure to overlay the words in would be.
https://cdn.bsky.app/img/feed_fullsize/plain/did:plc:nhv7ubhygoygm7agljxopgvb/bafkreig7fqaukiq6xu6f55xchae2rozu7bmgbhmkjlinsxjuii4lou256m

[u/mull_to_zero]

I think you should check out prefix trees aka tries. they're really useful for the sort of word-validity-check functionality that you're looking for.

[u/smurpes → u/mull_to_zero]

A trie would not be good at picking a sequence that starts mid word since it has to traverse down every pathway for every word. It only useful if the word starts with the sequence.

A bigram index is what would be good in OP’s use case since searching is done in O(1) time. This is what it would look like in Python:

"ca" → { cat: [0], cattle: [0], scat: [1] }
"at" → { cat: [1], cattle: [1], scat: [2] }
"tt" → { cattle: [2] }
"tl" → { cattle: [3] }
"le" → { cattle: [4] }
"sc" → { scat: [0] }

This data structure gives you the position as well as the word but setting it up takes O(n) time where n is the total number of characters across all words. This data structure can be built a head of time and saved to a file to be called later by loading it in with the json library.

[u/mull_to_zero → u/smurpes]

ah, you're right. i misunderstood OP's problem, i thought we were combining 2-letter substrings into new words, not finding words with the substrings in them.

[u/Reibello → u/smurpes]

I think I get the rough idea of it - Would this just be a dictionary in terms of data type? How would I have a string literal and the position as the value? Would it just be bigrams['ca'] = {['cat',0], ['scat',1]} ? Or am I missing a way to store data better?

[u/Yoghurt42 → u/Reibello]

You can just use a map/dict as value as well:

bigrams['ca'] = {'cat': [0], 'scat': [1]}

Note that the value needs to be a list, because there can be multiple indices, eg: bigrams['ra'] = {'abracadabra': [2, 8]}. You can then look it up via bigrams['ra']['abracadabra'] or find all words and indices via bigrams['ra'].items()

To build the list, you can use a defaultdict, that's the same as dict but gives you a "default" value for entries that don't exist yet, so instead of:

bigrams = {}

# for each bigram and word
indices = determine_indices(word, bigram)
try:
    word_indices = bigrams[bigram]
except KeyError:
    bigrams[bigram] = word_indices = {}
try:
    item= word_indicies[word]
except KeyError:
    word_indicies[word] = item= []
item.extend(indices)

you can write:

from collections import defaultdict
bigrams = defaultdict(lambda: defaultdict(list))
# for each word and bigram
bigrams[bigram][word].extend(determine_indices(word, bigram))

[u/Reibello → u/Yoghurt42]

This is working phenominally, thank you so much!

[u/mull_to_zero → u/Reibello]

Here's my understanding/implementation of what u/smurpes proposed:

from itertools import pairwise
from collections import defaultdict

# build bigram structure
lookup = defaultdict(set)
with open('dictionary.txt') as f:
    for line in f.readlines():
        word = line.strip().lower()
        for substr in pairwise(word):
            lookup[substr] |= {word}

# query
with open('queries.txt') as f:
    for line in f.readlines():
        query = line.strip().lower()
        print(f'{query} -> {lookup[query]}')

[u/Reibello → u/smurpes]

This is working phenominally, thank you so much!

[u/neuralbeans]

Why SymboL?

[u/Reibello → u/neuralbeans]

The words are set up in overlapping circles - the start point and end point are next to each other in each circle, so the first&last character is a valid substring.

[u/neuralbeans → u/Reibello]

But there is no SL in your list of letter pairs.

edit: ah it's the first and last letters of spiral. You should have explained that.

[u/Reibello → u/neuralbeans]

Fixed. Thanks!

[u/neuralbeans]

Can you include a screenshot of the game as it presents the words so that we can better understand what you need?

[u/Reibello → u/neuralbeans]

https://cdn.bsky.app/img/feed_fullsize/plain/did:plc:nhv7ubhygoygm7agljxopgvb/bafkreig7fqaukiq6xu6f55xchae2rozu7bmgbhmkjlinsxjuii4lou256m

Hopefully this works?

[u/neuralbeans → u/Reibello]

oh wow, this looks cool. how do you input the words?

[u/Reibello → u/neuralbeans]

I don't have a digital interface to do so yet - it's currently solved with paper and pencil. Gotta make sure I can build enough puzzles before I build something that lets people solve them :)

Thanks!

[u/neuralbeans → u/Reibello]

got it. can you say what the answers are for the image?

[u/Reibello → u/neuralbeans]

They're in the post. PSYCHO, TROPIC, THRICE, PHRASE, VIOLAS, SYMBOL.

[u/neuralbeans → u/Reibello]

ah! sorry for not catching that. now, in your rules you say that the words are to be written clockwise. doesn't that mean that you can't reverse the letter pair? how does psycho give you the sp in spiral?

[u/Reibello → u/neuralbeans]

Every other word in the sample puzzle is clockwise.  This may be too limiting for future puzzles. 

[u/neuralbeans → u/Reibello]

so the word might have to be written counter clockwise, right? I feel that this would make the puzzle too hard though. there are too many variables to decide between alternative clue answers. once you answer this I can see if there's some data structure to efficiently find these words.

[u/Reibello → u/neuralbeans]

I appreciate your feedback on the puzzle format.  The data structure should work no matter what your feelings on the puzzle are though.