## Saturday, July 26, 2008

### I got in a "jam"...

Round 1A of Google's Code Jam programming contest (in which I participated) ended about an hour-and-a-half ago (there are three sub-rounds of Round 1 and contestants can compete in two of them to try to move on to Round 2).

A failure (on my part) to pay close attention to the requirements of the first problem meant I implemented an algorithm with a complexity of `O(n! * n!)`, which means 25 401 600 iterations for `n = 7` (sort of reasonable) but 1 625 702 400 iterations for `n = 8`, something my laptop wouldn't be able to finish in any reasonable amount of time. It's much worse when you consider that n was expected to go as high as 800! Once I read that, it occurred to me that I had been going at it entirely the wrong way... About an hour-and-a-half of going the wrong way, which involved implementing (and debugging) a nice "permute the items of this list" method.

You see, there was a trick to the problem. Once I realized this, I replaced the double permutation loop with two calls to Sort() and a single `O(n)` loop. D'oh! My solution to the small input was judged as correct, so I proceeded to the large input. It ran just as fast and so I submitted its output, too. Well, again, I screwed up with the requirements and it turns out my math was overflowing left, right and center and thus, when the contest ended, I got a measly 5 points (out of a possible 15 for that problem and out of a possible 100 for all 3 problems!), which means I ranked 2363 out of 2394. (you don't find out if your submission to the large version is correct until the end of the contest - I also only attempted the first problem)

Oh, well... I might try again in Round 1C (Sunday at 05:00 local time!), but in the meantime I thought I'd publish some of the source code that came out of this. I used Visual Studio 2008, which meant I could try out the neat features of the C# that came out with .NET 3.5, such as:
• the `var` keyword
• extension methods
• LINQ

OK, so I didn't need to use LINQ, nor did I use extension methods until after the contest, but here's my touched-up `Permutations` iterator method, generalized to any `IList<T>` instance:
`public static class Extension { public static IEnumerable<IList<T>> Permutations<T> ( this IList<T> input ) { int numElements = input.Count; var slotOffsets = new int[numElements]; var slotBusy = new bool[numElements]; bool allDone = false; while ( !allDone ) { #region Set slotBusy flags to false for ( int i = 0; i < numElements; i++ ) { slotBusy[i] = false; } #endregion IList<T> permutation = new List<T> ( numElements ); int lastSelected = -1; for ( int i = 0; i < numElements; i++ ) { for ( int j = 0; j < numElements; j++ ) { int selectedSlot = ( lastSelected + 1 + j + slotOffsets[i] ) % numElements; if ( !slotBusy[selectedSlot] ) { slotBusy[selectedSlot] = true; permutation.Add ( input[selectedSlot] ); lastSelected = selectedSlot; break; } } } yield return permutation; #region Update offsets for ( int i = 0; i < numElements; i++ ) { slotOffsets[i]++; if ( slotOffsets[i] < ( numElements - i ) ) { break; } else { if ( i == numElements - 1 ) { allDone = true; } else { slotOffsets[i] = 0; } } } #endregion } }}`
...which you can use as follows (notice how it's magically a method on any IList<> implementation?):
`IList<int> inputList = new List<int> ( new int[] { 1, 2, 3 } );foreach ( List<int> permutation in inputList.Permutations ( ) ) { StringBuilder sb = new StringBuilder ( ); sb.Append ( "[" ); bool isFirst = true; foreach ( var item in permutation ) { if ( !isFirst ) { sb.Append ( ", " ); } else { isFirst = false; } sb.Append ( item ); } sb.Append ( "]" ); Console.WriteLine ( sb.ToString() );}`
...and it should produce the following output:
`[1, 2, 3][2, 3, 1][3, 1, 2][1, 3, 2][2, 1, 3][3, 2, 1]`

I just wish I had prepared this method before the contest, although I think some actual practice in solving these kinds of problems would have helped me more. Maybe next time... :)