PERL WEEKLY CHALLENGE – 055

This is my 25th week participating into the weekly challenge.


TASK #1

Flip Binary

You are given a binary number B, consisting of N binary digits 0 or 1s0, s1, …, s(N-1).

Choose two indices L and R such that 0 ≤ L ≤ R < N and flip the digits s(L), s(L+1), …, s(R). By flipping, we mean change 0 to 1 and vice-versa.

For example, given the binary number 010, the possible flip pair results are listed below:

  • L=0, R=0 the result binary: 110
  • L=0, R=1 the result binary: 100
  • L=0, R=2 the result binary: 101
  • L=1, R=1 the result binary: 000
  • L=1, R=2 the result binary: 001
  • L=2, R=2 the result binary: 011

Write a script to find the indices (L,R) that results in a binary number with maximum number of 1s. If you find more than one maximal pair L,R then print all of them.

Continuing our example, note that we had three pairs (L=0, R=0)(L=0, R=2), and (L=2, R=2) that resulted in a binary number with two 1s, which was the maximum. So we would print all three pairs.


This was a bit of a challenging one as I don’t usually work with bit operators. I didn’t want to “cheat” and work with strings that represent binary and decided to use purely binary arithmetic for this challenge.

The hard part of those problem was flipping the correct bits. I solved this by splitting the binary number into two parts using masks. The first part being the bits to flip and the second part being the bits to keep.

So lets say we want to flip 010 where L = 0 and R = 1, we would need to seperate 010 into two parts 01 and 0, We use the masks which are 110 and 001 respectively.

Then add the flipped bits and the unflipped bits to get the answer.

Here is a simple example for 010 where L = 0 and R = 1

Split into two parts:
flip_bits: 010 & 110 = 010
kept_bits: 010 & 001 = 000

we then flip the “flip_bits”
~ 010 = 101

Reapply the mask to the flip_bits
101 & 110 = 100

Then add both parts
101 + 000 = 100

So 010 becomes 100, for L = 0 and R = 1

It’s cognitively heavy but it works, hopefully the code explains it better than i can.

To test: remember to use the integer representation of the bit string and the length of the bit string.

For example, to test 010:

./ch-1.pl 2 3

or

perl6 ./ch-1.p6 2 3

if the length of the bitstring isn’t supplied
like ./ch-1.pl 2, then the length of the bitstring will be calculated dynamically. In this case the bit string will look like 10, giving different results that the example.


Perl 5 solution

#!/usr/bin/perl
# Test: ./ch-1.pl 2 3
use strict;
use warnings;
use feature qw /say/;

my $b = $ARGV[0];
my $n = $ARGV[1];

# Calculate $n if not supplied
$n = int(log($b) / log(2)) + 1
	unless($n);

# Lets keep it to 1 to 32 bits and
# throw out bits outside of our range
$n = 32 if ($n > 32);
$n = 1  if ($n < 1);
my $mask = (2 ** $n - 1);
$b = $b & $mask;

# Print the original number
say "ORIGINAL: " . sprintf("%0${n}B", $b) . "\n";

# Store the solution;
my %solutions;
my $longest_soluton = 0;

# flip algorithm
for my $l (0 .. $n -1) {
	for my $r ($l .. $n - 1) {
		# We create two bit masks.
		# The first mask is what we use to flip the bits
		# and the second mask is what we use to keep the
		# original builts then add up the flipped bits
		# with the kept bits

		# Flip Mask
		my $flip_mask = 0;
		for my $i ($l .. $r) {
			$flip_mask += (2 ** ($n - $i - 1) );
		}

		# Calculate the keep mask
		my $keep_mask = (~ $flip_mask) & $mask;

		# Flip the relevant bits and calculate kept bits
		my $flipped_bits =  ~ ($b & $flip_mask) & $flip_mask;
		my $kept_bits    = $b & $keep_mask;

		# Add the bits outside the flipped bit
		my $flipped_number = $flipped_bits + $kept_bits;

		# Now store the number of ones
		my $length = calculate_true_bits($flipped_number);

		# Store the solutions
		$solutions{$length} = []
			unless ($solutions{$length});

		push @{$solutions{$length}}, {
			L      => $l,
			R      => $r,
			number => $flipped_number
		};

		# Length of the longest solution
		$longest_soluton = $length
			if ($longest_soluton < $length);
	}
}

# Print the solutions
say "SOLUTIONS length($longest_soluton):";
for my $solution (@{$solutions{$longest_soluton}}) {
	say 'L: ' . $solution->{L} .
	    ' R: ' . $solution->{R} .
	    ' number: ' . sprintf("%0${n}B", $solution->{number});
}

# Calculate the number of true bits
sub calculate_true_bits {
	my $number = shift;
	my $count = 0;

	do {
		$count++ if ($number & 1);
	} while ($number = $number >> 1);

	return $count;
}

Output

ORIGINAL: 010

SOLUTIONS length(2):
L: 0 R: 0 number: 110
L: 0 R: 2 number: 101
L: 2 R: 2 number: 011

Raku solution

