## Advent Calendar - December 20, 2022

Tuesday, Dec 20, 2022| Tags: Raku, JavaScript

### |   Day 19   |   Day 20   |   Day 21   |

The gift is presented by `Roger Bell_West`. Today he is talking about his solution to “The Weekly Challenge - 192”. This is re-produced for Advent Calendar 2022 from the original post by him.

## Equal Flips For All

I’ve been doing the Weekly Challenges.

The latest involved a binary negation and list division. (Note that this is open until `27 November 2022`.)

You are given a positive integer, `\$n`.

Write a script to find the binary flip.

This turns out to be: take the binary representation (with no leading zeroes), then exchange all `0s` and `1s` to get an inverse value.

This is clearly intended to be a problem about binary representations. But we don’t need to do that. Instead, I find the value of the `leftmost set bit` in the input by counting repeated shift rights until there’s nothing left – e.g. `5` is processed as `101`, `10`, `1`, `0`, so `three` shifts. (i.e. `log base 2`.) Then shift `1` left that many times (getting `8`). Subtract 1: `7`, which gives me what in binary would be a series of `"1"` of the same length as the original number. Then subtract the input from that (gosh, an actual legitimate `"take away the number you first thought of"`).

This sequence is in the OEIS and the graph makes this approach particularly obvious.

Some languages have access to `CPU functions` to count leading zeroes and thus get a binary magnitude that way, but I did this the same way throughout. `JavaScript`:

``````function binaryflip(n) {
let m = n;
let r = 0;
while (m > 0) {
m >>= 1;
r += 1;
}
return (1 << r) - 1 - n;
}
``````

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.

`"Distribute"` turns out to mean `"subtract one from a list value, adding it to another adjacent list value"`. So this has to be done iteratively `[0 3 0] → [1 2 0] → [1 1 1] = 2 steps` , adding and subtracting `1` each time. If a number is higher than both its neighbours, the process is not immediately obvious, but this one seemed to work.

## Raku

``````sub equaldistribution(@list) {
``````

Check that an even distribution is possible.

``````    my \$s = @list.sum;
if (\$s % @list.elems != 0) {
return -1;
}
``````

Get a target value for each element.

``````    my \$m = \$s div @list.elems;
my \$out = 0;
my @w = @list;
while (True) {
for (0..@w.elems-2) -> \$i {
``````

Going through the list, if this value is higher than it needs to be, move any surplus into the next element.

``````            if (@w[\$i] > \$m) {
my \$v = @w[\$i] - \$m;
@w[\$i+1] += \$v;
\$out += \$v;
@w[\$i] = \$m;
``````

If it’s lower, take as much as possible from the next element (without letting it go below zero.)

``````            } elsif (@w[\$i] < \$m) {
my \$v = min(\$m - @w[\$i], @w[\$i+1]);
@w[\$i+1] -= \$v;
\$out += \$v;
@w[\$i] += \$v;
}
}
``````

If the job’s done, exit, otherwise loop again.

``````        if (@w.all == \$m) {
last;
}
}
return \$out;
}
``````

Full code on GitHub.

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.

## SO WHAT DO YOU THINK ?

If you have any suggestions or ideas then please do share with us.