Peter
Peter Campbell Smith

The smallest hero

Weekly challenge 244 — 20 November 2023

Week 244: 20 Nov 2023

Task 2

Task — Group hero

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.

Examples


Example 1
Input: @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

Analysis

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.

Try it 

Try running the script with any input:



example: 1, 2, 3, 4, 5 — max of 6 numbers, please

Script


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

Output


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

 

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