## Advent Calendar - December 2, 2023

Saturday, Dec 2, 2023| Tags: Perl

### |   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.

`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] );
}
``````

#### * `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.

## SO WHAT DO YOU THINK ?

If you have any suggestions or ideas then please do share with us.