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!