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... :)
