Perl Weekly Challenge #218 - Feeling Negative
Tags: perlweeklychallenge, perl, product, negative
Published: 2023-05-24 23:31:52

Hi everybody! Back this week with a solution to just the first challenge project. I know I won't have time for the second one, plus I'm not sure of an efficient solution. I really liked this first one, though! I got to try some new techniques in it.

Spoiler alert, since I know it's only Wednesday/Thursday depending on where you are, but if you're looking to solve this challenge yourself you might prefer not to read this yet.

So the goal of the first challenge is to find the 3 integers in a list that have the greatest product, and print the product.

First, here's the code as usual:

    #!/usr/bin/perl

    use strict;
    use v5.24;

    my @sorted = sort {abs($b) <=> abs($a)} @ARGV;
    my $complete;
    until ($complete) {
        my $negCount = isNeg($sorted[0]) + isNeg($sorted[1]) + isNeg($sorted[2]);
        if ($negCount == 2 || $negCount == 0) {
            $complete = 1;
        } else {
            my $positives;
            for (2..$#sorted) {
                $positives = 1 if !isNeg($sorted[$_]);
            }
            if ($positives) {
                for (2, 1, 0) {
                    if (abs($sorted[$_]) == $sorted[$_]) {
                        next;
                    } else {
                        splice (@sorted, $_, 1);
                        last;
                    }
                }
            } else {
                say $sorted[-1] * $sorted[-2] * $sorted[-3] and exit;
            }
        }
    }
    say $sorted[0] * $sorted[1] * $sorted[2];

    sub isNeg {
        my $num = shift;
        return $num < 0 ? 1 : 0;
    }

So, what's it doing? First of all, we know that we want the list sorted so highest numbers are first, because they will result in the highest product if the 3 highest are first. So this means we can first sort by absolute value. However, the element of complexity here is that negative numbers can change things. If you have 1 or 3 negative numbers as your top 3 by absolute value, you need to get that down to 0 or 2. Otherwise the multiplication by an odd number of negative numbers results in a negative product, which is certainly not going to be the greatest product. If we can't get the negative numbers in the final 3 to 2 or 0, then we have special handling for that negative product.

So first, we use a custom sort routine to sort the list by absolute values without replacing them. This was recommended by ChatGPT, and it's an excellent solution to this. I need to think of custom sort routines as solutions for more things. Then we start a loop until we've decided we've found the top 3 finalists.

We count the number of negative numbers in the top three, and if we don't need any further filtering we end the loop. If we do need further filtering, we check if there are any other positive numbers to filter to. If there aren't, we assume we have a negative product and choose the smallest numbers possible to multiply and print out. If there are, we splice out negatives until we get an additional positive in the top 3.

It might sound complicated, but negative numbers do really complicate this task. I have a feeling someone else will find a more efficient or easier way to do it, so I look forward to the other solutions. And I look forward to solutions for the second task also. See you next week!