The twice largest and

number of cuties

Weekly challenge 191 — 14 November 2022

Week 191 - 14 Nov 2022

Task 1

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.

Example 1Input: @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 > 4Example 2Input: @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 <= 5Example 3Input: @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 <= 6Example 4Input: @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

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.

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

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

Peter Campbell Smith is hereby placed in the public domain