The latest on letters in squares

Somewhere along the way this summer I quit doing crosswords for a while. Maybe my gardening hobby took over, or I didn’t want to touch the computer after work, or perhaps pandemic has been too much of a stressor, or maybe it just felt too much of an obligation to keep up with — whatever the reason, I fell out of practice a bit. Visualized, my puzzling activity for 2022 looks like this:


legend: white = streak meaning I solved it the day of, gray = I did it (possibly much) later, black = still haven’t opened it

I also skipped entirely the ACPT this year.

Recently, though, an LWN story about Gnome Crosswords rekindled my interest a bit. A few of the puzzles from my website have been merged into this project, and I have another few sitting around that I will polish up and submit someday.

This was a good exercise to clean up some awkward fill:

  • BOB / MAKO cross to BIB / MAKI; for this rejected-from-NYT puzzle, I still felt bad about putting my own name in it; also I guess MAKI is more common for anyone who has ever eaten sushi
  • PETRE [Architect of Christchurch Basilica (?!)] / GAR to PETME / GAM in this puzzle. Although GAM feels objectifying, I clued it as bygone film noir slang. Anyway PETRE was so terrible that it had to go.
  • Same puzzle, AKA / OKE [Just great, in old slang (?!)] to ADA / ODE. People running Linux are quite likely to know Ada Lovelace, besides which it is in mainstream puzzles by now, and OKE is very O_o.

There are still some lousy answers in both puzzles, driven by grid shape so fixing would require a lot of work, but these tiny tweaks make them a lot less bad.

Meanwhile, I’ve completed most of the early-week puzzles over the last few weeks, chasing the 5-minute mark on Tuesday puzzles (personal best currently 5:07) and the 4-minute mark on Mondays (4:12).

The discussion in the LWN thread was about crossword file formats, and since Gnome crosswords uses ipuz, I dusted off XwordJS and added ipuz support, and even wrote a couple of test cases. For my money I still prefer XD, much the same as I prefer Markdown to HTML, which brings me back to the image at the beginning of the post.

When I was a wee lad, we would write programs to make images, and all libraries sucked in these times so we would often roll our own. As an example of sucking, this is from a real-life comment in actual code:

 * We use C's setjmp/longjmp facility to return control.  This means that the
 * routine which calls the JPEG library must first execute a setjmp() call to
 * establish the return point.  We want the replacement error_exit to do a
 * longjmp().  But we need to make the setjmp buffer accessible to the
 * error_exit routine.  To do this, we make a private extension of the
 * standard JPEG error handler object.  (If we were using C++, we'd say we
 * were making a subclass of the regular error handler.)

Being poor students at the time, we could not afford to spend our hard-earned money on compression, decimal to binary conversion, or complex serializers, so we did the simplest possible thing that worked: we wrote out P[BGP]M text files (we were profligate when it came to disk). My little visualization was done just in this way: open up vim, a few macros later, a PGM file is born. I let gimp handle the hard work of rotating, scaling up, and converting to PNG, but ImageMagick probably would’ve worked just as well.

P2
7 38
255

128 128 128 128 128 128 255
255 255 255 255 255 255 255
[...]

There is a lot to be said for plain old text, and no, that does not include JSON.

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: