### Perl Weekly Challenge: Week 87

#### Challenge 1:

Longest Consecutive Sequence

You are given an unsorted array of integers `@N`.

Write a script to find the longest consecutive sequence. Print 0 if none sequence found.

##### Example 1:
``````Input: @N = (100, 4, 50, 3, 2)
Output: (2, 3, 4)
``````
##### Example 2:
``````Input: @N = (20, 30, 10, 40, 50)
Output: 0
``````
##### Example 3:
``````Input: @N = (20, 19, 9, 11, 10)
Output: (9, 10, 11)
``````

This is my Perl solution.

First the input (which I get from the command line) has to be sorted. It irks me that Perl can't automatically sort lists of numbers without `\$a <=> \$b`. It trips me up every time. Perl does all kinds of other things automagically so I don't know why it can't do this especially as Raku manages it. Oh well.

``````my @N = sort { \$a <=> \$b } @ARGV;
``````

I set up two arrays, `@sequence` which contains the current sequence (initially seeded with the first element of `@N`) and `@longest` which is initially empty but will keep the longest sequence found so far.

``````my @sequence = ( \$N );
my @longest;
``````

Now we can just traverse `@N` starting from the second element and compare it to the previous element. If it is 1 greater, it can be added to the running `@sequence`. If `@sequence` is longer than `@longest`, it becomes `@longest`.

But if the current element is greater than one more than the previous element, `@sequence` has to be restarted with the current element.

``````for my \$i (1 .. scalar @N - 1) {
if (\$N[\$i] == \$N[\$i - 1] + 1) {
push @sequence, \$N[\$i];

if (scalar @sequence > scalar @longest) {
@longest = @sequence;
}

} else {
@sequence = ( \$N[\$i] );
}
}
``````

By the end either we have a longest sequence which we can print (I've also chosen to add `()` around it) or `@sequence` is empty and we print `0`.

``````say scalar @longest ? (q{(} . (join q{, }, @longest) . q{)}) : 0;
``````

(Full code on Github.)

This is the Raku version. It's just a straightforward port so there isn't more to say.

``````sub MAIN(*@N) {
my @n = @N.sort;
my @sequence = ( @n );
my @longest;

for 1 ..^ @n.elems  -> \$i {
if @n[\$i] == @n[\$i - 1] + 1 {
@sequence.push(@n[\$i]);

if @sequence.elems > @longest.elems {
@longest = @sequence;
}

} else {
@sequence = ( @n[\$i] );
}
}

say @longest.elems ?? (q{(} ~ @longest.join(q{, }) ~ q{)}) !! 0;
}
``````

(Full code on Github.)

#### Challenge 2:

Largest Rectangle

You are given matrix `m x n` with `0` and `1`.

Write a script to find the largest rectangle containing only `1`. Print `0` if none found.

##### Example 1:
``````Input:
[ 0 0 0 1 0 0 ]
[ 1 1 1 0 0 0 ]
[ 0 0 1 0 0 1 ]
[ 1 1 1 1 1 0 ]
[ 1 1 1 1 1 0 ]

Output:
[ 1 1 1 1 1 ]
[ 1 1 1 1 1 ]
``````
##### Example 2:
``````Input:
[ 1 0 1 0 1 0 ]
[ 0 1 0 1 0 1 ]
[ 1 0 1 0 1 0 ]
[ 0 1 0 1 0 1 ]

Output: 0
``````
##### Example 3:
``````Input:
[ 0 0 0 1 1 1 ]
[ 1 1 1 1 1 1 ]
[ 0 0 1 0 0 1 ]
[ 0 0 1 1 1 1 ]
[ 0 0 1 1 1 1 ]

Output:
[ 1 1 1 1 ]
[ 1 1 1 1 ]
``````

My first impression was that this problem is quite similar to challenge 2 in week 84 and I hoped I would be able to reuse that code but in fact I had to modify it quite a bit because in that challenge we only needed to find the four corners of a rectangle whereas we need to know the value of all its internal points too. I'll show you my Raku solution first.

``````sub MAIN(
Str \$file #= a file describing a matrix of 1's and 0's where every line
#= is a row in the matrix.
) {
``````

The matrix is read from a file and a regular expression is used to extract the `1`'s and `0`'s into a 2d array.

``````    my @matrix;
for \$file.IO.lines -> \$line {
@matrix.push(\$line.match(/ (0|1) /, :g));
}
``````

Two variables are set up to store the largest rectangle found so far. Only it's height and width need to be stored.

``````    my \$maxheight = 0;
my \$maxwidth = 0;
``````

Now we go through `@matrix` row by row and column by column.

``````    for 0 ..^ @matrix.elems -> \$m {
for 0 ..^ @matrix[\$m].elems -> \$n {
``````

If a `1` is found, it is a potential rectangle. So we make some variables to record its origin (the upper left corner) and its height and width.

``````            if @matrix[\$m][\$n] == 1 {
my \$row = \$m;
my \$col = \$n;
my \$left = \$n;
my \$height = 0;
my \$width = 0;
``````

We then see how many consecutive `1`'s there are on that row.

``````                while \$col < @matrix[\$row].elems && @matrix[\$row][\$col] == 1 {
\$width++;
\$col++;
}
``````

Then we see how many rows there are with the same number of `1`'s in the same position. Note the use of `.all()` and an array slice to represent a row of the rectangle.

``````                while \$row < @matrix.elems && @matrix[\$row][\$left ..^ \$left + \$width].all == 1 {
\$height++;
\$row++;
}
``````

This gives us a rectangle. We compare the area of this rectangle to the area of the previous largest rectangle if any. If the current rectangle is larger, it becomes the new largest rectangle.

``````                if \$height * \$width > \$maxheight * \$maxwidth {
\$maxheight = \$height;
\$maxwidth = \$width;
}
}
}
}
``````

When `@matrix` has been fully searched, we will know the size of the largest rectangle. Apparently according to the examples given with the spec, 1x1 rectangles (i.e. single `1` values) don't count for this challenge so we check if the area of the largest rectangle is 2 or more. If it is, we print out a rectangle of 1s of similar size otherwise we print 0.

``````    if \$maxheight * \$maxwidth < 2 {
say '0';
} else {
for 0 ..^ \$maxheight {
say q{[ }, "1 " x \$maxwidth, q{]};
}
}
}
``````

(Full code on Github.)

The only big difference in the Perl code is that there is no `.all()` method so I wrote a quick subroutine to mimic it. In retrospect, using `grep()` instead of a for loop would have been more concise.

``````sub all {
my @array = @_;

for (@array) {
if (\$_ != 1) {
return undef;
}
}

return 1;
}
``````

The rest is pretty much the same as Raku so I have not bothered reproducing it here.

(Full code on Github.)