Category Archives: puzzles

Crossword digest

This month my age incremented again. On the very anniversary of my birth, I received an email from Will Shortz’s assistant, saying (nicely) that the puzzle I submitted back in November didn’t make the cut. I was prepared for this: a puzzle with a similar theme came out a couple of weeks after I mailed mine in, and well, it’s not exactly that unique in the first place. Also the middle section of my puz is a bit of a stretch. And, I felt bad about not trying to excise 23-A from the puzzle.

But anyway, their loss is your loss! Click here to try it.

The 2018 American Crossword Puzzle Tournament starts this coming weekend. Last year, I complained that the online crossword tournament used a Java applet and would have almost no browser support by this time. This year, the online solver is running a version of my own XwordJS, customized (by me) for the ACPT’s backend (which I had nothing to do with). Here’s hoping it works.

After the 2017 tournament, I hoped to increase my solving speed to be more competitive this time around. In reality, I didn’t put much effort into this goal, so I expect to be about the same. My best NYT Monday time, for that one month when I tracked it, was a hair over 7 minutes, far from the front of the pack.

Meanwhile, I did make a bit of progress in solving cryptics, having done the puzzle a few times in the Toronto Star and actually finishing last week’s. I have to say they aren’t as fun as American style crosswords due to the arbitrariness of the cluing, or so I tell myself so that I can feel less dumb.

On board the rebus

My most recent post, for those too lazy to follow the link and hit the “Reveal All” button, is a crossword puzzle announcing the birth of our third son, Samuel Yit-Mun Copeland. We’re over the moon with this new guy in our family. Here he is nearly asleep in my arms as I type this.

But now for something more boring.

I decided months ago that my typical geeky announcement would take the form of a crossword since I’ve been playing in that area recently (previous announcements: a manpage for Alex, an ascii-art crypto program for Ian). And why not make this puzzle interesting by constructing my first rebus puzzle?

A rebus puzzle is one in which a single square can have multiple letters. Part of the fun of solving is realizing at some point that an answer must be right, yet it cannot fit the available cells, so something really weird is going on. Then one curses the constructor and starts with a new set of assumptions.

Constructing such a puzzle is not too much harder than any ordinary puzzle, since all the rebus squares will be part of the themers that the constructor selects up front. Because of this, the fill software doesn’t even really need to care about rebuses — one can use any placeholder for the rebus squares and then edit the final crossword file to add in the full string.

Having lots of theme squares does constrain the grid somewhat, as does having a number of circles on top of that (in this case the circles spell out our new son’s name). But I cheated a little bit: I decided having any old separation between circles was fine as long as the components were all on the same line, and his name is short so that was no major obstacle. In the end I’m pretty happy with the fill considering the 55 theme squares + 20 circles.

Each time I make a puzzle, I also make a number of improvements to my filling software. I’ve long since forgotten whether the goal is building puzzles or building a puzzle builder.

I mentioned before that I had optimized the javascript filler to the point that it was potentially usable in a webapp; this webapp is now a thing. For this puzzle, I used that app as well as my interactive python command-line filler, which has some additional features like estimating the number of eventual solutions using more levels of look-ahead. Finally, I also used a version of the python filler that will take a completed grid and try to optimize it by repeatedly clearing sections of the grid and refilling it randomly.

There is still a good deal of performance work to do on the filler itself. The basic structure is still similar to the backtracking algorithm in QXW: bitmaps are used to filter available words for each cell, and we fill each entry starting with the entries with fewest fills. I made two minor changes in my version: the word list is initially sorted by score and indexed on length so that we can try highest scoring words first and eliminate comparisons against words that will never fit; and entire entries are filled instead of single cells so that score of an entire word is maximized.

I implemented my current algorithm from scratch in C, and it clocks in under half a second for my test puzzle: a little faster than QXW’s implementation and some 30x faster than the very same algorithm in javascript. In terms of LOC, they are roughly the same: 573 (python), 696 (javascript), 763 (C). You can watch them compete below.

So the javascript implementation is frightfully slow. Getting it down to the level of, say, two times the C code, would be a major win, but beyond my current level of js optimization know-how.

