Sub five

I am mostly keeping up my daily ritual of doing the NYT crossword and generally getting faster, with most of my solves now below my historical average, but it’s getting harder to set a personal best. Every once in a while a puzzle comes along that is abnormally easy for the day-of-the-week, so that my best times are fairly far from the mean. It would be interesting to see the whole distribution over time, but as far as I know that data is not available.

Anyhow, determined to meet my entirely arbitrary goal of a sub-5 minute NYT crossword solve, I sat down today and did eleven Monday puzzles in a row. The eleventh (April 13, 2020) clocked in at 4:48. Success! When you do them back-to-back like this, it’s comical how frequently the same answer will appear from one to the next. Not just well-worn friends like ASEA, but slightly further out words: for example OKRA came up in almost the same grid location between this one and May 11, 2020. The other interesting thing about speed solving is how infrequently I’ll even notice the theme. I only just now went back to see the theme on this puzzle. DROPS/OCEAN were a nice touch.

I put some letters in squares

This weekend I burnished my geek CRED (clued as such in some puzzle) by participating in the virtualized 2021 American Crossword Puzzle Tournament. This year, they used Not-My-Software, which is a good thing because I would hate to be on tech support the year everyone that had to do virtual crosswording for the first time. I solved 6/8 puzzles cleanly which is enough to land just above the bottom 20% of the entrants! Of the misses, puzzle 5 was a beast, while puzzle 7 was pretty nice, but I didn’t get the theme quickly enough and lost five or ten minutes feeding the youngster breakfast during the solve. My fastest time was 6:58 on the (unscored) final which is no great shakes compared to the field but pretty good for me.

In other news, github thinks that I helped make the Mars helicopter fly. I’ve no delusions that my meager contributions to Linux are even compiled into whatever image that drone is actually running, but all the same, very cool!

35 seconds

After a bit of a break, I am back to doing the NYTXW every day, except when I forget. Out of laziness, I am just using their webapp instead of my own, thereby saving at least two clicks. As a result, I get their fancy stats deal for free.

As a completely pointless milestone, I’d like to break the five minute barrier sometime this year. I got pretty close with last Monday’s puz, and it didn’t feel like it was possible to type any faster. But I understand that in the competitive world, times are typically half that. Five minutes is somewhere around four seconds per answer, seems doable.

2019 Crossword Tournament

The American Crossword Puzzle Tournament starts this weekend. Once again, a version of my xword webapp is being used, with only a few minor changes since last time (sorry).

I did almost no puzzling last year, so I’ll give it a go, but I’m not expecting to finish in the top 100 this time around. Good luck to anyone participating!

More filler

I noticed some HTML5 crossword construction apps have sprung up over the last year, so I no longer have first mover status on that. Also their UIs are generally better and I dislike UI work, so it seemed reasonable to join forces. Thus, I sent some PRs around.

It was surprising to me that the general SAT solver used by Phil, written in C compiled to asmjs was so much slower than a pure Javascript purpose-built crossword solver (mine). I assumed the SAT solver might make certain search optimizations that could overcome the minor optimizations related to mine being only a crossword solver. So, yay, my code is not that bad?

In these apps the filler runs as a web worker so even when slow it isn’t too noticable (except for hogging a core).

Anyway you can try out my filler today with Kevin (filler code is here, which is exactly the code in my own app except with some janky whitespace because I stripped out all flow annotations).

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.