The Weekly Challenge 055

Flip Binary and Wave Array

Solutions on GitHub

Task 1: Flip Binary

You are given a binary string. You are allowed to flip characters (0 to 1 or 1 to 0) in one contiguous segment exactly once. Find the segment [L, R] that maximizes the number of 1s in the resulting string.

Example Output

Input: "010" Output: Max 1s: 2 (Segments: [0, 0], [0, 2], [2, 2])

Logic

Generate all possible pairs of indices L and R. For each pair, flip the contiguous segment between them and count the total number of 1s. Keep track of the maximum count and the corresponding indices.

Perl Solution

ch-1.pl

sub process_all_flips { my $binary = shift; my %all_results; my $max = 0; my @numbers = split //, $binary; for my $l_count ( 0 .. scalar(@numbers)-1 ) { for my $r_count ( $l_count .. scalar(@numbers)-1 ) { my $inverted = do_flip( $l_count, $r_count, $binary ); my $ones_count = () = $inverted =~ /1/gi; push @{ $all_results{$ones_count} }, [ $l_count, $r_count ]; $max = $ones_count if $ones_count > $max; } } return $all_results{$max}; }

Python Solution

ch-1.py

class BinFlip: def process_all_flips(self): for l_count in range(len(self.to_flip)): for r_count in range(l_count, len(self.to_flip)): self.l_count = l_count self.r_count = r_count self.current_flip = self.do_flip() self.process_current() return self.max_ones, self.all_flips[self.max_ones]

Task 2: Wave Array

Given an array of unique integers, find all permutations that form a wave array. A wave array is an array a where a[0] >= a[1] <= a[2] >= a[3] <= ....

Example Output

Input: [1, 2, 3, 4] Output: [2, 1, 4, 3], [3, 1, 4, 2], [3, 2, 4, 1], [4, 1, 3, 2], [4, 2, 3, 1]

Logic

Generate all permutations of the array. For each permutation, check if it alternates between decreasing and increasing steps (wave shape).

Perl Solution

ch-2.pl

sub check_wave { my $perm_ref = shift; my $direction = 1; # 1 = greater, -1 = smaller for ( 0 .. scalar(@$perm_ref) - 2 ) { if ( $direction == 1 ) { return 0 if $$perm_ref[$_] < $$perm_ref[ $_ + 1 ]; } else { return 0 if $$perm_ref[$_] > $$perm_ref[ $_ + 1 ]; } $direction *= -1; } return 1; }

Python Solution

ch-2.py

class WaveArray: @property def check_wave(self): direction = 1 for seq_count in range(len(self.current_wave)-1): if direction == 1: if self.current_wave[seq_count] < self.current_wave[seq_count+1]: return False else: if self.current_wave[seq_count] > self.current_wave[seq_count+1]: return False direction *= -1 return True