CY's Take on PWC#087
If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).
After the long-haul Sudoku Task, this week we come to meet two tiny tasks.
Task 1 Longest Consecutive Sequence
It seems unavoidable for me that we have to sort the input first:
sub long_consec{
my @list = sort {$a<=>$b} @_;
#...
my @list = sort {$a<=>$b} @_;
#...
Then I use a for loop and a temporary list variable @potential_max_opp
my $max_len = 1;
my @max_opp;
my @potential_max_opp = ($list[0]);
for (1..$#list) {
if ($list[$_-1] == $list[$_]-1) {
push @potential_max_opp, $list[$_];
} else
{
if (scalar @potential_max_opp > $max_len) {
$max_len = scalar @potential_max_opp;
@max_opp = @potential_max_opp;
}
@potential_max_opp = ($list[$_]);
}
}
return \@max_opp;
}
my @max_opp;
my @potential_max_opp = ($list[0]);
for (1..$#list) {
if ($list[$_-1] == $list[$_]-1) {
push @potential_max_opp, $list[$_];
} else
{
if (scalar @potential_max_opp > $max_len) {
$max_len = scalar @potential_max_opp;
@max_opp = @potential_max_opp;
}
@potential_max_opp = ($list[$_]);
}
}
return \@max_opp;
}
Pretty straight-forward.
Some ideas: There should be some more efficient algorithms, maybe similar to counting sort , if the range of integers is given and the integers are "dense" enough.
---
Since this is a task on list, I write Lisp codes after a few weeks (checking: last time is Challenge #80, oh! )
and it is probably a bad implementation as a lot of global variables
have been used... Stop confession. The most interesting point is making (50 48 301 4 51 3 2 49 29 300) as ((2 3 4) (29) (48 49 50 51) (300 301))
-- from an unsorted list to a list of sorted lists which each are
composed of consecutive integers --. Interested readers may go to GitHub
to see the full code.
Task 2 Largest Rectangle
I think my codes are not the most optimized.
There is a four-layer for loops. In order to get the largest rectangle as early as we can, I put reverse for the latter two layers for loop.
for my $i (0..$N-2) {
for my $j (0..$M-2) {
for my $k (reverse $i+1..$N-1) {
if (all_ones(\@mat,$i,$k,$j)) {
for my $l (reverse $j+1..$M-1) { # to be continued...
for my $j (0..$M-2) {
for my $k (reverse $i+1..$N-1) {
if (all_ones(\@mat,$i,$k,$j)) {
for my $l (reverse $j+1..$M-1) { # to be continued...
all_ones(\@mat, $p1, $p2, $p3) checks the $p1-th to $p2-th column terms on the $p3-th row.
As said, I want to get the largest rectangle as soon as possible. There is a if conditional for checking whether the rectangle with vertices ($i,$j), ($k,$j), ($i,$l) and ($k,$l) is larger than the currently found rectangle with largest area, before checking every entry "inside" the "rectangle" is 1:
if (($k-$i+1)*($l-$j+1) > $largest_area) { #...
Then here is the main dish of the task:
my $count = $l;
my $bool;
do {
$bool = all_ones(\@mat, $i, $k, $count);
$count = $count-1;
} while ($count > $j && $bool);
if ($bool and $count==$j) {
$largest_area = ($k-$i+1)*($l-$j+1);
$rect_width = $k-$i+1;
$rect_height = $l-$j+1;
}
my $bool;
do {
$bool = all_ones(\@mat, $i, $k, $count);
$count = $count-1;
} while ($count > $j && $bool);
if ($bool and $count==$j) {
$largest_area = ($k-$i+1)*($l-$j+1);
$rect_width = $k-$i+1;
$rect_height = $l-$j+1;
}
The COVID-19 is more active in winter. Beware.
Do tell or correct me, if you have oppositions, want to discuss or give me advice!
Dear friends, stay alert and healthy! □
This blog is inactive and replaced by https://e7-87-83.github.io/coding/blog.html ; but I post highly Perl-related posts here.
Leave a comment