Ups and Downs, Beginnings and Ends (PWC 297)

Challenge 297 solutions in Perl by Matthias Muth

These are my Challenge 297 Task 1 and 2 solutions in Perl
for The Weekly Challenge.

Summary

Task 1: Contiguous Array
The trick is to use ups and downs (+1 and -1) instead of binary (1, 0), and add up those numbers. The sum will be the same before and after each subarray with an equal number of the two values, because they will inhibit each other.
Then find the longest stretch between positions having the same sum value.
One pass through the array only, $O(n)$ .

Task 2: Semi-Ordered Permutation
Determine the positions of '1' and 'n' (the largest number). The number of moves needed is their distance from the left and right end of the array, respectively. Minus one if the '1' was at the right of the 'n' originally.
Not actually doing the moves!
One pass, again, for finding the positions, even with an early loop exit ( $O(n)$ , too).
Then a simple formula.

Code:
Find the complete source code for both tasks, including tests, on Github.

Task 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.

Example 1

Input: @binary = (1, 0)
Output: 2
(1, 0) is the longest contiguous subarray with an equal number of 0 and 1.

 
Example 2

Input: @binary = (0, 1, 0)
Output: 2
(1, 0) or (0, 1) is the longest contiguous subarray with an equal number of 0 and 1.

 
Example 3*

Input: @binary = (0, 0, 0, 0, 0)
Output: 0

 
Example 4

Input: @binary = (0, 1, 0, 0, 1, 0)
Output: 4

I'm using a trick for making it easier to detect subarrays with an equal number of the two values:
I translate binary 1 and 0 into values +1 and -1, or 'ups and downs'.

Then, for any contiguous subarray with an equal number of +1 and -1,
the sum of its values will be zero.

Now, I built a cumulated sum, walking through the array.
Whenever a cumulated sum value occurs twice,
there is a subarray with an equal number of ups and
downs in between, and its length is the difference between the indexes where
the sum values occurred.

For the the program, I therefore mark the index of the
first occurrence of each sum value in a hash lookup as I walk through the array.
Then I remember the maximum of the length values while iterating.

use v5.36;

sub contiguous_array( @binary ) {
    my $max_length = 0;

    my $sum = 0;
    # The sum value of zero appears *before* the first number.
    my %first_appearance = ( 0 => -1 );

    for my $index ( keys @binary ) {
        # Add -1 or +1 to the running sum.
        $sum += $binary[$index] == 0 ? -1 : +1;
        $first_appearance{$sum} //= $index;
        my $length = $index - $first_appearance{$sum};
        $max_length = $length
            if $length > $max_length;
    }
    return $max_length;
}

Glad to have found a solution that needs only one loop over the array,
without repeated counting of subarrays.
$O(n)$ rules!

Task 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 a sequence of integers from 1 to n of length n containing each number exactly once.
A permutation is called semi-ordered if the first number is 1 and the last number equals n.
You are ONLY allowed to pick adjacent elements and swap them.

Example 1

Input: @ints = (2, 1, 4, 3)
Output: 2
Swap 2 <=> 1 => (1, 2, 4, 3)
Swap 4 <=> 3 => (1, 2, 3, 4)

 
Example 2

Input: @ints = (2, 4, 1, 3)
Output: 3
Swap 4 <=> 1 => (2, 1, 4, 3)
Swap 2 <=> 1 => (1, 2, 4, 3)
Swap 4 <=> 3 => (1, 2, 3, 4)

 
Example 3

Input: @ints = (1, 3, 2, 4, 5)
Output: 0
Already a semi-ordered permutation.

There's no need for actually doing all the swaps to move the numbers!
It's enough to find the positions of '1' and 'n' (the largest number).
I chose not to use two calls to find (from List::Util) for that, but to keep it simple, in a single loop. I exit the loop early once both positions are known.

The number of moves needed than can be computed with a simple formula, adding.
the distance of the '1' from the left end of the array (which is its position, actually) and the distance of the 'n' from its right end.

If we find the '1' to the right of the 'n', that saves us one swap, because as they pass each other, that single swap will move them both in their respective desired direction.

Actually, the main exercise here is finding nice variable names...

use v5.36;

sub semi_ordered_permutation( @ints ) {
    my $n = scalar @ints;
    my ( $one_index, $n_index );
    for my $index ( keys @ints ) {
        $one_index = $index if $ints[$index] == 1;
        $n_index   = $index if $ints[$index] == $n;
        last if defined $one_index && defined $n_index;
    }
    my $moves_for_one = $one_index;
    my $moves_for_n   = ( $n - 1 ) - $n_index;
    return $moves_for_one + $moves_for_n
        - ( $one_index > $n_index ? 1 : 0 );
}

Here, again, it's looping over the array only once, even exiting the loop early.
So $O(n)$ again!

Thank you for the challenge!

Find the complete source code for both tasks, including tests, on GitHub.