# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC192 - Equal Distribution

**TL;DR**

**OR: donâ€™t be so negative!**

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

# The challenge

You are given a list of integers greater than or equal to zero,

`@list`

.Write a script to distribute the number so that each members are same. If you succeed then print the total moves otherwise print -1.

Please follow the rules (as suggested by

`Neils van Dijke`

[2022-11-21 13:00]`1) You can only move a value of '1' per move 2) You are only allowed to move a value of '1' to a direct neighbor/adjacent cell`

Example 1:`Input: @list = (1, 0, 5) Output: 4 Move #1: 1, 1, 4 (2nd cell gets 1 from the 3rd cell) Move #2: 1, 2, 3 (2nd cell gets 1 from the 3rd cell) Move #3: 2, 1, 3 (1st cell get 1 from the 2nd cell) Move #4: 2, 2, 2 (2nd cell gets 1 from the 3rd cell)`

Example 2:`Input: @list = (0, 2, 0) Output: -1 It is not possible to make each same.`

Example 3:`Input: @list = (0, 3, 0) Output: 2 Move #1: 1, 2, 0 (1st cell gets 1 from the 2nd cell) Move #2: 1, 1, 1 (3rd cell gets 1 from the 2nd cell)`

# The questions

Our fine host manwar is finding new ways of being creative *and*
inclusive, so this time he handed over rules description to Neils van
Dkjke. Excellent job both!

I might regret asking this question, but why only non-negative integers?

Another question â€“and this is seriousâ€“ are we supposed to find the
*minimum* number of steps if the **equal distribution** can be done? It
seemsâ€¦ not! Iâ€™ll try to aim at it, anyway.

# The solution

This. Was. Fun.

I started thinking of complex algorithms for finding the best place to
put stuff, *this might go here, but what if that is closer* when it
suddenly appeared.

Letâ€™s start from the far left. Suppose we have a spare unit that we have to reallocate somewhere. The optimal choice is to find the closer gap going rightwards, and this also moves us closer to an optimal solution.

How come? Suppose thereâ€™s another spare unit *somewhere*. For equal
distribution to be feasible, then there must be another empty slot
somewhere else. If this additional spare unit is left of the first slot,
then using it for the leftmost leads us to a solution that has the same
cost as not doing this. On the other hand, if itâ€™s on the right of the
leftmost empty slot, then using it for the leftmost spare unit is going
to save us some steps (at least one).

The first case is like this:

```
Spare Spare Gap Gap
1 2 1 2
XX XX
XX XX XX XX
XX XX XX XX XX XX
XX XX XX XX XX XX
```

Using Spare 1 to fill in Gap 1 costs 3 moves, which means that we spend other 3 moves to use Spare 2 to fill Gap 2, for a total of 6 moves. Doing this in reverse order means that we move Spare 2 for 1 step, and Spare 1 for 5 steps, for a total of 6 steps again. Hence, our strategy of filling the leftmost gap (Gap 1) with the leftmost Spare (Gap 2) is optimal in this case.

Letâ€™s not consider the second case:

```
Spare Gap Spare Gap
1 1 2 2
XX XX
XX XX XX XX
XX XX XX XX XX XX
XX XX XX XX XX XX
```

Our strategy costs us 4 moves (2 + 2); the reverse strategy costs 6 (5 to send Spare 1 to Gap 2, 1 to send Spare 2 into Gap 1). So, our strategy wins.

Iterate, and we have an optimal strategy.

So OK, now we have a strategy, but do we have an *algorithm*? An
*efficient algorithm*?

If we address one spare and gap matching at a time, we surely donâ€™t as this more or less scales like $O(DN)$, where $D$ is the number of displaced elements and $N$ is the number of slots in the list.

On the other hand, our strategy tells us that going from left to right
*works*. So weâ€™ll just organize a bus tour from left to right: at each
stop, we either take passengers onboard (when there are spare ones), or
we do nothing (when the slot has the right number of elements), or we
drop passengers (to fill the gaps).

Onlyâ€¦ *what do we do if the gap is left of the spare*? No worries!
Weâ€™ll leave one real passenger in the gap, taking onboard a *negative
passenger*, and then weâ€™ll fill in the negative passenger later when we
stop at the slot with the spare one. We have anti-matter, why canâ€™t we
have *anti-passengers*?!?

OK, shut the fun up and show the code time:

```
#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use List::Util 'sum';
my @inputs = map { split m{[\s,]+}mxs } @ARGV;
@inputs = qw< 1 0 5 > unless @inputs;
say equal_distribution(@inputs);
sub equal_distribution (@inputs) {
my $total = sum(@inputs);
return -1 if $total % @inputs;
my $average = $total / @inputs;
my ($delta, $moves) = (0, 0);
for my $value (@inputs) {
$moves += abs($delta);
$delta += $value - $average;
}
return $moves;
}
```

Variable `$delta`

tells us how many positive or negative passengers we
have onboard. Each bus stop, anyway, counts one move for either ones, so
we consider the absolute value to count the overall number of `$moves`

.

Raku time:

```
#!/usr/bin/env raku
use v6;
sub MAIN (*@args) {
my @inputs = @argsÂ».split(/<[ \s , ]>+/).Slip.flat;
@inputs = <1 0 5> unless @inputs;
put equal-distribution(@inputs);
}
sub equal-distribution (@inputs) {
my $total = @inputs.sum;
return -1 unless $total %% @inputs;
my $average = ($total / @inputs).Int;
my ($delta, $moves) = 0, 0;
for @inputs -> $value {
$moves += $delta.abs;
$delta += $value - $average;
}
return $moves;
}
```

Bonus point if you can guess how long it took me to figure the right
incantation of `Slip`

and `flat`

this time.

I almost forgot to mention that the failure case when there is no *equal
distribution* can be tackled by simply checking if the sum of all items
can be divided evenly among the available slots.

This algorithm now goes $O(N)$, because we have one full initial sweep to find the amount of elements that should end up in each slot, plus another full sweep of the bus going from left to right.

Stay safe and beware the anti-passengers that are suspiciously similar to youâ€¦ you might annihilate one another!

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