RogerBW's Blog

Perl Weekly Challenge 50: merged intervals and noble integers 30 March 2020

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

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1