Foo meets Bar and

the wizardly trio

Weekly challenge 187 — 17 October 2022

Week 187 - 17 Oct 2022

Task 2

You are given a list of positive numbers, `@n`

, having at least 3 numbers.

Write a script to find the triplets `(a, b, c)`

from the given list that satisfies the following rules.

- a + b > c
- b + c > a
- a + c > b
- a + b + c is maximum.

In case, you end up with more than one triplets having the maximum then:

- pick the triplet where
`a >= b >= c`

.

Example 1Input: @n = (1, 2, 3, 2); Output: (3, 2, 2)Example 2Input: @n = (1, 3, 2); Output: ()Example 3Input: @n = (1, 1, 2, 3); Output: ()Example 4Input: @n = (2, 4, 3); Output: (4, 3, 2)

My first approach to this was to use `Algorithm::Combinatorics`

to get all the possible triplets, filter out the ones that satisfy rules 1, 2 and 3, and find which of these maximises `a + b + c`

. In my submission that is Method 1 and it certainly works.

However, there is an easier way - my Method 2:

- Sort the supplied list into reverse order
- Suppose the first three items are now m, n and o.
- If o is greater than m - n, then we have the solution - output it and stop
- If not, discard the first item in the list and if there are still at least 3 items in the list go back to step 2.
- If you get here, there is no solution.

Why does this work?

In a reverse sorted list, the first three numbers are the three largest in the list, and clearly their sum is the largest possible triplet sum, so that's rule 5 taken care of.

For any three reverse sorted numbers m, n and o, rules 1 and 3 will always be satisfied because any sum involving m is already larger than o, so we only need to do test 2. If that succeeds, we have the solution, because no subsequently found triplet will have a larger sum.

If it fails, then no solution can contain m, because if n + o doesn't exceed m then no other pair will. So we can discard m and work on the next triplet (n, o and p) in the same way.

#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.28; # The Weekly Challenge - 2022-10-17 use utf8; # Week 187 - task 2 - Magical triplets use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; use Algorithm::Combinatorics qw[variations]; my (@tests, $test, $iter, $triplet, $sum, $max, @triplet, @results, $r, $j, @rand, @this); @tests = ([1, 2, 3, 2], [1, 3, 2], [1, 1, 2, 3], [2, 4, 3], [1, 2, 3, 4, 5, 6, 7], [1, 7, 13, 34, 51, 78, 0, 4, 56, 43, 199, 20], [1, 0, 0]); for $j (0 .. 19) { $rand[$j] = int(rand(1000)); } push @tests, \@rand; say qq[\nMETHOD 1]; TEST: for $test (@tests) { say qq[\nInput: (] . join(', ', @$test) . ')'; $max = 0; @results = (); # generate all possible triplets $iter = variations($test, 3); while ($triplet = $iter->next) { # apply tests 1 to 3 next unless $triplet->[0] + $triplet->[1] > $triplet->[2]; next unless $triplet->[1] + $triplet->[2] > $triplet->[0]; next unless $triplet->[0] + $triplet->[2] > $triplet->[1]; # calc a + b + c and see if it is >= the max seen so far $sum = $triplet->[0] + $triplet->[1] + $triplet->[2]; next unless $sum >= $max; @results = () if $sum > $max; push @results, [$triplet->[0], $triplet->[1], $triplet->[2]]; $max = $sum; } # no solution if (scalar @results == 0) { say qq[Output: ()]; # just one solution } elsif (scalar @results == 1) { say qq[Output: ($results[0]->[0], $results[0]->[1], $results[0]->[2])]; # several solutions: need to apply test 5 and select the first } else { for $r (@results) { if ($r->[0] >= $r->[1] and $r->[1] >= $r->[2]) { say qq[Output: ($r->[0], $r->[1], $r->[2])]; next TEST; } } # possibly they could all fail test 5 say qq[Output: ()]; } } say qq[\nMETHOD 2]; TEST2: for $test (@tests) { # sort the input list into decreasing order @this = @$test; say qq[\nInput: (] . join(', ', @this) . ')'; @this = reverse (sort { $a <=> $b } @this); # work along the list until you find three successive elements a, b, c where a - b < c for $j (0 .. scalar @this - 3) { next if $this[$j] - $this[$j + 1] >= $this[$j + 2]; say qq[Output: ($this[$j], $this[$j + 1], $this[$j + 2])]; next TEST2; } # no such triplet meets the criteria say qq[Output: ()]; }

METHOD 1 Input: (1, 2, 3, 2) Output: (3, 2, 2) Input: (1, 3, 2) Output: () Input: (1, 1, 2, 3) Output: () Input: (2, 4, 3) Output: (4, 3, 2) Input: (1, 2, 3, 4, 5, 6, 7) Output: (7, 6, 5) Input: (1, 7, 13, 34, 51, 78, 0, 4, 56, 43, 199, 20) Output: (78, 56, 51) Input: (1, 0, 0) Output: () Input: (650, 337, 664, 958, 970, 292, 208, 781, 564, 628, 455, 273, 39, 598, 729, 365, 407, 675, 38, 966) Output: (970, 966, 958) METHOD 2 Input: (1, 2, 3, 2) Output: (3, 2, 2) Input: (1, 3, 2) Output: () Input: (1, 1, 2, 3) Output: () Input: (2, 4, 3) Output: (4, 3, 2) Input: (1, 2, 3, 4, 5, 6, 7) Output: (7, 6, 5) Input: (1, 7, 13, 34, 51, 78, 0, 4, 56, 43, 199, 20) Output: (78, 56, 51) Input: (1, 0, 0) Output: () Input: (650, 337, 664, 958, 970, 292, 208, 781, 564, 628, 455, 273, 39, 598, 729, 365, 407, 675, 38, 966) Output: (970, 966, 958)

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