PWC 371 Subset Equilibrium (Just nod if you can hear me)

Another explosive weekly challenge. And by explosive I mean exponential complexity. Let's see what we've got. First I'll adjust the background music for equilibrium ... Comfortably Numb

Relax, I'll Need Some Information First

You are given an array of numbers. Write a script to find all subsets where the sum of elements equals the sum of their indices.

# Example 1 Input: @nums = (2, 1, 4, 3)
#.          Output: (2, 1), (1, 4), (4, 3), (2, 3)
#   Subset 1: (2, 1) Values: 2 + 1 = 3 Positions: 1 + 2 = 3
#   Subset 2: (1, 4) Values: 1 + 4 = 5 Positions: 2 + 3 = 5
#   Subset 3: (4, 3) Values: 4 + 3 = 7 Positions: 3 + 4 = 7
#   Subset 4: (2, 3) Values: 2 + 3 = 5 Positions: 1 + 4 = 5
#
# Example 2 Input: @nums = (3, 0, 3, 0)
#           Output: (3, 0), (3, 0, 3)
#   Subset 1: (3, 0) Values: 3 + 0 = 3 Positions: 1 + 2 = 3
#   Subset 2: (3, 0, 3) Values: 3 + 0 + 3 = 6 Positions: 1 + 2 + 3 = 6
#
# Example 3 Input: @nums = (5, 1, 1, 1)
#           Output: (5, 1, 1)
#   Subset 1: (5, 1, 1) Values: 5 + 1 + 1 = 7 Positions: 1 + 2 + 4 = 7
#
# Example 4 Input: @nums = (3, -1, 4, 2)
#           Output: (3, 2), (3, -1, 4)
#   Subset 1: (3, 2) Values: 3 + 2 = 5 Positions: 1 + 4 = 5
#   Subset 2: (3, -1, 4) Values: 3 + (-1) + 4 = 6 Positions: 1 + 2 + 3 = 6
#
# Example 5 Input: @nums = (10, 20, 30, 40)
#           Output: ()

Just the Basic Facts, Can You Show Me Where It Hurts?

Perusing the examples, I see that there are a couple of unstated requirements. From example 1, the improper subset (1,2,3,4) should work, but it's not in the given output, so apparently that should be excluded. And in example two, the subset (3) should work, but it's not in the output, so apparently subsets have to have at least two members.

I don't see any way of doing this other than generating all possible subsets and checking if they work. My approach is going to be to number the positions, and generate all possible subsets of the positions. Extracting members from the given list will be done with a hash slice. There's going to be a little annoyance that the task numbers positions starting from 1, while Perl array indexing is based from 0.

For a set of n members, there are 2ⁿ-1 possible subsets. I know that a way to generate subsets is to count from 1 to 2ⁿ-1 and check which bits are 1s in the binary representation. I know how to generate all possible subsets, but do I want to? Because I also know that there are CPAN modules that do this, and I have Algorithm::Combinatorics hanging around from previous problems, with its convenient subsets function, so let's use that.

I Do Believe It's Working, Good

sub sseq(@nums)
{
    use Algorithm::Combinatorics qw/subsets/;
    use List::Util qw/sum0/;
    my @result;

    my $s = subsets( [0 .. $#nums] );
    while ( my $position = $s->next() )
    {
        my $size = scalar(@$position);
        # Only proper subsets of size 2 or more
        next if $size == scalar(@nums) || $size < 2;

        # Subsets are indexed at zero, but positions at 1, so compensate in sum
        my $sumPosition = $size + sum0  @$position;

        my $sumNumbers = sum0 @nums[ @$position ];

        if ( $sumNumbers == $sumPosition )
        {
            push @result, [@nums[@$position]]
        }
    }
    return \@result;
}

Your Lips Move, But I Can't Hear What You're Saying

Explanatory notes:

• use Algorithm::Combinatorics qw/subsets/ -- This function creates an iterator to generate consecutive subsets from a given list of members. We're going to pass it a list of positions, from 0 to the last index of @nums.

• use List::Util qw/sum0/ -- sum0 handles empty lists by returning zero instead of an error, as sum does. That shouldn't come up in this particular function, but I generally use sum0 as my default, because I invariably get a warning from sum about an empty array and end up changing it anyway.

• my $size = scalar(@$position) -- the size of the position array comes up repeatedly, so let's get a handle on it.

• my @sumPosition = $size + sum0(...) -- The sum we're looking for is based on using positions numbered from 1, but we have them numbered from 0. We need to add 1 to each of the positions, which is the same as adding the number of positions.

• my @sumNumbers = sum0 @nums[ @$position ] -- Here's why I wanted positions to be indexed from zero: so that they could be used in a hash slice to extract the corresponding numbers.

• push @result, [@nums[@$position]] -- the result of this function is going to be a reference to an array of arrays (it's array reference turtles all the way down). Once again, the hash slice, now encased in [] to create an array reference.

That'll Keep You Going Through the Show

This function answers the question, but it leaves two things undone.

First, the order of the lists is unspecified. There's no apparent reason for the order in the examples, and I quickly found out that the subsets iterator doesn't return subsets in the same order as the examples.

To create unit tests, I want to check that arrays contain the same members, but order doesn't matter. In the Test2 suite, this can be accomplished by putting the expected elements into a bag data structure.

sub runTest
{
    use Test2::V0;
    use Test2::Tools::Compare qw/bag item/;
    my $check;

    $check = bag { item [1,4]; item [2,1]; item [2,3]; item [4,3]; end(); };
    is( sseq(2,1,4,3), $check, "Example 1");
[...]

Our bags are checked, so ...

Come On, It's Time To Go

Second, to display the output, we have to unwrap the array references and render them as formatted strings.

say join ", ", map { "(" . join(", ", $_->@*) . ")" } sseq(@ARGV)->@*;

What's going on here?

• sseq(@ARGV)->@* -- Call our function, using the command line arguments, and dereference it (which yields an array of array references).
• map { ... } -- Transform each of the array references
• "(" . join(", ", $_->@*) . ")" -- $_ is a reference to an array, so $_->@* is the list of elements in the array. Make it a comma-separated string, encased in parentheses.
• say join ", ", ... -- output each of those parenthesized strings, separated by commas

I Have Become Comfortably Numb

Equilibrium achieved.