PWC 318 Task 2 Reverse Equals

Problem Description

You are given two arrays of integers, each containing the same elements as the other. Write a script to return true if one array can be made to equal to the other by reversing exactly one contiguous subarray.

Example 1:
- @source = (3, 2, 1, 4)
- @target = (1, 2, 3, 4)
- Output: true (3,2,1 reverses to 1,2,3)
Example 2:
- @source = (1, 3, 4)
- @target = (4, 1, 3)
- Output: false
Example 3:
- @source = (2)
- @target = (2)
- Output: true

The thinking part

At first glance, it seems like we might have to enumerate all the possible sub-sequences and reverse each one. But after a little more time for the coffee to work its magic, there's a simpler approach.

@source:   = = = = > > > = = = =
@target:   = = = = < < < = = = =

The string has three parts. Somewhere in the middle is a sequence that can be reversed (maybe), and on either side of that are sequences that are equal. With that in mind, let's put on some music and write some Perl.

The fun part

sub revEq ($source, $target)
{
    use List::Util qw/zip/;
    use List::MoreUtils qw/first_index last_index/;

    # Arrays must be the same size
    return false if $source->$#* != $target->$#*;

    # Combine the two arrays into pairs
    my @pair = zip($source, $target);

    # Find the left segment of equal elements
    my $left = first_index { $_->[0] != $_->[1] } @pair;

    # If strings are equal, we can stop
    return true if $left == -1;

    # Find the right segment of equal elements
    my $right = last_index { $_->[0] != $_->[1] } @pair;

    # Extract the middle that could be reversed.
    my @midsrc = $source->@[$left .. $right];
    my @midtrg = $target->@[$left .. $right];

    # Check that one is the reverse of the other
    while ( @midsrc  &&  shift @midsrc == pop @midtrg ) {}
    return @midsrc == 0;
}

Programming notes

There are some sub-problems that we don't need to re-invent. (Previous PWC challenges have already re-invented them anyway). I'm going to use common library routines from List::Util and List::MoreUtils
zip -- I want to compare corresponding elements. I could loop over indexes and start down the road to off-by-one hell, but I'd rather operate on lists as a whole and let the language and its libraries do my array bookkeeping. zip will turn two lists into one list of pairs.
first_index and last_index -- I want the first position on the left and on the right where the two sequences don't match. If the strings are equal, this would return -1.
array slices -- Knowing the bounds of the possibly-reversed sub-sequence, I can extract it with a slice. I know that the range will be valid, because I already returned if there was no unequal element, so at this point in the program, $left must be less than or equal to $right.
reversal check -- The obvious thing to do would be to reverse either @midsrc or @midtrg and then do an array compare. What I'm doing here instead is walking over both of them from opposite ends, destroying them in the process. If @midsrc is reduced to empty, then the strings must be mirror images.

PWC 318 Task 2 Reverse Equals