Is it possible to have a rotationally invariant identifier of a boolean matrix?

Question

Say I have a matrix of ones and zeros, and I would like a 'identifier' for this matrix that takes the same value regardless of whether the matrix is rotated by 90, 180, or 270 degrees, i.e. a 4-to-1 mapping. Ideally, this identifier should be 1/4 the size of the matrix. Is it possible to write a function that does this mapping?

Background: I was looking at this problem on the UVa problem set. I don't exactly need such a function to solve the problem, but it seems reasonable that it would exist, and using it would make for a more elegant solution.

Answer 1

Yes. You can take your original matrix A, and rotate it to all the possible configurations A', A'' and A'''. You can then sort these using some sorting of your choosing (just be consistent) , pick the first, and hash that using any hash function of your choosing (again, the actual hash function doesn't matter, just be consistent).

Obviously this can be optimized heavily by not actually doing the full rotation and sorting - you can do the comparisons lazily, stopping as soon as you know which rotation sorts first - but the principle is the same.