RabbitFarm

2024-12-01

Contiguous and Semi-Ordered

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1: Contiguous Array

You are given an array of binary numbers, @binary.

Write a script to return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Let’s not concern ourselves with any particular efficiencies and just analyze all the subsets of the given numbers!

The main loop for iterating over all the contiguous sub-arrays.

⟨loop over all sub-arrays 1 ⟩≡


do{
my $i = $_;
do{
my $j = $_;
if($i != $j && $i < $j){
my @s = @{$b}[$i .. $j];
my $zeroes = grep {$_ == 0} @s;
my $ones = grep {$_ == 1} @s;
$max_length = @s if $zeroes == $ones &&
@s > $max_length;
}
} for 0 .. @{$b} - 1;
} for 0 .. @{$b} - 1;
◇

Fragment referenced in 2.

Uses: $b 2, $max_length 2.

We really just need one subroutine to co-ordinate the inputs and run the main loop that’s required.

⟨main subroutine 2 ⟩≡


sub contiguous_array{
my $b = [@_];
my $max_length = 0;
⟨loop over all sub-arrays 1 ⟩
return $max_length;
}
◇

Fragment referenced in 3.

Defines: $b 1, $max_length 1.

Putting it all together...

"ch-1.pl" 3≡


⟨preamble 4 ⟩
⟨main subroutine 2 ⟩
⟨main 5 ⟩
◇

⟨preamble 4 ⟩≡


use v5.40;
◇

Fragment referenced in 3, 9.

The rest of the code just runs some simple tests.

⟨main 5 ⟩≡


MAIN:{
say contiguous_array 1, 0;
say contiguous_array 0, 1, 0;
say contiguous_array 0, 0, 0, 0, 0;
say contiguous_array 0, 1, 0, 0, 1, 0;
}
◇

Fragment referenced in 3.

Sample Run
$ perl perl/ch-1.pl 
2 
2 
0 
4

Part 2: Semi-Ordered Permutation

You are given permutation of $n integers, @ints. Write a script to find the minimum number of swaps needed to make the @ints a semi-ordered permutation.

A permutation is called semi-ordered if the first number is 1 and the last number equals n. That means we need to count the number of swaps needed to move 1 to the beginning and $n to the end.

At first thought, I wonder if there’s a catch? Does the swapping end up moving 1 or $n further from its destination? That doesn’t seem to be the case even if they were adjacent to each other. That is because they are moving in opposite directions. 1 is always moving left and $n is always moving right. Although they may swap with each other it will always be of benefit to them both.

Let’s start with the code for swapping left and and right to move 1 and $n in their respective directions.

⟨swap left 6 ⟩≡


($i->[$j - 1], $i->[$j]) = ($i->[$j], $i->[$j - 1]);
$j--;
$swaps++;
◇

Fragment referenced in 8.

Uses: $i 8, $swaps 8.

⟨swap right 7 ⟩≡


($i->[$n + 1], $i->[$n]) = ($i->[$n], $i->[$n + 1]);
$n++;
$swaps++;
◇

Fragment referenced in 8.

Uses: $i 8, $swaps 8.

We’ll put everything together in a subroutine.

⟨semi_ordered: co-ordinates all the swaps and checks 8 ⟩≡


sub semi_ordered{
my $i = [@_];
my $swaps = 0;
my $j = -1;
my $n = @{$i};
do{
$j = $_ if $i->[$_] == 1;
$n = $_ if $i->[$_] == $n;
} for 0 .. @{$i} - 1;
{
if($j != 0){
⟨swap left 6 ⟩
}
if($n != @{$i} - 1){
⟨swap right 7 ⟩
}
redo unless $j == 0 && $n == @{$i} - 1;
}
return $swaps;
}
◇

Fragment referenced in 9.

Defines: $i 6, 7, $swaps 6, 7.

The rest of the code drives some tests.

"ch-2.pl" 9≡


⟨preamble 4 ⟩
⟨semi_ordered: co-ordinates all the swaps and checks 8 ⟩
⟨main 10 ⟩
◇

⟨main 10 ⟩≡


MAIN:{
say semi_ordered 2, 1, 4, 3;
say semi_ordered 2, 4, 1, 3;
say semi_ordered 1, 3, 2, 4, 5;
}
◇

Fragment referenced in 9.

Sample Run
$ perl perl/ch-2.pl 
2 
3 
0

References

The Weekly Challenge 297
Generated Code

posted at: 23:34 by: Adam Russell | path: /perl | permanent link to this entry