The weekly challenge 370 - Task 2: Scramble String

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-370/#TASK2
  3 #
  4 # Task 2: Scramble String
  5 # =======================
  6 #
  7 # You are given two strings A and B of the same length.
  8 #
  9 # Write a script to return true if string B is a scramble of string A otherwise
 10 # return false.
 11 #
 12 # String B is a scramble of string A if A can be transformed into B by a single
 13 # (recursive) scramble operation.
 14 #
 15 # A scramble operation is:
 16 #
 17 ## - If the string consists of only one character, return the string.
 18 ## - Divide the string X into two non-empty parts.
 19 ## - Optionally, exchange the order of those parts.
 20 ## - Optionally, scramble each of those parts.
 21 ## - Concatenate the scrambled parts to return a single string.
 22 #
 23 ## Example 1
 24 ##
 25 ## Input: $str1 = "abc", $str2 = "acb"
 26 ## Output: true
 27 ##
 28 ## "abc"
 29 ## split: ["a", "bc"]
 30 ## split: ["a", ["b", "c"]]
 31 ## swap: ["a", ["c", "b"]]
 32 ## concatenate: "acb"
 33 #
 34 ## Example 2
 35 ##
 36 ## Input: $str1 = "abcd", $str2 = "cdba"
 37 ## Output: true
 38 ##
 39 ## "abcd"
 40 ## split: ["ab", "cd"]
 41 ## swap: ["cd", "ab"]
 42 ## split: ["cd", ["a", "b"]]
 43 ## swap: ["cd", ["b", "a"]]
 44 ## concatenate: "cdba"
 45 #
 46 ## Example 3
 47 ##
 48 ## Input: $str1 = "hello", $str2 = "hiiii"
 49 ## Output: false
 50 ##
 51 ## A fundamental rule of scrambled strings is that they must be anagrams.
 52 #
 53 ## Example 4
 54 ##
 55 ## Input: $str1 = "ateer", $str2 = "eater"
 56 ## Output: true
 57 ##
 58 ## "ateer"
 59 ## split: ["ate", "er"]
 60 ## split: [["at", "e"], "er"]
 61 ## swap: [["e", "at"], "er"]
 62 ## concatenate: "eater"
 63 #
 64 ## Example 5
 65 ##
 66 ## Input: $str1 = "abcd", $str2 = "bdac"
 67 ## Output: false
 68 #
 69 ############################################################
 70 ##
 71 ## discussion
 72 ##
 73 ############################################################
 74 #
 75 # We recursively build all possible scrambles of $str. We then check
 76 # each of those for wether it matches $str2 and return true if that's
 77 # the case. In the end, we didn't find any scramble that matches $str2,
 78 # so we return false.
 79 
 80 use v5.36;
 81 
 82 scramble_string("abc", "acb");
 83 scramble_string("abcd", "cdba");
 84 scramble_string("hello", "hiiii");
 85 scramble_string("ateer", "eater");
 86 scramble_string("abcd", "bdac");
 87 
 88 sub scramble_string($str1, $str2) {
 89     say "Input: \"$str1\", \"$str2\"";
 90     my @scrambled = find_scrambles($str1);
 91     foreach my $scr (@scrambled) {
 92         return say "Output: true" if $scr eq $str2;
 93     }
 94     say "Output: false";
 95 }
 96 
 97 sub find_scrambles($str) {
 98     return ($str) if length($str) == 1;
 99     my @result = ();
100     foreach my $i (1..length($str)-1) {
101         my $l = substr($str, 0, $i);
102         my $r = substr($str, $i);
103         my @left = find_scrambles($l);
104         my @right = find_scrambles($r);
105         foreach my $left (@left) {
106             foreach my $right (@right) {
107                 push @result, $left . $right;
108                 push @result, $right . $left;
109             }
110         }
111     }
112     return @result;
113 }