This is my response to The Weekly Challenge #189.
Input: @array = qw/e m u g/, $target = 'b'
Output: e
Input: @array = qw/d c e f/, $target = 'a'
Output: c
Input: @array = qw/j a r/, $target = 'o'
Output: r
Input: @array = qw/d c a f/, $target = 'a'
Output: c
Input: @array = qw/t g a l/, $target = 'v'
Output: v
I have chosen to write a procedure doing the job, with the main program wrapping up the examples:
File: greater-character
#! /usr/bin/env raku
unit sub MAIN (:v(:$verbose));
say greater_character( qw/e m u g/, 'b'); # [1]
say greater_character( qw/d c e f/, 'a'); # [1]
say greater_character( qw/j a r/, 'o'); # [1]
say greater_character( qw/d c a f/, 'a'); # [1]
say greater_character( qw/t g a l/, 'v'); # [1]
sub greater_character (@array, $target)
{
my @greater = @array.grep( * gt $target ); # [2]
say ":A:[{ @array.join(",") }] T:$target F:[{ @greater.join(", ") }] \
S:[{ @greater.sort.join(", ") }]"
if $verbose;
return @greater.sort.first // $target # [3]
}
[1] Print the result of using the five examples, one at a time.
[2] Keep characters greater than the target, using grep and
gt (as in «greater than», the string comparison variant of
>).
[3] Sort the list (of characters greater than the target), and return the first one. If we have an empty list, as in the fifth example, return the target itself.
Running it:
$ ./greater-character
e
c
r
c
v
Looking good.
Let us have a go at verbose mode, to see what is going on:
$ ./greater-character -v
:A:[e,m,u,g] T:b F:[e, m, u, g] S:[e, g, m, u]
e
:A:[d,c,e,f] T:a F:[d, c, e, f] S:[c, d, e, f]
c
:A:[j,a,r] T:o F:[r] S:[r]
r
:A:[d,c,a,f] T:a F:[d, c, f] S:[c, d, f]
c
:A:[t,g,a,l] T:v F:[] S:[]
v
A is the input array, T is the target, F is the filtered array, and S is the sorted (filtered) array.
Here is a one liner version of the procedure
sub greater_character (@array, $target)
{
return @array.grep( * gt $target ).sort.first // $target;
}
Input: @array = (1, 3, 3, 2)
Output: (3, 3)
The degree of the given array is 2.
The possible subarrays having the degree 2 are as below:
(3, 3)
(1, 3, 3)
(3, 3, 2)
(1, 3, 3, 2)
And the smallest of all is (3, 3).
Input: @array = (1, 2, 1, 3)
Output: (1, 2, 1)
Input: @array = (1, 3, 2, 1, 2)
Output: (2, 1, 2)
Input: @array = (1, 1, 2, 3, 2)
Output: (1, 1)
Input: @array = (2, 1, 2, 1, 1)
Output: (1, 2, 1, 1)
Yet again, the main program supplying the examples to a dedicated procedure doing the actual work:
File: array-degree
#! /usr/bin/env raku
unit sub MAIN (:v(:$verbose));
say array_degree(1, 3, 3, 2);
say array_degree(1, 2, 1, 3);
say array_degree(1, 3, 2, 1, 2);
say array_degree(1, 1, 2, 3, 2);
say array_degree(2, 1, 2, 1, 1);
sub array_degree (*@array)
{
my $degree = @array.Bag.map( *.value ).max; # [1]
my @candidates;
say "\n:Array: ", @array, " with degree $degree" if $verbose;
for 0 .. @array.elems -1 -> $start # [2]
{
for $start .. @array.elems -1 -> $stop # [3]
{
my @slice = @array[$start .. $stop]; # [4]
my $slice_degree = @slice.Bag.map( *.value ).max; # [5]
@candidates.push: @slice if $degree == $slice_degree; # [6]
say ":Slice: [$start - $stop] -> @slice[] \
{ $degree == $slice_degree ?? "+" !! ""} " if $verbose;
}
}
say ":Candidates: ", @candidates if $verbose;
my @sorted = @candidates.sort({ $^a.elems <=> $^b.elems }); # [7]
say ":Sorted: ", @sorted if $verbose;
return @sorted.first; # [8]
}
[1] The degree. The Bag type gives us the unique values
as keys, and the frequencey as the values. Then we transfor each key/value pair to a
single value (the value) and finally we pick the largest one.
See
docs.raku.org/type/Bag
for more information about the Bag type.
[2] Iterate over the start index of the slice candidate.
[3] .. and the end index.
[4] Get the actual array slice. (Note that we could have skipped slices with too few items, i.e. less than the degree, but doing it the hard way works - as the arrays are pretty small.
[5] Get the degree of the slice.
[6] Add the slice to the list of candidates, if it has the correct degree.
[7] Sort the list of candidates, by the number of elemens in each one.
[8] Return the first one, as that has the lowest number of items - thus the smallest slice.
Running it:
$ ./array-degree
[3 3]
[1 2 1]
[2 1 2]
[1 1]
[1 2 1 1]
Looking good.
With verbose mode. The trailing + indicates a slice with the correct
degree.
$ ./array-degree -v
:Array: [1 3 3 2] with degree 2
:Slice: [0 - 0] -> 1
:Slice: [0 - 1] -> 1 3
:Slice: [0 - 2] -> 1 3 3 +
:Slice: [0 - 3] -> 1 3 3 2 +
:Slice: [1 - 1] -> 3
:Slice: [1 - 2] -> 3 3 +
:Slice: [1 - 3] -> 3 3 2 +
:Slice: [2 - 2] -> 3
:Slice: [2 - 3] -> 3 2
:Slice: [3 - 3] -> 2
:Candidates: [[1 3 3] [1 3 3 2] [3 3] [3 3 2]]
:Sorted: [[3 3] [1 3 3] [3 3 2] [1 3 3 2]]
[3 3]
:Array: [1 2 1 3] with degree 2
:Slice: [0 - 0] -> 1
:Slice: [0 - 1] -> 1 2
:Slice: [0 - 2] -> 1 2 1 +
:Slice: [0 - 3] -> 1 2 1 3 +
:Slice: [1 - 1] -> 2
:Slice: [1 - 2] -> 2 1
:Slice: [1 - 3] -> 2 1 3
:Slice: [2 - 2] -> 1
:Slice: [2 - 3] -> 1 3
:Slice: [3 - 3] -> 3
:Candidates: [[1 2 1] [1 2 1 3]]
:Sorted: [[1 2 1] [1 2 1 3]]
[1 2 1]
:Array: [1 3 2 1 2] with degree 2
:Slice: [0 - 0] -> 1
:Slice: [0 - 1] -> 1 3
:Slice: [0 - 2] -> 1 3 2
:Slice: [0 - 3] -> 1 3 2 1 +
:Slice: [0 - 4] -> 1 3 2 1 2 +
:Slice: [1 - 1] -> 3
:Slice: [1 - 2] -> 3 2
:Slice: [1 - 3] -> 3 2 1
:Slice: [1 - 4] -> 3 2 1 2 +
:Slice: [2 - 2] -> 2
:Slice: [2 - 3] -> 2 1
:Slice: [2 - 4] -> 2 1 2 +
:Slice: [3 - 3] -> 1
:Slice: [3 - 4] -> 1 2
:Slice: [4 - 4] -> 2
:Candidates: [[1 3 2 1] [1 3 2 1 2] [3 2 1 2] [2 1 2]]
:Sorted: [[2 1 2] [1 3 2 1] [3 2 1 2] [1 3 2 1 2]]
[2 1 2]
:Array: [1 1 2 3 2] with degree 2
:Slice: [0 - 0] -> 1
:Slice: [0 - 1] -> 1 1 +
:Slice: [0 - 2] -> 1 1 2 +
:Slice: [0 - 3] -> 1 1 2 3 +
:Slice: [0 - 4] -> 1 1 2 3 2 +
:Slice: [1 - 1] -> 1
:Slice: [1 - 2] -> 1 2
:Slice: [1 - 3] -> 1 2 3
:Slice: [1 - 4] -> 1 2 3 2 +
:Slice: [2 - 2] -> 2
:Slice: [2 - 3] -> 2 3
:Slice: [2 - 4] -> 2 3 2 +
:Slice: [3 - 3] -> 3
:Slice: [3 - 4] -> 3 2
:Slice: [4 - 4] -> 2
:Candidates: [[1 1] [1 1 2] [1 1 2 3] [1 1 2 3 2] [1 2 3 2] [2 3 2]]
:Sorted: [[1 1] [1 1 2] [2 3 2] [1 1 2 3] [1 2 3 2] [1 1 2 3 2]]
[1 1]
:Array: [2 1 2 1 1] with degree 3
:Slice: [0 - 0] -> 2
:Slice: [0 - 1] -> 2 1
:Slice: [0 - 2] -> 2 1 2
:Slice: [0 - 3] -> 2 1 2 1
:Slice: [0 - 4] -> 2 1 2 1 1 +
:Slice: [1 - 1] -> 1
:Slice: [1 - 2] -> 1 2
:Slice: [1 - 3] -> 1 2 1
:Slice: [1 - 4] -> 1 2 1 1 +
:Slice: [2 - 2] -> 2
:Slice: [2 - 3] -> 2 1
:Slice: [2 - 4] -> 2 1 1
:Slice: [3 - 3] -> 1
:Slice: [3 - 4] -> 1 1
:Slice: [4 - 4] -> 1
:Candidates: [[2 1 2 1 1] [1 2 1 1]]
:Sorted: [[1 2 1 1] [2 1 2 1 1]]
[1 2 1 1]
And that's it.