Archive for November, 2009

Movember: Day 20

Day 20

I’ve started giving some consideration to what to do with my face after Movember. The easy answer is to grow back the full beard… but I’ve had that for years, and it feels like this was a good excuse to do something different.

At the moment I’m thinking maybe a goatee. That means it can roughly keep its current shape, but without quite so much bleeding from the chin.

No comments

Movember: Day 19

Day 19

Ugh. The temperature has reached the mid-thirties for most of this week, and looks like it’ll easily do it again today.

At least the air conditioning in the office is working. That’s unusual at the best of times, but this would be a really bad day for it to give up.

Also, my current relative lack of facial hair turns out to be a good thing in hot weather. Who’da thunk it? Maybe the timing of Movember isn’t a complete coincidence, at least in the southern hemisphere.

No comments

Movember: Day 18

Day 18

Okay, yesterday – this is important everyone – yesterday at work I actually did, in real life, the Frodo-flipping-the-ring-in-the-air-and-catching-it-on-one-finger thing.

With witnesses.

And then, after a few tries, I did it again. Which actually (according to DMM at least) makes it less of an achievement – if I’d done it once it would be a billion-to-one fluke; doing it twice shows that it’s easy.

Also, I spun it flat (around the y axis) instead of end-over-end (around the x axis). That may have had something to do with why it was… you know, possible at all.


Movember: Day 17

Day 17

I’ve reached the conclusion that nobody can tell if your facial hair is asymmetrical. There are very few times during the course of normal social interaction that you stare at someone dead-on and don’t move your head for long enough for them to compare the sides of your face, and they stare back at you long enough to notice.

Maybe if you were gazing lovingly at someone over a romantic dinner, maybe, they might get a chance to weigh up your facial hair.

That’s probably the main reason that fancy restaurants have dim lighting.


Tournaments as sorting algorithms

From a discussion in our Magic group…

You can think of a tournament as a sorting algorithm for ordering the players by skill, where each match is a comparison.

There are a couple of differences:

  • Many tournaments only determine a partial ordering – for example, if it’s only looking for a winner.
  • Comparisons between two players aren’t guaranteed to be consistent. One player could beat another in one match and lose to the same player in another match; or you could have a scissors-paper-rock type of cycle between three or more players.

For current purposes, we can ignore the first difference and only talk about tournaments where the goal is to rank all the players.

The second point is more interesting. A sorting algorithm assumes that there’s a complete order over the elements, which there isn’t in this case. We could either make it somehow resilient to noise, or find some way to break cycles, all of which is complicated. Or we could let the algorithm do whatever comparisons it does, and if it happens to be inconsistent with previous results then hopefully it’ll be resilient to it somehow. (In the worst case, a dumb-ass algorithm like a naive bubble sort might not terminate.)

Or – and this is why I’ve been thinking about it since this afternoon – we could only make comparisons for which we can’t already infer an answer.

This has some advantages. It means that we can never reach a contradiction where one player beat another but ended up ranked lower than them. It puts a natural limit on the length of the tournament, because the more matches you play, the more potential match-ups become redundant, until there are none left. It might mean that a player can get an unusually low ranking from a bad match-up early on, but that will tend to happen in a scissors-paper-rock sort of situation where no ranking is going to be consistent anyway, so one solution will be as good as any.

So, some solutions that came to mind…

A quicksort tournament would start by choosing one person as the pivot. Everyone plays a match against that person. Then the other players split off into two pools – those who beat the person, and those who didn’t. (Let’s assume there are no draws.) Each of those pools chooses another pivot and repeats until everyone is either a pivot or in a pool by themselves.

There’s an obvious downside to this in, for example, Friday night Magic – the first pivot has to play at least two matches (if those two players either both win or both lose) before anyone else can do anything. Another downside is that there’s a lot of variation in how many matches each person plays – the first pivot plays n-1 matches, but someone else could potentially only play one match (if they’re the only one who beats or is beaten by the first pivot).

(Actually this isn’t necessarily a bad thing for our Magic tournaments – the conversation started with someone pointing out that we have different amounts of free time to play with – but it would be nice the variation wasn’t too big. It would be even nicer if you could direct the extra matches towards people with more time to play.)

A merge sort tournament would avoid some of the first problem – players would pair off at the start of the night, and bottlenecks only start happening at the end of the first round. It still has the varying number of matches problem though. So our ideal sorting algorithm for a tournament would:

  • be able to do lots of comparisons in parallel,
  • do about the same number of comparisons on each element, and
  • not compare elements if it could infer their order.

The first and third constraints are tricky once it gets going – you can’t have multiple matches running in parallel that could potentially give contradictory results. One approach for small numbers of players might be to brute-force it – keep a directed graph of players and schedule matches for which (a) there currently isn’t a path in either direction and (b) there won’t be a path in either direction for any of combination of outcomes of the games currently running. I actually started coding this when I got home, but was quickly distracted by something less confusing.

I gotta break out my Knuth vol. 2…

1 comment

Movember: Day 16

Day 16

Still trying to get this thing symmetrical. Still failing.

The good news is that my laptop is upgraded and restored to the point where I can at least post this. The ironic news is that the gDesklets CPU monitor is showing a consistent 20% usage by the gDesklets CPU monitor (and, to be fair, a few other desklets). So… am I back to the old days of a bare desktop and no way to know much load my machine is under except by the heat coming from the grille on the side? Or will I find a more efficient CPU monitor? Stay tuned!

No comments


Ahhh, gDesklets. This makes it feel like uni, when pimping your desktop was basically a diploma course.

No comments

Karmic Koala

I’m in the middle of upgrading Ubuntu on my laptop.

Well, no, that’s not entirely true. I’ve finished upgrading, and now I’m waiting for my home directory to rsync from the server that I backed it up to. It’s moving steadily at about 100MB a minute, which seems sort of slow, but not surprisingly so given how crufty everything in between is, and I’m definitely not going to investigate it before it’s done.

I did actually go to the effort of putting /home on a different partition when I installed it originally, so that I could upgrade it and keep my home directory in place, but I also formatted it as Reiser, which I think has possibly been at the root of some performance and drive-clicking problems, so I’ve reformatted both partitions as ext4, which is presumably somewhat better supported in Ubuntu, being the default filesystem, except that there’s this vague rumour that it occasionally corrupts very large files, except that nobody can reproduce it and they’re starting to think that the reports are bogus, but of course the nature of software is that it’ll never fail when you’re actually looking at it, so now it’s niggling in the back of everyone’s mind that one day all your stuff might be corrupted.

Wasn’t there a time when these things were simple?

No, now that I think about it. It’s always been this complicated. But it’s sure as fuck not getting any simpler.

No comments

Movember: Day 15

Day 15

Today’s random facial-hair-related piece of coolness: The Longest Way is a guy who planned to walk from China to Germany. That in itself isn’t all that relevant (although it is awesome), but he has a time-lapse video of his beard.

Also, he stopped about a third of the way through the planned trip (but still having walked across most of mainland China) and caught a plane home, because he decided that what he really wanted to do was go to university. That… is also interesting.

No comments

Movember: Day 14

Day 14

If I’m not mistaken, today, being the half-way point, is judgment day – the day you can rate my mo.

This whole thing… is such a weird concept.

1 comment

« Previous PageNext Page »