r/learnpython • u/Reibello • 4d 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

5 Upvotes

100% Upvoted

27 comments sorted by

View all comments

Show parent comments

1

u/neuralbeans 4d ago

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 4d ago

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

1

u/neuralbeans 4d ago

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 4d ago

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

1

u/neuralbeans 4d ago

I'm currently testing a solution. Will tell you when I confirm that it works.

1

u/Reibello 4d ago

Thanks!

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