Peter
Peter Campbell Smith

Third highest and maximum xor

Weekly challenge 205 — 20 February 2023

Week 205 - 20 Feb 2023

Task 1

Task — Third highest value

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

Analysis

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.

Try it 

Example: 1, 2, 2, 3

Script


#!/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];
}

Output


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 which has been created by
Peter Campbell Smith is hereby placed in the public domain