r/computerscience • u/TheNumbhead • Jun 01 '22
I wrote a wave function collapse algorithm for generating dense NYT-style crossword puzzles
8
u/void5253 Jun 01 '22
That's impressive! Could you give some sort of a roadmap as to how I should go about learning such algorithms? I'm very interested in such things, but don't know where to start learning.
8
u/TheNumbhead Jun 01 '22
Thanks! I can't say that what's worked for me will work with your learning style, but I like to learn by doing. For instance, I found wave function collapse while researching for a game I'm making. I found Dijkstra's algorithm in that research phase as well, which is an indispensable (and fairly simple), algorithm for pathfinding. I also encounter algorithms of various sorts through my job as a software engineer. For me, algorithms are an exciting stepping stone for some end goal I have in mind, not an end goal in themselves, though I know many people enjoy algorithms for their own sake.
I'd also say regularly checking in on HN has helped keep me up-to-date on what is capturing the imaginations of other computer scientists out there--algorithms show up there now and then.
1
u/void5253 Jun 01 '22
Thank you! Do you reckon I should study math as well? Are there any other topics I should know as prerequisites?
3
u/TheNumbhead Jun 01 '22
I think it depends on your goals. Want to learn as many algorithms as possible? Read books on algorithms and take classes online or at a community college. Want to land a programming job at a big tech company? Work problems on Project Euler or Advent of Code. Want to learn to apply algorithms? Read up on various algorithms online, and build a small project that uses one of them. These are just a few ideas--for each one, you'd pick up the math you need along the way. Though if you want to be an algorithms expert (which I certainly am not), I would highly recommend taking a class or getting a graduate degree. Getting rapid feedback from an expert is one of the best ways to learn fast IMO
3
u/FatFingerHelperBot Jun 01 '22
It seems that your comment contains 1 or more links that are hard to tap for mobile users. I will extend those so they're easier for our sausage fingers to click!
Here is link number 1 - Previous text "HN"
Please PM /u/eganwall with issues or feedback! | Code | Delete
3
2
u/KiranEvans Jun 01 '22
This is one of the coolest inventions I've seen in a while. Would love to see it in action more! How big can it go? Would love to generate the template for it and watch it keep filling in the words infinitely!
2
u/TheNumbhead Jun 01 '22
I appreciate that--thank you. I've only tried it on 15x15 boards so far, but experimenting on larger boards is on my roadmap. There is no theoretical limit to board size I can think of, so it would be fun to see how far we can push it. The main struggle with larger boards will probably be that the algorithm will need to do more dictionary lookups (which are kind of slow) per tile placed since it will have to propagate the constraints of the collapsed state further than in the 15x15 case.
1
u/metastimulus Jun 01 '22
Very interesting! Have you tried generating any audio with this?
2
u/TheNumbhead Jun 01 '22
Ooh, do you mean like mapping each letter to a note on a pentatonic scale? That's a cool idea--like strange, algorithmic wind chimes.
1
1
1
u/OleksandrKompaniiets Aug 31 '22
Check this:
I developed that soft 15 years ago. The algorithm of generating is way simpler. You just need to select the axis of symmetry or w/o
0
Jun 02 '22
[deleted]
1
u/TheNumbhead Jun 02 '22
I have some interest in putting out an open source version of this, yes! What I have right now is a React app with a bunch of other stuff bolted on to it. A stripped down open source version would be a great way for me to participate in seeing the use of and interest in wave function collapse increase.
0
39
u/TheNumbhead Jun 01 '22
First time posting here! I thought I'd share my progress on a recent hobby project. I was dabbling in procedural generation recently and came across wave function collapse, which is an algorithm inspired by quantum mechanics. The link above explains it well--in short, the algorithm starts with a blank canvas as an output, treating it as a "wave" where each tile is in some superposition of states; i.e., each tile could be any of the possible tiles. In my case, each tile can be one of 26 letters. Then, the algorithm iteratively collapses each tile into a single state, and given the rules between the tiles (e.g., each "across" or "down" section must be a word in a dictionary), collapses more and more tiles in the output canvas until each one has only one state. Each iteration, it collapses the tile with the lowest Shannon entropy next.
I have seen this applied to procedural world/canvas generation to great effect. I've never seen it applied to words, so I thought it would be a fun challenge to make a dense NYT-style crossword builder with it. My algorithm is a wave function collapse algorithm with backtracking built in, so if it hits a contradiction, it will back up and try again, backing up further for each repeated contradiction. The brighter the blue, the lower the entropy for that tile.
This is just the start of this project--I'm trying to build the most accessible crossword puzzle builder I can. The amazing thing about wave function collapse is, because it continually constrains the not-yet-collapsed parts of the board, it allows me make suggestions to the user about where they should place their next word (essentially, I'll suggest the word slot that is lowest entropy) and present a list of words to choose from my dictionary. I could see this being used by lay people to build crosswords for friends, online communities, maybe even schools. I'm continuing work on fleshing out this project more, so I may be back in the future with an update!