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
|
#!/usr/bin/perl -s
use v5.24;
use Test2::V0;
use experimental qw(signatures);
our ($tests, $examples);
run_tests() if $tests || $examples; # does not return
die <<EOS unless @ARGV == 1;
usage: $0 [-examples] [-tests] [B]
-examples
run the examples from the challenge
-tests
run some tests
B
binary number
EOS
### Input and Output
main: {
local $" = ',';
local $, = ',';
say map "(@$_)", flip_max_bits(shift)->@*;
}
### Implementation
# Count the "ones" in all prefixes preceding L and the "ones" in all
# suffixes succeeding R. Then loop over all (L, R) and count the
# "zeroes" in the according part. The sum of the prefix ones, the
# middle zeroes and the suffix ones is the total number of "ones" after
# flipping the middle bits. Recording all maxima.
sub flip_max_bits ($n) {
my @lr;
my $maxbits = '-Inf';
my @lbits;
my $tmp;
push @lbits, ($tmp = substr $n, 0, $_) =~ tr/1/1/
for (0 .. length($n) - 1);
my @rbits;
push @rbits, ($tmp = substr $n, $_ + 1) =~ tr/1/1/
for (0 .. length($n) - 1);
for my $l (0 .. length($n) - 1) {
for my $r ($l .. length($n) - 1) {
my $rbits = $rbits[$r];
my $bits = $lbits[$l] + $rbits[$r] +
($tmp = substr $n, $l, $r - $l + 1) =~ tr/0/0/;
if ($bits > $maxbits) {
$maxbits = $bits;
@lr = ([$l, $r]);
} elsif ($bits == $maxbits) {
push @lr, [$l, $r];
}
}
}
\@lr;
}
### Examples and tests
sub run_tests {
SKIP: {
skip "examples" unless $examples;
is flip_max_bits('010'), [[0, 0], [0, 2], [2, 2]], 'example';
}
SKIP: {
skip "tests" unless $tests;
}
done_testing;
exit;
}
|
