The smallest hero

Weekly challenge 244 — 20 November 2023

Week 244 - 20 Nov 2023

Task 2

You are given an array of integers representing the strength. Write a script to return the sum of the powers of all possible combinations; power is defined as the square of the largest number in a sequence, multiplied by the smallest.

Example 1Input: @nums = (2, 1, 4) Output: 141 Group 1: (2) => square(max(2)) * min(2) => 4 * 2 => 8 Group 2: (1) => square(max(1)) * min(1) => 1 * 1 => 1 Group 3: (4) => square(max(4)) * min(4) => 16 * 4 => 64 Group 4: (2,1) => square(max(2,1)) * min(2,1) => 4 * 1 => 4 Group 5: (2,4) => square(max(2,4)) * min(2,4) => 16 * 2 => 32 Group 6: (1,4) => square(max(1,4)) * min(1,4) => 16 * 1 => 16 Group 7: (2,1,4) => square(max(2,1,4)) * min(2,1,4) => 16 * 1 => 16 Sum: 8 + 1 + 64 + 4 + 32 + 16 + 16 => 141

I couldn't see an easy (but see below) alternative to generating all the combinations
of all the subsets of `@nums`

, so that's what my code does. I used a module (Algorithm::Combinatorics)
to generate the combinations, because ... well, why not?

Then it's a case of identifying the smallest and largest of each combination and multiplying
them as instructed, and with 15 elements in `@nums`

that runs in well under a second.

The only possible optimisation I could see is that once you've seen a combination of
`($i, $j)`

, you can skip
calculating any other combination, say `($i, $p, $q, $j)`

if `$p`

and `$q`

are within the range `$i .. $j`

- but you
still need to add the previously calculated value into `$sum`

again. I think, but have not verified,
that the savings would be minimal given the amount of additional code needed.

#!/usr/bin/perl use v5.26; # The Weekly Challenge - 2023-11-20 use utf8; # Week 244 task 2 - Group hero use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use Algorithm::Combinatorics 'combinations'; my $details = 1; group_hero(2, 1, 4); group_hero(6, 8, 10); $details = 0; group_hero(1, 2, 4, 5, 7, 9, 11, 15, 19, 23, 30, 31, 39, 41, 47); sub group_hero { my (@nums, $count, $sum, $c, $iter, $comb, $smallest, $largest, $i, $explain, $product); # initialise @nums = @_; $count = @_; $sum = 0; $explain = ''; # loop over sizes of combination to consider for $c (1 .. $count) { # loop over combinations from @nums of that size $iter = combinations(\@nums, $c); while ($comb = $iter->next) { # get smallest and largest $smallest = 1e6; $largest = -1e6; for $i (0 .. $c - 1) { $smallest = $comb->[$i] if $comb->[$i] < $smallest; $largest = $comb->[$i] if $comb->[$i] > $largest; } # increment $sum $product = $smallest * $largest ** 2; $explain .= ' (' . join(', ', @$comb) . ') => ' . ($largest ** 2) . qq[ * $smallest = $product\n] if $details; $sum += $product } } # show results say qq[\nInput: \@nums = (] . join(', ', @nums) . ')'; say qq[Output: $sum\n] . substr($explain, 0, -1); }

Input: @ints = (2, 1, 4) Output: 141 (2) => 4 * 2 = 8 (1) => 1 * 1 = 1 (4) => 16 * 4 = 64 (2, 1) => 4 * 1 = 4 (2, 4) => 16 * 2 = 32 (1, 4) => 16 * 1 = 16 (2, 1, 4) => 16 * 1 = 16 Input: @ints = (6, 8, 10) Output: 4112 (6) => 36 * 6 = 216 (8) => 64 * 8 = 512 (10) => 100 * 10 = 1000 (6, 8) => 64 * 6 = 384 (6, 10) => 100 * 6 = 600 (8, 10) => 100 * 8 = 800 (6, 8, 10) => 100 * 6 = 600 Input: @ints = (1, 2, 4, 5, 7, 9, 11, 15, 19, 23, 30, 31, 39, 41, 47) Output: 143239195

Peter Campbell Smith is hereby placed in the public domain