I’ve been doing the Perl Weekly
Challenges. The
latest
involved list searches and matrices. (Note that this is open until 22
November 2020.)
TASK #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.
The algorithm I used is: sort the list. Then for each list member, if
it's one higher than the previous one (or it's the first one) push it
onto the current sequence. Otherwise store the current sequence (if
it's longer than one previously found), and push the list member onto
the new current sequence. (And check at the end for a sequence in
progress; I added another test case for that. There are doubtless
prettier ways of doing this without duplicating code, but this is a
quick hack that works.)
sub lcs {
my $ns=shift;
my @l=sort {$a <=> $b} @{$ns};
my @w;
my @r;
while (my $n = shift @l) {
if ((scalar @w == 0) || $n==$w[-1]+1) {
push @w,$n;
} else {
if (scalar @w > scalar @r) {
@r=@w;
}
@w=($n);
}
}
if (scalar @w > scalar @r) {
@r=@w;
}
if (scalar @r > 1) {
return \@r;
} else {
return 0;
}
}
Raku is basically identical except that I get proper parameter passing.
For Python, since I'm taking things off the list one at a time and
Python lists are ineffecient if you do that at the front, I reverse
the list before entering the algorithm and take things off the end.
def lcs(n):
l=list(n)
l.sort(reverse=True)
w=list()
r=list()
while (len(l)):
n=l.pop()
if (len(w)==0 or n==w[len(w)-1]+1):
w.append(n)
else:
if (len(w) > len(r)):
r=w
w=[n]
if (len(w) > len(r)):
r=w
if (len(r)>1):
return r
return 0
Ruby works basically like the Perl/Raku version.
And Rust is more like Python in that I reverse the sorted list first.
Defining the potential capacity of a vector can lead to a time saving
since it doesn't need to be reallocated as it grows.
Also I changed the definition slightly: if no sequence is found, I
return [0] rather than 0, because that way I have a single return
type.
A slight complication in that pop()
returns an Option and I have to
test that – but I can't stick that in the while loop condition.
(while 1
would probably work as well.)
fn lcs(ns: Vec<i32>) -> Vec<i32> {
let mut l=ns;
l.sort();
l.reverse();
let mut w=Vec::<i32>::with_capacity(l.len());
let mut r=vec![0];
while l.len()>0 {
let nn=l.pop();
let n: i32;
match nn {
None => break,
Some(x) => n = x,
}
if w.len()==0 || n == w[w.len()-1]+1 {
w.push(n);
} else {
if w.len() > r.len() {
r = w;
}
w=Vec::<i32>::with_capacity(l.len());
w.push(n);
}
}
if w.len() > r.len() {
r = w;
}
return r;
}
TASK #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.
This is similar to the one in #84, but with more fiddliness. I'm sure
this isn't the best algorithm, but it was one I could code up quickly:
loop over each possible starting point, then loop over each possible
rectangle size, then loop over each actual entry. This means a lot of
repetition; probably a better approach would be, from the starting
point, to extend each row until one hit a zero, each column ditto,
then work out possible rectangles from there. But I didn't; and at
least it should be fairly cheap to check values in a two-dimensional
array.
"Largest" isn't defined; I chose "maximum area".
The real oddity here is that the problem wants the actual rectangle,
rather than its dimensions or location. Since that's intrinsically a
bunch of 1
values, I build it at the end from the dimensions rather
than copying out the actual data.
sub lr {
my $s=shift;
my $maxx=$#{$s};
my $maxy=$#{$s->[0]};
my $maxa=0;
my @c;
First loops: check all starting points, skip onward if it isn't a 1.
foreach my $x (0..$maxx-1) {
foreach my $y (0..$maxy-1) {
if ($s->[$x][$y]==1) {
Second loops: check each possible rectangle size (minimum 2×2)
foreach my $tx ($x+1..$maxx) {
foreach my $ty ($y+1..$maxy) {
And within that rectangle, check each cell, aborting the check if we
find a single zero.
my $valid=1;
OUTER:
foreach my $sx ($x..$tx) {
foreach my $sy ($y..$ty) {
if ($s->[$sx][$sy] != 1) {
$valid=0;
last OUTER;
}
}
}
If we found a rectangle, and its area is larger than any we've
previously found, store its width and height.
if ($valid) {
my @l=($tx-$x+1,$ty-$y+1);
my $a=$l[0]*$l[1];
if ($a > $maxa) {
$maxa=$a;
@c=@l;
}
}
}
}
}
}
}
If we found a rectangle, generate a list of lists of 1
s and return it.
if (@c) {
my @o;
foreach (1..$c[0]) {
push @o,[(1) x $c[1]];
}
return \@o;
}
return 0;
}
Raku is similar, with some tweaks to the list generation (it wants to
produce a Seq
rather than a List
):
if (@c) {
my @o;
for (1..@c[0]) {
push @o,(1 xx @c[1]).List;
}
return @o;
}
Python cannot, by design, break out of an inner loop in one step, so:
valid=1
for sx in range(x,tx+1):
for sy in range(y,ty+1):
if (s[sx][sy]!=1):
valid=0
break
if (valid==0):
break
if (valid):
l=[tx-x+1,ty-y+1]
a=l[0]*l[1]
if (a > maxa):
maxa=a
c=l
and at the end (note *
for duplicating a list):
if (len(c)):
o=list()
for i in range(0,c[0]):
o.append([1] * c[1])
return o
else:
return 0
Ruby sort of can break out of an inner loop but it gets fiddly, so I
used the same pattern here.
valid=true
x.upto(tx) do |sx|
y.upto(ty) do |sy|
if (s[sx][sy] != 1)
valid=false
break
end
end
if valid==false
break
end
end
and the same *
for list duplication:
if (c.length > 0)
o=Array.new
1.upto(c[0]) do
o.push([1] * c[1])
end
return o
Again with Rust I tweaked the rules to make the return type
consistent. (Doubtless there is some way of fiddling this, but it's
not what Rust wants you to do.) No break-from-inner here either, as
far as I can tell from a superficial check. But oh, how beautiful the
compilation of the return value:
return vec![vec![1; c[1]]; c[0]];
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.