The weekly challenge 318 - Task 2: Reverse Equals

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-318/#TASK2
 3 #
 4 # Task 2: Reverse Equals
 5 # ======================
 6 #
 7 # You are given two arrays of integers, each containing the same elements as
 8 # the other.
 9 #
10 # Write a script to return true if one array can be made to equal the other by
11 # reversing exactly one contiguous subarray.
12 #
13 ## Example 1
14 ##
15 ## Input: @source = (3, 2, 1, 4)
16 ##        @target = (1, 2, 3, 4)
17 ## Output: true
18 ##
19 ## Reverse elements: 0-2
20 #
21 #
22 ## Example 2
23 ##
24 ## Input: @source = (1, 3, 4)
25 ##        @target = (4, 1, 3)
26 ## Output: false
27 #
28 #
29 ## Example 3
30 ##
31 ## Input: @source = (2)
32 ##        @target = (2)
33 ## Output: true
34 #
35 ############################################################
36 ##
37 ## discussion
38 ##
39 ############################################################
40 #
41 # We let two variables walk the indices in the array, starting at
42 # 0 and going up to the index of the last element. Then we cut the
43 # source array into 3 parts:
44 # - a slice from the start to $i - 1
45 # - a slice from $i to $j
46 # - a slice from $j + 1 until the index of the last element
47 # Then we put all of these parts together, reversing the second of these
48 # subarrays. If the temporary array is the same as @target we found
49 # a solution, so we can return true. If in the end, we didn't find a
50 # solution, we need to return false.
51 #
52 
53 use v5.36;
54 
55 reverse_equals( [3, 2, 1, 4], [1, 2, 3, 4] );
56 reverse_equals( [1, 3, 4], [4, 1, 3] );
57 reverse_equals( [2], [2] );
58 
59 sub reverse_equals( $source, $target ) {
60     my @source = @$source;
61     my @target = @$target;
62     say "Input: (" . join(", ", @source) . "), (" . join(", ", @target) . ")";
63     return say "Output: false" unless scalar(@source) == scalar(@target);
64     foreach my $i (0..$#source) {
65         foreach my $j ($i..$#source) {
66             my @tmp = @source[0..$i-1];
67             push @tmp, reverse @source[$i..$j];
68             push @tmp,  @source[$j+1..$#source];
69             my $matching = 1;
70             foreach my $k (0..$#tmp) {
71                 if($tmp[$k] != $target[$k]) {
72                     $matching = 0;
73                 }
74             }
75             return say "Output: true" if $matching;
76         }
77     }
78     say "Output: false";
79 }