Rosio Pavoris a blog

Last week my room was repainted (which involved taking down about a million pictures, filling four times as many thumbtack holes, and getting rid of the wallpaper), which is nice. Because it had to be done before the furniture we inherited from my grandfather arrived, it’s kind of rushed, but overall it’s much cleaner. One side of the room is light grey (like the ceiling), and the other is “taupe” (#50404D, actually purple taupe).
It also covered the fungus problem quite neatly (which is one of the reasons we painted rather than wallpapering again; because of the fungus my ceiling had to be repainted about twice a year so far, but you can’t replace wallpaper that easily), and apparently the cause of it has finally been established (a clogged drainpipe causing rainwater to drain into my walls), and it’s being fixed in September.

Then the aforementioned furniture arrived, of which I got some.¹ I should really take another picture of that second one; bright flash doesn’t do it justice, and everything looks tacky if you fill it with DVDs.²
Both of those are considerably older than I am and easily the most expensive things I own, so I question the wisdom of putting them here before fixing the drainpipe, but at least now I can get rid of that hellish chair without feeling guilty.
There’s also tens of thousands of monies worth of new furniture downstairs, which looks incredibly out of place. We finally got to the point where nearly all of our furniture matched and was kind of modernish, and now we have tons of antiques cocking things up again. Maybe it’ll be better once the rest of the art actually gets here.

All of this has meant I haven’t been able to get any real work done, but at least things should quiet down now. My sister is in France right now, so it’s quiet enough to get some rest now. I hope to be rested by the time everyone leaves for Malta in August, anyway. Pity the neighbors persist in their existence.

Yesterday I realised I pay our esteemed host $23.40 a year for AWStats, but it’s only configured for the www. subdomain, so I went ahead and wrote a config file and set up a cron job to get it to work for my own subdomain. Manually, because cPanel is still a piece of shit.
So is AWStats, for the most part, but I wanted it because unlike Webalizer, it keeps track of OSes, and it has prettier graphs.

Preliminary results:

Of the 31.2% of my readers that use Linux, 74% use Debian or Ubuntu, with the remaining 26% using “GNU Linux (Unknown or unspecified distribution)”.
All of the Mac OS users use Mac OS X, unsurprisingly, but it doesn’t specify specific versions.
53.9% Windows users is disappointing, but at least XP users still outnumber Vista users about three to one. And one guy is still using Windows 98.
I desperately want to believe the 9.8% people using “Unknown” are on Plan 9, but looking at the user agent strings, most of them seem to be people on mobile phones and PSPs, and a handful of bots not properly recognised as such.³
This is only about a day’s worth of logs, though, so I’m sure it’ll change.

(The BSD dude is on FreeBSD, by the way.)

In completely unrelated news, I redid the blogroll in the sidebar, and I’m looking for opinions. →
If you can’t see it, you’ll have to go to the main page, because it’s invisible for individual post pages.
With the increasing tendency towards text-heavy posts I figured some more pictures would be nice. It did mean cutting fourteen links, but most of those were either dead (either in the actually-gone sense or the not-updating-anymore sense, though the latter is still true for most of the ones that survived) or mainstream enough that they don’t need me linking to them. If you were one of them and want to be linked again, post moar and send me high-contrast pictures of yourself.

Anyway, /prog/ is back, so fuck this blogging thing.

¹ More pictures. I enjoy writing desks even though they’re carrion feeders.

² I’m getting a separate DVD rack, I think. Since that closet replaces one closet and one set of shelves, I have some room for more furniture anyway.

³ As far as browsers go, Firefox is unsurprisingly the most popular, with exactly 60% of my visitors using it. 25.4% use IE, despite the helpful advice these people get at the top of the page. 55.9% of IE users use IE7, so I guess that’s alright. This does, however, mean that 11% of you are using both Windows and IE6, which is very, very sad.

I was browsing Reddit (with the quality of Slashdot’s editing going from utterly crap to considerably worse, and the discussion going from merely ignorantly libertarian to frothing-at-the-mouth ultra-conservatism, I need a new place to get my tech news from, so I’ve been trying a few other websites), and I came across this article on the “eight ball problem”.
If you’re averse to clicking links, the idea is that you’re given eight balls, one of which is slightly heavier than the others, and a set of scales. Your task is to find the heavier ball in as few weighings as possible.

I’ve been told it’s a popular job interview question, and the author of the article is probably right in saying that most computer science types would naturally try a binary search, which would get you the heavier ball in three weighings.
He then goes on to describe an algorithm that does it in two weighings: first you weigh balls 1 through 3 against 4 though 6. If both sets weigh the same, the heavier ball is either 7 or 8, and you just weigh those against each other. If not, take the set of three that was the heaviest and weigh the first ball against the second. If they weigh the same, the heavier ball is the third. If not, you have found the heavier ball.

This is indeed faster for eight balls, but is it faster in all situations, and how much?

The algorithm can be generalised as follows:

1. If you have one ball, you are done. It is the heavier. Otherwise:
2. Make two sets of n balls where n is the number of balls divided by three, rounded up. The third set, which may be empty, is the remainder of the balls.
3. Weigh the first set against the second.
4. If they weigh the same amount, your new set of balls is the third set. Otherwise, the new set is the heavier of the two sets. Discard the other balls.
5. Go back to step 1.

The astute among you may have noticed that while the binary search algorithm will always finish in the same time, this isn’t always true for this other algorithm; its best- and worst-case performance times differ for sets of balls that aren’t neatly divisible by 3 all the way down.
It’s not going to be a huge difference, especially for small amounts of balls, but it’s good to note.

The binary search will always take log₂(n) weighings to find the heavier ball, where n is the number of balls. It’s not immediately obvious how many the new algorithm will take, so let’s just write a program simulating it and run it a bunch of times.
While this seems an obvious place to use a functional language, I’m sorry to admit that I don’t yet feel comfortable with Haskell, and Scheme isn’t very legible, so I did it in Java.¹
That program outputs data in a gnuplot-friendly format, so let’s use it (gnuplot doesn’t like logarithms in base 2, but you’ll remember from your high school maths that log(n) / log(2) is equivalent):

We noted earlier that the second algorithm won’t always take the same amount of time, so the plotted line is the average time it will take. If you want to see the best- and worst-case performances plotted as well, you can do so yourself. The output data is here.

So yes, it does look like this algorithm is always faster, though binary search should really be fast enough for most purposes, and it’s somewhat easier to implement.
For 10,000 balls, this algorithm takes 8.84 weighings on average (and 9 in the worst case), while a binary search takes 14. For a million, it takes about 12.95 (13 in the worst case), and a binary search takes 20.
Unless someone is killing one of your loved ones for each weighing, I wouldn’t bother.

¹ Even as Java goes this is slower than it could be. For legibility’s sake I’m using Ball objects of my own making when I could be using ints or even booleans to represent the balls, for instance, and a getWeight() method call rather than a not-that-much-longer inline calculation. I invite you to write your own, better code in your favorite language.
Update: Like Python, for example. That was surprisingly painless, especially considering that it’s the first thing I’ve ever written in Python. It took maybe a third of the time it took me to write the Java version to write, and it’s not even that much slower, even though it’s an interpreted language.

In which I make myself useful. Also known as: adventures in procrastination.

I’ve been meaning to learn either Hebrew or Yiddish for ages now, and apparently an important first step to that is learning how to read the Hebrew alphabet. So obviously rather than just spend an hour or so learning the alphabet, I spent an evening writing a program to help me learn the alphabet, and then another one expanding it to be useful for other people as well.
The result is Grapheme, though really, it can be used for more than just graphemes.

The basic idea is that you load a set and then it shows you glyphs from that set and prompts you for input. You enter the name of the glyph, and then it tells you if you got it right or not, and asks if you want to continue. If you say no, it shows you your total score and exits.
Relatively straightforward. If you really want to master a script, it’s usually more important to write than to read, but I guess it can still be useful.
If you have difficulty running it, check the readme file.

The sets included with version 1.0 are:

The readme file has instructions for making your own sets, if you should want to. If you do make one, and you think other people might be interested in it, by all means send it to me and I’ll add it to the lot.
Or if you’d like to have a set included but lack the ability to make it yourself, ask me and I’ll see what I can do.
I intend to add a few more sets myself in the near future (particularly Arabic and a score of Indian scripts, though I’m not sure how they work and if they’re at all suited to this sort of thing).

The source code is included in the .jar file (and if you don’t know how to get at it it probably won’t be terribly useful to you), and is licensed under the GPL.

(Incidentally, this is my thousandth post on this blog. I need a better hobby.)

Update: I’ve added three sets: Arabic, Bengali, and Ogham. The Bengali set only includes vowels and consonants, not modifiers or conjuncts, because I’m not sure how important they are. Feedback wanted from someone who actually knows anything about this, plz.
Version 1.1 also has a system-dependent Swing Pluggable Look-and-Feel, because Swing’s default look annoys me. If Windows’ annoys you, use a real OS.

Ⅰ

Hear the sleepwalkers with the bellwethers —
Silver bellwethers!
What a worship of mesh their memo foretells!
How they tinkle, tinkle, tinkle,
In the icy airhead of nightingale!
While the starknesses that oversprinkle
All the hedges, seem to twinkle
With a crystalline delivery;
Keeping timetable, timetable, timetable,
In a soundness of Runic rice,
To the tiredness that so musically wells
From the bellwethers, bellwethers, bellwethers, bellwethers,
bellwethers, bellwethers, bellwethers —
From the jitterbug and the tipper of the bellwethers.

Read the rest of this entry »

They’re consistently described as being three apples tall (“hauts comme trois pommes”; apparently including their hats). If these apples are regular apples, that means they’re ten inches to a foot tall. Given the size of their heads, they’d probably weigh well over ten pounds each.
They’re enormous.

You could say that they’re supposed to be those small sour apples, which would make them closer to six inches tall and put their weight at under two pounds, but that doesn’t appear to be what Peyo had in mind.
Consider this size reference chart used by the animators of the Hanna-Barbera series (courtesy of these people):

They come up to Gargamel’s hideously deformed knees!
They’re usually a bit smaller in the comic itself, but not much:

People don’t generally realise how big they are, and when told their first instinct is to assume they’ve always been drawn small and the description is wrong, but the comics are pretty consistent, and while the animated series has serious issues with proportion in general, they usually get it mostly right as well.

Note, incidentally, the gargantuan mushrooms in which they live.
Given the fact that there are ninety-nine Smurfs (including Smurfette, though not including the kids or Grandpa; actually, the issue of counting the Smurfs is a tricky one, though it’s always around a hundred), none of whom ever appear to be sharing houses, that means there are at least ninety-nine of those mushrooms (and probably rather more), which seems to give the village a surface area of about 5,000 square feet (in the comics; presumably more in the cartoon). Small for a human town, but huge for a forest clearing trying to stay out of sight.
Add the dam and Miner Smurf’s mines to that and the Smurf civilisation becomes really hard to miss.

If I were Gargamel, I wouldn’t just storm into the Smurf village and expect to get away without physical harm to myself or my cat, my point is. An individual Smurf might be handleable, but even a handful of them could do serious damage.
Though really, the Smurfs themselves don’t even seem to realise this. I’m sure there’s been at least one comic where they’ve fought back, but they almost always just panic and run.

The entire Smurf narrative would make a whole lot more sense if the Smurfs were actually tiny.
These are the things that keep me up at night.

Edit: Okay, having found and reviewed my actual comics, I’d like to retract my earlier statement that they’re consistently three apples tall there too. In fact, it’s more like one to one and a half.
What actually happened, as far as I can tell, is that “haut comme trois pommes” is a French expression just meaning “not very haut at all”, and it doesn’t imply any actual comparison to apples. Hanna-Barbera’s translators didn’t realise this, though, so they produced their hideously oversized Smurfs, forever scarring a generation of impressionable children prone to overthinking cartoons.
My respect for Peyo is restored.