Perl Weekly Challenge: Week 309
Challenge 1:
Min Gap
You are given an array of integers,
@ints, increasing order.Write a script to return the element before which you find the smallest gap.
Example 1
Input: @ints = (2, 8, 10, 11, 15)
Output: 11
8 - 2 => 6
10 - 8 => 2
11 - 10 => 1
15 - 11 => 4
11 is where we found the min gap.
Example 2
Input: @ints = (1, 5, 6, 7, 14)
Output: 6
5 - 1 => 4
6 - 5 => 1
7 - 6 => 1
14 - 7 => 7
6 and 7 where we found the min gap, so we pick the first instance.
Example 3
Input: @ints = (8, 20, 25, 28)
Output: 28
8 - 20 => 14
25 - 20 => 5
28 - 25 => 3
28 is where we found the min gap.
This one seemed fairly straightforward but there were some interesting subtleties.
I began by allocating a hash. The keys are going to be the gap sizes and the values, the elements after each gap (which the spec rather confusingly refers to as "the element before which you find ... the gap.")
my %diffs;
Noe we traverse the indices of @ints starting from the second element to the last.
The value of the preceding element is subtracted from the current element. The result
becomes the key and the current element becomes the value of an element of %diffs.
for 1 .. @ints.end -> $i {
%diffs{ @ints[$i] - @ints[$i - 1] } = @ints[$i];
}
Once all gaps have been found, we just need to find the smallest key in %diffs with .min()
and print the associated value.
say %diffs{%diffs.keys.min};
This gives use the correct answer for example 1 but for example 2 we get 7 instead of 6. Why? Because
there are two gaps of length 1 and the position of the second one overwrites the position of the first one.
But as per the spec, we want the first instance. The solution is to change %diffs so that its' values are
arrays of positions not single ones. We rewrite the line within the loop so each position is .push()ed into this
array.
%diffs{ @ints[$i] - @ints[$i - 1] }.push(@ints[$i]);
We also have to slightly modify the last line so we are selecting the first position we found for the smallest key.
say %diffs{%diffs.keys».Int.min}[0];
Now we get the answer 6 for example 2 as we should.
Example 3 has a typo; the difference should be 12 not 14. (It doesn't change the final answer though.)
Even worse, our solution is wrong! We get back 20 instead of 28. After some investigation I realized the reason
is that hash keys even if they outwardly look like numbers are actually Strings. So .min() was comparing
the keys alphabetically instead of numerically. I fixed this by converting all the keys to Ints before
comparison with the hyper method call operator » and .Int(). Now everythinf is ship-shape.
say %diffs{%diffs.keys».Int.min}[0];
The Perl version is mostly the same.
my %diffs;
for my $i (1 .. scalar @ints - 1) {
push @{ $diffs{ $ints[$i] - $ints[$i - 1] } }, $ints[$i];
}
Perl doesn't have .min() but it is easy to emulate by taking the 0'th elemen of an ascending numeric sort().
say @{ $diffs{ (sort { $a <=> $b } keys %diffs)[0] } }[0];
Challenge 2:
Min Diff
You are given an array of integers,
@ints.Write a script to find the minimum difference between any two elements.
Example 1
Input: @ints = (1, 5, 8, 9)
Output: 1
1, 5 => 5 - 1 => 4
1, 8 => 8 - 1 => 7
1, 9 => 9 - 1 => 8
5, 8 => 8 - 5 => 3
5, 9 => 9 - 5 => 4
8, 9 => 9 - 8 => 1
Example 2
Input: @ints = (9, 4, 1, 7)
Output: 2
9, 4 => 9 - 4 => 5
9, 1 => 9 - 1 => 8
9, 7 => 9 - 7 => 2
4, 1 => 4 - 1 => 3
4, 7 => 7 - 4 => 3
1, 7 => 7 - 1 => 6
We can do this in one line of Raku.
@*ARGS.combinations(2).map({ ($_[0] - $_[1]).abs }).min.say
Input comes from the command line parameters. .combinations(2) provides all two-element combinations of the
input. In .map(), the absolute value of difference between the two members of each combination is found by subtraction and .abs(). The smallest difference is found with .min() and printed with .say().
The Perl version is not quite as concise because we have to provide an implementation of .combinations() but
with that, the core is also one line.
say 0+(sort { $a <=> $b } map { abs($_->[0] - $_->[1]) } combinations(\@ints, 2))[0];
Also once again we use the numeric sort workaround for the lack of .min().
say followed by a parenthesis is interpreted as a function (it is actually an operator; Perl is weird.)
and a warning about it is emitted. One way to surpress the warning is to put 0+ in front of the parenthesis.