My UPS works… (sorta)

Shame the ISP connection dropped out.

I have 3 UPS for 4 computers, 2 monitors, a switch and an adsl modem (and a phone).

The alarms woke me up just after 4 this morning, although it appears that one of the UPS had already failed before I was awake.
I run a text based online role playing game server on one of the computers (which was connected to a UPS which hadn’t failed), so I logged in to warn everyone that the power was out, but no one was there because the adsl connection had been out for 2 minutes.

Shut everything down, but in the dark I couldn’t see where to turn the main UPS off.
Went back to sleep and an bit more than an hour later, the main UPS alarm was still going. It was light enough to see a bit then, so I could finally turn it off.

7am, power was still out so I went to work. Guess my text based MORPG won’t be back up online until I get home this afternoon. Looking at an 11 hour outage, which I think is as long as all outages combined since I last moved house.

Update: GCJ

Finalized results are out – 139th for me.

The third question would of gotten me 87th and finally 37 points was above the cut off.

In a moment of inspiration, I realised that my solution to the 3rd problem would have solved both the small and the hard, which would have gotten me through.

However, it fails to produce the correct result, even though it runs in time. I guess there is another bug in my ternary search.

Successful Fail

I came 143rd (out of 180 in the APAC).

With 2 minutes to go I started running my code for a test case which if it had passed, would have gotten me ~80th. However I was running debug code, with the debugger attached!
A couple of minutes after the comp finished, my code finished running.

Additionally, I was about a couple of minutes of coding away from getting out the first problem, which would have gotten me ~38th position. Which was close to the cutoff for 36th. Poor concentration during the early part of the comp on my part explains why I failed to see the last little bit until just after the competition.

However, I plan to keep working on TMD.Algo (which was practically no help in todays competition, of course) and hopefully next year I’ll get to those finals. (Although my best is still 2005, I’m not getting any younger…)


A new release of TMD.Algo can be found here.

I’ve added a bunch of stuff since last time, and its even got a few more test cases.

It still needs a bunch more really, but time flies.

If anyone out there uses this thing, I strongly recommend against using the BigInteger hack I added today. Either wait for .Net ~4 when its really available, or grab the mono library. I’m not really sure why I decided to add BigInteger support this way.

Same caveats apply as before, I shipped it without the signing key but without modifying the solution.

Tommorrow is the Google code jam regional onsites, so I’m off to a fun filled day in the city, so to speak.

Stuff I’ve done in the past

I just realised that this site has no links to all the software I keep on it.

My old sudoku solver. Its not all that special… but it can print out its logic for most puzzles, so you can sometimes learn new things from it.

My raytracer. It uses TAL files which were defined in the University of Sydney computer graphics class. Although it supports a few custom extensions so it can do pictures like this.

My LoopDeLoop game. It is a generic implementation of the LoopDeLoop/Slitherlink/Kwontom loops puzzle game. It has a multiplayer mode and support for non-standard grids.

My AppleHunt game. This is a game I came up with at random which is kind of fun. The solver in it is unfortunately brute force, so it has a pretty limited range when it comes to generating puzzles.

My LOTRO chat log text to speech program. Seems someone had a similar idea with the same name so this will be renamed shortly…

A new release

TMD.Algo finally escaped.

You can get it here.

There is a bunch of new stuff, however not all of it has been tested yet, so as usual use with caution.

The graph class is especially ultra-alpha right now.

One final note, this is a source code and binary release, but it won’t actually compile out of the box.
If you want to make it compile there are several things to do.

  1. Create a private key to sign your custom builds (or remove the key signing).
  2. Update the InternalsVisibleTo on TMD.Algo so the test cases can see the ugly internal methods.
  3. Install NUnit 2.4.8 (or maybe a more recent version will work).
  4. Install FxCop 1.36 into the default location (or modify the post build step for TMD.Algo).

Hopefully that should cover it, I haven’t actually tried the steps myself.

