Equal Flip with Raku

This is my response to The Weekly Challenge #192.

Challenge #192.1: Binary Flip

Input: $n = 5
Output: 2

First find the binary equivalent of the given integer, 101.
Then flip the binary digits 0 -> 1 and 1 -> 0 and we get 010.
So Binary 010 => Decimal 2.

Input: $n = 4
Output: 3

Decimal 4 = Binary 100
Flip 0 -> 1 and 1 -> 0, we get 011.
Binary 011 = Decimal 3

Input: $n = 6
Output: 1

Decimal 6 = Binary 110
Flip 0 -> 1 and 1 -> 0, we get 001.
Binary 001 = Decimal 1

Why bother, when we can use the built-in bitwise negation operator +^?

> say +^5;  # -> -6

Yes, well. Not quite the expected result, as it flipped the sign bit as well. Reading the documentation would have told us so...

See docs.raku.org/routine/+$CIRCUMFLEX_ACCENT for more information about the infix bitwise negation operator +^.

So we have to program it manually.

#! /usr/bin/env raku

unit sub MAIN (Int $n where * > 0, :v(:$verbose));

my $binary  = $n.base(2);                                          # [1]
my $flip    = $binary.comb.map({ $_ eq '1' ?? '0' !! '1' }).join;  # [2]
my $decimal = $flip.parse-base(2);                                 # [3]

if $verbose
{
  say ":Binary: $binary";
  say ":Flip:   $flip";
}

say $decimal;

[1] Turn the number into binary (with base).

See docs.raku.org/routine/base for more information about base.

[2] Reverse all the bits of the binary representation, using map on each character (gotten with comb), and glued together afterwards with join.

[3] Convert the binary representation back to a decimal value (with parse-base).

See docs.raku.org/routine/parse-base for more information about parse-base.

Running it:

$ ./binary-flip  5
2

$ ./binary-flip  4
3

$ ./binary-flip  6
1

Looking good.

Let us try with verbose mode, and add some more values:

$ ./binary-flip -v 5
:Binary: 101
:Flip:   010
2

$ ./binary-flip -v 4
:Binary: 100
:Flip:   011
3

$ ./binary-flip -v 6
:Binary: 110
:Flip:   001
1

$ ./binary-flip -v 255
:Binary: 11111111
:Flip:   00000000
0

$ ./binary-flip -v 256
:Binary: 100000000
:Flip:   011111111
255

It is possible to make it shorter, by removing the verbose mode:

#! /usr/bin/env raku

unit sub MAIN (Int $n where * > 0);

say $n.base(2).comb.map({ $_ eq '1' ?? '0' !! '1' }).join.parse-base(2);

It is possible to flip Boolean values with a single not operation:

#! /usr/bin/env raku

unit sub MAIN (Int $n where * > 0);

say $n.base(2).comb.map( { + ! + $_ } ).join.parse-base(2);
                         # 3 2 1

The downside (in this case better called the flipside, perhaps?) is that we have to coerce the digit from a string to a numeric value [1] before applying not [2], as it (i.e. not) does not (i.e. doesn't) play well with strings.

The final + [3] (the first one, when we read from the left) coerces the Boolean value back to the digit 0 or 1.

Even shorter:

#! /usr/bin/env raku

unit sub MAIN (Int $n where * > 0);

say $n.base(2).comb.map( + ! + * ).join.parse-base(2);

Now that should be unreadable for non-Raku programmers...

Challenge #192.2: Equal Distribution

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)

Input: @list = (0, 2, 0)
Output: -1

It is not possible to make each same.

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)

#! /usr/bin/env raku

unit sub MAIN (*@list where @list.elems > 1 && all(@list) ~~ /^\d+/,  # [1]
               :v(:$verbose));

my $sum     = @list.sum;               # [2]
my $target  = $sum div @list.elems;    # [3]

if $target != $sum / @list.elems       # [4]
{
  say -1;                              # [4a]
  exit;                                # [4b]
}

say ":Computing..." if $verbose;

my $moves = 0;                         # [5]

my @list2 = @list.map: +*;             # [6]

for 0 .. @list2.elems - 2 -> $index    # [7]
{
  while @list2[$index] > $target       # [8]
  {
    $moves++;                          # [8a]
    @list2[$index]--;                  # [8b]
    @list2[$index+1]++;                # [8c]
    say ":Move $moves: @list2[]" if $verbose;
  }

  while @list2[$index] < $target       # [9]
  {
    $moves++;                          # [9a]
    @list2[$index]++;                  # [9b]
    @list2[$index+1]--;                # [9b]
    say ":Move $moves: @list2[]" if $verbose;
  }
}

say $moves;                            # [10]

[1] We use a slurpy array (*@list) to get all the arguments. Then we attach a where clause to ensure that we have at least one element (as I am pretty sure that it takes at least two elements to form a list, on the other hand, I may have mixed it up with a tango) and that they are all non-negtaive integers.

[2] We are going to short cut the whole operation if it is impossible to reach the desired result. We need the sum of all the values for that.

[3] Then we get the target value for each element in the list, as an integer (courtesy of the integer division operator div).

See docs.raku.org/routine/div for more information about div.

[4] Then we do a normal division, and if the result is the same (as the integer division result) we are good (as we will find a solution when we have a go at it). If not, print "-1" [4a] and exit [4b].

Note that I have taken a shortcut here, by allowing negative intermediary numbers. This is of course illegal (for mere mortals), but it does not matter in practice - as the number of operations is the same as if we did it the correct way (of shuffling values further away back towards us).

The first example is shown below, as altered by the program. Increased values are shown in green, and lowered ones in red. We can change the first and second operation (with the ones on the right) to awoid negatice values, but the overall number of operations will not be affected.

[5] The number of moves, i.e. the end result. To be printed in [10].

[6] The input is a list of IntStr values, that for some reason do not like beeing treated to ++ or --. So we set up a copy, where we ensure that the values are numeric (with the + prefix).

See docs.raku.org/routine/+ for more information about the Numeric Coercion Prefix Operator +.

[7] Iterate over the indices of the array, except the last one. As we are working on pairs; the current one and the next.

[8] As long as the current value (i.e. the value at the current index in the array) is higher than the target, offload 1 to the next value.

[9] Or, as long it is lower, take 1 from the next value.

[10] Print the number of operations.

Running it:

$ ./equal-distribution 1 0 5
4

$ ./equal-distribution 0 2 0
-1

$ ./equal-distribution -v 0 3 0
2

Looking good.

With verbose mode:

$ ./equal-distribution -v 1 0 5
:Computing...
:Move 1: 2 -1 5
:Move 2: 2 0 4
:Move 3: 2 1 3
:Move 4: 2 2 2
4

$ ./equal-distribution -v 0 2 0
-1

$ ./equal-distribution -v 0 3 0
:Computing...
:Move 1: 1 2 0
:Move 2: 1 1 1
2

And that's it.