# Test: perl6 ch-1.p6 2 3

multi MAIN(Int $b where * > 0) {
	my $n = ((log($b) / log(2)) + 1).Int;
	$n = 32 if ($n > 32);
	MAIN($b, $n);
}

multi MAIN(Int $a where * > 0 , Int $n where 0 < * < 32) {
	# Throw out bits outside of our range
	my $mask = (2 ** $n - 1);
	my $b = $a +& $mask;

	# Original binary
	say "ORIGINAL: " ~ sprintf("%0*b", $n, $b) ~ "\n";

	# Store the solution;
	my %solutions;
	my $longest_solution = 0;

	# flip algorithm
	for (0 .. $n -1) -> $l {
		for ($l .. $n - 1) -> $r {
			# Flip Mask
			my $flip_mask = 0;
			for ($l .. $r) -> $i {
				$flip_mask += (2 ** ($n - $i - 1) );
			}

			# Calculate the keep mask
			my $keep_mask = (+^ $flip_mask) +& $mask;

			# Flip the relevant bits and calculate kept bits
			my $flipped_bits =  +^ ($b +& $flip_mask) +& $flip_mask;
			my $kept_bits    = $b +& $keep_mask;

			# Add the bits outside the flipped bit
			my $flipped_number = $flipped_bits + $kept_bits;

			# Now store the number of ones
			my $length = calculate-true-bits($flipped_number);

			# Store the solutions
			%solutions{$length} = []
				unless (%solutions{$length});

			my %solution = 	(
				L      => $l,
				R      => $r,
				number => $flipped_number
			);

			%solutions{$length}.push(%solution);

			# Length of the longest solution
			$longest_solution = $length
				if ($longest_solution < $length);
		}
	}

	say "SOLUTIONS length($longest_solution):";
	for  (@(%solutions{$longest_solution})) -> $solution {
		say 'L: ' ~ $solution{'L'} ~
		    ' R: ' ~ $solution{'R'} ~
		    ' Number: ' ~
		    sprintf("%0*b", $n, $solution{'number'});
	}
}

# Calculate the number of true bits
sub calculate-true-bits(Int $n is copy) {
	my $count = 0;

	repeat {
		$count++ if ($n +& 1);
	} while ($n = $n +> 1);

	return $count;
}

Output

ORIGINAL: 010

SOLUTIONS length(2):
L: 0 R: 0 number: 110
L: 0 R: 2 number: 101
L: 2 R: 2 number: 011

TASK #2

Wave Array

Any array N of non-unique, unsorted integers can be arranged into a wave-like array such that n1 ≥ n2 ≤ n3 ≥ n4 ≤ n5 and so on.

For example, given the array [1, 2, 3, 4], possible wave arrays include [2, 1, 4, 3] or [4, 1, 3, 2], since 2 ≥ 1 ≤ 4 ≥ 3 and 4 ≥ 1 ≤ 3 ≥ 2. This is not a complete list.

Write a script to print all possible wave arrays for an integer array N of arbitrary length.

Notes:

When considering N of any length, note that the first element is always greater than or equal to the second, and then the ≤, ≥, ≤, … sequence alternates until the end of the array.


Brain was a bit exhausted from the last challenge so I just Brute forced this with https://metacpan.org/pod/Algorithm::Combinatorics and raku’s permutations as we’re probably doing an exhaustive search.

I’m sure there is a mathematically better way to come up with a solution.

Perl 5 solution

#!/usr/bin/perl
# Test: ./ch-1.pl 4
use strict;
use warnings;
use feature qw /say/;
use Algorithm::Combinatorics qw(permutations);

my $n = $ARGV[0];
my @array = (1 .. $n);

# Permutations
my $iter = permutations(\@array);

# Loop through each combination
while (my $p = $iter->next) {
	my $is_wave = 1;

	for (my $i = 1; $i < scalar(@$p); $i++) {
		if ( $i % 2 == 1 && $p->[$i] >= $p->[$i - 1] ||
		     $i % 2 == 0 && $p->[$i] <= $p->[$i - 1] ) {;
			$is_wave = 0;
			last;
		}
	}

	say join ' ', @$p if ($is_wave);
}

Output

2 1 4 3
3 1 4 2
3 2 4 1
4 1 3 2
4 2 3 1

Raku solution

# Test: perl6 ch-2.p6 4
sub MAIN(Int $n where * > 0) {
	[1 .. $n].permutations.grep({is-wave($_)}).join("\n").say;
}

# Is the array a wave
sub is-wave(@n) {
	my $is_wave = True;
	loop (my $i = 1; $i < @n.elems; $i++) {
		if ( $i % 2 == 1 && @n[$i] >= @n[$i - 1] ||
		     $i % 2 == 0 && @n[$i] <= @n[$i - 1] ) {;
			$is_wave = False;
			last;
		}
	}
	return $is_wave;
}

Output

2 1 4 3
3 1 4 2
3 2 4 1
4 1 3 2
4 2 3 1

One thought on “PERL WEEKLY CHALLENGE – 055

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