Besides that, there is likely some algorithmic optimization that could bring larger gains. Knowing that the “crossword fill problem” is an instance of SAT, I went off to read what Knuth had to say about it (Vol 4 fascicles 5-6), and, as usual, came away with a lot more to think about. The “word square” section is very similar to crossword filling, and indeed the algorithm is close to my existing search, except that it uses trie data structures to cut down on the number of possible words visited at each level. It’s unclear to me at present whether tries would be a win here given that we don’t always start filling with a prefix or suffix, but it could be worth an (ahem) try. Also I may look at branch-and-bound search pruning and parallel search at some point.

Fill faster

I’ve not done much work lately on my forked-from-QXW, written-in-C crossword filler, as getting that code up to snuff amounts to a rewrite. But one thing it has going for it is that it is very fast.

Meanwhile, I have my own written-from-scratch-in-python filler that I’m pretty happy with in terms of results and features, but which is no speed demon. And then I wanted to have this all work on my phone, so I re-implemented it in javascript. Yes, I’m writing a lot of code lately in this language that I do not care for.

Anyhow, down this rabbit hole I go, and one thing that is clear is that the interpreted language versions are not fast. Representative times to fill a grid:

cpython:    114 s
node js:    49 s
pypy:       26 s
C (qxw):    0.5 s

Amazing how much faster pypy is compared to CPython running the same code!

Well, I spent an afternoon optimizing the python and JS fillers, and got a decent speed-up:

pypy:       5 s
node js:    2 s (24x improvement)

Not bad, and in the realm of being usable for an online filler app. Much of the speedup came from avoiding common interpreted language constructs (like regex) that one would never go near in C.

I cobbled together enough of a web UI for this in order to fill this new puzzle on my phone while the 4 year old was having a long snooze in my lap. Guess what 20-Down we’ve been shopping for lately?

Wooden finish

I made a new crossword puzzle, theme is pretty basic/boring but it has the dubious distinction of being filled entirely by my own software (interactively with my input). Originally 57A was going to be a literal revealer for the other themers, but I couldn’t get a good fill around that gimmick so it got simplified.

Play in the mobile-friendly iframe below or chase this link for full screen:

That time I wrote a Go server

My crossword puzzle web app grew up somewhat: now it is (optionally) backed by a database.

How we ended up here: I started this project from a completely different, and still mostly unexplored, direction: I wanted to be able to construct crosswords while on the go, since I occasionally find myself with some downtime and no keyboard. Just having a grid to type into is really enough for that — paper grids will do in a pinch, but who wants to kill trees and carry around a pencil and paper all the time.

Once I had a grid component, as a test, I built out a puzzle-solving application using 100% client-side code. That is, the JS can parse the puzzle files, render UI, save state locally, handle all the interaction without talking to a web server other than for the initial download. Then, naturally, creeping featurism took over and it became my daily solving app for NYT puzzles.

Doing everything client-side is nice because you never need the internet. Having a database backend provides some upsides though: you can more easily track progress (“how fast am I solving puzzles?”), and you can sync state across multiple devices: start on the desktop and move to phone later. Once you have syncing, you can also do collaborative puzzle solving, which is nice as the wife and I like to do the Sundays together. So if you go to this site, you can upload a puzzle, copy and share the resulting URL (randomized hash-path id indicates the ‘solution in progress’), and do an actual “crosswords with friends” unlike the branded game of the same name which is only solo play. I reserve the right to delete any data or break this feature at any time: it mostly exists for my current fickle amusement.

While the frontend is being written in a language I mostly don’t care for and don’t really know that well (ReactJS), I decided I might as well try learning yet another language on the backend. My first golang foray and a worse-is-better development paradigm led to this terrible non-idiomatic code on my github (here is the JS frontend). PRs welcome.

I’m not yet sure how I feel about Go. On the one hand, the “having types” and “lack of 2to3 transition disaster” features put it somewhat ahead of Python, and it is not as crusty as Java. On the other hand, those are fairly low bars and Go feels like a 90s language with a few minor changes. I haven’t spent enough time with it to get a feel either way about performance.

The ACPT online tournament, it turns out, uses a Java applet for the client, and it’s getting harder to find browsers that support that (I had to use an ESR Firefox release, which felt like going back in time 10 years even to this Debian-stable user). I am hoping that by next year they will have some similar kind of JS UI in place.

