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@_;
    #...

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;
}

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...

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;
}


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! □

link for codes: ch-1.pl, ch-2.pl, ch-1.lsp

Leave a comment

About C.-Y. Fung

user-pic a beginner in programming; passionate in mathematics, distance running and gender issues; from Hong Kong. https://twitter.com/e7_87