Third highest and maximum xor

Weekly challenge 205 — 20 February 2023

Week 205 - 20 Feb 2023

Task 1

We are given an array of integers and asked to find the third highest value. The examples suggest how the output should be presented.

The first solution that comes to mind is to reverse sort @array, and the third highest value will then be $array[2]. But this won't work because there may be duplicates, so for example if the array is 1, 2, 2, 3, the third highest value is 1, not 2.

So what we need is to sort the unique values in the array, and happily there is a module for that - List::Uniq. With that installed, the line that does the work is:

@fixed = sort {$b <=> $a} uniq(@array);

... and the answer is $fixed[2] - the third element of @fixed. But Mohammad wants some pretty printing of the result which allows for there being no third highest value, and I have completed the possibilities by adding test for no second highest, and also no first highest - ie the list is empty.

It could be said that sorting the list is overkill, and it's probably true that a faster solution exists by looping over the list keeping a running tally of the top three values seen. I'll leave that for someone else.

#!/usr/bin/perl # Peter Campbell Smith - 2023-02-20 use v5.28; use utf8; use warnings; use List::Uniq ':all'; # Task: You are given an array of integers. Write a script to find the # third highest value in the array. # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/205/1 my (@test, $j); third_highest(5, 3, 4); third_highest(5, 6); third_highest(5, 4, 4, 3); third_highest(-3, -2, -1); third_highest(1, 1, 1, 1, 1); third_highest(); # make a longer example - 100 random numbers in (0 .. 999) for $j (0 .. 99) { $test[$j] = int(rand(1000)); } third_highest(@test); sub third_highest { # find the 3rd highest value in the argument list my (@array, $result, $count); # get the unique values in the list and sort them largest to smallest @array = sort {$b <=> $a} uniq(@_); $count = scalar @array; # select appropriate legend if ($count >= 3) { $result = qq[First highest is $array[0]. Second highest is $array[1]. Third highest is $array[2].]; } elsif ($count == 2) { $result = qq[First highest is $array[0]. Second highest is $array[1]. Third highest is missing so maximum is returned.]; } elsif ($count == 1) { $result = qq[First highest is $array[0]. Second and third highest are missing so maximum is returned.]; } else { $result = 'List is empty.'; } say qq[\nInput: \@array = (] . join (', ', @_) . ')' . qq[\nOutput: $result]; }

Input: @array = (5, 3, 4) Output: First highest is 5. Second highest is 4. Third highest is 3. Input: @array = (5, 6) Output: First highest is 6. Second highest is 5. Third highest is missing so maximum is returned. Input: @array = (5, 4, 4, 3) Output: First highest is 5. Second highest is 4. Third highest is 3. Input: @array = (-3, -2, -1) Output: First highest is -1. Second highest is -2. Third highest is -3. Input: @array = (1, 1, 1, 1, 1) Output: First highest is 1. Second and third highest are missing so maximum is returned. Input: @array = () Output: List is empty. Input: @array = (255, 114, 782, 446, 107, 132, 539, 567, 813, 100, 729, 434, 38, 609, 271, 340, 2, 615, 610, 592, 504, 604, 688, 952, 243, 672, 445, 101, 23, 64, 403, 835, 543, 517, 405, 943, 745, 20, 855, 418, 643, 6, 250, 626, 314, 187, 592, 790, 285, 82, 487, 57, 884, 348, 661, 107, 651, 336, 3, 535, 533, 266, 577, 766, 115, 332, 630, 517, 400, 108, 190, 265, 804, 434, 374, 41, 880, 403, 768, 513, 365, 140, 13, 499, 130, 365, 806, 313, 526, 521, 400, 724, 950, 11, 389, 631, 711, 220, 79, 218) Output: First highest is 952. Second highest is 950. Third highest is 943.

The content of
this website
is licensed by
Peter
Campbell Smith under a
Creative Commons Attribution 4.0 International Licence