Weekly Challenge #083 Task #2 :: (Perl) 
Tags: challenge, perlweeklychallenge, perl, raku
Published: 2020-10-23 13:06:42

## [**TASK #2 › Flip Array**](https://perlweeklychallenge.org/blog/perl-weekly-challenge-083/#TASK2)

## **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](https://docs.raku.org/routine/race). So I came up with

```perl
... 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](https://dev.to/jeongoon/weekly-challenge-083-task-2-raku-2cjm#race)

  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.
```perl
> ([X] (^20).map({ $_, -$_ })).elems # ^20 eqv. 0..19
1048576
```
is faster than,
```perl
> (^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...*
```perl
(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.
```perl
... 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](https://metacpan.org/pod/Algorithm::Combinatorics)
```shell
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**](https://github.com/jeongoon/perlweeklychallenge-club/blob/master/challenge-083/jeongoon/perl/CombinationsIndex.pm)
```shell
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](https://github.com/jeongoon/perlweeklychallenge-club/blob/master/challenge-083/jeongoon/go/ch-2.go)
  *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
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
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](https://github.com/jeongoon/perlweeklychallenge-club/blob/master/challenge-083/jeongoon/haskell/ch-2.hs)
  Here we go, Haskell version. I made my own version of combinations again. you can find it [HERE](https://github.com/jeongoon/perlweeklychallenge-club/blob/master/challenge-083/jeongoon/haskell/Combinations.hs) because -- In Haskell -- recursive version is unbeatably faster than my own version of non-recursive combinations.
```shell
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](https://github.com/jeongoon/perlweeklychallenge-club/blob/master/challenge-083/jeongoon/raku/ch-2.yet-another-race.raku), but I conclude that Raku doesn't like flow control. and IMHO, this part will be where Raku needs to improve!! 😅