This is my response to The Weekly Challenge #327.
n integers.
1..n
in the given array.
Input: @ints = (1, 2, 1, 3, 2, 5)
Output: (4, 6)
The given array has 6 elements.
So we are looking for integers in the range 1..6 in the given array.
The missing integers: (4, 6)
Input: @ints = (1, 1, 1)
Output: (2, 3)
Input: @ints = (2, 2, 1)
Output: (3)
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 0 && all(@ints) ~~ Int, # [1]
:v(:$verbose));
my $max = @ints.elems; # [2]
my $set = @ints>>.Int.grep( 0 < * <= $max).Set; # [3]
if $verbose
{
say ": Range: 1 .. $max";
say ": Matches: { $set.keys.sort.join(", ") }";
}
my @missing = (1..$max).grep({ ! so $set{$_} }); # [4]
say "({ @missing.join(", ") })"; # [5]
[1] The challenge does not say that negative inters are illegal, even if the examples do not have any, so I have chosen to allow them. At least one integer.
[2] The number of elements, i.e. the upper limit in the lookup range.
[3] Coerce the input values to Integers to get rid of the printing
unfriendly IntStr type they have, courtesy of the command line. Then use
grep to only keep values in the lookup range, and finally Set to
turn that into a hash like structure.
See docs.raku.org/routine/Set for more information about Set.
[4] Start with the range values, apply grep to only keep the
values that do not occur in the Set. We use the Boolean coercer so and
negate that with !.
[5] Pretty print the result.
Running it:
$ ./missing-integers 1 2 1 3 2 5
(4, 6)
$ ./missing-integers 1 1 1
(2, 3)
$ ./missing-integers 2 2 1
(3)
Looking good.
With verbose mode:
$ ./missing-integers -v 1 2 1 3 2 5
: Range: 1 .. 6
: Matches: 1, 2, 3, 5
(4, 6)
$ ./missing-integers -v 1 1 1
: Range: 1 .. 3
: Matches: 1
(2, 3)
$ ./missing-integers -v 2 2 1
: Range: 1 .. 3
: Matches: 1, 2
(3)
Input: @ints = (4, 1, 2, 3)
Output: [1,2], [2,3], [3,4]
The minimum absolute difference is 1.
Pairs with MAD: [1,2], [2,3], [3,4]
Input: @ints = (1, 3, 7, 11, 15)
Output: [1,3]
Input: @ints = (1, 5, 3, 8)
Output: [1,3], [3,5]
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 0 && all(@ints) ~~ Int # [1]
&& @ints.elems == @ints.unique.elems, # [1a]
:v(:$verbose));
my @sort = @ints.sort; # [2]
my @diff = (1 .. @sort.end).map({ @sort[$_] - @sort[$_ -1] }); # [3]
my $mad = @diff.min; # [4]
my $set = @ints>>.Int.Set; # [5]
my @result; # [6]
if $verbose
{
say ": Sorted: @sort[]";
say ": Diff: @diff[]";
}
for sort $set.keys -> $k # [7]
{
my $is-mad = so $set{$k + $mad}; # [8]
@result.push: ($k, $k + $mad) if $is-mad; # [9]
say ": $k, { $k+1 } { $is-mad ?? "is MAD" !! "does not exist" }"
if $verbose;
}
say @result.raku; # [10]
[1] Integers only, and at least one of them. Ensure that they are unique by getting rid of duplcates and check that this does not alter the number of elements [1a].
[2] Sort the values, so that we can compare two and two neighbours in search of the MAD.
[3] For each index (except the very first one), use map to get the
difference between the value at the current index and the one to the left.
This is by design a positive value, so can be used as is.
[4] Get the MAD value.
[5] Get rid of the IntStr type, as in the first part of the challenge,
and turn the input into a Set.
[6] The result will end up here.
[7] Iterate over the set keys, in sorted order. Note that this will be numeric sorting order, courtesy of [5].
[8] Do we have the upper half of the pair?
[9] If so, add it to the result.
[10] Not-so-pretty print the result.
Running it:
$ ./mad 4 1 2 3
[(1, 2), (2, 3), (3, 4)]
$ ./mad 1 3 7 11 15
[(1, 3),]
$ ./mad 1 5 3 8
[(1, 3), (3, 5)]
Looking good. I.e. correct. Pretty it ain't...
With verbose mode:
$ ./mad -v 4 1 2 3
: Sorted: 1 2 3 4
: Diff: 1 1 1
: 1, 2 is MAD
: 2, 3 is MAD
: 3, 4 is MAD
: 4, 5 does not exist
[(1, 2), (2, 3), (3, 4)]
$ ./mad -v 1 3 7 11 15
: Sorted: 1 3 7 11 15
: Diff: 2 4 4 4
: 1, 3 is MAD
: 3, 5 does not exist
: 7, 9 does not exist
: 11, 13 does not exist
: 15, 17 does not exist
[(1, 3),]
$ ./mad -v 1 5 3 8
: Sorted: 1 3 5 8
: Diff: 2 2 3
: 1, 3 is MAD
: 3, 5 is MAD
: 5, 7 does not exist
: 8, 10 does not exist
[(1, 3), (3, 5)]
And that's it.