Happy Tug with Raku
[140] Published 8. August 2021.This is my response to the Perl Weekly Challenge #124.
Challenge #124.1: Happy Women Day
Venus Symbol, international gender symbol for
women. Please feel free to use any character.
Example:
^^^^^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^^^^^
^
^
^
^^^^^
^
^
Cut & Paste does the job:
File: happy-women-day
#! /usr/bin/env raku
" ^^^^^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^^^^^
^
^
^
^^^^^
^
^
".print;
Running it:
^^^^^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^^^^^
^
^
^
^^^^^
^
^
That was easy…
Let us have a go at «Any character». And I mean it literally; you can use any character whatsover (preferably a printable one, but that is not enforced):
File: happy-women-day-any
#! /usr/bin/env raku
unit sub MAIN (Str $char where $char.chars == 1); # [1]
"
^^^^^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^ ^
^^^^^
^
^
^
^^^^^
^
^
".subst('^', $char, :g).substr(1).print; # [2]
[1] Specify a (single) character on the command to use instead of the default caret.
[2] Replace the caret with whatever was specified on the command line
with subst (substitute). Note the «:g» (global) argument, so that the
replacement is done for all the carets (and not just once).
See
docs.raku.org/routine/subst
for more information about subst.
Running it with «♀», the Unicode Female Character (affectionately known as U+2640) and «#»:
$ ./happy-women-day-any ♀
♀♀♀♀♀
♀ ♀
♀ ♀
♀ ♀
♀ ♀
♀ ♀
♀ ♀
♀ ♀
♀ ♀
♀ ♀
♀♀♀♀♀
♀
♀
♀
♀♀♀♀♀
♀
♀
$ ./happy-women-day-any '#'
#####
# #
# #
# #
# #
# #
# #
# #
# #
# #
#####
#
#
#
#####
#
#
Note the quotes, as # is a shell metacharacter.
We can actually do it much shorter:
File: happy-women-day-short
#! /usr/bin/env raku
say "♀";
Running it:
$ ./happy-women-day-short
♀
Challenge #124.2: Tug of War
$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)
Subset 1 = (30, 0, 5, -5)
Subset 2 = (10, -15, 20, -25, 40)
We can try to be smart; sorting the values and placing alternate values in each subset. But that would not in any way lead to a correct result - as shown by this program:
File: tow-dispatcher
#! /usr/bin/env raku
unit sub MAIN (*@n where @n.elems > 0 && all(@n) ~~ Int, :v(:$verbose));
my @subset1;
my @subset2;
for @n.sort -> $current
{
@subset1.sum <= @subset2.sum
?? @subset1.push: $current
!! @subset2.push: $current;
}
my $sum1 = @subset1.sum;
my $sum2 = @subset2.sum;
say "Subset 1 = ({ @subset1.join(", ") }){ $verbose ?? " (sum: $sum1)" !! "" }";
say "Subset 2 = ({ @subset2.join(", ") }){ $verbose ?? " (sum: $sum2)" !! "" }";
say ": Difference: { ($sum1 - $sum2).abs }" if $verbose;
Note that the program does not place the values in alternate sets (as I proclaimed up front), but rather in the set with the currently lowest sum.
The first example looks ok (never mind the difference in the sums):
$ ./tow-dispatcher 10 20 30 40 50 60 70 80 90 100
Subset 1 = (20, 40, 60, 80, 100)
Subset 2 = (10, 30, 50, 70, 90)
$ ./tow-dispatcher -v 10 20 30 40 50 60 70 80 90 100
Subset 1 = (10, 30, 50, 70, 90) (sum: 250)
Subset 2 = (20, 40, 60, 80, 100) (sum: 300)
: Difference: 50
But the second example does not work out at all, as we are supposed to have the same number of values in each set:
$ ./tow-dispatcher 10 -15 20 30 -25 0 5 40 -5
Subset 1 = (-25, -15, -5, 0, 5, 10, 20, 30)
Subset 2 = (40)
$ ./tow-dispatcher -v 10 -15 20 30 -25 0 5 40 -5
Subset 1 = (-25, -15, -5, 0, 5, 10, 20, 30) (sum: 20)
Subset 2 = (40) (sum: 40)
: Difference: 20
Trying to be even smarter is certainly possible, as exemplified by the programs «tow-dispatcher2» and «tow-dispatcher3» (included in the zip file, and not discussed here) - but they fail as well.
The Hard Way - Combinations
So let us do this the hard way; setting up every possible combination and do the math.
The first step is to pick half the values. We can do this
with combinations. We can pass it an argument, which is the number of
elements we want in each set; half the size in our case):
> say <1 2 3 4>.combinations(2); # -> ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
That gave us Subset 1. Subset 2 is simply the whole set minus Subset 1. Raku even has an operator for that; called set difference. I'll get to it shortly.
See
docs.raku.org/routine/combinations
for more information about combinations.
But what if the number of elements in the input is odd; e.g. 5? The first subset will get two elements all the time, and the second one will get the remaining three elements. The question: Do we need three elements in the first subset as well?
Let us try; subsets with 2 and 3 elements:
> say <1 2 3 4 5>.combinations(2)
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))
> say <1 2 3 4 5>.combinations(3)
((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) \
(3 4 5))
Then we can compare the results we got from the two commands above. The first column (in green) has the first subset. The second column (in blue) has the second subset, ordered so that the combination (of column 1 and 2) (in yellow) gives us the whole set:
Conclusion: We do not need to take special care when we have an odd number of elements, as we get them for free in the second subset.
But if you want to go there, regardlessly, here is how to do it (with a range as
argument to combinations):
> my @n = <1 2 3 4 5>;
> say @n.combinations(@n.elems/2 .. @n.elems/2 + 0.5)
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5) (1 2 3) \
(1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
Observation: When we have an even number of elements, each result will be calculated
twice with this approach. E.g. Subset 1: 1,2 - Subset 2: 3,4
and the duplicate Subset 1: 3,4 - Subset 2: 1,2. That is
inefficient, but adding checks to remedy this will increase the overhead - and may not
be worth it.
Then the program:
File: tug-of-war
#! /usr/bin/env raku
unit sub MAIN (*@n where @n.elems > 0 && # [1]
all(@n) ~~ Int && # [1a]
@n.elems == @n.unique.elems, # [1b]
:v(:$verbose),
:a(:$all)); # [8]
my $best = Inf; # [2]
my @subset1; # [3]
my @subset2; # [3]
for @n.combinations(@n.elems / 2) -> @first # [4]
{
my @second = (@n (-) @first).keys.sort; # [5]
my $difference = (@first.sum - @second.sum).abs; # [6]
if $difference < $best # [7]
{
say ": { @first.join(", ") } - { @second.join(", ") } = $difference \
[BEST]" if $verbose;
$best = $difference; # [7a]
@subset1 = @first; # [7b]
@subset2 = @second; # [7c]
last if $best == 0 && !$all; # [8]
}
else
{
say ": { @first.join(", ") } - { @second.join(", ") } = $difference"
if $verbose;
}
}
say "Subset 1 = ({ @subset1.join(", ") })"; # [9]
say "Subset 2 = ({ @subset2.join(", ") })"; # [9]
say ": Difference: $best" if $verbose;
[1]
Ensure at least one element. They must all be integers [1a]
(checked with an all junction), and unique (by removing
duplicates and comparing the number of items with the original list) [1b].
[2] The lowest (best) difference so far. Start with a very high number (Inf is the highest there is), so that any combination is an improvement
[3] Store the first and second subsets here, when we find a new one. These sets is the answer, when we finish the loop.
[4] Iterate over all the combinations.
[5]
Get the second subset with set difference operator (-).
The result is a Set, a hash like data structure, so we must apply keys
to get the actual values.
[6] Compute the difference in the sums. Note the use of
abs (absolute value) to remove a negative sign, if any.
[7] A better match (lower sum difference)? If so, take note of the new values.
[8] If we have found two sets with difference zero, we can stop looking - as we cannot better that. Use the «-a» command line option to avoid that, if you want verbose mode to show all the combinations.
[9] And finally, print the result (subsets).
See
docs.raku.org/routine/all
for more information about all.
See
docs.raku.org/routine/unique
for more information about unique.
See
docs.raku.org/routine/(-),%20infix%20%E2%88%96
for more information about the set difference operator (-).
See
docs.raku.org/type/Set
for more information about the Set type.
See
docs.raku.org/routine/abs
for more information about abs.
Running it on the first example:
$ ./tug-of-war 10 20 30 40 50 60 70 80 90 100
Subset 1 = (10, 20, 50, 90, 100)
Subset 2 = (30, 40, 60, 70, 80)
We got the subsets in the wrong order (compared with the challenge), but that does not really matter.
With verbose mode, to see what is going on:
$ ./tug-of-war -v 10 20 30 40 50 60 70 80 90 100
: 10, 20, 30, 40, 50 - 60, 70, 80, 90, 100 = 250 [BEST]
: 10, 20, 30, 40, 60 - 50, 70, 80, 90, 100 = 230 [BEST]
: 10, 20, 30, 40, 70 - 50, 60, 80, 90, 100 = 210 [BEST]
: 10, 20, 30, 40, 80 - 50, 60, 70, 90, 100 = 190 [BEST]
: 10, 20, 30, 40, 90 - 50, 60, 70, 80, 100 = 170 [BEST]
: 10, 20, 30, 40, 100 - 50, 60, 70, 80, 90 = 150 [BEST]
: 10, 20, 30, 50, 60 - 40, 70, 80, 90, 100 = 210
: 10, 20, 30, 50, 70 - 40, 60, 80, 90, 100 = 190
: 10, 20, 30, 50, 80 - 40, 60, 70, 90, 100 = 170
: 10, 20, 30, 50, 90 - 40, 60, 70, 80, 100 = 150
: 10, 20, 30, 50, 100 - 40, 60, 70, 80, 90 = 130 [BEST]
: 10, 20, 30, 60, 70 - 40, 50, 80, 90, 100 = 170
: 10, 20, 30, 60, 80 - 40, 50, 70, 90, 100 = 150
: 10, 20, 30, 60, 90 - 40, 50, 70, 80, 100 = 130
: 10, 20, 30, 60, 100 - 40, 50, 70, 80, 90 = 110 [BEST]
: 10, 20, 30, 70, 80 - 40, 50, 60, 90, 100 = 130
: 10, 20, 30, 70, 90 - 40, 50, 60, 80, 100 = 110
: 10, 20, 30, 70, 100 - 40, 50, 60, 80, 90 = 90 [BEST]
: 10, 20, 30, 80, 90 - 40, 50, 60, 70, 100 = 90
: 10, 20, 30, 80, 100 - 40, 50, 60, 70, 90 = 70 [BEST]
: 10, 20, 30, 90, 100 - 40, 50, 60, 70, 80 = 50 [BEST]
: 10, 20, 40, 50, 60 - 30, 70, 80, 90, 100 = 190
: 10, 20, 40, 50, 70 - 30, 60, 80, 90, 100 = 170
: 10, 20, 40, 50, 80 - 30, 60, 70, 90, 100 = 150
: 10, 20, 40, 50, 90 - 30, 60, 70, 80, 100 = 130
: 10, 20, 40, 50, 100 - 30, 60, 70, 80, 90 = 110
: 10, 20, 40, 60, 70 - 30, 50, 80, 90, 100 = 150
: 10, 20, 40, 60, 80 - 30, 50, 70, 90, 100 = 130
: 10, 20, 40, 60, 90 - 30, 50, 70, 80, 100 = 110
: 10, 20, 40, 60, 100 - 30, 50, 70, 80, 90 = 90
: 10, 20, 40, 70, 80 - 30, 50, 60, 90, 100 = 110
: 10, 20, 40, 70, 90 - 30, 50, 60, 80, 100 = 90
: 10, 20, 40, 70, 100 - 30, 50, 60, 80, 90 = 70
: 10, 20, 40, 80, 90 - 30, 50, 60, 70, 100 = 70
: 10, 20, 40, 80, 100 - 30, 50, 60, 70, 90 = 50
: 10, 20, 40, 90, 100 - 30, 50, 60, 70, 80 = 30 [BEST]
: 10, 20, 50, 60, 70 - 30, 40, 80, 90, 100 = 130
: 10, 20, 50, 60, 80 - 30, 40, 70, 90, 100 = 110
: 10, 20, 50, 60, 90 - 30, 40, 70, 80, 100 = 90
: 10, 20, 50, 60, 100 - 30, 40, 70, 80, 90 = 70
: 10, 20, 50, 70, 80 - 30, 40, 60, 90, 100 = 90
: 10, 20, 50, 70, 90 - 30, 40, 60, 80, 100 = 70
: 10, 20, 50, 70, 100 - 30, 40, 60, 80, 90 = 50
: 10, 20, 50, 80, 90 - 30, 40, 60, 70, 100 = 50
: 10, 20, 50, 80, 100 - 30, 40, 60, 70, 90 = 30
: 10, 20, 50, 90, 100 - 30, 40, 60, 70, 80 = 10 [BEST]
: 10, 20, 60, 70, 80 - 30, 40, 50, 90, 100 = 70
: 10, 20, 60, 70, 90 - 30, 40, 50, 80, 100 = 50
: 10, 20, 60, 70, 100 - 30, 40, 50, 80, 90 = 30
: 10, 20, 60, 80, 90 - 30, 40, 50, 70, 100 = 30
: 10, 20, 60, 80, 100 - 30, 40, 50, 70, 90 = 10
: 10, 20, 60, 90, 100 - 30, 40, 50, 70, 80 = 10
: 10, 20, 70, 80, 90 - 30, 40, 50, 60, 100 = 10
: 10, 20, 70, 80, 100 - 30, 40, 50, 60, 90 = 10
: 10, 20, 70, 90, 100 - 30, 40, 50, 60, 80 = 30
: 10, 20, 80, 90, 100 - 30, 40, 50, 60, 70 = 50
: 10, 30, 40, 50, 60 - 20, 70, 80, 90, 100 = 170
: 10, 30, 40, 50, 70 - 20, 60, 80, 90, 100 = 150
: 10, 30, 40, 50, 80 - 20, 60, 70, 90, 100 = 130
: 10, 30, 40, 50, 90 - 20, 60, 70, 80, 100 = 110
: 10, 30, 40, 50, 100 - 20, 60, 70, 80, 90 = 90
: 10, 30, 40, 60, 70 - 20, 50, 80, 90, 100 = 130
: 10, 30, 40, 60, 80 - 20, 50, 70, 90, 100 = 110
: 10, 30, 40, 60, 90 - 20, 50, 70, 80, 100 = 90
: 10, 30, 40, 60, 100 - 20, 50, 70, 80, 90 = 70
: 10, 30, 40, 70, 80 - 20, 50, 60, 90, 100 = 90
: 10, 30, 40, 70, 90 - 20, 50, 60, 80, 100 = 70
: 10, 30, 40, 70, 100 - 20, 50, 60, 80, 90 = 50
: 10, 30, 40, 80, 90 - 20, 50, 60, 70, 100 = 50
: 10, 30, 40, 80, 100 - 20, 50, 60, 70, 90 = 30
: 10, 30, 40, 90, 100 - 20, 50, 60, 70, 80 = 10
: 10, 30, 50, 60, 70 - 20, 40, 80, 90, 100 = 110
: 10, 30, 50, 60, 80 - 20, 40, 70, 90, 100 = 90
: 10, 30, 50, 60, 90 - 20, 40, 70, 80, 100 = 70
: 10, 30, 50, 60, 100 - 20, 40, 70, 80, 90 = 50
: 10, 30, 50, 70, 80 - 20, 40, 60, 90, 100 = 70
: 10, 30, 50, 70, 90 - 20, 40, 60, 80, 100 = 50
: 10, 30, 50, 70, 100 - 20, 40, 60, 80, 90 = 30
: 10, 30, 50, 80, 90 - 20, 40, 60, 70, 100 = 30
: 10, 30, 50, 80, 100 - 20, 40, 60, 70, 90 = 10
: 10, 30, 50, 90, 100 - 20, 40, 60, 70, 80 = 10
: 10, 30, 60, 70, 80 - 20, 40, 50, 90, 100 = 50
: 10, 30, 60, 70, 90 - 20, 40, 50, 80, 100 = 30
: 10, 30, 60, 70, 100 - 20, 40, 50, 80, 90 = 10
: 10, 30, 60, 80, 90 - 20, 40, 50, 70, 100 = 10
: 10, 30, 60, 80, 100 - 20, 40, 50, 70, 90 = 10
: 10, 30, 60, 90, 100 - 20, 40, 50, 70, 80 = 30
: 10, 30, 70, 80, 90 - 20, 40, 50, 60, 100 = 10
: 10, 30, 70, 80, 100 - 20, 40, 50, 60, 90 = 30
: 10, 30, 70, 90, 100 - 20, 40, 50, 60, 80 = 50
: 10, 30, 80, 90, 100 - 20, 40, 50, 60, 70 = 70
: 10, 40, 50, 60, 70 - 20, 30, 80, 90, 100 = 90
: 10, 40, 50, 60, 80 - 20, 30, 70, 90, 100 = 70
: 10, 40, 50, 60, 90 - 20, 30, 70, 80, 100 = 50
: 10, 40, 50, 60, 100 - 20, 30, 70, 80, 90 = 30
: 10, 40, 50, 70, 80 - 20, 30, 60, 90, 100 = 50
: 10, 40, 50, 70, 90 - 20, 30, 60, 80, 100 = 30
: 10, 40, 50, 70, 100 - 20, 30, 60, 80, 90 = 10
: 10, 40, 50, 80, 90 - 20, 30, 60, 70, 100 = 10
: 10, 40, 50, 80, 100 - 20, 30, 60, 70, 90 = 10
: 10, 40, 50, 90, 100 - 20, 30, 60, 70, 80 = 30
: 10, 40, 60, 70, 80 - 20, 30, 50, 90, 100 = 30
: 10, 40, 60, 70, 90 - 20, 30, 50, 80, 100 = 10
: 10, 40, 60, 70, 100 - 20, 30, 50, 80, 90 = 10
: 10, 40, 60, 80, 90 - 20, 30, 50, 70, 100 = 10
: 10, 40, 60, 80, 100 - 20, 30, 50, 70, 90 = 30
: 10, 40, 60, 90, 100 - 20, 30, 50, 70, 80 = 50
: 10, 40, 70, 80, 90 - 20, 30, 50, 60, 100 = 30
: 10, 40, 70, 80, 100 - 20, 30, 50, 60, 90 = 50
: 10, 40, 70, 90, 100 - 20, 30, 50, 60, 80 = 70
: 10, 40, 80, 90, 100 - 20, 30, 50, 60, 70 = 90
: 10, 50, 60, 70, 80 - 20, 30, 40, 90, 100 = 10
: 10, 50, 60, 70, 90 - 20, 30, 40, 80, 100 = 10
: 10, 50, 60, 70, 100 - 20, 30, 40, 80, 90 = 30
: 10, 50, 60, 80, 90 - 20, 30, 40, 70, 100 = 30
: 10, 50, 60, 80, 100 - 20, 30, 40, 70, 90 = 50
: 10, 50, 60, 90, 100 - 20, 30, 40, 70, 80 = 70
: 10, 50, 70, 80, 90 - 20, 30, 40, 60, 100 = 50
: 10, 50, 70, 80, 100 - 20, 30, 40, 60, 90 = 70
: 10, 50, 70, 90, 100 - 20, 30, 40, 60, 80 = 90
: 10, 50, 80, 90, 100 - 20, 30, 40, 60, 70 = 110
: 10, 60, 70, 80, 90 - 20, 30, 40, 50, 100 = 70
: 10, 60, 70, 80, 100 - 20, 30, 40, 50, 90 = 90
: 10, 60, 70, 90, 100 - 20, 30, 40, 50, 80 = 110
: 10, 60, 80, 90, 100 - 20, 30, 40, 50, 70 = 130
: 10, 70, 80, 90, 100 - 20, 30, 40, 50, 60 = 150
: 20, 30, 40, 50, 60 - 10, 70, 80, 90, 100 = 150
: 20, 30, 40, 50, 70 - 10, 60, 80, 90, 100 = 130
: 20, 30, 40, 50, 80 - 10, 60, 70, 90, 100 = 110
: 20, 30, 40, 50, 90 - 10, 60, 70, 80, 100 = 90
: 20, 30, 40, 50, 100 - 10, 60, 70, 80, 90 = 70
: 20, 30, 40, 60, 70 - 10, 50, 80, 90, 100 = 110
: 20, 30, 40, 60, 80 - 10, 50, 70, 90, 100 = 90
: 20, 30, 40, 60, 90 - 10, 50, 70, 80, 100 = 70
: 20, 30, 40, 60, 100 - 10, 50, 70, 80, 90 = 50
: 20, 30, 40, 70, 80 - 10, 50, 60, 90, 100 = 70
: 20, 30, 40, 70, 90 - 10, 50, 60, 80, 100 = 50
: 20, 30, 40, 70, 100 - 10, 50, 60, 80, 90 = 30
: 20, 30, 40, 80, 90 - 10, 50, 60, 70, 100 = 30
: 20, 30, 40, 80, 100 - 10, 50, 60, 70, 90 = 10
: 20, 30, 40, 90, 100 - 10, 50, 60, 70, 80 = 10
: 20, 30, 50, 60, 70 - 10, 40, 80, 90, 100 = 90
: 20, 30, 50, 60, 80 - 10, 40, 70, 90, 100 = 70
: 20, 30, 50, 60, 90 - 10, 40, 70, 80, 100 = 50
: 20, 30, 50, 60, 100 - 10, 40, 70, 80, 90 = 30
: 20, 30, 50, 70, 80 - 10, 40, 60, 90, 100 = 50
: 20, 30, 50, 70, 90 - 10, 40, 60, 80, 100 = 30
: 20, 30, 50, 70, 100 - 10, 40, 60, 80, 90 = 10
: 20, 30, 50, 80, 90 - 10, 40, 60, 70, 100 = 10
: 20, 30, 50, 80, 100 - 10, 40, 60, 70, 90 = 10
: 20, 30, 50, 90, 100 - 10, 40, 60, 70, 80 = 30
: 20, 30, 60, 70, 80 - 10, 40, 50, 90, 100 = 30
: 20, 30, 60, 70, 90 - 10, 40, 50, 80, 100 = 10
: 20, 30, 60, 70, 100 - 10, 40, 50, 80, 90 = 10
: 20, 30, 60, 80, 90 - 10, 40, 50, 70, 100 = 10
: 20, 30, 60, 80, 100 - 10, 40, 50, 70, 90 = 30
: 20, 30, 60, 90, 100 - 10, 40, 50, 70, 80 = 50
: 20, 30, 70, 80, 90 - 10, 40, 50, 60, 100 = 30
: 20, 30, 70, 80, 100 - 10, 40, 50, 60, 90 = 50
: 20, 30, 70, 90, 100 - 10, 40, 50, 60, 80 = 70
: 20, 30, 80, 90, 100 - 10, 40, 50, 60, 70 = 90
: 20, 40, 50, 60, 70 - 10, 30, 80, 90, 100 = 70
: 20, 40, 50, 60, 80 - 10, 30, 70, 90, 100 = 50
: 20, 40, 50, 60, 90 - 10, 30, 70, 80, 100 = 30
: 20, 40, 50, 60, 100 - 10, 30, 70, 80, 90 = 10
: 20, 40, 50, 70, 80 - 10, 30, 60, 90, 100 = 30
: 20, 40, 50, 70, 90 - 10, 30, 60, 80, 100 = 10
: 20, 40, 50, 70, 100 - 10, 30, 60, 80, 90 = 10
: 20, 40, 50, 80, 90 - 10, 30, 60, 70, 100 = 10
: 20, 40, 50, 80, 100 - 10, 30, 60, 70, 90 = 30
: 20, 40, 50, 90, 100 - 10, 30, 60, 70, 80 = 50
: 20, 40, 60, 70, 80 - 10, 30, 50, 90, 100 = 10
: 20, 40, 60, 70, 90 - 10, 30, 50, 80, 100 = 10
: 20, 40, 60, 70, 100 - 10, 30, 50, 80, 90 = 30
: 20, 40, 60, 80, 90 - 10, 30, 50, 70, 100 = 30
: 20, 40, 60, 80, 100 - 10, 30, 50, 70, 90 = 50
: 20, 40, 60, 90, 100 - 10, 30, 50, 70, 80 = 70
: 20, 40, 70, 80, 90 - 10, 30, 50, 60, 100 = 50
: 20, 40, 70, 80, 100 - 10, 30, 50, 60, 90 = 70
: 20, 40, 70, 90, 100 - 10, 30, 50, 60, 80 = 90
: 20, 40, 80, 90, 100 - 10, 30, 50, 60, 70 = 110
: 20, 50, 60, 70, 80 - 10, 30, 40, 90, 100 = 10
: 20, 50, 60, 70, 90 - 10, 30, 40, 80, 100 = 30
: 20, 50, 60, 70, 100 - 10, 30, 40, 80, 90 = 50
: 20, 50, 60, 80, 90 - 10, 30, 40, 70, 100 = 50
: 20, 50, 60, 80, 100 - 10, 30, 40, 70, 90 = 70
: 20, 50, 60, 90, 100 - 10, 30, 40, 70, 80 = 90
: 20, 50, 70, 80, 90 - 10, 30, 40, 60, 100 = 70
: 20, 50, 70, 80, 100 - 10, 30, 40, 60, 90 = 90
: 20, 50, 70, 90, 100 - 10, 30, 40, 60, 80 = 110
: 20, 50, 80, 90, 100 - 10, 30, 40, 60, 70 = 130
: 20, 60, 70, 80, 90 - 10, 30, 40, 50, 100 = 90
: 20, 60, 70, 80, 100 - 10, 30, 40, 50, 90 = 110
: 20, 60, 70, 90, 100 - 10, 30, 40, 50, 80 = 130
: 20, 60, 80, 90, 100 - 10, 30, 40, 50, 70 = 150
: 20, 70, 80, 90, 100 - 10, 30, 40, 50, 60 = 170
: 30, 40, 50, 60, 70 - 10, 20, 80, 90, 100 = 50
: 30, 40, 50, 60, 80 - 10, 20, 70, 90, 100 = 30
: 30, 40, 50, 60, 90 - 10, 20, 70, 80, 100 = 10
: 30, 40, 50, 60, 100 - 10, 20, 70, 80, 90 = 10
: 30, 40, 50, 70, 80 - 10, 20, 60, 90, 100 = 10
: 30, 40, 50, 70, 90 - 10, 20, 60, 80, 100 = 10
: 30, 40, 50, 70, 100 - 10, 20, 60, 80, 90 = 30
: 30, 40, 50, 80, 90 - 10, 20, 60, 70, 100 = 30
: 30, 40, 50, 80, 100 - 10, 20, 60, 70, 90 = 50
: 30, 40, 50, 90, 100 - 10, 20, 60, 70, 80 = 70
: 30, 40, 60, 70, 80 - 10, 20, 50, 90, 100 = 10
: 30, 40, 60, 70, 90 - 10, 20, 50, 80, 100 = 30
: 30, 40, 60, 70, 100 - 10, 20, 50, 80, 90 = 50
: 30, 40, 60, 80, 90 - 10, 20, 50, 70, 100 = 50
: 30, 40, 60, 80, 100 - 10, 20, 50, 70, 90 = 70
: 30, 40, 60, 90, 100 - 10, 20, 50, 70, 80 = 90
: 30, 40, 70, 80, 90 - 10, 20, 50, 60, 100 = 70
: 30, 40, 70, 80, 100 - 10, 20, 50, 60, 90 = 90
: 30, 40, 70, 90, 100 - 10, 20, 50, 60, 80 = 110
: 30, 40, 80, 90, 100 - 10, 20, 50, 60, 70 = 130
: 30, 50, 60, 70, 80 - 10, 20, 40, 90, 100 = 30
: 30, 50, 60, 70, 90 - 10, 20, 40, 80, 100 = 50
: 30, 50, 60, 70, 100 - 10, 20, 40, 80, 90 = 70
: 30, 50, 60, 80, 90 - 10, 20, 40, 70, 100 = 70
: 30, 50, 60, 80, 100 - 10, 20, 40, 70, 90 = 90
: 30, 50, 60, 90, 100 - 10, 20, 40, 70, 80 = 110
: 30, 50, 70, 80, 90 - 10, 20, 40, 60, 100 = 90
: 30, 50, 70, 80, 100 - 10, 20, 40, 60, 90 = 110
: 30, 50, 70, 90, 100 - 10, 20, 40, 60, 80 = 130
: 30, 50, 80, 90, 100 - 10, 20, 40, 60, 70 = 150
: 30, 60, 70, 80, 90 - 10, 20, 40, 50, 100 = 110
: 30, 60, 70, 80, 100 - 10, 20, 40, 50, 90 = 130
: 30, 60, 70, 90, 100 - 10, 20, 40, 50, 80 = 150
: 30, 60, 80, 90, 100 - 10, 20, 40, 50, 70 = 170
: 30, 70, 80, 90, 100 - 10, 20, 40, 50, 60 = 190
: 40, 50, 60, 70, 80 - 10, 20, 30, 90, 100 = 50
: 40, 50, 60, 70, 90 - 10, 20, 30, 80, 100 = 70
: 40, 50, 60, 70, 100 - 10, 20, 30, 80, 90 = 90
: 40, 50, 60, 80, 90 - 10, 20, 30, 70, 100 = 90
: 40, 50, 60, 80, 100 - 10, 20, 30, 70, 90 = 110
: 40, 50, 60, 90, 100 - 10, 20, 30, 70, 80 = 130
: 40, 50, 70, 80, 90 - 10, 20, 30, 60, 100 = 110
: 40, 50, 70, 80, 100 - 10, 20, 30, 60, 90 = 130
: 40, 50, 70, 90, 100 - 10, 20, 30, 60, 80 = 150
: 40, 50, 80, 90, 100 - 10, 20, 30, 60, 70 = 170
: 40, 60, 70, 80, 90 - 10, 20, 30, 50, 100 = 130
: 40, 60, 70, 80, 100 - 10, 20, 30, 50, 90 = 150
: 40, 60, 70, 90, 100 - 10, 20, 30, 50, 80 = 170
: 40, 60, 80, 90, 100 - 10, 20, 30, 50, 70 = 190
: 40, 70, 80, 90, 100 - 10, 20, 30, 50, 60 = 210
: 50, 60, 70, 80, 90 - 10, 20, 30, 40, 100 = 150
: 50, 60, 70, 80, 100 - 10, 20, 30, 40, 90 = 170
: 50, 60, 70, 90, 100 - 10, 20, 30, 40, 80 = 190
: 50, 60, 80, 90, 100 - 10, 20, 30, 40, 70 = 210
: 50, 70, 80, 90, 100 - 10, 20, 30, 40, 60 = 230
: 60, 70, 80, 90, 100 - 10, 20, 30, 40, 50 = 250
Subset 1 = (10, 20, 50, 90, 100)
Subset 2 = (30, 40, 60, 70, 80)
: Difference: 10
The difference is 10, and the program had to run through all the combinations to be sure that a lower value isn't achievable).
The second example:
$ ./tug-of-war 10 -15 20 30 -25 0 5 40 -5
Subset 1 = (10, -15, 30, 5)
Subset 2 = (-25, -5, 0, 20, 40)
$ ./tug-of-war -v 10 -15 20 30 -25 0 5 40 -5
: 10, -15, 20, 30 - -25, -5, 0, 5, 40 = 30 [BEST]
: 10, -15, 20, -25 - -5, 0, 5, 30, 40 = 80
: 10, -15, 20, 0 - -25, -5, 5, 30, 40 = 30
: 10, -15, 20, 5 - -25, -5, 0, 30, 40 = 20 [BEST]
: 10, -15, 20, 40 - -25, -5, 0, 5, 30 = 50
: 10, -15, 20, -5 - -25, 0, 5, 30, 40 = 40
: 10, -15, 30, -25 - -5, 0, 5, 20, 40 = 60
: 10, -15, 30, 0 - -25, -5, 5, 20, 40 = 10 [BEST]
: 10, -15, 30, 5 - -25, -5, 0, 20, 40 = 0 [BEST]
Subset 1 = (10, -15, 30, 5)
Subset 2 = (-25, -5, 0, 20, 40)
: Difference: 0
We got the subsets in the wrong order, again.
The program stopped at the first zero, as it should. Use the «-a» command line option to get all the combinations. The result (the two subsets) is the same, though.
$ ./tug-of-war -v -a 10 -15 20 30 -25 0 5 40 -5
: 10, -15, 20, 30 - -25, -5, 0, 5, 40 = 30 [BEST]
: 10, -15, 20, -25 - -5, 0, 5, 30, 40 = 80
: 10, -15, 20, 0 - -25, -5, 5, 30, 40 = 30
: 10, -15, 20, 5 - -25, -5, 0, 30, 40 = 20 [BEST]
: 10, -15, 20, 40 - -25, -5, 0, 5, 30 = 50
: 10, -15, 20, -5 - -25, 0, 5, 30, 40 = 40
: 10, -15, 30, -25 - -5, 0, 5, 20, 40 = 60
: 10, -15, 30, 0 - -25, -5, 5, 20, 40 = 10 [BEST]
: 10, -15, 30, 5 - -25, -5, 0, 20, 40 = 0 [BEST]
: 10, -15, 30, 40 - -25, -5, 0, 5, 20 = 70
: 10, -15, 30, -5 - -25, 0, 5, 20, 40 = 20
: 10, -15, -25, 0 - -5, 5, 20, 30, 40 = 120
: 10, -15, -25, 5 - -5, 0, 20, 30, 40 = 110
: 10, -15, -25, 40 - -5, 0, 5, 20, 30 = 40
: 10, -15, -25, -5 - 0, 5, 20, 30, 40 = 130
: 10, -15, 0, 5 - -25, -5, 20, 30, 40 = 60
: 10, -15, 0, 40 - -25, -5, 5, 20, 30 = 10
: 10, -15, 0, -5 - -25, 5, 20, 30, 40 = 80
: 10, -15, 5, 40 - -25, -5, 0, 20, 30 = 20
: 10, -15, 5, -5 - -25, 0, 20, 30, 40 = 70
: 10, -15, 40, -5 - -25, 0, 5, 20, 30 = 0
: 10, 20, 30, -25 - -15, -5, 0, 5, 40 = 10
: 10, 20, 30, 0 - -25, -15, -5, 5, 40 = 60
: 10, 20, 30, 5 - -25, -15, -5, 0, 40 = 70
: 10, 20, 30, 40 - -25, -15, -5, 0, 5 = 140
: 10, 20, 30, -5 - -25, -15, 0, 5, 40 = 50
: 10, 20, -25, 0 - -15, -5, 5, 30, 40 = 50
: 10, 20, -25, 5 - -15, -5, 0, 30, 40 = 40
: 10, 20, -25, 40 - -15, -5, 0, 5, 30 = 30
: 10, 20, -25, -5 - -15, 0, 5, 30, 40 = 60
: 10, 20, 0, 5 - -25, -15, -5, 30, 40 = 10
: 10, 20, 0, 40 - -25, -15, -5, 5, 30 = 80
: 10, 20, 0, -5 - -25, -15, 5, 30, 40 = 10
: 10, 20, 5, 40 - -25, -15, -5, 0, 30 = 90
: 10, 20, 5, -5 - -25, -15, 0, 30, 40 = 0
: 10, 20, 40, -5 - -25, -15, 0, 5, 30 = 70
: 10, 30, -25, 0 - -15, -5, 5, 20, 40 = 30
: 10, 30, -25, 5 - -15, -5, 0, 20, 40 = 20
: 10, 30, -25, 40 - -15, -5, 0, 5, 20 = 50
: 10, 30, -25, -5 - -15, 0, 5, 20, 40 = 40
: 10, 30, 0, 5 - -25, -15, -5, 20, 40 = 30
: 10, 30, 0, 40 - -25, -15, -5, 5, 20 = 100
: 10, 30, 0, -5 - -25, -15, 5, 20, 40 = 10
: 10, 30, 5, 40 - -25, -15, -5, 0, 20 = 110
: 10, 30, 5, -5 - -25, -15, 0, 20, 40 = 20
: 10, 30, 40, -5 - -25, -15, 0, 5, 20 = 90
: 10, -25, 0, 5 - -15, -5, 20, 30, 40 = 80
: 10, -25, 0, 40 - -15, -5, 5, 20, 30 = 10
: 10, -25, 0, -5 - -15, 5, 20, 30, 40 = 100
: 10, -25, 5, 40 - -15, -5, 0, 20, 30 = 0
: 10, -25, 5, -5 - -15, 0, 20, 30, 40 = 90
: 10, -25, 40, -5 - -15, 0, 5, 20, 30 = 20
: 10, 0, 5, 40 - -25, -15, -5, 20, 30 = 50
: 10, 0, 5, -5 - -25, -15, 20, 30, 40 = 40
: 10, 0, 40, -5 - -25, -15, 5, 20, 30 = 30
: 10, 5, 40, -5 - -25, -15, 0, 20, 30 = 40
: -15, 20, 30, -25 - -5, 0, 5, 10, 40 = 40
: -15, 20, 30, 0 - -25, -5, 5, 10, 40 = 10
: -15, 20, 30, 5 - -25, -5, 0, 10, 40 = 20
: -15, 20, 30, 40 - -25, -5, 0, 5, 10 = 90
: -15, 20, 30, -5 - -25, 0, 5, 10, 40 = 0
: -15, 20, -25, 0 - -5, 5, 10, 30, 40 = 100
: -15, 20, -25, 5 - -5, 0, 10, 30, 40 = 90
: -15, 20, -25, 40 - -5, 0, 5, 10, 30 = 20
: -15, 20, -25, -5 - 0, 5, 10, 30, 40 = 110
: -15, 20, 0, 5 - -25, -5, 10, 30, 40 = 40
: -15, 20, 0, 40 - -25, -5, 5, 10, 30 = 30
: -15, 20, 0, -5 - -25, 5, 10, 30, 40 = 60
: -15, 20, 5, 40 - -25, -5, 0, 10, 30 = 40
: -15, 20, 5, -5 - -25, 0, 10, 30, 40 = 50
: -15, 20, 40, -5 - -25, 0, 5, 10, 30 = 20
: -15, 30, -25, 0 - -5, 5, 10, 20, 40 = 80
: -15, 30, -25, 5 - -5, 0, 10, 20, 40 = 70
: -15, 30, -25, 40 - -5, 0, 5, 10, 20 = 0
: -15, 30, -25, -5 - 0, 5, 10, 20, 40 = 90
: -15, 30, 0, 5 - -25, -5, 10, 20, 40 = 20
: -15, 30, 0, 40 - -25, -5, 5, 10, 20 = 50
: -15, 30, 0, -5 - -25, 5, 10, 20, 40 = 40
: -15, 30, 5, 40 - -25, -5, 0, 10, 20 = 60
: -15, 30, 5, -5 - -25, 0, 10, 20, 40 = 30
: -15, 30, 40, -5 - -25, 0, 5, 10, 20 = 40
: -15, -25, 0, 5 - -5, 10, 20, 30, 40 = 130
: -15, -25, 0, 40 - -5, 5, 10, 20, 30 = 60
: -15, -25, 0, -5 - 5, 10, 20, 30, 40 = 150
: -15, -25, 5, 40 - -5, 0, 10, 20, 30 = 50
: -15, -25, 5, -5 - 0, 10, 20, 30, 40 = 140
: -15, -25, 40, -5 - 0, 5, 10, 20, 30 = 70
: -15, 0, 5, 40 - -25, -5, 10, 20, 30 = 0
: -15, 0, 5, -5 - -25, 10, 20, 30, 40 = 90
: -15, 0, 40, -5 - -25, 5, 10, 20, 30 = 20
: -15, 5, 40, -5 - -25, 0, 10, 20, 30 = 10
: 20, 30, -25, 0 - -15, -5, 5, 10, 40 = 10
: 20, 30, -25, 5 - -15, -5, 0, 10, 40 = 0
: 20, 30, -25, 40 - -15, -5, 0, 5, 10 = 70
: 20, 30, -25, -5 - -15, 0, 5, 10, 40 = 20
: 20, 30, 0, 5 - -25, -15, -5, 10, 40 = 50
: 20, 30, 0, 40 - -25, -15, -5, 5, 10 = 120
: 20, 30, 0, -5 - -25, -15, 5, 10, 40 = 30
: 20, 30, 5, 40 - -25, -15, -5, 0, 10 = 130
: 20, 30, 5, -5 - -25, -15, 0, 10, 40 = 40
: 20, 30, 40, -5 - -25, -15, 0, 5, 10 = 110
: 20, -25, 0, 5 - -15, -5, 10, 30, 40 = 60
: 20, -25, 0, 40 - -15, -5, 5, 10, 30 = 10
: 20, -25, 0, -5 - -15, 5, 10, 30, 40 = 80
: 20, -25, 5, 40 - -15, -5, 0, 10, 30 = 20
: 20, -25, 5, -5 - -15, 0, 10, 30, 40 = 70
: 20, -25, 40, -5 - -15, 0, 5, 10, 30 = 0
: 20, 0, 5, 40 - -25, -15, -5, 10, 30 = 70
: 20, 0, 5, -5 - -25, -15, 10, 30, 40 = 20
: 20, 0, 40, -5 - -25, -15, 5, 10, 30 = 50
: 20, 5, 40, -5 - -25, -15, 0, 10, 30 = 60
: 30, -25, 0, 5 - -15, -5, 10, 20, 40 = 40
: 30, -25, 0, 40 - -15, -5, 5, 10, 20 = 30
: 30, -25, 0, -5 - -15, 5, 10, 20, 40 = 60
: 30, -25, 5, 40 - -15, -5, 0, 10, 20 = 40
: 30, -25, 5, -5 - -15, 0, 10, 20, 40 = 50
: 30, -25, 40, -5 - -15, 0, 5, 10, 20 = 20
: 30, 0, 5, 40 - -25, -15, -5, 10, 20 = 90
: 30, 0, 5, -5 - -25, -15, 10, 20, 40 = 0
: 30, 0, 40, -5 - -25, -15, 5, 10, 20 = 70
: 30, 5, 40, -5 - -25, -15, 0, 10, 20 = 80
: -25, 0, 5, 40 - -15, -5, 10, 20, 30 = 20
: -25, 0, 5, -5 - -15, 10, 20, 30, 40 = 110
: -25, 0, 40, -5 - -15, 5, 10, 20, 30 = 40
: -25, 5, 40, -5 - -15, 0, 10, 20, 30 = 30
: 0, 5, 40, -5 - -25, -15, 10, 20, 30 = 20
Subset 1 = (10, -15, 30, 5)
Subset 2 = (-25, -5, 0, 20, 40)
: Difference: 0
Note that we computed the second subset each time (in the loop), just to get the sum (and the verbose output, granted). We can do it much smarter, by computing the total sum up front, and subtract the sum of the first subset. That gives the sum of the second subset.
File: tug-of-war-sum
#! /usr/bin/env raku
unit sub MAIN (*@n where @n.elems > 0 &&
all(@n) ~~ Int &&
@n.elems == @n.unique.elems,
:v(:$verbose),
:a(:$all));
my $best = Inf;
my @subset1;
my $sum = @n.sum; # [1]
for @n.combinations(@n.elems / 2) -> @first
{
my @second = (@n (-) @first).keys.sort;
my $difference = ($sum - @first.sum).abs; # [1a]
if $difference < $best
{
say ": { @first.join(", ") } - { (@n (-) @first).keys.sort.join(", ") } \
= $difference [BEST]" if $verbose; # [3]
$best = $difference;
@subset1 = @first;
last if $best == 0 && !$all;
}
else
{
say ": { @first.join(", ") } - { (@n (-) @first).keys.sort.join(", ") } \
= $difference" if $verbose; # [3]
}
}
say "Subset 1 = ({ @subset1.join(", ") })";
say "Subset 2 = ({ (@n (-) @subset1).keys.sort.join(", ") })"; # [2]
say ": Difference: $best" if $verbose;
[1] Compute the sum of the whole set, and use that to ge the sum of the second subset - without computing the subset itself [1a].
[2] We can then get away with computing the second subset just once; when we print the result.
[3] … excpet if we use verbose mode. Then we have to compute the second subset each time.
Running this version of the program gives the same result.
Here is a shorter version, with the verbose output removed:
File: tug-of-war-sum-plain
#! /usr/bin/env raku
unit sub MAIN (*@n where @n.elems > 0 &&
all(@n) ~~ Int &&
@n.elems == @n.unique.elems);
my $best = Inf;
my @subset1;
my $sum = @n.sum;
for @n.combinations(@n.elems / 2) -> @first
{
my @second = (@n (-) @first).keys.sort;
my $difference = ($sum - @first.sum).abs;
if $difference < $best
{
$best = $difference;
@subset1 = @first;
last if $best == 0;
}
}
say "Subset 1 = ({ @subset1.join(", ") })";
say "Subset 2 = ({ (@n (-) @subset1).keys.sort.join(", ") })";
Set Bonus
We have treated a Set as a mathematical Set (using the Raku typeSet),
where each value is distinct.
But what if Set is just meant as a bunch? I.e. not distinct. I did not enforce distinct values in «tow-dispatcher», as it did not compute Sets. We can fix (or maule) the «tug-of-war» program:
File: tug-of-war-bag
#! /usr/bin/env raku
unit sub MAIN (*@n where @n.elems > 0 && all(@n) ~~ Int, # [1]
:v(:$verbose),
:a(:$all));
my $best = Inf;
my @subset1;
my @subset2;
for @n.combinations(@n.elems / 2) -> @first
{
my @second = (@n (-) @first.Bag).kxxv.sort; # [2]
my $difference = (@first.sum - @second.sum).abs;
if $difference < $best
{
say ": { @first.join(", ") } - { @second.join(", ") } = $difference \
[BEST]" if $verbose;
$best = $difference;
@subset1 = @first;
@subset2 = @second;
last if $best == 0 && !$all;
}
else
{
say ": { @first.join(", ") } - { @second.join(", ") } = $difference"
if $verbose;
}
}
say "Subset 1 = ({ @subset1.join(", ") })";
say "Subset 2 = ({ @subset2.join(", ") })";
say ": Difference: $best" if $verbose;
[1] The unique part has gone.
[2]
We coerce @first to a Bag (a Set like type,
where the values have weight; i.e. duplicates). This ensures that the result of the set
difference operator is also a Bag, and that duplicates are retained. Then we use
kxxv instead of keys to get the values in the Bag, as a list
with duplicates.
See
docs.raku.org/type/Bag
for more information about the Bag type.
See
docs.raku.org/routine/kxxv
for more information about kxxv.
Running it:
$ ./tug-of-war-bag 1 2 2 3
Subset 1 = (1, 3)
Subset 2 = (2, 2)
$ ./tug-of-war-bag -v 1 2 2 3
: 1, 2 - 2, 3 = 2 [BEST]
: 1, 2 - 2, 3 = 2
: 1, 3 - 2, 2 = 0 [BEST]
Subset 1 = (1, 3)
Subset 2 = (2, 2)
: Difference: 0
$ ./tug-of-war-bag -v 1 2 2 3 5
: 1, 2 - 2, 3, 5 = 7 [BEST]
: 1, 2 - 2, 3, 5 = 7
: 1, 3 - 2, 2, 5 = 5 [BEST]
: 1, 5 - 2, 2, 3 = 1 [BEST]
: 2, 2 - 1, 3, 5 = 5
: 2, 3 - 1, 2, 5 = 3
: 2, 5 - 1, 2, 3 = 1
: 2, 3 - 1, 2, 5 = 3
: 2, 5 - 1, 2, 3 = 1
: 3, 5 - 1, 2, 2 = 3
Subset 1 = (1, 5)
Subset 2 = (2, 2, 3)
: Difference: 1
$ ./tug-of-war-bag -v 1 2 2 3 6
: 1, 2 - 2, 3, 6 = 8 [BEST]
: 1, 2 - 2, 3, 6 = 8
: 1, 3 - 2, 2, 6 = 6 [BEST]
: 1, 6 - 2, 2, 3 = 0 [BEST]
Subset 1 = (1, 6)
Subset 2 = (2, 2, 3)
: Difference: 0
$ ./tug-of-war-bag -v -a 1 2 2 3 6
: 1, 2 - 2, 3, 6 = 8 [BEST]
: 1, 2 - 2, 3, 6 = 8
: 1, 3 - 2, 2, 6 = 6 [BEST]
: 1, 6 - 2, 2, 3 = 0 [BEST]
: 2, 2 - 1, 3, 6 = 6
: 2, 3 - 1, 2, 6 = 4
: 2, 6 - 1, 2, 3 = 2
: 2, 3 - 1, 2, 6 = 4
: 2, 6 - 1, 2, 3 = 2
: 3, 6 - 1, 2, 2 = 4
Subset 1 = (1, 6)
Subset 2 = (2, 2, 3)
: Difference: 0
Equality Bonus
It is much easier to check if we can partition the set into to subsets (of the sameish size) with the same sums - i.e. that the difference is zero.
The program prints 1 if it finds two subsets with the same sum,
and 0 otherwise.
#! /usr/bin/env raku
unit sub MAIN (*@n where @n.elems > 0 &&
all(@n) ~~ Int, # && # [1]
# @n.elems == @n.unique.elems, # [1]
:v(:$verbose));
my $half-sum = @n.sum / 2;
if $verbose
{
say ": Half sum: $half-sum";
say ": Combinations: ", @n.combinations(@n.elems / 2);
say ": Sums: ", @n.combinations(@n.elems / 2).map({ @$_.sum});
}
# (say "0"; exit ) unless $half-sum == $half-sum.Int; # [2]
say + so @n.combinations(@n.elems / 2).map({ @$_.sum}).any == $half-sum; # [3]
# F E D # A ######################### # B ########### # C ############
[1] Add the commented out code if you want a true Set, i.e. no duplicates.
[2] This line checks that the sum is even. If it isn't, then we cannot get two sums with the same value. It is disabled, as it next line takes care of this situation - albeit slower.
[3] Get all the combinations [A], convert them (with map) to the
sum [B], apply an any junction (to the list of sums) to see if any
of them are equal to the half sum [C]. The result of that operation is a Junction,
which we collapse to a Boolean value with so [D]. We coerce that
Boolean value to an integer (True -> 1, False -> 0) with the prefix +
operator [E], and finally we print the value [G].
Running it:
$ ./tug-of-war-zero -v 1 2 3 4 5
: Half sum: 7.5
: Combinations: ((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))
: Sums: (3 4 5 6 5 6 7 7 8 9)
0
$ ./tug-of-war-zero -v 1 2 3 4 6
: Half sum: 8
: Combinations: ((1 2) (1 3) (1 4) (1 6) (2 3) (2 4) (2 6) (3 4) (3 6) (4 6))
: Sums: (3 4 5 7 5 6 8 7 9 10)
1
And that's it.