Uniquely Empty with Raku

This is my response to The Weekly Challenge #228.

Challenge #228.1: Unique Sum

Input: @int = (2, 1, 3, 2)
Output: 4

In the given array we have 2 unique elements (1, 3).

Input: @int = (1, 1, 1, 1)
Output: 0

In the given array no unique element found.

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.

#! /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.

#! /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:

#! /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

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: ()

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...

#! /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:

#! /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.