[agf]

Yeah, zip is w*h. I meant to replace it once everything was working but forgot. It's simple to write a "TransposedMatrix" wrapper that only adds constant overhead:

  class TransposedMatrix(object):
     def __init__(self, matrix, index = None):
         self.matrix = matrix
         self.index = index

     def __getitem__(self, index):
         if self.index is None:
             return TransposedMatrix(self.matrix, index)
         return self.matrix[index][self.index]

     def __len__(self):                                 
         if self.index is None:
             return len(self.matrix[0])      
         return len(self.matrix)

and I've updated the gist to do that. Thanks for pointing it out.

The tests are definitely quick & dirty; I'm aware there can be more than one correct answer.