by Arne Sommer

Uniquely Empty with Raku

[248] Published 5. August 2023.

This is my response to The Weekly Challenge #228.

Challenge #228.1: Unique Sum

You are given an array of integers.

Write a script to find out the sum of unique elements in the given array.

Example 1: ```Input: @int = (2, 1, 3, 2) Output: 4 In the given array we have 2 unique elements (1, 3). ``` Example 2: ```Input: @int = (1, 1, 1, 1) Output: 0 In the given array no unique element found. ``` Example 3: ```Input: @int = (2, 1, 3, 4) Output: 10 In the given array every element is unique. ```

Let begin with some, let us say, musings...

The `unique` method does not quite fit, as it removes duplicates only - and leaves one instance of each unique value:

```> say <2 1 3 2>.unique; # -> (2 1 3) ```

See docs.raku.org/routine/unique for more information about `unique`.

So no luck there...

The `repeated` method gives us a list of values that occur more than once, which is the opposite of what we want:

```> say <2 1 3 2>.repeated; # -> (2) ```

See docs.raku.org/routine/repeated for more information about `repeated`.

We can use the Set Minus operator `∖` to get there:

```> my @a = <2 1 3 2>; > say @a ∖ @a.repeated; # -> Set(1 3) ```

Note that the Set Minus operator «∖» is a Unicode character (U+2216), and not a regular «\».

We got a Set. We can extract the values (i.e. the Set keys) with the `keys` method:

```> say (@a ∖ @a.repeated).keys; # -> (1 3) ```

See docs.raku.org/type/Set for more information about the `Set` type.

And finally, the sum:

```> say (@a ∖ @a.repeated).keys.sum; # -> 4 ```

Let us wrap it up as a program, and try the other examples.

File: unique-sum-set ```#! /usr/bin/env raku unit sub MAIN (*@int where @int.elems > 0 && all(@int) ~~ Int, # [1] :v(:\$verbose)); my @unique = (@int ∖ @int.repeated).keys; say ": Unique: @unique[]" if \$verbose; say @unique.sum; # [2] ```

[1] Ensure at least one integer.

[2] Print the sum of the values that only occured once.

Running it:

```\$ ./unique-sum-set 2 1 3 2 4 \$ ./unique-sum-set 1 1 1 1 0 \$ ./unique-sum-set 2 1 3 4 10 ```

Looking good.

With verbose mode:

```\$ ./unique-sum-set -v 2 1 3 4 : Unique: 3 1 4 2 10 \$ ./unique-sum-set -v 2 1 3 4 : Unique: 1 2 3 4 10 ```

Oops. A Set (just like a hash) does not have any idea of (sorting) order, so we get the keys shuffled about. We could sort the verbose output, so that the result is the same each time. But the order can still be considered wrong, as it is not the same as the input.

This is just for the verbose mode, so it does not really matter, but let us see if we can do this in a way that retains the order anyway...

Let us have a go at the `reduce` method, with a user supplied function. This reduces (so to speak) the input list to a single value:

```> say <2 1 3 2>.reduce(&infix:<+>); # -> 8 ```

This is just a complicated way of saying the much simpler:

```> say <2 1 3 2>.sum; # -> 8 ```

Which we can do explicitly as:

```> say <2 1 3 2>.reduce(&sum); # -> 8 ```

Or, if you want to use the reduction meta operator `[]`:

```> say [+] <2 1 3 2>; # -> 8 ```

Note that the examples shows the limited scope of the `reduce`; it works on single values, not on the whole shebang. We need a way of looking at the values in contect.

And that is a task for the `Bag` type, as we are interested in value frequencies, i.e. entries with the same value - and their occurence.

File: unique-sum-bag ```#! /usr/bin/env raku unit sub MAIN (*@int where @int.elems > 0 && all(@int) ~~ Int, :v(:\$verbose)); my @unique = @int.Bag.grep( *.value == 1 ).map( *.key ); # [1] say ": Unique: @unique[]" if \$verbose; say @unique.sum; ```

[1] Coerce the list to a `Bag`, a hash like structure where the values in the list turns out as keys, and the values are the number of times they occured. Then we use `grep` to get rid of elements that does not have a value of 1 (i.e. get rid of values that occured multiple times). We still have a `Bag` structure, so we use `map` to replace each element (a key/value pair) with the key - the original value.

