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