1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#! /opt/local/bin/perl
#
# flippenbitter.pl
#
# TASK #2 › Binary Substrings
# Submitted by: Mohammad S Anwar
# 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.
#
# Example 1:
# Input: $B = “101100101”, $S = 3
# Output: 1
#
# Binary Substrings:
# "101": 0 flip
# "100": 1 flip to make it "101"
# "101": 0 flip
#
# Example 2:
# Input $B = “10110111”, $S = 4
# Output: 2
#
# Binary Substrings:
# "1011": 0 flip
# "0111": 2 flips to make it "1011"
#
# method:
# I rather enjoy these odd little puzzles with a lot of small moving
# parts working towards some exotic goal. In this one we need to
# segment the initial string, making sure it divides out evenly,
# then compare the bits in each segment against those in all of the
# remaining segments, calculating the changes required to alter the
# other to match the first, then sum the results for the list.
# Finally, after comparing each section the minimum sum among all
# the sections, representing the most efficiant way to go about
# things, will be the result requested. The given goal, the number
# of bits flipped to equalize the segments to one of the values
# without specifiying which, does not serve any obvious practical
# purpose in itself. It could be a widget in a longer chain of data
# processing, but who knows? This robs us the opportunity to provide
# background and commentary on the context, but on the other hand
# allows us to focus on the quiltwork: stiching together smaller
# disparate ideas to form a cohesive whole.
#
# Whew!
#
# Ok so let's break that down again:
# - make sure the division is even (or it makes no sense)
# - for each segment:
# - convert to decimal
# - xor with other segments to find bit differences
# - sum different bits for entire list
# - compare aginst and possibly replace a running minimum of flips required
# There are a couple of implementation notes to go along with this
# sequence of actions. One is in identifying which bits between two
# binary strings are different. We can cut straight to the meat of
# the matter by using a binary XOR on the two strings; identical
# bits either 0 or 1 will produce a zero, differences will produce a
# 1. As we want the *number* of differences and don't care about the
# structure, we can get this by summing the bits in the XOR result.
#
# This seems much more efficiant that breaking apart the binary
# strings and directly comparing bits, but there's a caveat: the
# bitwise operators work on *decimal* numbers, necessatating a
# conversion to base-10, and to sum the bits it's easiest to work in
# binary. Fortunately it's easy to switch back and forth.
#
# Another refactoring we can make is that once we have originally
# produced the bitstring segments we no longer ever need to see them
# in binary notation, so we can immediately convert the list of
# values to base-10. This cleans up the code underneath, at the
# expense of easily debugging exactly what's happening in the binary
# notation. But, as I said, a refactor move. We've eliminated
# printing some internal variables to peek in on the action, and
# we're honing a process that's vetted.
#
#
#
# © 2021 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
use warnings;
use strict;
use feature ":5.26";
sub minflips {
## given a segment length and binary bitstring,
## segment the binary string and determine the minimum flips required to
## produce consistency among sections, using any section as the model
my ($size, $bin) = @_;
return undef if length($bin)%$size;
my @sections;
## section into equal sized parts and convert to decimal
push @sections, oct('0b'.substr($bin, 0, $size, '')) while length $bin > 0;
my $min = "Inf";
for ( 0..$#sections ) {
my $flips = bitflips($_, @sections);
$min = $flips if $flips < $min;
}
return $min;
}
sub bitflips {
## given a list of decimal numbers and an index,
## compute the number of flipped bits to transform all numbers in the list
## to the value indicated at index $idx
my ($idx, @sections) = @_;
my $flips = 0;
for my $sect (@sections) {
my $xored = sprintf "%b", $sections[$idx] ^ $sect; ## sections are decimal here
$flips += $_ for split //, $xored;
}
return $flips;
}
use Test::More;
is(minflips(3, "101100101"), 1, 'ex-1');
is(minflips(4, "10110111"), 2, 'ex-2');
is(minflips(3, "110001011101010"), 6, '5 sections');
is(minflips(3, "110001011101010111001010101010010000111101111110"), 21, 'many sections');
is(minflips(3, "000000"), 0, 'no work done - 0s');
is(minflips(2, "010101"), 0, 'no work done - mixed');
is(minflips(2, "0101010"), undef, 'not divisible');
done_testing();
|