As far as the ACPT itself: it was a lot of fun. Out of the seven puzzles, I finished four with time to spare, my best time being just over ten minutes on puzzle number four. My worst puzzle was the first in which I completed only 50/76 answers. Overall I ended up (as of last time I checked) in 87th place out of 141, so, firmly on the left side of the curve. Oh well, plenty of room to improve.

ACPT

The American Crossword Puzzle Tournament starts tomorrow. I’ve paid the entrance fee for the online “bragging rights only” track, so I’m looking forward to seeing some interesting puzzles and to get an idea of how my solving skills stack up. Considering that competitive solvers often finish well under five minutes on a Monday and my best is in the ten minute range, probably not that great, but we shall see.

I recently started a couple of the London Times cryptic crossword books; these are hard. As in NYT Saturdays are a cakewalk by comparison. Partly, because I’m not terribly knowledgeable of British geography and slang, partly because I haven’t learned to recognize the various clue forms, and partly because they are just tough. Example clue: [Notice boy going round vehicle after parking]. Answer: PLACARD. Because “PLACARD” is a notice, and in that word “LAD” (boy) is literally going around “CAR” (vehicle), which both come after “P” which you just have to know is an abbreviation of parking. So yeah, tricky.

React reaction

An embarrassing admission to make: I wrote something in javascript.[1]

Actually, I wrote it in React, because I still think of javascript as that awful language that works differently in every browser, and so, you know, to stay relevant, I decided to learn the framework that web developers everywhere have already cast into yesterday’s wastebin for the new shiny. This, pretty much.[2]

Anyway, I replaced the third-party crossword app on my website with my own NIH version and made it somewhat responsive [3] so that it works on my phone. Also there are two new-ish puzzles since the last time I posted, dated 2016-11-25 and 2016-12-30. Each of them has its own set of problems, but I think I am at least learning where I need to improve.

To this neophyte, my impression is that using React (and ES6) is much nicer than that terrible language that they compile down to. On the other hand, the pattern of moving state up the object hierarchy away from an object’s view feels backwards and not very OO-like. Perhaps if I also used Flux then I might get enlightened on this point, but that is for another day.

[1] Here’s a nickel, kid. Buy yourself a real language.
[2] The day that my relevance depends on knowing the latest JS framework is the day that I will take up a completely different career.
[3] Anything worth doing is worth doing somewhat.

On placing letters

Work continues on my fork of the QXW crossword filler, which by now is about 50% rewritten by me and ultimately will end up looking nothing like its predecessor. Already it is a command-line, monte carlo automatic filler instead of a user-directed GTK program. Both have their uses, I think.

In a previous post, I wished that QXW supported scored dictionaries. It turns out that it does, though in my tests it gave unexpected results in many cases. I’ve reworked most of that code and am pretty happy with the results I get now. Just to cherry-pick a before-and-after example:

input:

...#...
...#...
.......
##.X.##
.......
...#...
...#...

before:

SBA#STA
BJS#AIX
WASHMEN
##AXA##
ICGARDS
IUE#AWK
PFS#HHM

after:

THE#BHE
FOR#EAT
COUNCIL
##PXA##
LETTUCE
ARE#SEE
DID#EAR

The latter grid looks a lot more like actual words, though it does still have some garbage entries.

QXW’s algorithm could be roughly stated as “find the hardest to fill cell, then fill it with the highest scoring letter, repeat.” It is a naturally recursive algorithm (implemented iteratively with stacks) that either terminates when the grid is filled, or unwinds and tries the next best letter.

I have some issues with this approach, the main one being that maximizing letter score seems unlikely to maximize score of whole words. I’ve been thinking about this problem some, including the form of optimality that I would like to achieve: maximize the sum of the scores of every word.

A simple brute force algorithm implementing this could be “fill each entry with a word, compute the score, and repeat until all words in all entries have been tried, taking the grid with maximum score.” It’s fairly easy to realize this exponential algorithm though you may be waiting a looooooooooong time for it to finish.

