Bored in Vegas

As usual, my advice on Vegas is, don't bother. This trip, I've gotten sick (something flu-like), been fed far too much, sucked in a lot of signature smoke, been too hot outside and too cold inside, and now my flight home is indefinitely delayed due to mechanical problems (I'm now in the airport).

Unfortunately, I'm coming back in 2 weeks for the TopCoder Open. Oh well.

Visualising sorting algorithms

This is another one of my rare technical posts, as opposed to news of which countries I've been visiting.

If you're in computer science, you've probably seen an animation of sorting algorithms, maybe heard a rendition, or seen a visual representation. I have, somewhat by accident, discovered a different way to visualise a sorting algorithm: plot points for memory accesses, with address on the X axis and time (counted by accesses) on the Y axis, and different colours for reads and writes. It produces some rather pretty pictures. Note that these are not to scale relative to each other - the Y axis has been compressed to fit the entire sort into a fixed height.

Ye olde bubblesort. Some of the patterns are an optical illusion due to aliasing, but the green spikes are a feature of the algorithm.

Insertion sort - the version optimized for mostly sorted content. Although the data is random, you can see that in many cases it reduces the search distance.Shellsort, clearly showing the phases.

Selection sort:Heapsort: the solid lines at the top are the heap-building phase, while the rest shows the extraction. Note the very slight slope to the bottom-right line: as the heap gets smaller, the heap extraction gets faster, but only as O(log N).
Divide-and-conquer algorithms have a pretty fractal nature. This is quicksort - the perturbations in the fractal indicate the random selection of pivots (it just picks the middle, rather than median-of-3). Mergesort: this diagram is twice as wide as the others because it uses temporary storage on the right.

Budapest (again)

Yes, it's blog time again! Once again, it was the 24-hour Challenge in Budapest.

Like last year, there were some very interesting and tough problems. This year they did a much better job of implementation, and there were far fewer issues with things crashing and so it was more enjoyable. Unfortunately we didn't do as well as last year, but we still managed to come 5th.

After the contest, we finally got our cruise on the Danube. This time we came better prepared with info on where to catch the tourist boats. It turns out we were just looking in the wrong area, and if you go to the right place there are scores of them.

IT Challenge over

It ran smoothly, so not much to report. Stellenbosch won, UKZN came second and UCT third. Now I get a week of holiday in Cape Town; too bad half my friends have moved to other places.

IT Challenge 2010

I'm off to South Africa next week to help run the finals of the Standard Bank IT Challenge. This is a contest for teams of 4 university students. We've already run the heats to select one team from each of 9 universities; on Thursday the teams will meet at Standard Bank headquarters to do the final.

It's been some crazy hard work (including just about every free moment for the last week or two), but it should be a really great contest. We're hoping to have live standings during the contest (although we'll stop them an hour before the end) at http://sbitc2010.dyndns.org/ (yes, that link won't work right now, and probably won't after the contest either).

After that it's off to Cape Town for a week of hard-earned relaxation.

All Jammed up

Following my usual trend of only blogging when I travel and have some pictures I need to post, here's some photos from my last trip to the Googleplex for Google Code Jam. I was somewhat off form, but still managed to make 10th. If you want to see some seriously scary problems, take a look at the site. There is also an article about it here, including a video showing some of my ugly mug.

Photos from Bulgaria

I'm back in England. The contest was great fun and I'm going to miss the Bulgarian warmth and sunshine.

How not to be seen

Don't turn up.

That seems to be the view of most of the people I've talked to about the IOI planned excursion to the Black Sea. It apparently involves 4-6 hours on a bus. Each way. Not including the time you spend waiting around at the beginning until everyone gets on the bus. And leaving at 6am. When the time comes, I for one won't be found wanting. I won't be found at all, since I will be sleeping the sleep of the just, or possible just very tired.

Apart from the attempt to inflict long periods of time on buses (which in my case normally consists of periods of boredom interspersed by vomiting), things have been going pretty well here - in fact far smoother than usual. The SA team also did pretty respectably on the first day, and the second day is finishing in a few minutes. I haven't been on any of the excursions so far (being on the scientific committee seems to involve lots of work, but it's all been fun), but I plan to take myself off to the old town tomorrow (hopefully with some other leaders to make it more fun).

Bulgaria, land of enormous hotel rooms

It's blog time again! As usual, it's because I'm travelling - this time to IOI again, in Bulgaria. Haven't been here long, but so far I've been blown away by the size of the hotel room. More news when I've actually been out and about more.

Fording the... ox?

So, now that Tim is living in Oxford, I had a sufficiently good excuse to go and visit, and so I did so last weekend. The weather was rubbish, the company was good, and the town is quite pretty, in a more spread-out way than Cambridge. We went to see the science museum (which had lots of surveying stuff), and otherwise just wandered around the place. Um, not sure what else to add to that really.

We came second!

I don't have photos to post yet, but there are more details and pictures at http://www.challenge24.org/2009/blog

And the contest was... was... I still don't know!

There were technical problems (a fair number of them) during the contest, so the closing ceremony is only at 12. And since the scoreboard was one of the casualties, we still don't know how we did. But talking to one or two other teams, it sounds like we did reasonably well. Details to follow.

Also, I have now been awake well over 24 hours, with more to come. If you feel yourself going a bit squiggly and turning into a 6-foot chicken, do not be alarmed - I am merely hallucinating.

Hungry in Hungary

I'm sitting in Budapest, in preparation for a 24-hour programming contest. And lunch on the plane was a small ham sandwich, so I'm feeling peckish. Um, I don't really have much to add to that for the moment - more news once we've actually done the contest and done some touristy stuff. Tonight we're just going to crash and get a good night's sleep.

Don't let it snow...

... I want my flight to leave on time. So yes, life has been exciting, since yesterday England suffered about 10cm of snow, which apparently is the most in almost 20 years. So needless to say, they're totally unequipped for it, and large parts of the transport network including Heathrow ground to a halt. Fortunately, today had no snow that I've noticed and bright (if anemic) sunshine, so it looks like I'll be catching my flight in spite of the 3.5-hour journey from my house to Heathrow (normally it would be around 2.5).

This seems like it's going to be the things-falling-apart trip. Apart from the transport system, I opened my suitcase up to put my warm things in it just before checkin, and when I came to lock it up again I found that my lock had turned into a collection of bits on the floor. All very educational, but not much fun right before flying into Joburg airport which is notorious for baggage theft. So, any luggage thieves reading this: there is nothing valuable in my luggage. I promise. Don't bother.

Then after that, my watch started falling apart as I was checking in. Fortunately the pin didn't fall out and I was able to stick it back together.

Let's hope nothing else falls apart, like the plane, or my presentation on Friday.

The smallest park in the world

I've just got back from Portland, Oregon, from a business trip. I knew absolutely nothing about it before leaving, and I started with assumption of a typical American sprawl with end-to-end freeways and strip-malls. In fact the central part where I was a very pleasant surprise - good sidewalks, very short blocks, a river with a nice green bit next to it to walk along, etc.

It also features the smallest park in the world (Mill Ends park), which I thought was suitably amusing:


I only had one morning of free time (the rest of it being spent in the hotel eating too much food and trying not to get sucked into pointless arguments). Apart from the park, I went to Powell's book store, which is as large as the park is small. Just the SF/F section was about the size of a small public library, and I discovered a lot of books I'd never heard of, and bought a few for an insanely low price.

It burns us!

For those of you who don't already know, I've spent the last 11 days or so in Cape Town. The first morning I walked outside, squinted, and went "Ah, so that's what sunlight looks like." It made me realise just how sun-starved I've been in the UK winter.

It's been a great time here, and I've been out or seen people almost every day. Sadly, tonight I return to the land of clouds, roundabouts, pubs and 700-year old architecture.

Code Jam (like raspberry jam, but better)

Normally I blog about my trips while I'm on them (to kill time in airports), but this one was so short I didn't even both taking a laptop. In fact, I didn't even bother taking checked baggage, instead fitting everything for two days into a backpack. That sounds reasonably enough until you realise that it includes a keyboard and sufficient warm weather gear to stand around waiting for a bus in Cambridge. On the way back I think the backpack was about 99% of its theoretical maximum capacity.

The Code Jam itself is a contest run by Google. I've been to a previous one that ran on the TopCoder engine, but this time they've made a new format which really suits me. It's a lot less time-pressured than TC, and also more forgiving of mistakes. Having won my regional and finished in the top 3 in every round, I thought my chances were pretty good, but unfortunately I panicked near the end (partially because I forgot the contest started late and so I had more time than I thought), and so ended up third. Nevertheless I'm fairly happy since I didn't screw anything else up.

Pictures to follow - unfortunately not many or very exciting, since I didn't take my camera to the Googleplex on the assumption that they wouldn't allow photography (and indeed they didn't allow it inside the buildings).

How I learnt to stop worrying and love AMD's shader compiler

Normally I just post about travel and other daily trivia here, but I feel the need to get some good old tech ranting in. So, normal people (i.e. non-nerds), feel free to stop reading now :-)

I've been trying to do some OpenGL development at home, with the ATI X1600 in my laptop, and I've managed to find 3 serious bugs within about an hour. Firstly, my program would just crash while trying to compile a shader. After tinkering with my program for a while to try and eliminate anything I might have broken, I started removing bits of the shader. And guess what? If you index an array with a ternary expression, it crashes the driver.

Ok, I can work around that by moving the ternary into a temporary variable. Fix a few genuine compilation errors, and get to this message:

Fragment shader failed to compile with the following errors:

Well, that's helpful. Would be more helpful if it was followed by a list of errors, as is traditional in such cases. However, by again randomly removing pieces of code, I determine that a loop with an indeterminate number of iterations will cause this. Some hardware doesn't actually support loops (it just unrolls them), so fine, I'll run up to the maximum number of iterations I might need, and just early-out once I hit the number I actually need. Even when unrolling, such hardware normally supports forward branches, since it can just conditionalise the instructions hit by the branch. But not this sorry excuse for a compiler, it just gives me the same error. However, if I wrap the loop body in an "if" statement, it's happy to forward branch there.

Now, I finally have both my shaders compiled, I'm ready to link! It's much harder to make linker errors than compiler errors, although I did accidentally end up not writing to a varying that I was reading and which the linker helpfully complained about. I fix that, and is was well. And if you believe that, you haven't been paying attention. Of course it isn't. In spite of the cheery "Fragment shader was successfully compiled to run on hardware" from the compiler, the linker now asserts that "Fragment Shader not supported by HW". Why not? Well, remember that ternary expression? It turns out that while refactoring it fixed the crash, it's still not supported. It appears that the fragment shader can't do dynamic indexing, at least on varying arrays. So, some more refactoring, to move the array lookup inside each branch of the ternary, and now it all compiles and links.

I haven't tried running it yet, of course. I'm not sure I want to.

Photos from Montreal

As usual, I'm happy enough to take photos, but very lazy about getting them off my camera. I've finally got a round tuit, so here are some photos.

The South African who went up a hill and came down... a hill?

So, Sunday was see-Montreal day with Neil. A friend of his loaned us his bike, so we were able to cycle around town. Montreal has some great cycle lanes - unlike Cambridge, where it's usually just a demarkated cycle lane, these are actually separate to the road, blocked off by a concrete ridge so that motorists can't park in the cycle lane or cut you off or anything (and you don't have to share it with pedestrians either).

Montreal is named after the local "mountain", Mont Royal. which Wikipedia tells me stands at a whopping 233m above sea level. It's covered in trees and has a very pleasant gravel road that winds its way gently up, which we spent some time going up (on our bicycles), and of course going down. I'll post some pictures when I get the motivation to get them off my camera.

Today until Friday is basically meetings, so I won't have much more to post for a while.