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 `1`

s 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 `1`

s 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... ;-)

could you give us some more elaborative solution for this problem. The perl code is obfucated.