Looking Out To Sea

We got to see James Cameron’s new epic on Tuesday night, Avatar in 3D.

The three-dimensional aspect was very well done — much better than Beowulf in 3D which was hampered by terrible graphics. It looked fabulous and, who knows, maybe the added depth helped to make the action clearer.

Unfortunately the plot was fairly boring and the characters were about as shallow as it’s possible to get. In fact, it was largely the characters from Aliens — including Sigourney Weaver herself — fighting the Corporation and their unethical ways. They had a knuckle-head military guy, who appears to be a subtle blend of Duke Nukem and Kilgore from Apocalypse Now. No, I tell lie, there was nothing subtle there at all. They had a sleazy company guy and they had a mining operation set up to gather Unobtainium. I couldn’t help but snigger that they actually called their precious metal unobtainium. I wonder if they use it to make MacGuffins?

The clock applet in GNOME is surprisingly useful to keep track of friends and family in foreign places, and considerably less naff than having real clocks on the wall labelled “New York”, “Paris”.

This is a screenshot from my desktop at work, showing locations of company offices, my brother and the launch site for the NASA test rocket last month. (Don’t judge me!)

I really like being able to see whether someone is likely to be up just by looking at the map. It also makes it very clear in winter which countries get more sunlight than others (hint: it’s the ones having their summer time!). And those poor countries across the top which hardly see a ray of sunshine all winter. :-( I shall have to check in six months time how the coverage of light/dark across the globe has changed.

Anyone else got a similar gizmo which is apparently useless but that gives a great deal of excitement?

Last week we pulled out the Mathematics Notes book from secondary school¹. This was the book in which we had to write all the definitions and meanings for what we learned; and it had to be written in ink, for some reason that escapes me now.

Can you remember the formula for the volume of a sphere? Could you derive it if you had to? I’m happy to say I remembered it but I haven’t had a go at pulling it together from first principles. It’s all that integration, innit?

If you had kids in ten or twenty years’ time that were learning this stuff do you think you could help them with their homework?

I read Jane Eyre and now I finally understand The Eyre Affair. The “original” ending in The Eyre Affair is not the real one, and the one which gets created is the real one (to some approximation: there are no time-travelling super-villains).

I was getting worried as the book went on because it seemed so much like the rubbish ending from The Eyre Affair was going to be the real one. That Jane really was going to India to be a missionary’s wife to the detestable St John Rivers. But she pulls it back from the brink.

So now that I’ve thoroughly spoiled the book for you, what’s it actually about? Well, it’s your standard fare of feisty young lass being brought up by an aunt who hates her. She’s sent off to school to have some docility and meekness beaten into her, which thankfully doesn’t work. Then there’s stuff about growing up and falling in love. It sounds bland in these terms but it’s pretty riveting when you’re inside it.

I picked up two books at last month’s book group but it’s taken me a wee while to get through this first one. It wasn’t the rollicking read I was hoping for.

Douglas Coupland’s Microserfs is about a group of programmers in the early 90s who leave Microsoft for a Silicon Valley startup. It’s populated by the usual nerdy stereotypes — bearded millionaires, basement dweebs, greasy marketing guys and social misfits.

microserf (day 99)
© Jenny Spadafora

Tragically, none of it seems remotely interesting. All these smart people say nothing very interesting at all. The computer game which they create is not very interesting. Nothing very interesting happens to them in the creation of the game. It reaches completion without any hitches or even much in the way of work, as far as I can tell.

Along the way the characters have uninteresting conversations about… well, anything that strikes their fancy. As long as it remains uncontroversial and shallow they’ll talk about it — TV series, junk food, roads and buildings. But if there’s anything to be gleaned from these conversations it’s probably wrong. Even the one topic of conversation you would assume the techies could manage, computers, remains strangely beyond them. Who could seriously say something like “your body is your hard drive” who knew what either was?

The book is written as a diary, interspersed with pages of stream-of-consciousness word association. Nothing else irritated me quite as much as the word-association pages, because nothing else was quite so explicity saying look how goddamn deeeeeep I am.

In the last dozen pages the shallow characters of these people is thrown into stark relief, as something truly emotional and affecting happens. This really just illustrates how pointless the previous couple of hundred pages was, as we really know nothing about these people other than their ability to make dull conversation.

If you want to compare this tedious nonsense to something that is at least a real diary of a real programmer at a real startup, Jamie Zawinski has published diary excerpts from the early days of Netscape (then Mosaic). He at least mentions the programming once in a while.

So, now that this disappointment is over I’m going to start something which has been recommended by more people, Jane Eyre. This will also help me to put another recent book into its proper context.

Mac users may (not) want to try this:

• Press and hold the ctrl-alt-cmd keys (the three left-most keys on the bottom row)
• Then repeatedly tap the full stop key

You may stop when your display looks a bit stupid. To reverse the process hold down the three modifiers and tap the comma key instead.

Now, tell me how you would manage all that by accident. Twice. And not notice that you were doing it either time until it was already done.

Once you’ve managed that, try dragging Mail.app from /Applications onto your desktop and doing a system update in a multi-user system. It is possible (though how, I am still unsure) to update the copy on your desktop while leaving an old copy elsewhere which other users will still try to use. The old version will cease to work if the OS update leaves it incompatible with the rest of the system.

All this is possible! All this can be yours!

A couple of days ago I mentioned implementing simulated annealing for my comicbake program so I thought I would take some time to explain what that means and why it’s helpful. I’m sure there are some curious souls out there wondering what it’s all about!

He is seeking it, seeking it, all his thought is bent on it.

Let us start with a discussion of search.

Search is what you do when you don’t know how to get something by straightforward means. The type of search you do depends on what you’re looking for. Sometimes you know the goal but want to know how to get there. How to get from A to B is literally the problem solved by route-finding programs like Google Maps. The other type of search is where you don’t know what the goal is but you know what properties it has. You don’t know what your next chess move might be until you examine the board, but ideally it would involve not losing any pieces, and maybe gaining one of the opponent’s pieces.

Some searches are completely “uninformed” and will examine all possible solutions. This is obviously quite slow, so is avoided in all but the smallest of cases.

A simple improvement is to assume that any small change that improves the current solution can be used as a starting point to hunt for another small change. This is called “hill-climbing”, as we slowly ascend the terrain of the search space towards the highest point. An uninformed search would walk back and forwards across the landscape in a regular pattern as if looking for a contact lens. Hill climbing would never go back down hill, but follow the steepest course up hill.

The Gloaming from Beinn Bheoil.
© Iain Gillespie

The trouble with hill climbing, as any ramblers out there will know, is the minor summits. You get to the top of a small hill which seemed so all-encompassing, and you realise it actually stands in the shadow of a more massive peak. And to get onto that peak, you have to go downhill. Standard hill-climbing search doesn’t know there are other peaks and won’t ever go downhill to find them. It gets stuck in the foothills.

Simulated annealing is one further improvement to standard hill climbing search. It allows us to go down instead of up sometimes, if the direction we have chosen takes us down. We won’t always go downhill, as we want the gradual trend to be upwards, but a small proportion of downhill treks will help us avoid being trapped on the little peaks. To continue with the hill-climbing theme we can decide that the chances of going downhill as well as up should depend on how energetic we feel. Early in the day we may be willing to strike out in search of new peaks, but as the day wears on and the legs begin to tire, the adventurous spirit wanes.

Search with simulated annealing helps to avoid being trapped in locally good areas. The name in fact comes from the process of heating worked metal and cooling it very slowly — the molecules in this case are affected by temperature, allowing them to break out of their warped crystalline structure and slowly form better bonds as the temperature drops.

There were minstrels and mountebanks and harpers and clowns

What does all this have to do with where we started? With comic strips? You can probably see, in some vague way, how the search process might work if we actually wanted to find the tallest point in a range of hills, but how does this translate to the actual problem at hand?

In case there is any confusion, the problem at hand is choosing the best location to place speech bubbles on an individual panel of a comic strip, so that none of the bubbles overlap each other or hide the characters’ faces. Rather than jumping straight in to the solution we’ll work up to it slowly.

It helps to consider the problem in terms of the degrees of freedom we have at any point. How many things can we change at any step of the problem, in order to make the situation better or worse (ie, to ascend or descend our metaphorical hill)? If we were doing an actual hillwalk we could define our location in terms of x and y co-ordinates (such as latitude and longitude), and for every co-ordinate there would be a unique, corresponding height. Think of it as an association from co-ordinate to height:

(x,y) → Height

Here we have two degrees of freedom, as we can change each of the x and y co-ordinates independently to change our height.

In some situations you have more degrees of freedom. If you’re walking around your house looking for mobile phone signal you might also wave the phone in the air, or stand on the kitchen table or anything else if you think it will work. In this case you’re changing x, y and z co-ordinates. The value which changes is signal strength, and you’re trying to find the combination of co-ordinates which maximises signal.

(x,y,z) → Signal

This situation has three variable aspects, but other situations will have more. Every time we increase the number of variables the problem gets harder. Next you might imagine having to solve this problem to get several compatible solutions. If two people want to use their mobile phone at the same time they both can’t stand in the same spot. Now we need two places where the signal is strong! We can increase this to three, four, five…

But let’s pull things back a bit. If there are two mobile phone users in the same general area they both want good signal. We’ll say for the sake of explanation that we have three people waiting for really important calls:

Phone1(x,y,z) → Signal1
Phone2(x,y,z) → Signal2
Phone3(x,y,z) → Signal3

We want to maximise the sum of all the signals, so that everybody gets a good quality connection.

Maximise (Signal1 + Signal2 + Signal3)

To maximise the signal across all the phones we still only have the options of changing x, y or z for each. If we number each co-ordinate of each phone — so that Phone1 is located at point (x1,y1,z1) — we can see that we really need to maximise the following function:

(x1,y1,z1,x2,y2,z2,x3,y3,z3) → Overall Signal

That’s a lot of choices! And the more things there are to change, the harder the problem is and the more likely that we’ll waste time changing things which don’t affect the overall problem.

(The astute might have noticed that if everyone starts off with okay signal, we might be able to give someone really great signal at the cost of bumping someone else into a signal black hole. Overall the sums might not change, or they may prefer the unfair arrangement to the fair-but-mediocre one. We can avoid this by careful planning.)

Johnny Boo, Twinkle Power
© John Cooper

Now back to the problem again. We’ve got a selection of bubbles that all have to occupy unique places on the comic panel. There are a few places which they definitely can’t occupy (the space occupied by characters’ faces) and they also shouldn’t be out of order otherwise the comic won’t make much sense.

This is more or less the same as the mobile phone example without the ability to change z co-ordinate. For simplicity we actually invert the sense of the search — what we’re trying to do is find sea-level rather than the highest peak, though the principle is identical. To do that we invent a set of guidelines, and breaking each guidelines induces a penalty, or “cost”. The search process is trying to find an arrangement which reduces the cost to zero by not breaking any guidelines.

If we’re finding the ideal arrangement of three speech bubbles then this is the function we have to minimise. Notice the similarity to all the others before:

(x1,y1,x2,y2,x3,y3) → Cost

To calculate the cost we add up all the individual penalties which would each contribute to a “bad” solution:

• Overlapping another bubble induces a penalty. There’s an additional penalty for each bubble that overlaps another, which reduces the chances of them all piling up at one spot on the image.
• Overlapping a character’s face induces a penalty.
• Being out of order induces a penalty proportional to how far out of order a bubble is. If the first bubble appears sixth that’s really bad — it’s at totally the wrong side of the image — so we need to ensure that kind of thing doesn’t happen.

With these simple rules we run the computer through the simple procedure of moving the bubbles randomly, assessing their cost and then repeating. They slowly settle on their chosen state and the search process ends.

Along the way we’ve been keeping note of best overall position of each speech bubble. If it’s the current position we leave them there, but if they have been rearranged since then we revert to the overall best formation.

This search procedure is widely used for a lot of difficult problems — problems which would take too long to solve exhaustively. It’s also surprisingly simple to implement the core. The hard part is coming up with suitable cost measures which are quick but effective.

A conversation over IM earlier today. I’m the guilty D in this exchange.

M: Then all you need is a sofa on wheels, and you can really travel in style.

D: I know where I can get one of them! Ssofa so good you might say, but how do I couch my idea in more marketable terms? I don’t want to lounge around all day, I want to chaise the big money!

M: Those were terrible.

D: You can’t deny the joy of punning — have a go, you ottoman.

M: You are a bad man.

D: It was all going so well, and then I just went and put my futon it.

M: I’m going to report you to the ‘Law and Order: Misuse of Puns’ division

D: Will they lock me up and take me away in divan?

Five minutes pass.

D: Oh no, I’ve killed him.

It’s been a busy few days on the code front. After coming to no real conclusions about the best way to lay speech bubbles out on a page deterministically, I’ve decided to explore the issue of search. I’ve knocked up a quick implementation of simulated annealing, which I’m now weaving in to rest of the code.

Like all random search methods, simulated annealing lives or dies on the quality of the heuristics you can provide. Since you don’t generally know the answer when you’re solving the problem you can’t test any intermediate solutions in the obvious manner. You instead have to test properties which you expect the solution to have. In this case, I have to test that, for example, the speech bubbles are laid out sequentially on the page. Any pair of speech bubbles which are out of order will ruin the sense of the comic, so this is fairly important.

There are other measures of goodness (or badness) of a solution, and some may be more effective than others. This has to be offset against the cost of computing the worth of each solution. If it takes 5 minutes to generate one scene it’s no use to me. Most people would rather place bubbles manually than wait this long. So speed is similarly important.

Right now I’m just waiting. I want to use the Mersenne Twister PRNG from Hackage, and it’s just my luck that the Hackage server appears to be down at the moment:

$ cabal install mersenne-random
Resolving dependencies...
Downloading mersenne-random-1.0...
cabal: Error: some packages failed to install:
mersenne-random-1.0 failed while downloading the package.

I’m optimistic about the results from this approach. I’ve been doing some reading on graph visualisation and also map labelling, which both have a lot in common with my problem. Simulated annealing appears to be effective in both instances, so I look forward to seeing what it produces in the end. When I get my shipment of random numbers…

Whenever you have to configure something on a computer — especially in the case of wireless networking — you inevitably come across strange terminology mismatch. Each person that designs a user interface decides that the technical terms which the user needs to enter/know about are not friendly enough, so they get “translated” with some arbitrary scheme. Which is why the same information will be called password or passphrase or secret or authentication key depending on who tells it.

Maybe they have a point in some cases. If you’re steeped in the jargon none of it seems strange or frightening. But I can’t help thinking that maybe there would be less confusion if everybody used the same words to describe the same thing. From a quick check, neither the GNOME or Apple style guides deal with this issue.

The greatest example of this strange folly, and how it makes everything harder for everyone, is when you have to configure a standalone email client. None of the major ISPs seem to give out the standard details any more. Instead they have screenshots and step-by-step guides — a different guide for each popular mail client — telling how you how to enter the same data into differently-named boxes. Obviously this makes the problem of configuring an “unsupported” client much harder. Transferring details from one working mail client to a new one is even harder, as you ultimately have to guess which features the old mail client enables automatically, and vice versa. Nightmare.