Peter
Peter Campbell Smith

The twice largest and
number of cuties

Weekly challenge 191 — 14 November 2022

Week 191 - 14 Nov 2022

Task 1

Task — Twice largest

You are given list of integers, @list. Write a script to find out whether the largest item in the list is at least twice as large as each of the other items.

Examples


Example 1
Input: @list = (1,2,3,4)
Output: -1
The largest in the given list is 4. However 4 is not 
  greater than twice of every remaining elements.
1 x 2 <= 4
2 x 2 <= 4
2 x 3 >  4

Example 2
Input: @list = (1,2,0,5)
Output: 1
The largest in the given list is 5. Also 5 is greater 
  than twice of every remaining elements.
1 x 2 <= 5
2 x 2 <= 5
0 x 2 <= 5

Example 3
Input: @list = (2,6,3,1)
Output: 1
The largest in the given list is 6. Also 6 is greater 
  than twice of every remaining elements.
2 x 2 <= 6
3 x 2 <= 6
1 x 2 <= 6

Example 4
Input: @list = (4,5,2,3)
Output: -1
The largest in the given list is 5. Also 5 is not greater
  than twice of every remaining elements.
4 x 2 >  5
2 x 2 <= 5
3 x 2 >  5

Analysis

The simplest way to do this is to reverse-sort the list, and then the condition is simply whether the first item in the sorted list is no less than double the second.

Given a modern computer this will complete in milliseconds in even quite a long list. But when I started programming over 50 years ago sorting was something to be avoided as it took so long, especially if the list of items to be sorted was more than would fit in memory. Back then, 128 kB was a large computer, so sorting things like a payroll took hours, with numerous stops to change tapes (about 40cm in diameter) on tape drives which had to be cleaned every hour with cotton buds and isopropanol.

So a better algorithm - for 1970 - would be to make a single pass through the list, checking each value to see if is the largest seen so far, and also if it is the second largest, like this:

if ($this > $largest) {
    $second = $largest;
    $largest = $this;
}

And again, the test after completing the pass if whether the largest is greater than or equal to the second largest.

I've coded both of these methods in my submission.

Try it 

Try running the script with any input:



example: 1, 2, 3, 4, 8

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-11-14
# PWC 191 task 1

use v5.28;
use utf8;
use warnings;

my (@tests, $test, @sorted, $largest, $second, $this);

@tests = ([1, 2, 3, 4], [1, 2, 0, 5], [2, 6, 3, 1], [4, 5, 2, 3], 
    [1, 5, 16, 28, 35, 44, 50, 61, 78, 83, 99, 200]);

# loop over tests
while ($test = shift @tests) {
    
    # method A
     @sorted = reverse sort {$a <=> $b} @$test;
     say qq[\nInput:    \@list = (] . join(', ', @$test) . qq[)\nOutput1: ] . ($sorted[0] >= 2 * $sorted[1] ? '1' : '-1');

    # method B 
    $largest = $second = 0;
    for $this (@$test) {
        if ($this > $largest) {
            $second = $largest;
            $largest = $this;
        }
     }
     say qq[Output2: ] . ($largest >= 2 * $second ? '1' : '-1');         
}

Output


Input:    @list = (1, 2, 3, 4)
Output1: -1
Output2: -1

Input:    @list = (1, 2, 0, 5)
Output1: 1
Output2: 1

Input:    @list = (2, 6, 3, 1)
Output1: 1
Output2: 1

Input:    @list = (4, 5, 2, 3)
Output1: -1
Output2: -1

Input:    @list = (1, 5, 16, 28, 35, 44, 50, 61, 78, 83, 99, 200)
Output1: 1
Output2: 1

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain