RabbitFarm

2022-11-27

Flipping to Redistribute

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given a positive integer, \$n. Write a script to find the binary flip.

Solution

``````
use v5.36;
sub int2bits{
my(\$n) = @_;
my @bits;
while(\$n){
my \$b = \$n & 1;
unshift @bits, \$b;
\$n = \$n >> 1;
}
return @bits
}

sub binary_flip{
my(\$n) = @_;
my @bits = int2bits(\$n);
@bits = map {\$_^ 1} @bits;
return oct(q/0b/ . join(q//, @bits));
}

MAIN:{
say binary_flip(5);
say binary_flip(4);
say binary_flip(6);
}
``````

Sample Run

``````
\$ perl perl/ch-1.pl
2
3
1
``````

Notes

There was once a time when I was positively terrified of bitwise operations. Anything at that level seemed a bit like magic. Especially spooky were the bitwise algorithms detailed in Hacker's Delight! Anyway, has time has gone on I am a bit more confortable with these sorts of things. Especially when, like this problem, the issues are fairly straightforward.

The code here does the following:

• converts a given integer into an array of bits via `int2bits()`

• flips the bits using an xor operation (the `map` in `binary_flip()`)

• converts the array of flipped bits to the decimal equivalent via `oct()` which, despite the name, handles any decimal, binary, octal, and hex strings as input.

Part 2

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.

Solution

``````
use v5.36;
use POSIX;

sub equal_distribution{
my(@integers) = @_;
my \$moves;
my \$average = unpack("%32I*", pack("I*",  @integers)) / @integers;
return -1 unless floor(\$average) ==  ceil(\$average);
{
map{
my \$i = \$_;
if(\$integers[\$i] > \$average && \$integers[\$i] > \$integers[\$i+1]){\$integers[\$i]--; \$integers[\$i+1]++; \$moves++}
if(\$integers[\$i] < \$average && \$integers[\$i] < \$integers[\$i+1]){\$integers[\$i]++; \$integers[\$i+1]--; \$moves++}
} 0 .. @integers - 2;
redo unless 0 == grep {\$average != \$_} @integers;
}
return \$moves;
}

MAIN:{
say equal_distribution(1, 0, 5);
say equal_distribution(0, 2, 0);
say equal_distribution(0, 3, 0);
}
``````

Sample Run

``````
\$ perl perl/ch-2.pl
4
-1
2
``````

Notes

The rules that must be followed are:

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.

First we compute the average of the numbers in the list. Provided that the average is a non-decimal (confirmed by comparing `floor` to `ceil`) we know we can compute the necessary "distribution".

The re-distribution itself is handled just by following the rules and continuously looping until all values in the list are the same.

References

oct

Challenge 192

posted at: 19:04 by: Adam Russell | path: /perl | permanent link to this entry