Task — Reverse equals

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 the other by reversing exactly one contiguous subarray.

Examples

Example 1
Input: @source = (3, 2, 1, 4)
       @target = (1, 2, 3, 4)
Output: true
Reverse elements: 0-2

Example 2
Input: @source = (1, 3, 4)
       @target = (4, 1, 3)
Output: false

Example 3
Input: @source = (2)
       @target = (2)
Output: true

Analysis

What is a subarray? Can it be zero or one element long? Can it comprise the entire array? Example 3 shows that a length of one is allowed, and I have chosen to assume that the entire array is also allowed - for example 1, 2, 3 and 3, 2, 1 yield 'true'.

In general, my algorithm is:

• Return 'false' if the arrays are not the same length, which clearly can't meet the criterion.
• Find the first array index $i where the values in the two arrays differ
• Find the last array index $j where they differ
• Check if the subarray from $i to $j in the first array matches the reversed subarray from $j to $i in the second
• If it does, the output value is 'true', or if not, it is 'false'

That covers most of the cases except the ones where the two arrays are identical, in which case the first step listed above will fail to find a point of difference. But as Example 3 shows that a subarray of length 1 is allowed, clearly 'reversing' any one element of the first array in an identical pair will leave it identical to the second, so in that case I have returned 'true', and arbitrarily chosen element 0 as the one to reverse.

That only leaves the case of both arrays being empty.

This article proposes a definition of subarray which allows a zero length subarray. So in this case I return 'true' because an empty array has an empty subarray, which can be reversed and still be empty.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-04-21
use utf8;     # Week 318 - task 2 - Reverse equals
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

reverse_equals([1, 2, 3, 4, 5], [1, 4, 3, 2, 5]);
reverse_equals([1, 2, 3, 4, 5], [1, 3, 4, 2, 5]);
reverse_equals([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]);
reverse_equals([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]);
reverse_equals([3], [3]);
reverse_equals([], []);
reverse_equals([1, 2, 3, 4, 5], [4, 3, 2, 1]);

sub reverse_equals {
    
    my (@a, @b, $i, $j, $k, $jj, $result);
    
    @a = @{$_[0]};
    @b = @{$_[1]};
    
    # cannot be true if the array are different lengths
    if ($#a == $#b) {
        
        # in case strings are identical
        $result = $#a > -1 ? qq[0 to 0] : 'zero-length subarray';
        
        # find start of potential reversal
        A: for $i (0 .. $#a - 1) {
            next if $a[$i] == $b[$i];
            $result = '';
                
            # find potential end
            B: for ($j = $#b; $j >= $i; $j --) {
                next if $b[$j] == $a[$j];
                
                # check for reversibility
                $jj = $j;
                K: for $k ($i .. $j) {
                    last A if $a[$k] != $b[$jj];
                    last K if -- $jj < $k;
                }
                
                # success!
                $result .= qq[$i to $j];
                last A;         
            }
            last A;
        }               
    } 

    say qq[\nInput:  \@a = (] . join(', ', @a) . qq[),\n        \@b = (] . join(', ', @b) . q[)];
    say qq[Output: ] . ($result ? qq[true - $result] : 'false');
}

Output

Input:  @a = (1, 2, 3, 4, 5),
        @b = (1, 4, 3, 2, 5)
Output: true - 1 to 3

Input:  @a = (1, 2, 3, 4, 5),
        @b = (1, 3, 4, 2, 5)
Output: false

Input:  @a = (1, 2, 3, 4, 5),
        @b = (1, 2, 3, 4, 5)
Output: true - 0 to 0

Input:  @a = (1, 2, 3, 4, 5),
        @b = (5, 4, 3, 2, 1)
Output: true - 0 to 4

Input:  @a = (3),
        @b = (3)
Output: true - 0 to 0

Input:  @a = (),
        @b = ()
Output: true - zero-length subarray

Input:  @a = (1, 2, 3, 4, 5),
        @b = (4, 3, 2, 1)
Output: false