Perl Weekly Challenge 191

21 Nov, 2022

This week's first task is almost a continuation of task II.

Task 1: Binary Flip

You are given a positive integer, $n.

Write a script to find the binary flip.

Example 1

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.

Example 2

Input: $n = 4
Output: 3

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

Example 3

Input: $n = 6
Output: 1

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

My approach was the same for both the Go and Python solution, and I used the same algorithm as in the task explanation:

find the binary equivalent of the given integer:

the builtin bit_length() in Python does just that. it returns the number of bits necessary to represent an integer in binary, excluding the sign and leading zeros. ¹

flipping the binary digits:

set the mask of n => (1 << n.bit_length() - 1).
One nasty edge case is when n == 0. I came against it while testing the code for robustness. For example, (0).bit length() == 0 and shifting the bit 1 << 0 returns 1, which gives you zero when XORing (0 ^ 0) == 0 and the correct answer should be 1, as we are asked to flip the binary digit. Getting the max() between 1 and the mask ensures that we get 1 when n == 0.
toggle the set bits in n.bit_length() with an XOR operation.

Here's the code for both languages:

Python

import unittest

class TestSolutionI(unittest.TestCase):

    def binary_flip(self, n):
        mask = max(1, (1 << n.bit_length()) - 1)
        return n ^ mask

    def test_binary_flip(self):
        self.assertEqual(self.binary_flip(5), 2, "example 1")
        self.assertEqual(self.binary_flip(4), 3, "example 2")
        self.assertEqual(self.binary_flip(6), 1, "example 3")
        self.assertEqual(self.binary_flip(0), 1, "nasty edge case")
        self.assertEqual(self.binary_flip(-10), -7, "negative num edge case")


if __name__ == "__main__":
    unittest.main(verbosity=True)

package main

import "math/bits"

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func BinaryFlip(n int) int {
	mask := max(1, (1<<(bits.Len(uint(n))) - 1))
	return n ^ mask
}

Task 2: Equal Distribution

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.

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)

When I initially sketched a solution for task II, I was going to approach it with Dynamic Programming and some bitmasks, until I realize that the solution was right in front of me. For example:

We are asked to find the distribution in the given list, so that each member gets the same number. Well, it turns out, that this is one of the functions of arithmetic mean in descriptive statistics.
In other words, mean() measures the central location of the data. In this case, that is exactly what we need! Once we find it, we evenly distribute it across each member.
Let's see the code:

from statistics import mean
from unittest import main, TestCase

cases = [
    ([1, 0, 5], 4),
    ([0, 2, 0], -1),
    ([0, 3, 0], 2),
]

class TestSolutionII(TestCase):

    def equal_distro(self, _list):
        m = int(mean(_list))
        if m == 0:
            return -1
        else:
            return m + m

    def test_equal_distribution(self):
        for _input, output in cases:
            with self.subTest(_input=output):
                self.assertEqual(self.equal_distro(_input), output)


if __name__ == "__main__":
    main(verbosity=2)

Let's take Example 1:

the arithmetic mean of the list (1, 0, 5) == 2 (floored).
there are 3 members in the list.
if we give each member the "mean" the aka average of all the values in the "pot".
then we can evely distribute it amongst the three!

The edge case on Example 2:

if the mean of the list is 0.
then it simply means we have 0 to distribute evenly!
thus, we return -1

Moreover, we can extend this script to support reporting the desired distribution. We can simply refactor as follows:

def equal_distro(_list):
  from statistics import mean
  m = int(mean(_list))
  if m == 0:
    return -1
  else:
    print([m] * len(_list))
    return m + m

"""
>>> equal_distro([1, 0, 5])
[2, 2, 2]
4

>>> equal_distro([0, 2, 0])
-1

>>> equal_distro([0, 3, 0])
[1, 1, 1]
2
"""

This will give you the even distribution for each list that has a possible solution.

Happy hacking!

P.S: For the Go solutions. See here!

Reference

https://docs.python.org/3/library/stdtypes.html#int.bit_length↩

#go #perl_weekly_challenge #python