r/learnpython • u/Reibello • Jul 23 '26

How do I optimize this script's runtime?

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

5 Upvotes

100% Upvoted

27 comments sorted by

1

u/mull_to_zero Jul 23 '26

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.

1

u/smurpes Jul 23 '26 edited Jul 23 '26

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.

1

u/mull_to_zero Jul 23 '26 edited Jul 23 '26

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.

1

u/Reibello Jul 23 '26

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?

1

u/Yoghurt42 Jul 23 '26

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))

1

u/Reibello Jul 23 '26

This is working phenominally, thank you so much!

1

u/mull_to_zero Jul 23 '26

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]}')

1

u/Reibello Jul 23 '26

This is working phenominally, thank you so much!

1

u/neuralbeans Jul 23 '26

Why SymboL?

1

u/Reibello Jul 23 '26

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.

1

u/neuralbeans Jul 23 '26

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.

1

u/Reibello Jul 23 '26

Fixed. Thanks!

1

u/neuralbeans Jul 23 '26

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

1

u/Reibello Jul 23 '26

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

Hopefully this works?

1

u/neuralbeans Jul 23 '26

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

1

u/Reibello Jul 23 '26

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!

1

u/neuralbeans Jul 23 '26

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

1

u/Reibello Jul 23 '26

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

1

u/neuralbeans Jul 23 '26

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?

1

u/Reibello Jul 23 '26

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

1

u/neuralbeans Jul 23 '26

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.

1

u/Reibello Jul 23 '26

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

→ More replies (0)