Jared Martin

This blog post contains the "missing comments" from my contribution to the Perl Weekly Challenge 055. If you haven't read the Task #1 Problem Description: Flip Binary you might want to do that first.

Now to document a bit more, my submission for PWC 056 Task #1.

First, please feel free to suggest a better style of exposition. At work, I usually lard my code with comments galore, but with small demonstration programs I prefer to get as much code onto one page as possible, so now I'll try to illuminate a bit more my thoughts, no promises that they will be illuminating. Of course, let me know of any outright errors you catch as well, please.

The Idea

Break the binary string into its constituent subgroups of 0s and 1s and to calculate the delta for each subgroup if it was "flipped". This means a subgroup of 0s would have a positive value if flipped, e.g., '000' would have a value of +3 and '11111' would have a value of -5. The net gain/loss of flipping a substring of the input string is therefore just the sum of the deltas of the subgroups in the substring.

• Only consider substrings that begin and end on a 0 subgroup, since you will only want to include a 1 subgroup in your substring to get to more 0s to flip.


• Only consider the cases of starting at the first 0 of a 0 subgroup (the "leftmost zero" of the subgroup) and stopping at the last 0 of a 0 subgroup (the "rightmost zero" of the subgroup).

Input

I decided to require a string of 1s and 0s for input. Another approach could have been to require a bignum integer and then take it apart in its binary representation.

Validation

Just make sure the one argument is a string consisting only of 1s and 0s.

Parsing

• Capture any leading or trailing 1s. They will never be in a maximal flip.
• Obtain the $midstr, which is a substring starting with the first 0 and ending on the last 0 of the input string.
• The initialization of $begstr is done to handle the case were the input string is all 1s.
• Then, use the g flag on the regexp to generate a list of 0 groups and 1 groups.
• The grep retrieves alternating list members because I could not figure out how to capture a group of all the same leading character without using two captures.
• The map converts the groups of 0s and 1s to their deltas, which is all that is needed for the analysis.

The Analysis

The array @groups now contains the deltas for each subgroup of 0s and of 1s. By construction, the first element in @groups is the positive delta of the first subgroup of 0s in the input string and the last element in @groups is the positive delta of the last subgroup of 0s in the input string.

The loop finds the sum of the detas for every substring of the input string that starts on a leftmost zero" and ends on a "rightmost zero". The maximum sum, with corresponding left and right indices (& there may be more than one pair of these) is saved each time through the loop, with an overall maximum being kept. At the end of the loop only the maximums that are equal to the overall maximum are kept. These are the @answers.

The Output

Just run through the answers. Although not required according to the task, the flipped string is printed for each answer. This is the only time in this program where the string is actually flipped.

Conclusion

I feel pretty good about the efficiency of this algorithm. Because it is careful about what its looping through, I think it should stand up well in any "code shootout".