See docs.raku.org/type/Bag for more information about the `Bag` type.

The code in [1] is a rip off from the program «ulam-sequence» from my Primarily Ulam article, in response to the Perl Weekly Challenge #144.

Running it:

```\$ ./unique-sum-bag 2 1 3 2 4 \$ ./unique-sum-bag 1 1 1 1 0 \$ ./unique-sum-bag 2 1 3 4 10 ```

Looking good.

With verbose mode:

```\$ ./unique-sum-bag -v 2 1 3 2 : Unique: 3 1 4 \$ ./unique-sum-bag -v 1 1 1 1 : Unique: 0 \$ ./unique-sum-bag -v 2 1 3 4 : Unique: 1 2 4 3 10 ```

Sort of good...

The `Bag` does not retain the order, so we have the same randomly sorted problem as with the `Set`:

```\$ ./unique-sum-bag -v 2 1 3 4 : Unique: 4 2 1 3 10 \$ ./unique-sum-bag -v 2 1 3 4 : Unique: 2 3 1 4 10 ```

This is so fun...

The easy solution; remove verbose mode:

File: unique-sum ```#! /usr/bin/env raku unit sub MAIN (*@int where @int.elems > 0 && all(@int) ~~ Int); say @int.Bag.grep( *.value == 1 ).map( *.key ).sum; ```

I'll leave it at that.

Challenge #228.2: Empty Array

You are given an array of integers in which all elements are unique.

Write a script to perform the following operations until the array is empty and return the total count of operations.

If the first element is the smallest then remove it otherwise move it to the end.

Example 1: ```Input: @int = (3, 4, 2) Ouput: 5 Operation 1: move 3 to the end: (4, 2, 3) Operation 2: move 4 to the end: (2, 3, 4) Operation 3: remove element 2: (3, 4) Operation 4: remove element 3: (4) Operation 5: remove element 4: () ``` Example 2: ```Input: @int = (1, 2, 3) Ouput: 3 Operation 1: remove element 1: (2, 3) Operation 2: remove element 2: (3) Operation 3: remove element 3: () ```

Off we go. No musings this time, and no verbose mode...

File: empty-array ```#! /usr/bin/env raku unit sub MAIN (*@int where @int.elems > 0 # [1] && all(@int) ~~ Int # [1a] && @int.elems == @int.unique.elems); # [1b] my \$operations = 0; # [2] while @int.elems # [3] { my \$first = @int.shift; # [4] \$operations++; # [4a] @int.push: \$first if \$first > @int.min; # [5] } say \$operations; # [6] ```

[1] At least one element, all of them must be integers [1a], and they must all be different [1b] (as discovered if we have a shorter list after removing duplicates.

[2] The number of operations will end up here.

[3] As long as the array has elements.

[4] Get the first element, and uncrease the number of operations [a4].

[5] Add the removed element (from [4]) to the end, if applicable.

[6] Print the number of operations.

Running it:

```\$ ./empty-array 3 4 2 5 \$ ./empty-array 1 2 3 3 ```

Looking good.

It is easy to add verbose mode, but it does complicate the program:

File: empty-array-verbose ```#! /usr/bin/env raku unit sub MAIN (*@int where @int.elems > 0 && all(@int) ~~ Int && @int.elems == @int.unique.elems, :v(:\$verbose)); my \$operations = 0; while @int.elems { my \$first = @int.shift; \$operations++; if \$first > @int.min { @int.push: \$first; say ": Operation \$operations: move \$first to end: ({ @int.join(", ") })" if \$verbose; } elsif \$verbose { say ": Operation \$operations: remove element \$first: ({ @int.join(", ") })"; } } say \$operations; ```

Running it:

```\$ ./empty-array-verbose -v 1 2 3 : Operation 1: remove element 1: (2, 3) : Operation 2: remove element 2: (3) : Operation 3: remove element 3: () 3 \$ ./empty-array-verbose -v 3 4 2 : Operation 1: move 3 to end: (4, 2, 3) : Operation 2: move 4 to end: (2, 3, 4) : Operation 3: remove element 2: (3, 4) : Operation 4: remove element 3: (4) : Operation 5: remove element 4: () 5 ```

And that's it.