The Matrix golf had a rather thin field (hopefully only temporary), but some really cool code (especially in the post-mortem).

The problem statement was short enough to be quoted here in full:

Let A be an N*N matrix of zeros and ones. A submatrix S of A is any group of contiguous entries that forms a square or a rectangle. Write a program that determines the number of elements of the largest submatrix of ones in A . Largest here is measured by area.

Before going into the details, a brief example of how the algorithm I used works. Assume the following matrix:

00011
00110
01110
10110
00010

The longest string of 1s is the 111 on line 3, so that's the largest submatrix of one line (with an area of 1*3=3). Then transform the matrix by doing a stringwise and on each line and the line that follows it. The last line will be chopped off:

00010
00110
00110
00010

Obviously the only way to get a 1 on the transformed matrix is to have one on the corresponding position in two successive lines in the untransformed matrix. So the string 11 (found on both lines 2 and 3) corresponds to an area of 2*2=4 in the original matrix. Repeat the transform:

00010
00110
00010

Now any 1 is going to be the result of 3 1s on consecutive lines, so 11 on line two means there was a submatrix of area 2*3=6 on the original matrix. Repeating the whole process two more times would result in finding an area of 4 and one of area 5. The answer for this matrix would therefore be 6.

My solution (59 characters):

#!perl -lp0
s/1*/$B[$?*length$&]=$&/ge,/
/,$_&=$'
while++$?;$_=$#B

As usual, we slurp the whole input into $_ with -p0 and take care of the trailing newline with -l. In addition to $_, a couple of other variables contain some interesting state. @B is used for keeping track of the largest area that's been found (an old golf trick; we're only interested in the size of the array, not the values stored in it). $? holds the current iteration (i.e. the multiplier for the area calculation). $? is used since it can only contain an unsigned short (0-65535), and therefore repeatedly incrementing it in the condition of the while results in the variable overflowing to 0 after 65535 iterations. (Another variable with a similar behaviour is $^C, which holds signed chars. I used $? instead since at some point my program couldn't handle negative multipliers)

As mentioned before, the program contains a while-loop whose condition is just incrementing $?. The body of the while implements most of the algorithm. Some code is executed for each string of 1s with s/1*/.../ge. The code in question is $B[$?*length$&]=$&, which just calculates the area of the submatrix that the string of 1s represents (by multiplying $? and the length of the matched substring, i.e. $&), and stores something in that index of @B. In this case, the value being stored is $& since (despite using s///) we don't actually want to modify $_ yet. This takes care of finding the largest area.

To implement the transformation described earlier, a /\n/ is used to find the first newline in $_. After this a stringwise and of $_ and $' will have done the tranformation (including chopping off the last line). Once the loop ends, we just assign $#B (the largest index of @B) to $_, which is then printed out thanks to the -p command line argument.

This was a very cool golf. My only regret is missing a completely obvious optimization of replacing the s/1*//ge with a suitable crafted map, which would've saved two strokes. Well, not completely obvious since I only realized that it would've been possible when writing this post. Perhaps I should start writing these things earlier... ;-)