I am totally on board with the “code first, optimize later” school of programming. But sometimes one can forget to optimize, which can be a minor issue (if the code was already pretty optimized) or a major one (if there’s a glaringly obvious improvement to be made). I recently coded something up to help someone out and it definitely needed some optimization before it was done.<\/p>\n
If you haven’t done Matt Gaffney’s “Shake It Up” crossword<\/a> you might want to do it before reading further, because there will be massive spoilers. Done? All right, let’s continue. So Matt asked me if there would be a way to fill a corner of a crossword grid with a 4×4 block of letters such that (a) one square was a Qu rebus and (b) the 4×4 block contained a 17-letter word following Boggle rules. In Boggle, you try to make long words by moving like a king in chess through the 4×4 block, never landing on the same letter more then once. Now, it’s certainly easy to make a block like that which spells, say, SESQUICENTENNIALS:<\/p>\n but it’s harder to make one that would then fit inside a crossword. Here, for instance, we have the troubling EEEL and SNTS, letter patterns which don’t fit in many good crossword entries.<\/p>\n My first thought was: for each 17-letter Boggle word (I started with INCONSEQUENTIALLY, SESQUICENTENNIALS and QUADRICENTENNIALS, but others are possible) I created a random grid with those letters, and then checked to see if the word was actually inside with Boggle rules, and then if the resulting letter patterns were good for a crossword. I was pretty happy with this solution, but it was painfully slow! Why? Well, essentially because 16! is a humongous number (20,922,789,888,000 — approximately the number of red blood cells in the human body, thanks Wolfram Alpha!<\/a>) and so I was making 20 trillion grids (give or take) for each word I wanted to analyze. I had a working solution, but it was unbearably slow, so I needed to optimize.<\/p>\n My next thought was: instead of making a random grid and checking if it’s Boggle-friendly, why not just start with a Boggle-friendly grid? This turned out to be no harder to code up than checking to see if a grid contained the word and it dropped the number of possible grids from 20 trillion to under 400,000. Still a big number, but WAY smaller. (For reference: 20 trillion seconds is over 600,000 years; 400,000 seconds is about four and a half days). This made the algorithm quite fast.<\/p>\n You can check out the code here<\/a>. I wrote it in C++ because that’s how I write all my code when I need it to run fast. You’ll note in the code that there’s another optimization that can be made, but at this point I’m happy with how fast it ran. Oh, and it did work for Matt — he was able to take some of the output and make a pretty nice crossword with it.<\/p>\n Enjoy!<\/p>\n","protected":false},"excerpt":{"rendered":" I am totally on board with the “code first, optimize later” school of programming. But sometimes one can forget to optimize, which can be a minor issue (if the code was already pretty optimized) or a major one (if there’s … Continue reading
\n<\/p>\n\r\nSESQ\r\nNECI\r\nTENN\r\nSLAI\r\n<\/pre>\n