Task — Scramble string

You are given two strings A and B of the same length. Write a script to return true if string B is a scramble of string A; otherwise return false. String B is a scramble of string A if A can be transformed into B by a single (recursive) scramble operation.

A scramble operation is:

• If the string consists of only one character, return the string.
• Divide the string X into two non-empty parts.
• Optionally, exchange the order of those parts.
• Optionally, scramble each of those parts.
• Concatenate the scrambled parts to return a single string.

Examples

Example 1
Input: $str1 = 'abc', $str2 = 'acb'
Output: true
'abc'
split: ['a', 'bc']
split: ['a', ['b', 'c']]
swap: ['a', ['c', 'b']]
concatenate: 'acb'

Example 2
Input: $str1 = 'abcd', $str2 = 'cdba'
Output: true
'abcd'
split: ['ab', 'cd']
swap: ['cd', 'ab']
split: ['cd', ['a', 'b']]
swap: ['cd', ['b', 'a']]
concatenate: 'cdba'

Example 3
Input: $str1 = 'hello', $str2 = 'hiiii'
Output: false
A fundamental rule of scrambled strings is that they must 
   be anagrams.

Example 4
Input: $str1 = 'ateer', $str2 = 'eater'
Output: true
'ateer'
split: ['ate', 'er']
split: [['at', 'e'], 'er']
swap: [['e', 'at'], 'er']
concatenate: 'eater'

Example 5
Input: $str1 = 'abcd', $str2 = 'bdac'
Output: false

Analysis

This is an excellent challenge in that the description makes it sound harder than it really is.

Firstly let's discard some strings that have obvious answers:

• strings of length 0 (false) or 1 (true)
• strings where A and B are not anagrams of each other (which also implies their being the same length as each other).

So the rules say we first have to divide A into 2 parts, and there are length($A) - 1 ways to do that.

We can optionally swap the two parts, so that doubles the number of possible outcomes at this point to 2 * length($A) - 2.

So let's now look at strings A and B together:

string A:  xxxxx|yyy
string B:  zzzzz|www

We are now allowed to scramble either part of string A, but no amount of scrambling will move a letter from one side of the split point to the other. So let's ignore that!

So the challenge answer - true or false, boils down to 'is string xxxxx an anagram of string zzzzz?' If the answer is 'yes', we already know that the whole of string A and of string B are anagrams of each other, so it follows that yyy must be an anagram of www.

How do we determine that two string are anagrams? If they were very long strings - say more than 1000 characters - I'd do it character by character, but for shorter ones, the easy way is simply to sort each into alphabetical order and check that they are identical.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2026-04-20
use utf8;     # Week 370 - task 2 - Scramble string
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

scramble_string('abc', 'acb');
scramble_string('abcd', 'cdba');
scramble_string('ateer', 'eater');
scramble_string('abcd', 'bdac');
scramble_string('csaerlmb', 'scramble');
scramble_string('aiontctunup', 'punctuation');
scramble_string('itsappointmedn', 'disappointment');

sub scramble_string {
    
    my (@string, $length, $split, @part0, @chars0, @chars1, $x, $j,
        $iter0, $iter1, @part1);
    
    # initialise and check validity
    @string = @_;
    say qq[\nInput:  \$string1 = '$string[0]'];
    say qq[        \$string2 = '$string[1]'];
    $length = length($string[0]);
    
    # validity check
    if ($length != length($string[1]) or $length == 0) {
        say qq[Output: false - strings must be of equal non-zero length];
        return;
    } elsif (sort_string($string[0]) ne sort_string($string[1])) {
        say qq[Output: false - strings must contain same characters];
        return;     
    } elsif ($length == 1) {
        say qq[Output: true ('$string[0]')];
        return;
    }
    
    # loop over split points
    for $split (0 .. $length - 2) {
        $part0[0] = substr($string[0], 0, $split + 1);
        $part0[1] = substr($string[0], $split + 1);
        
        # exchange or don't exchange parts
        for (0 .. 1) {
            if ($_) {
                $x = $part0[0];
                $part0[0] = $part0[1];
                $part0[1] = $x;
            }

            # now split $string[1] like $string[0]
            $part1[0] = substr($string[1], 0, length($part0[0]));
            $part1[1] = substr($string[1], length($part0[0]));
            
            # compare the left parts 
            if (sort_string($part0[0]) eq sort_string($part1[0])) {
                say qq[Output: true ('$part1[0]' . '$part1[1]')];
                return;
            }
        }
    }
    say qq[Output: false];
}

sub sort_string {
    return join('', sort {$a cmp $b} split('', $_[0]));
}

32 lines of code

Output

Input:  $string1 = 'abc'
        $string2 = 'acb'
Output: true ('a' . 'cb')

Input:  $string1 = 'abcd'
        $string2 = 'cdba'
Output: true ('cdb' . 'a')

Input:  $string1 = 'ateer'
        $string2 = 'eater'
Output: true ('eat' . 'er')

Input:  $string1 = 'abcd'
        $string2 = 'bdac'
Output: false

Input:  $string1 = 'csaerlmb'
        $string2 = 'scramble'
Output: true ('sc' . 'ramble')

Input:  $string1 = 'aiontctunup'
        $string2 = 'punctuation'
Output: true ('punctu' . 'ation')