Nobly Merged Raku
[61] Published 6. March 2020.This is my response to the Perl Weekly Challenge #50.
Challenge #50.1: Merge Intervals
Write a script to merge the given intervals where ever possible.
Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22]. The final result should be something like below: |
Interval Expansion
There are several ways to deal with this. I'll start with the easiest one conceptually; expanding the intervals to full lists and merge them. File: intermerge-gather
unit sub MAIN (Str $intervals
= '[2,7], [3,9], [10,12], [15,19], [18,22]', # [1]
:$verbose); # [2]
my @intervals = $intervals.split(/\,\s+/); # [3]
say ": @intervals[]" if $verbose; # [2a]
my @numbers; # [4]
for @intervals -> $current # [5]
{
die "$current: Not an interval"
unless $current ~~ /^\[(\d+)\,(\d+)\]$/; # [6]
my $from = $0.Int; # [7]
my $to = $1.Int; # [7]
die "Illegal interval: $from > $to" if $from > $to; # [8]
@numbers.append($0.Int .. $1.Int); # [9]
}
say ": @numbers[]" if $verbose; # [2b]
my @sorted = @numbers.sort.squish; # [10]
say ": @sorted[]" if $verbose; # [2c]
my @res = gather # [11]
{
my $start = @sorted.shift; # [12]
my $end = $start; # [12]
while @sorted # [13]
{
if @sorted[0] == $end +1 # [14]
{
$end++; # [14a]
@sorted.shift; # [14b]
}
else
{
take "[$start,$end]"; # [15]
$start = $end = @sorted.shift; # [15a]
}
}
take "[$start,$end]"; # [16]
}
say @res.join(", "); # [17]
[1] Specify the intervals as a single string. The default value is the actual intervals given in the challenge.
[2] Verbose mode is nice when developing code, especially when (and I mean «when», and not «if») the program gives an unexpected result.
[3] Split the interval string into a list of intervals (still as strings), on the form «[x,y]».
[4] We collect the numbers in this one.
[5] Iterate over the intervals,
[6] • Abort the program if the interval is illegal.
[7] • Pick out the «start» and «end» values.
[8] • Abort the program if the «end» is higher than the «start».
[9] • Add the (all the) numbers in the interval to our list.
[10] Sort the numbers (sort) and get rid
of duplicates (squish).
[11] I am fond of gather/take, so chose to
use this to merge the values into intervals.
[12] We start by removing the first value from the list, setting the «start» and «end» to that value.
[13] While we have more values in the list,
[14] • if the first one in the list follows on after the last one, set it as the new «end» [14a] and remove the value from the list [14b].
[15] &bill; else: return the current interval (as the next value doesn't belong to this one) and start a new one (as in [12]).
[16] Whatever is left is the final interval, and we return that.
[17] This one takes (pun intended) all the values (intervals) and prints them, comma separated.
Running it:
$ raku intermerge-gather
[2,12], [15,22]
$ raku intermerge-gather '[2,7], [3,9], [10,12], [15,19], [18,22]'
[2,12], [15,22]
$ raku intermerge-gather --verbose '[2,7], [3,9], [10,12], [15,19], [18,22]'
: [2,7] [3,9] [10,12] [15,19] [18,22]
: 2 3 4 5 6 7 3 4 5 6 7 8 9 10 11 12 15 16 17 18 19 18 19 20 21 22
: 2 3 4 5 6 7 8 9 10 11 12 15 16 17 18 19 20 21 22
[2,12], [15,22]
$ raku intermerge-gather '[2,7], [3,9], [10,12], [15,19], [18,22], [13,14]'
[2,22]
$ raku intermerge-gather --verbose '[2,7], [3,12], [15,19], [18,22], [13,14]'
: [2,7] [3,12] [15,19] [18,22] [13,14]
: 2 3 4 5 6 7 3 4 5 6 7 8 9 10 11 12 15 16 17 18 19 18 19 20 21 22 13 14
: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
[2,22]
$ raku intermerge-gather '[3,9]'
[3,9]
Note the output from Verbose Mode. The first line is the individual intervals (as strings). It looks almost the same as the input, but is a list of strings (instead of a single string). The next line has all the intervals expanded, in the specified order. The third line has them in sorted order, without duplicates.
Note that this program works for small(ish) intervals. Very large intervals (as e.g. [15, 100.000.000.000]) will take a very long time to compute - and use a lot of memory to hold all the values.
Try the following, lean back, and watch nothing happening:
$ raku intermerge-gather --verbose '[15,100000000000], [2,2]'
Non-Expanding Intervals
In this program we treat the intervals as indeed intervals, without expanding them. Merging intervals is much easier if they are sorted, so I have ensured that they are. (The example given in the challenge indicates that they should already be sorted, but I have chosen not to rely on that.)
Instead of gather/take I just print the values this
time.
unit sub MAIN (Str $intervals = '[2,7], [3,9], [10,12], [15,19], [18,22]',
:$verbose);
sub from ($interval) # [1]
{
$interval ~~ /^\[(\d+)\,\d+\]$/ || die "Not a legal interval"; # [1a]
return $0.Int; # [1b]
}
sub from-to ($interval) # [2]
{
$interval ~~ /^\[(\d+)\,(\d+)\]$/ || die "Not a legal interval"; # [2a]
return $0.Int, $1.Int; # [2b]
}
my @intervals = $intervals.split(/\,\s+/).sort( &from ); # [3]
say ": @intervals[]" if $verbose;
my ($from, $to) = from-to(@intervals.shift); # [4]
while @intervals # [5]
{
my ($new-from, $new-to) = from-to(@intervals.shift); # [6]
if $new-from <= $to +1 # [7]
{
$to = $new-to if $new-to > $to; # [7a]
}
else
{
print "[$from,$to], "; # [8]
$from = $new-from; # [8a]
$to = $new-to; # [8a]
}
}
say "[$from,$to]"; # [9]
[1] We need two helper functions, taking an interval string as argument. This one return the «from» value. We'll use this for sorting.
[2] This one return the «from» and «to» values.
[3] We split the string into separate intervals, and sort them (by the «from» values) at the same time. Note how we specify a custom sort function.
[4] Get the «from» and «to» values for the first interval.
[5] While there are more intervals,
[6] • Get the next one.
[7] • If the new one overlaps or follows on after the current one, set the «to» value to the new «to» value - if that one is higher.
[8] • If not: Print the interval, and prepare a new interval [8a].
[9] Print the final interval.
Running this program gives the same results as the first one, except that that this one actually works out for very large intervals:
$ raku intermerge-loop --verbose '[15,100000000000], [2,2]'
: [2,2] [15,100000000000]
[2,2], [15,100000000000]
The program is also smaller, so that is win as well.
An Interval Object
We could have solved this with a custom class (an interval object), with methods to merge them. But I don't think that would give a better looking program. We'd still need to figure out when to merge manually. So I have chosen not to do this.Challenge #50.2: Noble Integer
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. |
We must take each number in the list, and check if there are that many numbers with a value greater than that one in the list. That is straightforward:
File: noblint
subset N50 of Int where 50 >= * >= 1; # [2]
unit sub MAIN (*@numbers where @numbers.elems >= 3); # [1]
die "Illegal non-int input" unless all(@numbers) ~~ N50; # [3]
for @numbers.sort.squish -> $number # [4]
{
if @numbers.grep(* > $number).elems == $number # [5]
{
say $number; # [6]
exit; # [7]
}
}
[1] A Slurpy Argument to get all the input. Note that we cannot use a type constraint on slurpy arguments, so I added that separately (in [3]).
[2] A custom type definition that allows the integers 1 .. 50 only.
[3] Die if one or more of the arguments are illegal.
[4] Iterate over the numbers, in sorted order and without duplicates (if any).
[5] This one does what I said before the program code.
[6] Say the number.
[7] Commented out, so that we get duplicate hits - if any.
Running it:
$ raku noblint 2 6 1 3
2
$ raku noblint 1 2 3 6
2
The challenge doesn't specify if duplicate values should be allowed, but I have chosen to allow them.
$ raku noblint 2 6 1 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
2
They do not affect the match as long as we add them before the matching value.
The Question
«An interesting question is whether or not there can be multiple Noble Integers in a list.»Answer: No.
Why: Let us consider a generic list, where we have a match with the value «X» somewhere in the list:
The list is sorted, so all the values to the
left of «X» are either lower
than or equal to (as we allow duplicates) «X».
If we have duplicates, only the last one can be chosen (as we look for values higher
than it). To get a lower value we must move our
green marker at least one position to
the left. The new number is now at least 1 less than
«X» and the number of values higher
than it is at least 1 more than «X».
That gives the equation «X - 1 == X + 1» which cannot be satisfied.
The same logic applies in the other direction, to the right.
It is possible to have a list without a match, e.g. «1,2,3,4,5».
And that's it.