The Highest Maximum
with Raku

by Arne Sommer

The Highest Maximum with Raku

[225] Published 22. February 2023.

This is my response to The Weekly Challenge #205.

Challenge #205.1: Third Highest

You are given an array of integers.

Write a script to find out the Third Highest if found otherwise return the maximum.

Example 1:
Input: @array = (5,3,4)
Output: 3

First highest is 5. Second highest is 4. Third highest is 3.
Example 2:
Input: @array = (5,6)
Output: 6

First highest is 6. Second highest is 5. Third highest is missing, so
  maximum is returned.
Example 3:
Input: @array = (5,4,4,3)
Output: 3

First highest is 5. Second highest is 4. Third highest is 3.

File: third-highest
#! /usr/bin/env raku

unit sub MAIN (*@array where @array.elems >= 2       # [1]
                 && all(@array) ~~ /^<[0..9]>*$/, :v($verbose));

my @unique = @array.sort.squish.reverse;             # [2]

say ": Sorted Unique: { @unique.join(", ") }" if $verbose;

say @unique.elems >= 3 ?? @unique[2] !! @unique[0];  # [3]

[1] Ensure at least 2 elements, as it would not be much of an array with 0 or 1 elements. All of them must be non-negative integers, courtesy of the regex.

[2] Sort the array (with sort, lowest value first), get rid of duplicates (with sqish, which works on sorted arrays; use unique otherwise), and reverse the result (with reverse, highest value first).

See docs.raku.org/routine/squish for more information about squish.

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

See docs.raku.org/routine/reverse for more information about reverse.

[3] At least three elements? Print the third one (at index 2). If not, print the first one - which is the maximum.

Running it:

$ ./third-highest 5 3 4
3

$ ./third-highest 5 6
6

$ ./third-highest 5 4 4 3
3

Looking good.

With verbose mode:

$ ./third-highest -v 5 3 4
: Sorted Unique: 5, 4, 3
3

$ ./third-highest -v 5 6
: Sorted Unique: 6, 5
6

$ ./third-highest -v 5 4 4 3
: Sorted Unique: 5, 4, 3
3

Just to be sure that Raku does the right thing, i.e. sorts the values numerically (and not as strings):

$ ./third-highest -v 5 4 4 3 100 1 11 10
: Sorted Unique: 100, 11, 10, 5, 4, 3, 1
10

Challenge #205.2: Maximum XOR

You are given an array of integers.

Write a script to find the highest value obtained by XORing any two distinct members of the array.

Example 1:
Input: @array = (1,2,3,4,5,6,7)
Output: 7

The maximum result of 1 xor 6 = 7.
Example 2:
Input: @array = (2,4,1,3)
Output: 7

The maximum result of 4 xor 3 = 7.
Example 3:
Input: @array = (10,5,7,12,8)
Output: 7

The maximum result of 10 xor 5 = 15.

File: maximum-xor
#! /usr/bin/env raku

unit sub MAIN (*@array where @array.elems >= 2
                   && all(@array) ~~ /^<[0..9]>*$/,  # [1]
               :v(:$verbose));

my @unique = @array.unique;                          # [2]
my $end    = @unique.end;                            # [3]
my $max    = -Inf;                                   # [4]

say ": Unique: @unique[]" if $verbose;

for 0 .. $end - 1 -> $left                           # [5]
{
  for $left + 1 .. $end -> $right                    # [6]
  {
    my $xor = @unique[$left] +^ @unique[$right];     # [7]

    say ": @unique[$left] xor @unique[$right] -> $xor { "max" if $  }"
      if $verbose;

    $max = max($max, $xor);                          # [8]
  }
}

say $max;                                            # [9]

[1] Exactly the same as the «third-highest» program, from the first part of the challenge.

[2] Remove duplicates (with unique). Note that squish would not work here, as the array is not sorted.

[3] The index of the last element (with end), which is one less than the length (which we would get with length).

See docs.raku.org/routine/end for more information about end.

[4] The result will end up here. We will keep the highest value, so start with a value that is guaranteed to be lower than anything else - -Inf. Yes, we can definitely add a sign on Inifinity.

See https://docs.raku.org/type/Num#index-entry-Inf_(definition) for more information about the Infinity value Inf.

[5] We are going to apply XOR on every combination of values. So we iterate over the index for the first one (called left) here.

[6] Then we iterate over the second index (called right), starting just after the left index value. See the verbose output below to see that we get it right. (We do.)

[7] Get the XOR value, with the +^ operator.

See docs.raku.org/routine/+$CIRCUMFLEX_ACCENT for more information about the XOR operator +^.

[8] Keep the highest value, using max.

See docs.raku.org/routine/max for more information about max.

[9] Print the result.

Running it:

$ ./maximum-xor 1 2 3 4 5 6 7
7

$ ./maximum-xor 2 4 1 3
7

$ ./maximum-xor 10 5 7 12 8
15

Looking good.

Let us have a go at verbose mode:

$ ./maximum-xor -v 1 2 3 4 5 6 7
: Unique: 1 2 3 4 5 6 7
: 1 xor 2 -> 3 
: 1 xor 3 -> 2 
: 1 xor 4 -> 5 
: 1 xor 5 -> 4 
: 1 xor 6 -> 7 
: 1 xor 7 -> 6 
: 2 xor 3 -> 1 
: 2 xor 4 -> 6 
: 2 xor 5 -> 7 
: 2 xor 6 -> 4 
: 2 xor 7 -> 5 
: 3 xor 4 -> 7 
: 3 xor 5 -> 6 
: 3 xor 6 -> 5 
: 3 xor 7 -> 4 
: 4 xor 5 -> 1 
: 4 xor 6 -> 2 
: 4 xor 7 -> 3 
: 5 xor 6 -> 3 
: 5 xor 7 -> 2 
: 6 xor 7 -> 1 
7

$ ./maximum-xor -v 2 4 1 3
: Unique: 2 4 1 3
: 2 xor 4 -> 6 
: 2 xor 1 -> 3 
: 2 xor 3 -> 1 
: 4 xor 1 -> 5 
: 4 xor 3 -> 7 
: 1 xor 3 -> 2 
7

$ ./maximum-xor -v 10 5 7 12 8
: Unique: 10 5 7 12 8
: 10 xor 5 -> 15 
: 10 xor 7 -> 13 
: 10 xor 12 -> 6 
: 10 xor 8 -> 2 
: 5 xor 7 -> 2 
: 5 xor 12 -> 9 
: 5 xor 8 -> 13 
: 7 xor 12 -> 11 
: 7 xor 8 -> 15 
: 12 xor 8 -> 4 
15

And that's it.