Router redux

I had just a little bit of downtime over the last few weeks while Angeline and I reacquainted ourselves with how to take care of an infant. It’s like riding a bicycle: there are tons of things you forgot since last time.

One of the long-on-my-todo-list items finally got completed: I upgraded all of my wifi routers. I have 5: an old dual band 11n router and four TP-Link 11ac units, all of which were running some oldish build of OpenWRT.

I decided the 11n router’s time has come for the trash-heap, so I put the latest stable LEDE build on one of the TP-Links and swapped it out.

The other three are just access points without the router: they just have all the ports on the unit bridged together, connected to the router via a wired switch. I also have a mesh wifi interface up on each unit so that I could place the unit anywhere regardless of wired connectivity (though, in practice, I have wired drops everywhere so I don’t really use this.) For these, I build from source with just the required bits. I added a serial port to one of the units so I can test builds there before rolling out to the other two.

In all it was pretty painless since the LEDE build is more or less the same as OpenWRT. I did go through (LEDE) recovery once and found this fun issue:

root@(none):/tmp# sysupgrade -n lede-ar71xx-generic-archer-c7-v2-squashfs-sysupgrade.bin
Image metadata not found
killall: watchdog: no process killed
Commencing upgrade. All shell sessions will be closed now.
Failed to connect to ubus
root@(none):/tmp#

…because sysupgrade has different paths for failsafe vs not; and for some reason $FAILSAFE is not always set. Do this to work-around:

root@(none):/tmp# export FAILSAFE=1
root@(none):/tmp# sysupgrade -n lede-ar71xx-generic-archer-c7-v2-squashfs-sysupgrade.bin
Image metadata not found
killall: watchdog: no process killed
Commencing upgrade. All shell sessions will be closed now.
root@(none):/tmp# Connection to 192.168.1.1 closed by remote host.

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.

In which I ate the garden

The garden is now in its 16th week, I think. Despite the fungus problem with the tomatoes, I have to say it has been a fairly successful experiment so far: the chilies and basil have done great, while the tomatoes have still produced over a dozen softball sized fruits with lots more still on the vine. The ones in containers did less well (blossom-end rot) — I think there’s no use in venturing outside the planter box next year.

The chilacas have been the big producer. I have two plants, including one that hadn’t yet set fruit by the end of July. That latter since became top-heavy enough with peppers that a couple of stems broke off in high winds last night, so I hauled in around 20 peppers this morning. Salsa-to-be.


Some chilies



Anyway, this is what we’ve eaten thus far:

  • Tomatoes, by themselves
  • BLTs, of course
  • Caprese salad
  • Chicken with sauce chasseur
  • Sausages and mushrooms with fresh tomato sauce
  • Pepper steak (bell peppers, poblanos)
  • Pesto, normal and spicy with Hungarian peppers
  • Chilaca cheese dip (chilacas, yellow jalapeno[1] and poblanos)
  • Poppers (cherry peppers, chilacas, and Hungarian peppers)

The only fruit we haven’t meaningfully consumed in some way are the Thai chilies, which are incredibly hot. I’ll probably make those into some form of sriracha or chili paste.

[1] I think? Middle of the above photo — not really sure what these chilies are but they look similar to jalapenos on the outside and turn red when ripe, but the similarities largely end there.

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?

Garden Week 7

The garden is now jungle-like. There are real concerns that people have wandered into the garden and never returned, having lost their way out. I have a little bit of black spot on pretty much every tomato plant. My fault, I should have pruned the tomatoes more. I sprayed them with fungicide.

Even so, they have set fruit. I have a few per plant, maybe twenty in all.

Oh, I identified, and ate, the yellowish-green chili from last posting: the Hungarian wax pepper. Great sauteed in butter and spooned over salmon.

Garden update

My garden experiment continues, mostly successfully so far. Here are my notes for how it’s worked out, to remind myself what to do next year.

I built a 6′x4′ cedar box from 1″x6″ planks, all cut to nearly the right length by the helpful folks at the local home center. Some stainless steel decking screws and nearly a ton of VegMax(tm) dirt later, I had my raised bed set up.

While hardening off, the seedlings were getting watered about once every 1-2 days, with 4 cups of water per 10 seedlings. By May 28th I had them all planted out in the raised bed, staked, and mulched. At that time they looked like this:

I put a pair of tomato fertilizer spikes about 6 inches from each plant that same week. Since then I have been spraying with epsom salt every two weeks, and since last week I have started alternating that with fertilizer. The bugs are numerous but I’ve used insecticidal soap sparingly: so far, there doesn’t seem to be a ton of insect damage except on lower leaves. I haven’t pruned the tomato plants that much, just leaves that are obviously low and touching soil. As this has been a very wet spring so far, I’ve only had to water them once since planting (15 min on soaker hose).

One of my peppers (serrano? yellow cayenne?) has yielded fruit. I’m not sure what the final color is supposed to be, but I may pick it soon anyway to speed along some other buds on that plant. I also have a 1″ bell pepper on another plant. Part of the fun of using a mix of pepper seeds is that I have no idea which plants are going to produce what.

I lost one pepper seedling shortly after planting due to high winds snapping the stem in half.

The basil is doing fine, and much more prolific outdoors compared to my indoor plants.

My largest tomato plant got its first flowers yesterday. I’ve restaked some of them with 6′ spikes as they’ve outgrown the 2′ spikes already. One definite mistake I made was to plant the tomatoes with only 1′ spacing. I moved three of my smallest plants yesterday to containers so that at least one or two of the remaining garden plants will have the proper spacing. The others will fight it out, so we’ll see how that goes.

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.

Garden

Baby basil

Building on my success last year of managing to not kill a basil seedling, this summer I’ll try having a garden. To that end, I started in March with basil, rosemary, peppers, and tomato seeds. So far, some 24 plants, mostly tomatoes and peppers, have survived to the hardening-off stage and are ready to go in the ground in a couple weeks’ time.

On top of that, I have a few basil plants that will remain indoors, and a couple of very poor looking rosemary sprouts that may never reach adulthood. This represents quite a few levels up in my plant-tending acumen, as until now the only things I have been good at growing are dandelions in my lawn.

Plants