by Arne Sommer

# To a Greater Degree with Raku

[209] Published 6. November 2022.

This is my response to The Weekly Challenge #189.

## Challenge #189.1: Greater Character

You are given an array of characters (a..z) and a target character.

Write a script to find out the smallest character in the given array lexicographically greater than the target character.

Example 1: ```Input: @array = qw/e m u g/, \$target = 'b' Output: e ``` Example 2: ```Input: @array = qw/d c e f/, \$target = 'a' Output: c ``` Example 3: ```Input: @array = qw/j a r/, \$target = 'o' Output: r ``` Example 4: ```Input: @array = qw/d c a f/, \$target = 'a' Output: c ``` Example 5: ```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; } ```

## Challenge #189.2: Array Degree

You are given an array of 2 or more non-negative integers.

Write a script to find out the smallest slice, i.e. contiguous subarray of the original array, having the degree of the given array.

The degree of an array is the maximum frequency of an element in the array.

Example 1: ```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). ``` Example 2: ```Input: @array = (1, 2, 1, 3) Output: (1, 2, 1) ``` Example 3: ```Input: @array = (1, 3, 2, 1, 2) Output: (2, 1, 2) ``` Example 4: ```Input: @array = (1, 1, 2, 3, 2) Output: (1, 1) ``` Example 5: ```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.