RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest was about merging intervals and determining noble numbers.

Write a script to merge the given intervals where ever possible.

[2,7], [3,9], [10,12], [15,19], [18,22]

The script should merge [2, 7] and [3, 9] together to return [2, 9].

Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22].

The final result should be something like below:

[2, 9], [10, 12], [15, 22]

Slightly oddly, successive numbers aren't intended to be merged into the same interval; if I start with 2..9 and 10..12, they should remain separate. Which meant that my backup sloppy algorithm (put everything into hash keys, then derive the intervals from the combined key list) wouldn't work.

So we get the command-line arguments into a nested list:

while (@ARGV) {
  if (scalar @ARGV > 1) {
    push @i,[sort (shift @ARGV,shift @ARGV)];
  }
}

Then chunter through it repeatedly, squashing each overlapping range into a single range. It would probably be more efficient to sort them first, but this is a toy problem.

my $dirty=1;
while ($dirty) {
  $dirty=0;
OUTER:
  foreach my $a (0..$#i-1) {
    foreach my $b ($a+1..$#i) {
      if ($i[$a][1] >= $i[$b][0]) {
        $i[$a][1]=$i[$b][1];
        splice @i,$b,1;
        $dirty=1;
        last OUTER;
      }
    }
  }
}

And output in the appropriate format.

my @o;
foreach my $range (@i) {
  push @o,'['.$range->[0].', '.$range->[1].']';
}
print join(', ',@o),"\n";

Perl6 doesn't use references the same way, but I think I've got the hang of this now.

  if (@*ARGS.elems > 1) {
    push @i,sort((shift @*ARGS),(shift @*ARGS));
  }

though the main problem was that a last LABEL doesn't seem to work on my implementation (rakudo 2018.12-5 from Debian/stable) so I had to implement it by hand.

You are given a list, @L, of three or more random integers between 1 and 50. A Noble Integer is an integer N in @L, such that there are exactly N integers greater than N in @L. Output any Noble Integer found in @L, or an empty list if none were found.

An interesting question is whether or not there can be multiple Noble Integers in a list.

For example,

Suppose we have list of 4 integers [2, 6, 1, 3].

Here we have 2 in the above list, known as Noble Integer, since there are exactly 2 integers in the list i.e.3 and 6, which are greater than 2.

Therefore the script would print 2.

This feels like a computer science homework problem. The obvious thing to do is to sort the list and use index counting, so I did.

sub noble {
  my @l=sort @_;
  my @r;
  foreach my $m (0..$#l) {
    if ($l[$m] == $#l-$m) {
      push @r,$l[$m];
    }
  }
  return @r;
}