Advent Calendar 2023

|   Day 1   |   Day 2   |   Day 3   |

The gift is presented by Bob Lied. Today he is talking about his solution to The Weekly Challenge - 206. This is re-produced for Advent Calendar 2023 from the original post.

Task : Array Pairings

Perl Weekly Challenge number 206 has a task called "Array Pairings" to solve:

You are given an array of integers having even number of elements..
Write a script to find the maximum sum of the minimum of each pairs.

The solution (spoiler alert) is to sort the list and take a slice of every other element. In the Facebook Perl Programming group, Robbie Hatley asks if we can prove that this is the optimal solution. Here’s a proof.

Start by sorting the list descending, so that we have

a >= b >= c >= d >= ... x[1] >= x[0]

The first element, a, will be greater than anything it is paired with, so it will be eliminated from being in the sum. So what shall we pair with a? There are two choices: we can pair it with b, or we can pair it with something that is not b.

Suppose that we pair it with b. Then the resulting sum will be b + sum(x[i]), where all the x[i] are less than or equal to b. Let’s call this S1. The maximum value of S1 will be if all the list elements are equal to b, so S1 <= b + mb, where m is the number of other pairs contributing to the sum.

Now suppose we take the other choice, a number less than (or equal to) b from further down the sorted list; let’s call it x[j]. The resulting sum, let’s call it S2, will now have a maximum value of S2 <= x[j] + mb.

S2 must be less than or equal to S1, because x[j] <= b. So, our best choice to maximize the sum is to pair a with b.

Having disposed of a and b, consider the next highest value, c. The same reasoning applies: d will be the best choice to pair with c to maximize the sum. We can proceed down the whole list this way.

The Perl solution is a small function that exploits some language features:

sub arrayPairs($list)
{
    my @oddIndex = map { $_ * 2 + 1 } 0 .. int( $#{$list} / 2 );
    return sum(  (sort { $b <=> $a } $list->@*)[@oddIndex] );
}

* sub arrayPairs($list) – we are using function signatures from Perl 5.36. $list is a reference to an array of numbers.

* $#{$list} – yields the last index of the list (an odd number because we are given that the list has an even number of elements and we index starting from 0).

* 0 .. int($#{$list}/2) – the range operator generates a list of integers from 0 to half the size of $list.

* map { $_ * 2 + 1 } – applies the code between the braces to each element of the range. This generates the list 1,3,5,...

* $list->@* – array postfix dereferencing (catchy name) yields the entire array from a reference. We could have used @$list, but I’ve come to use the -> form consistently.

* sort { $b <=> $a } – sorts numerically in descending order. This is idiomatic in Perl, using the three-way comparison operator <=>. The default sort is for strings.

* (sort ...)[] – The sort returns a sorted array. Instead of assigning to a temporary variable, we can index directly into the resulting array by enclosing it in parentheses like this.

* (sort ..)[@oddIndex] – Using an array as the index selects more than one value (a slice) from the sorted array. I used the list of odd numbers we generated on the previous line. I could have put that expression in-line within the square brackets, but let’s concede something to readability.

* sum((sort..)[..]) – The sum function comes from the List::Util module

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.

|   Advent Calendar 2023   |