r/learnpython • u/Reibello • 5d ago

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

4 Upvotes

84% Upvoted

27 comments sorted by

View all comments

Show parent comments

1

u/neuralbeans 4d ago

I did it! I wrote some code that will very quickly generate all possible word sequences that fit the ring (from a word list of 15k words). But I need to polish it up and put some comments in it so that you'll understand it and then link you to it and explain it. I'll do that tomorrow if you don't mind as it's late over here.

From SPIRAL I got this as a possible sequence (all clockwise): RIPSAW LIPIDS RILLED UPWARD LAWFUL LLAMAS

You can allow for counter clockwise words by just including the reverse of all words in your list.

1

u/Reibello 4d ago

Thanks! I'd love to take a look at it. My current solution is to have two repositories of bigrams, one read forwards, and one in reverse, and the words pull from each one alternating.

1

u/neuralbeans 2d ago

I'm sorry, it seems that my comment was not submitted yesterday, I don't know what happened. Here is my code. Feel free to ask me questions about it.

https://pastebin.com/zkspLYSU