##
**TASK #2 › Flip Array**

##
**While Testing Race**

I wrote a Raku code to solve the task #2. My first goal is that get faster result by using more resource of my laptop by using .race. So I came up with

```
... snip
@n.combinations( 1..^ @n ).
race( :8degree:500batch ). 👈
map(
-> \n {
with $s - 2 * n.sum { # same as ( $s- n.sum ) - n.sum
next if $_ < 0;
$_ => n.elems
}
} ).
race( :8degree:500batch ). 👈
min.
value.
say
}
```

A couple of race() are added because I found the two throttles, the result was satisfying. It wasn't dramatically faster but about twice faster. You can find more details Here

When we compare the speed of between making permutations by using *[X]* and *combinations*, permutations is always faster than combinations.

##
**Permutations vs Combinations [Speed]**

i.e.

```
> ([X] (^20).map({ $_, -$_ })).elems # ^20 eqv. 0..19
1048576
```

is faster than,

```
> (^20).combinations.elems
1048576
```

When you run it in Raku you will feel that permutaions is definitely faster.

One question came across my head. *"What if I could reduce the length of the combinations?"*.

In this case, we can reduce the combinations because we only need the summation of two groups.

*for example...*

```
(12) <=> (7, 4)
```

So If we know summation of one group(12) then we can calculate another(7,4). because we know total sum as well (12+7+4)

i.e.

```
sum(7,4) == sum(12,7,4) - sum(12)
```

If the length of the list are the same(len 4 + len 4 = len 8). I can even check half side of the list but... I just skipped that part. I doesn't look helpful here (or maybe it does.. IDK...)

##
*Returning to* **Perl**

As a result, I wrote a Perl code like below.

```
... snip ...
my $totalSum = sum @N;
my $halfLen = int( .5 * @N ); # reduce the combinations in half
# initial values ...
my $minElems = +@N;
my $minSum = $totalSum;
for my $combi ( combinations( +@N, 1, $halfLen ) ) {
my $aSum = sum @N[ @$combi ];
my $bSum = $totalSum - $aSum;
my $curr =
( # $aSum == $bSum
[ 0, ( scalar @$combi < $halfLen
? scalar @$combi : scalar( @N - @$combi) ) ],
# $aSum > $bSum
[ $aSum - $bSum, scalar ( @N - @$combi) ],
# $aSum < $bSum
[ $bSum - $aSum, scalar @$combi ] )[ $aSum <=> $bSum ];
print "[sum: $$curr[0], elems: $$curr[1]] with @N[@$combi] ... " if $d;
if ( $$curr[0] > $minSum ) { # minimum sum not changed
next;
}
elsif ( $$curr[0] < $minSum ) { # minimum sum cahnged
# so does minimum elements
( $minSum, $minElems ) = @$curr;
}
elsif ( $$curr[1] < $minElems ) { # minimum sum is same
# but no. elements is less
$minElems = $$curr[1];
}
else {
say "" if $d;
}
}
... snip
```

I tested with a bit long list which is

```
12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
```

And the result is reasonably fast.

##
**Not So Precise Benchmarks**

###
Perl *With* Combinatorics Module

```
shell> time perl ch-2.using-algorithm-combinatorics.pl 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6
________________________________________________________
Executed in 2.41 secs fish external
...
```

###
**With** **My own combinations module**

```
shell> time perl ch-2.pl 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6
________________________________________________________
Executed in 1.86 secs fish external
...
```

But those are still *slower* than any compiled my version of Go and Haskell

(I'll update the full source link after pull request finished)

###
**Go** version

*Note: that ch-2.go use full length of combinations*, I just start to learn golang and wrote the code before thinking shirinking the combinations. nevertheless result was so quite satisfying.

```
shell> go run ch-2.go 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8 # not compiled
6
________________________________________________________
Executed in 443.40 millis fish external
...
```

```
shell> go build ch-2.go # go has already optimise the code
shell> time ./ch-2 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6
________________________________________________________
Executed in 238.32 millis fish external
...
```

###
**Haskell** Version

Here we go, Haskell version. I made my own version of combinations again. you can find it HERE because -- In Haskell -- recursive version is unbeatably faster than my own version of non-recursive combinations.

```
shell> ghc -O2 ch-2.hs
shell> time ./ch-2 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6
________________________________________________________
Executed in 202.51 millis fish external
...
```

I reckon that go version will win after optimizing the code where I did in Perl, but I don't think I will change the code. 😓

###
**However** Raku version was *not successful*

Here is link for code, but I conclude that Raku doesn't like flow control. and IMHO, this part will be where Raku needs to improve!! 😅

## Discussion (0)