Perl Weekly Challenge 97: Binary Substrings

You are given a binary string $B and an integer $S.

Write a script to split the binary string $B of size $S and then find the minimum number of flips required to make it all the same.

Overview

Just like in this weeks other challenge, we will use a command line parameter. We will use -s SIZE to indicate the size of the substrings. The binary strings will be read from standard input.

To calculate the minimum number of flips required, note that flipping a bit on position i of a sub string has no bearing on the flips required in any other position. So we can calculate the minimum number of flips required for each position i independently, and sum the totals.

To calculate the minimum number of flips required for a specific position i, we calculate the number of 0s in position i in all the sub strings. Given the number of 0s, we can calculate the number of 1s as both numbers should add up to the number of sub strings (and that number can be easily calculate by dividing the length of the binary string with the length of the sub strings). Now, the minimum number of flips required is the minimum of the number of 0s and the number of 1s. Observe that is may be possible we end up flipping to a string which is not one of the sub strings. Consider the binary string 111011011011, and sub string length of 4. Then we get the following sub strings:

1110
1101
1011

It requires flipping two bits to change one of the sub string to any of the others, so four flips would be required if the target where any of the sub strings. However, if we just flip the 0 bits, all sub strings end up being 1111, and only three flips are required.

Note that we don’t have to split the binary string into sub strings to calculate the number of flips. We can just leave the binary string as is, and use a simple formula. The bit at position i of sub string j, is at position j * size + i, where size is the given length of the sub strings. For languages which index strings starting from index 1, the formula is j * size + i + 1.

Solutions

We will not be showing any code related to parsing command line options. This is the same as for the other challenge of this week. In each language, we will have a variable size (or $size) which will contain the value passed in.

The implementation in each language is almost identical, except for some syntax variation.

Perl

while (<>) {
    chomp;
    my $sections = length () / $size;
    my $sum = 0;
    for my $i (0 .. $size - 1) {
        my $zeros = 0;
        for my $j (0 .. $sections - 1) {
            my $index = $j * $size + $i;
            $zeros ++ if substr ($_, $index, 1) eq "0";
        }
        my $ones = $sections - $zeros;
        $sum += min ($zeros, $ones);
    }
    say $sum;
}

For each position i, we count the number of 0 on that position. We then calculate the number of 1s in that position, and sum the minimum of the two.

Find the complete program on GitHub.

AWK

{
    sum = 0
    sections = length ($0) / size
    for (i = 0; i < size; i ++) {
        zeros = 0;
        for (j = 0; j < sections; j ++) {
            indx = j * size + i + 1  # Can't use 'index' as a variable
            if (substr ($0, indx, 1) == "0") {
                zeros ++
            }
        }
        ones = sections - zeros
        sum += zeros < ones ? zeros : ones
    }
    print sum
}

Find the complete program on GitHub.

Bash

while read line
do    sections=$((${#line} / $size))
      sum=0
      for ((i = 0; i < size; i ++))
      do   zeros=0
           for ((j = 0; j < sections; j ++))
           do    index=$(($j * $size + $i))
                 if   [ "${line:$index:1}" == "0" ]
                 then zeros=$(($zeros + 1))
                 fi
           done
           ones=$(($sections - $zeros))
           sum=$(($sum + ($zeros < $ones ? $zeros : $ones) ))
      done
      echo $sum
done

Find the complete program on GitHub.

C

    while ((strlen = getline (&line, &len, stdin)) != -1) {
        strlen --;                      /* We don't care about the newline */
        int sections = strlen / size; 
        int sum = 0;
        for (int i = 0; i < size; i ++) {
            int zeros = 0;
            for (int j = 0; j < sections; j ++) {
                int index = j * size + i;
                if (line [index] == '0') {
                    zeros ++;
                }
            }
            int ones = sections - zeros;
            sum += zeros < ones ? zeros : ones;
        }
        printf ("%d\n", sum);
    }
    free (line);

Find the complete program on GitHub.

Lua

for line in io . lines () do
    local sections = #line / size
    local sum = 0
    for i = 0, size - 1 do
        local zeros = 0
        for j = 0, sections - 1 do
            index = j * size + i + 1
            if   string . sub (line, index, index) == "0"
            then zeros = zeros + 1
            end
        end
        local ones = sections - zeros
        if   zeros < ones
        then sum = sum + zeros
        else sum = sum + ones
        end
    end
    io . write (sum, "\n")
end

Find the complete program on GitHub.

Node.js

require ('readline')
. createInterface ({input: process . stdin})   
. on ('line', _ => {
    let sum      = 0
    let sections = _ . length / size
    for (let i = 0; i < size; i ++) {
        let zeros = 0
        for (let j = 0; j < sections; j ++) {
            let index = j * size + i;
            if  (_ . substring (index, index + 1) == "0") {
                zeros ++
            }
        }
        let ones = sections - zeros
        sum += zeros < ones ? zeros : ones
    }
    console . log (sum)
});

Find the complete program on GitHub.

Python

for line in fileinput . input ():
    sections = len (line) / size
    sum = 0
    for i in range (size):
        zeros = 0
        for j in range (sections):
            index = j * size + i
            if line [index : index + 1] == "0":
                zeros += 1
        ones = sections - zeros
        sum += min (zeros, ones)
    print (sum)

Find the complete program on GitHub.

Ruby

ARGF . each_line do |line|
     sections = (line . length - 1) / size
     sum = 0
     for i in 0 .. size - 1 do
         zeros = 0
         for j in 0 .. sections - 1 do
             index = j * size + i
             if   line [index, 1] == "0"
             then zeros += 1
             end
         end
         ones = sections - zeros
         sum += [zeros, ones] . min
     end
     puts sum
end

Find the complete program on GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s