The weekly challenge 398 - Task 2: String Difference

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-398/#TASK2
  3 #
  4 # Task 2: String Difference
  5 # =========================
  6 #
  7 # You are given an array of equal length strings.
  8 #
  9 # Write a script to find the difference integer array of each word in the given
 10 # array. There will be one word with a different array; return that word.
 11 #
 12 ###   Each words[i] can be converted into a difference integer array
 13 ###   difference[i] of length n - 1 where difference[i][j] = words[i][j+1] -
 14 ###   words[i][j]
 15 #
 16 ## Example 1
 17 ##
 18 ## Input: @words = ("ab", "bc", "cd", "zy")
 19 ## Output: "zy"
 20 ##
 21 ## "ab" => [1 - 0] = [1]
 22 ## "bc" => [2 - 1] = [1]
 23 ## "cd" => [3 - 2] = [1]
 24 ## "zy" => [24 - 25] = [-1]
 25 #
 26 ## Example 2
 27 ##
 28 ## Input: @words = ("cba", "fed", "azy")
 29 ## Output: "azy"
 30 ##
 31 ## "cba" => [1 - 2, 0 - 1] = [-1, -1]
 32 ## "fed" => [4 - 5, 3 - 4] = [-1, -1]
 33 ## "azy" => [25 - 0, 24 - 25] = [25, -1]
 34 #
 35 ## Example 3
 36 ##
 37 ## Input: @words = ("pop", "ada", "beb", "cfc")
 38 ## Output: "pop"
 39 ##
 40 ## "pop" => [14 - 15, 15 - 14] = [-1, 1]
 41 ## "ada" => [3 - 0, 0 - 3] = [3, -3]
 42 ## "beb" => [4 - 1, 1 - 4] = [3, -3]
 43 ## "cfc" => [5 - 2, 2 - 5] = [3, -3]
 44 #
 45 ## Example 4
 46 ##
 47 ## Input: @words = ("aaaa", "zzzz", "mmmm", "aaba")
 48 ## Output: "aaba"
 49 ##
 50 ## "aaaa" => [0 - 0, 0 - 0, 0 - 0] = [0, 0, 0]
 51 ## "zzzz" => [25 - 25, 25 - 25, 25 - 25] = [0, 0, 0]
 52 ## "mmmm" => [12 - 12, 12 - 12, 12 - 12] = [0, 0, 0]
 53 ## "aaba" => [0 - 0, 1 - 0, 0 - 1] = [0, 1, -1]
 54 #
 55 ## Example 5
 56 ##
 57 ## Input: @words = ("aceg", "bdfh", "cegi", "azbz")
 58 ## Output: "azbz"
 59 ##
 60 ## "aceg" => [2 - 0, 4 - 2, 6 - 4] = [2, 2, 2]
 61 ## "bdfh" => [3 - 1, 5 - 3, 7 - 5] = [2, 2, 2]
 62 ## "cegi" => [4 - 2, 6 - 4, 8 - 6] = [2, 2, 2]
 63 ## "azbz" => [25 - 0, 1 - 25, 25 - 1] = [25, -24, 24]
 64 #
 65 ############################################################
 66 ##
 67 ## discussion
 68 ##
 69 ############################################################
 70 #
 71 # First, we create all the difference integer arrays.
 72 # Then, we compare the first two of them. If they are equal,
 73 # we find the odd out out later in the array. If they are not
 74 # equal, we compare the second one with the third one. If those
 75 # are the same, then the first one is the odd one out, otherwise
 76 # the second one is the odd one out.
 77 
 78 use v5.36;
 79 
 80 sub string_difference(@words) {
 81     say "Input: (" . join(", ", map { "\"$_\""} @words) . ")";
 82     my $diff = {};
 83     foreach my $word (@words) {
 84         my @chars = split //, $word;
 85         my $values = [];
 86         foreach my $index (0..$#chars-1) {
 87             push @$values, (ord($chars[$index+1]) - ord($chars[$index]));
 88         }
 89         $diff->{$word} = $values;
 90     }
 91     if(array_equal($diff->{$words[0]}, $diff->{$words[1]})) {
 92         # find the odd one out later in @words
 93         foreach my $i (2..$#words) {
 94             return say "Output: $words[$i]"
 95                 unless array_equal($diff->{$words[0]}, $diff->{$words[$i]});
 96         }
 97     } else {
 98         # if $words[1] eq $words[2], then $words[0] is the odd one out,
 99         # otherwise $words[1] is the odd one out
100         if(array_equal($diff->{$words[1]}, $diff->{$words[2]})) {
101             return say "Output: $words[0]";
102         }
103         return say "Output: $words[1]";
104     }
105 }
106 
107 sub array_equal($arr1, $arr2) {
108     my @arr1 = @$arr1;
109     my @arr2 = @$arr2;
110     return 0 if scalar(@arr1) != scalar(@arr2);
111     foreach my $i (0..$#arr1) {
112         return 0 if $arr1[$i] != $arr2[$i];
113     }
114     return 1;
115 }
116 
117 
118 string_difference("ab", "bc", "cd", "zy");
119 string_difference("cba", "fed", "azy");
120 string_difference("pop", "ada", "beb", "cfc");
121 string_difference("aaaa", "zzzz", "mmmm", "aaba");
122 string_difference("aceg", "bdfh", "cegi", "azbz");