Generics and .Net internals

I noticed the following method while on a journey through reflector the other day.

RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter(Type otherType)

Quite an odd method really.

Example in use:

This lets you make a GenericEqualityComparer<T> instance.

First thought is why wouldn’t you write
new GenericEqualityComparer<T>()

As it turns out its because GenericEqualityComparer has a restriction which says T : IEquatable and the current generic type calling this code has no restriction on T.

So this method is really useful. It allows you to write a set of if statements checking what T implements and then defer processing to appropriate special case generics.

Unfortunately the above method is internal, so you would have to do the equivelent with a bunch of reflection, probably a bit slower too.

I am thinking that we should petition Microsoft to provide a language construct which is syntactic sugar for this method.

var v = new GenericEqualityComparer<T>() : where T is IEquatable;
Could throw an InvalidOperationException if you haven’t guarded for the case where T is not IEquatable;

In other news of TMD.Algo should be out soon, I have a dequeue, a couple more sorts (really basic ones) and an alternative Heap which supports O(1) Contains, and O(log n) Remove at the expense of some extra book keeping. Useful for implementing Prim’s algorithm as the key reduction step can be done in O (log n) (as needed) by simply removing the entry and adding the new one after changing the key.

Google Code Jam 08

So, its been a couple of years since I last entered the google code jam. Back in 05 I came ~120th, and after a few cancelations it almost looked like I was going to go to the finals.

This year however the google code jam has been run in a dramatically different format. No longer powered by top coder, everyone runs their code on their own machines. This lets google’s site scale alot better, although it does add to the overhead of cheat detection.

Also new this year are regional finals. The top 500 competing at a ‘nearby’ google office before the real finals in the US.

So in a couple of weeks I will be at Google Sydney competing to be in the top 20% in APAC, so I can go to the US. I am unsure if this will be tougher then top 100 world wide, but at least the competition won’t be at 2am like the last two rounds before it. Still, there are alot of tough competitors in the APAC region.

I do have an incentive though, a friend of mine recently had his internet company bought by Google and he is working for YouTube now. He has offered a game of frisbee golf if I make it over there.

They offer job interviews to a subset of the people going. I was offered one but I turned it down. Several people have already commented that I am crazy for doing so. Maybe I am crazy because I personally can’t think what I would do at Google.

Finally however, GCJ 08 terms and conditions allow for the downloading of publically available libraries to assist in the writing of solutions during the competition. Specifically any library used must be available to all other contestants as well.

I have started work on such a library tailor made for algorithm competitions, and over the next couple of weeks intend to release it under a BSD or equivelent license via this website. The library will be for .Net and I am going to target .Net 3.5 as VS2008 is available at the competition.

For starters, any data structure in CLR’s Introduction To Algorithms, which is not in the .Net base libraries, I intend to implement. Additionally any specific algorithm which can be generalized from this book I also intend to provide. I am going to see if extension methods can be applied to delegates, because I think that would be a nice way to write ternary/binary searches for minimum/thresholds.

I currently have an implementation of IList which is backed by a red-black tree for log(n) indexed inserts. I also have another one which tracks the sum of all elements of the list prior to the current one efficiently (Specifically, it is actually generalized based on delegates for ‘addition’ and ‘subtraction’, so as long as the operator in question can be ‘undone’ it can be any accumulating operation).

If I have time, I am going to investigate implementing ‘flattened’ versions of these data structures, which store indexes into an array of nodes and maintain a free list, rather than allocating the nodes directly on the heap and using pointers. This technique usually results in a performance improvement, especialy in a garbage collected runtime. Additionally, if the array is expanded using the standard List expansion logic, the amortized additional costs on inserts are O(1). There is a memory penalty, although on a 64bit OS, with a limitation of 2^32 nodes in the collection, the memory penalty is significantly lower due to using ints instead of 64bit pointers. I am interested to see how a flattened linked list compares to the .Net runtimes built-in linked list.