# ETOOBUSY đźš€ minimal blogging for the impatient

# PWC124 - Tug of War

**TL;DR**

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

# The challenge

You are given a set of

`$n`

integers (n1, n2, n3, â€¦.).Write a script to divide the set in two subsets of

`n/2`

sizes each so that the difference of the sum of two subsets is the least. If`$n`

is even then each subset must be of size`$n/2`

each. In case`$n`

is odd then one subset must be`($n-1)/2`

and other must be`($n+1)/2`

.

Example`Input: Set = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100) Output: Subset 1 = (30, 40, 60, 70, 80) Subset 2 = (10, 20, 50, 90, 100) Input: Set = (10, -15, 20, 30, -25, 0, 5, 40, -5) Output: Subset 1 = (30, 0, 5, -5) Subset 2 = (10, -15, 20, -25, 40)`

# The questions

Just as a curiosity, Iâ€™d ask if itâ€™s a real *set* or something like a
*multiset*, where items might be repeated. Iâ€™ll assume itâ€™s a *set*,
which will come handy in the Raku solution, but the whole thing can
be rearranged to cope with *multisets* as well (as an example, the
Perl solution does not care about it).

# The solution

I was really in a hurry this time and I only got to implement the
dumbest of the algorithms: try all possible partitions of the input set
into two â€śhalvesâ€ť according to the rules, and keep the one with the best
*score*.

The condition weâ€™re using here is that the sum of only one of the two subsets is as close as possible to the half of the sum of all elements. This allows us to spare one sum at each iteration through the possible combinations.

Due to the hurry, I started from Perl first, leveraging the Combinations iterator:

```
sub tug_of_war (@set) {
my $n = scalar @set; # number of elements in the set
my $n_2 = $n % 2 ? ($n - 1) / 2 : $n / 2; # size of "smaller" subset
my $subset_target = sum(@set) / 2; # target "half" of sum
# we will go through the possible combinations of $n_2 elements out
# of our $n in the @set, checking their sum against the "subset target"
# of one-half of the total sum
my $cit = combinations_iterator($n_2, @set);
# this will keep our "best" rolling solution during the iteration, and
# the absolute best at the end
my ($solution, $solution_delta);
while (my @subsets = $cit->()) {
# our combinations_iterator returns both the $n_2 subset, as well as
# the remaining items. We will concentrate the sum on the first
# sub-array, i.e. the first subset
# we evaluate how far we are from the target sum for a subset. We
# don't care about the sign, just "how much" we're far off
my $subset_delta = abs(sum($subsets[0]->@*) - $subset_target);
# update our current best according to the new combination. This also
# takes care of the initialization at the first pass, thanks to the
# check for !$solution
($solution, $solution_delta) = (\@subsets, $subset_delta)
if (!$solution) || ($solution_delta > $subset_delta);
# if we're below the tolerance for our distance to the target, let's
# call it a day and return this solution!
last if $subset_delta < TOLERANCE;
}
return $solution->@*;
}
```

The Raku version is an attempt to a translation. We leverage the
â€śbatteries includedâ€ť combinations routine here, which does not
return a partition but just the combination, so we have to eventually
calculate the *other* half of the set by using the set difference
operator `(-)`

. This is where the difference between sets and multisets
kicks in, so as anticipated it might be easily addressed by doing this
calculation using Bags instead.

```
sub tug-of-war (@set) {
my $n = @set.elems; # number of elements in the set
my $n_2 = $n %% 2 ?? $n / 2 !! ($n - 1) / 2; # size of "smaller" subset
my $subset_target = @set.sum / 2; # target "half" of sum
my (@solution, $solution_delta);
for @set.combinations($n_2) -> @subset {
my $subset_delta = abs(@subset.sum - $subset_target);
($solution_delta, @solution) = ($subset_delta, |@subset)
if (!defined($solution_delta)) || ($solution_delta > $subset_delta);
last if $solution_delta < TOLERANCE;
}
return (@solution, (@set (-) @solution).keys);
}
```

The full code will be available soon in The Weekly Challenge repository, for nowâ€¦ have fun and stay safe!!!

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