there is a great difference

For some reason it occurred to me tonight to find the longest common substring in various classical novels.

There’s a bunch of interesting algorithmics involved here. The naive O(n3) approach is slower than a slow snail on a slow day. Dynamic programming gets you to an easy-to-understand O(n2) solution, but that’s still impractically slow for story-length strings. Things start getting really clever with Ukkonen’s algorithm and now we’re into practical runtime territory. You could get a constant-factor speedup by working on sequences of intern’d words rather than chars, but the above algorithm runs in under a minute as-is so I didn’t bother.

I downloaded and normalised some books from Project Gutenberg and ran my longest-common-substring on them.

  • Emma vs Pride and Prejudice: “when the ladies returned to the drawing room”
  • Dracula vs Frankenstein: “between two and three in the morning”
  • Dracula vs Pride and Prejudice: “but there was much to be talked of”
  • Dracula vs. Fiat Money Inflation in France: “the difficulties and dangers of”
  • Treasure Island vs Dracula: “threw himself on his knees and held”
  • Treasure Island vs Jekyll & Hyde: “and to make assurance doubly sure”
  • US Constitution vs Dracula: “to the best of my ability”

.. and last, but most self-referentially not least …

  • Emma vs Frankenstein: “there is a great difference”.

High precision wheels

This evening I was truing one of my bicycle wheels. I started out with a truing stand – literally, a metal bolt identifies high spots on the rim by rubbing against them. I managed to get the wheel pretty true. But then I remember that I also have a DTI, accurate to 0.01mm. It’s like a red rag to a perfectionist. After a bit of futzing with that, I could get the wheel true within ~0.1mm and so I stopped there. The first time I hit a bump it’ll blow that precision away! But it got me thinking … how you could automate this (rather laborious) wheel truing task.

After a bit of thinking, I realised you can utilise the fact that the wheel is made of conductive aluminium, and therefore can act as one plate of a capacitor. Sure enough, wikipedia agrees. Unfortunately, the sensors in question are quite pricey – $120 – so I doubt I’ll ever get one.

Could I make a homebrew version? I think it’d be hard. Given how small a wheel rim is, you’d probably only manage a plate 10x10mm. If you got the wheel true within 1mm, your plate distance would be maximum 1mm. So that gives a capacitance of 0.88pF. That sounds pretty small to my ears. Charged up to 5v and draining through a 1M resistor, it’d drop to around half its voltage in a mere 0.88 microseconds.

The typical low-tech way to measure unknown capacitances is to stick it in as part of the timing circuit for a 555 astable and then measure the resulting pulse frequency. Fine in theory, but I don’t own a frequency counter .. and also the frequency would be in the megahertz range.

Microchip have a nice technote describing how to use a PIC microcontroller to measure small capacitances – and when they say small, they mean sub-pF. I’m still digesting that.

I’m tempted to skip all the tricky stuff and just build a larger scale version to test the concept … just to see if I can make the basic method work at all. Whilst I started off thinking about measuring distances, it occurs to me that a large-scale variable-capacitance controller oscillator is … a theremin!

Timelapse bread

Made some tasty baguettes today, decided to do a webcam timelapse of the first and second rises:

Dough rising over 40 minutes:

Baguettes doing their second-rise over 50 minutes:

Cooking with Science

For the last couple of years, I’ve cooked lots of bread. Mostly, I’ve been creating my own recipes and cooking the bread “until it’s done”. But when I follow recipes, like the ones in this awesome book it’s clear than my gas oven is way hotter than it’s meant to be. Sometimes bread takes days to prepare, and I reaallly don’t want to burn it! So, out with the science and in with an oven thermometer!

Here’s what the temperature did when set to gas mark 6 … which should be 200C:
Gas Mark 6

I always knew that electric ovens take ages to heat up, but I was surprised to see that even gas ovens take about 10 mins to get up to temperature. However, the oven didn’t just heat up to 200C. It kept going … and going … all the way up to 228C. In old money, that’s gas mark 8, a full 2 marks above what I’d set.

I checked a few other settings, and it was pretty consistently out by two:
My Oven

I had always assumed that ‘gas mark’ was a funky old scale, but thanks to wikipedia and R’s plot function, it’s clearly nicely linear:

Gas Mark vs C

So, this is all useful information to help cook tasty things. But it’s a little bit tempting to also measure how quickly the oven cools down, and thereby model heat-loss. Or, to use the gas meter to see how much energy is going in, thereby indirectly measuring the average heat capacity of the (empty) oven. And so on …

Or, I could make some more bread. 🙂

Tracks on a plane

On my last flight home, I found that the GPS on my HTC Wildfire phone works fine in ‘airplane’ mode. It is, after all, only a receiver. I had to hold it up to the window for a while to get a fix on enough satellites, but after that it worked well for a while. The plane was flying at about 500mph, keeping to the same altitude pretty closely. I had the OSMAnd (open streetmap) app installed, and was able to see exactly where we were and just how quickly a plane flies on a streets-and-towns level map.

It’d be cool to have an augmented-reality version that let you point the phone camera out the plane window and tell you what towns and hills you were looking at. Not sure if the existing apps will work at 30,000ft or not!