# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC206 - Array Pairings

**TL;DR**

On with TASK #2 from The Weekly Challenge #206. Enjoy!

# The challenge

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.

Example 1`Input: @array = (1,2,3,4) Output: 4 Possible Pairings are as below: a) (1,2) and (3,4). So min(1,2) + min(3,4) => 1 + 3 => 4 b) (1,3) and (2,4). So min(1,3) + min(2,4) => 1 + 2 => 3 c) (1,4) and (2,3). So min(1,4) + min(2,3) => 2 + 1 => 3 So the maxium sum is 4.`

Example 2`Input: @array = (0,2,1,3) Output: 2 Possible Pairings are as below: a) (0,2) and (1,3). So min(0,2) + min(1,3) => 0 + 1 => 1 b) (0,1) and (2,3). So min(0,1) + min(2,3) => 0 + 2 => 2 c) (0,3) and (2,1). So min(0,3) + min(2,1) => 0 + 1 => 1 So the maximum sum is 2.`

# The questions

I guess Iâ€™d ask if thereâ€™s a limit on the input integers (to possibly use a big-integer library), as well as a limit on the size of the array.

# The solution

This challenge made me realize that Iâ€™m a (cyber)bully.

My first go-to solution is to go *brute force*. For the kind of inputs
that we get as examples in these challenges, itâ€™s even too much call it
*brute* (or *force*).

But brute force is just the tool of the bully: it works on the weak, but
backfires on the strong. So, in occasions like this, itâ€™s good to think
about *something else*.

The bottom line of the intuition in this case is that itâ€™s better to sort the array first (it doesnâ€™t matter if in increasing or decreasing order, would you say that?), then take items in pairs starting from either end.

Iâ€™ll not provide a formal proof here, but suffices to say that if we start from such an array (letâ€™s say in increasing order), then we have something like this:

\[(x_0 \le x_1) \le (x_2 \le x_3) \le ... \le (x_{2k} \le x_{2k+1})\]Now letâ€™s consider any couple of pairs, with $A \le B \le C \le D$:

\[... (A \le B) ... (C \le D) ...\]This contributes $A + C$ to the sum.

What would happen if we do any swap between the two? The contribution
from *other* pairs would be unchanged, so the modification depends on
what swap we do. There are a few possibilities, but the bottom line is
that the new contribution is *always* going to be $A + B$, because they
appear in different pairs and are (by definition) less than, or equal
to, both $C$ and $D$.

Hence, the swap leads us to:

\[A + B \le A + C\]Which means that either it does not change, or it gets worse.

Which means that weâ€™re good with our sorted array.

OK, enough wavy maths, letâ€™s get to the code, Perl first:

```
use List::Util qw< pairkeys sum >;
print array_pairings(@ARGV), "\n";
sub array_pairings { sum pairkeys sort { $a <=> $b } @_ }
```

Oh, the joys of CORE! Batteries *mostly* included, at last!

Raku goes on a similar note, we take advantage of lazy lists with automatic inference here:

```
sub MAIN (*@args) { put array-pairings(@args) }
sub array-pairings (Array[Int]() $array) { $array.sort[0, 2 ... *].sum }
```

I also got to learn something from liztormato, yay!

Soâ€¦ stay safe and well ordered!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*