What I have now is something like this greedy algorithm:

  1. Base case (no more entries):
    1. if grid is filled, return the grid
    2. return None
  2. Choose the longest unfilled entry crossing a “critical” cell
  3. Fill with the next highest ranked word for that entry
  4. Recurse. Repeat step 2 until grid is filled or no more words

In practice, with a large enough dictionary, this usually terminates without searching forever but you get some junk like PXA. I have added an arbitrary upper limit at which point I just give up the search.

An important thing to note is that the problem does not exhibit optimal substructure, so dynamic programming is not applicable. For example, take this template:

    ..E
    IPA
    PAT

We can fill it any number of ways. My algorithm will fill it like this:

    THE
    IPA
    PAT

…which is terrible (HPA — [Millibar alt.?]). Much better would be:

    SEE
    IPA
    PAT

…which is what you get if you fill the child “EPA” first.

There are a couple of things at work here: first, I pick the longest entry so .IP and .PA don’t even get a chance. Does this make sense? Should I instead pick shortest entry? Entry with fewest completions? Any of these might make better puzzles or at least move the junk around.

Second, THE is really really really common. The commonest three letter word ever. The previous sentence had one and so does this one. That’s a lot of THEs. Also it is a terrible word for crosswords. [Well, looking back through my NYT database, it has been used over a hundred times: {It's definite} or {Genuine article?} being decent clues.] Unfortunately, THE is so very common and so highly ranked that practically every high scoring puzzle will have one. So, my optimality metric may be sub-optimal in that respect. Flattening the word probability curve somewhat could partially address this issue.

It is clear that we could pick worse words at some levels to get a better overall result. So I implemented a very simple monte carlo search that looks like this:

  1. Run the greedy algorithm, saving decision stack
  2. Pick a random location in the stack, and from there, pick a random word (instead of best word). Re-start algorithm from there.
  3. Repeat this zillions of times, keeping track of best N grids as seeds for future iterations

Lots of variations on the above remain to be explored. Also, this approach opens the door for taking a completed grid, manufacturing a search tree that generated it, and then optimizing it from there. Don’t like the fill in a published puzzle? Let the computer regenerate it for you.

More boring crossword stuff

Since last post, I made two more puzzles, both standard newspaper size, and I appropriated and modified someone else’s javascript so that you can fill it in on that page. Both puzzles went through two drafts where I completely redid the fill after Angeline test-solved them and found some problems.

I’m still using Qxw, now with a 130k+ entry dictionary I built from 10 years of NYT puzzles, which works OK. Still, I feel like it could help even more: for example, it could rank words by their commonality in the corpus so that you don’t use something hyper-obscure that happened to be in one Saturday puzzle when the editor was asleep; or, it could give partial fills even though it may not be able to complete the whole thing; or, it could give hints on places to place black squares to improve chances that a reasonable fill exists.

To get at the latter, I extracted the qxw filler into a command-line program that just fills templates passed to it on stdin, and, into that, piped a python script that generates random valid grids. This helped for the most recent puzzle where a few spots had only two or three words that would fit given the themers, and moving a couple of blocks around was the difference between no-fills and some-fills. A quick improvement there would be to score the resulting grids, and use a genetic algorithm to produce new templates based on their fitness.

Anyway, these various ugly hacks are now on my github.

Another puzzle

As I wrote before, I recently tried my hand with crossword construction.

This new puzzle is my sophomore effort. This one, slightly bigger at 13×13, came together much more easily for some reason (luck?). This time I did not have resort to using any unknown words, and nothing is really obscure, with the possible exception of 17-across (a common crossword answer).

As before, I mostly let the theme clues dictate the layout, while I left in a few longer stretches this time. The top left and bottom right corners were sufficiently isolated that I did them by hand before bed, then the next day I filled the longer answers and finished the bottom within about 30 minutes. At this point 3/4 of the puzzle was filled manually. Then, Qxw woke up and was able to help fill the rest (including 18-across, a nice gift which I happily accepted) — still using the standard Linux dictionary file. I reworked some of its suggestions using some of my own, but it was quite a time-saver.

In all I’m happier with this puzzle than the previous one: there’s more wordplay, better theme, nothing too difficult (I think). Comments welcome.

I guess this means the next one will be full-size.