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