24 April 2026

Challenge 370

Scrambled Bans

Task 1: Popular Word
Task 2: Scramble String

Task 1: Popular Word

Submitted by: Mohammad Sajid Anwar

You are given a string paragraph and an array of the banned words.

Write a script to return the most popular word that is not banned. It is guaranteed there is at least one word that is not banned and the answer is unique. The words in paragraph are case-insensitive and the answer should be in lowercase. The words can not contain punctuation symbols.

Example 1

Input: $paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
       @banned = ("hit")
Output: "ball"

After removing punctuation and converting to lowercase, the word "hit" appears 3 times, and "ball" appears 2 times.
Since "hit" is on the banned list, we ignore it.

Example 2

Input: $paragraph = "Apple? apple! Apple, pear, orange, pear, apple, orange."
       @banned = ("apple", "pear")
Output: "orange"

"apple"  appears 4 times.
"pear"   appears 2 times.
"orange" appears 2 times.

"apple" and "pear" are both banned.
Even though "orange" has the same frequency as "pear", it is the only non-banned word with the highest frequency.

Example 3

Input: $paragraph = "A. a, a! A. B. b. b."
       @banned = ("b")
Output: "a"

"a" appears 4 times.
"b" appears 3 times.

The input has mixed casing and heavy punctuation.
The normalised, "a" is the clear winner, since "b" is banned, "a" is the only choice.

Example 4

Input: $paragraph = "Ball.ball,ball:apple!apple.banana"
       @banned = ("ball")
Output: "apple"

Here the punctuation acts as a delimiter.
"ball"   appears 3 times.
"apple"  appears 2 times.
"banana" appears 1 time.

Example 5

Input: $paragraph = "The dog chased the cat, but the dog was faster than the cat."
       @banned = ("the", "dog")
Output: "cat"

"the" appears 4 times.
"dog" appears 2 times.
"cat" appears 2 times.

"chased", "but", "was", "faster", "than" appear 1 time each.
"the" is the most frequent but is banned.
"dog" is the next most frequent but is also banned.
The next most frequent non-banned word is "cat".

Solution

The requested result may be found by chaining some string and list operations:

convert the paragraph to lower case
extract (alphabetic) words
drop banned words
count the number of appearances for each unique word
find the maximum count
return the corresponding word

Perl

One-to-one implementation of the above when reading from bottom to top.

use strict;
use warnings;
use experimental 'signatures';
use List::Util 'pairs';
use List::MoreUtils 'frequency';
use List::UtilsBy 'max_by';

sub popular_word ($str, @banned) {
    my $banned = join '|', map quotemeta, @banned;

    (max_by {$_->[1]}
        pairs
        frequency
        grep !/^(?:$banned)$/,
        lc($str) =~ /[a-z]+/g
    )->[0];
}

See the full solution to task 1.

J

A one-to-one implementation again - when reading right to left.

require 'regex'

notIn =. ] #~ [: -. e.~
cntUniq =. |:@((>@[ ; #@])/..~)
maxInd =. 1 i.~ ] = >./
popularWord =: [ ([: ([ {::~ maxInd@:>@])/ [: cntUniq notIn) f. '[a-z]+' rxall tolower@]

echo (<'hit') popularWord 'Bob hit a ball, the hit BALL flew far after it was hit.'
echo ('apple';'pear') popularWord 'Apple? apple! Apple, pear, orange, pear, apple, orange.'

See the full solution.

Task 2: Scramble String

Submitted by: Roger Bell_West

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.

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

Solution

Maybe there is a simpler way to solve this task, but the only approach I came up with was a recursive brute force check.

split $str1 in two non-empty parts
split $str2 in the same shape
recursively check if the first parts of both strings are scrambled and the second parts as well
flip the parts of $str1
split $str2 in the same shape
check the parts again
the recursion stops when the strings cannot be split (or if they are equal)

Perl

Stop recursion on single elements.
create four index lists:
1. the first k elements
2. all but the first k elements
3. all but the last k elements
4. the last k elements
loop over all valid values for k
pick elements corresponding to list 1. from A and B and recursively check if these are scrambled and
pick elements corresponding to list 2. from A and B and recursively check if these are scrambled
return “success” if these checks succeeded or otherwise:
pick elements corresponding to list 1. from A and list 4. from B and recursively check if these are scrambled and
pick elements corresponding to list 2. from A and and list 3. from B and recursively check if these are scrambled
return “success” if these checks succeeded or continue with the next k.

use strict;
use warnings;

sub scrambled {
    my @x = @_;
    $x[0]->@* == 1 && $x[0][0] eq $x[1][0] && return 1;
    my @ix;
    my $args = sub ($q) {
        map [$x[$_]->@[$ix[$q->[$_]]->@*]], 0, 1
    };
    my $last = $x[0]->$#*;
    for my $i (0 .. $last - 1) {
        @ix = map +([0 .. $_], [$_ + 1 .. $last]), $i, $last - $i - 1;
        p: for my $p ([[0, 0], [1, 1]], [[0, 3], [1, 2]]) {
            __SUB__->($args->($_)) || next p for @$p;
            return 1;
        }
    }
    _:
}

See the full solution to task 2.

J

This task was certainly the heaviest I tried to implement in J since I started learning this language in last November.

At first I was unsure if I could solve this task at all in J and now I’m surprised it even lead to a tacit verb.

Some J idioms I learned and that I used here:

The phrase x u1`u2@.v y, where x v y evaluates to a boolean result, produces a final result of x u1 y for zero and x u2 y for one, i.e. it acts as if-then-else.`
The phrase u^:v y, where v y evaluates to a boolean result, produces a final result of u y for one and y for zero. In Perl this could be written as v($y) ? u($y) : $y.
The phrase x u^:v^:_. y evaluates x u y repeatedly with y replaced by the previous result as long as the boolean x v y evaluates to one, i.e. it acts as a do-while loop.
$: specifies the verb that is currently being defined and allows anonymous recursion calls. By inserting and expanding such a verb in the definition of another verb by using f., the recursion point extends to the outer verb. This has some similarities to Perl’s __SUB__.

Assembling from smaller parts:

cut is an adverb and m cut is a verb that cuts y in two boxed parts, where the first part has a size of x. For m = 0 this will be y1;y2 and for m = 1 it is y2;y1

cut =. ((-^:)@[ ({. ; }.) ])"0 _

sizes is a verb that generates a list of all valid cut sizes for `y’.

sizes =. >:@i.@<:@#

cuts is a verb that generates a list of all valid cuts for y

cuts =. sizes@] (0 cut , 1 cut) ]

shape is a verb that cuts y into two parts with the same sizes as x

shape =. ] </.~ [: #&(0,1) ;@:($&.>)@[

recurpart is an adverb and m recurpart is a verb that unboxes the parts with index m from x and y and then performs a recursive call on these.

recurpart =. $:&(&{::)

check is a verb that checks if x1 / y1 and x2 / y2 are scrambled (short circuit on failure)

check =. (1 recurpart)^:(a: -: (0 recurpart))

nextIfNotDone is a verb that drops the first entity from x if y is not boxed empty or otherwise passes this value.

nextIfNotDone =. (}.@[)^:(-.@(a:&-:)@])

first is a verb that picks the first entity from y.

first =. {.@]

whileToDo is an adverb and u whileToDo is a verb that repeatedly performs x u y as long as y has items and is not boxed empty. The result from each x u y invocation is taken as y for the next cycle.

whileToDo =. (^:(*@#@] *. -.@(a:&-:@])))^:_.

ifEq is a conjunction and u`v ifEq performs x v y if x and y are equal or x u y otherwise.

ifEq =. @.(-:)

done is a verb that returns boxed empty signaling “done”.

done =. a:"_

The resulting tacit verb scrambled may be constructed from these parts:

boxed empty a: is used to signal success
signal “done” if x and y are equal
otherwise:
create all valid cuts for y
loop while there are cuts left and no scrambled cut has been found yet
- bring x into the same shape x1;x2 as the current cut
- check if x1 / y1 and x2 / y2 are scrambled
- signal “done” on successful check or
- drop the first item from the cut list
returns boxed empty on success and empty otherwise
counting the result’s items produces zero/one as boolean result

scrambled =: ([ (] nextIfNotDone f. [ (shape~ f. check f. ]) first f.) whileToDo cuts f.)`(done f.) ifEq

# 'abcd' scrambled 'cdab'
# 'abcd' scrambled 'bdac'

At least for check it is required to replace the verb name with its value using f.. This operation sets the recursion point $: within check to the verb scrambled. For other verbs this substitution may enable optimizations that would be suppressed otherwise. However, by replacing the named verbs with their values, the resolved verb becomes less comprehensible:

scrambled
([ (] }.@[^:(-.@(a:&-:)@]) [ ((] </.~ [: #&0 1 ;@:($&.>)@[)~ $:&(1&({::))^:(a: -: $:&(0&({::))) ]) {.@])^:(*@#@] *. -.@(a:&-:@]))^:_. (>:@i.@<:@# ((]@[ ({. ; }.) ])"0 _ , (-@[ ({. ; }.) ])"0 _) ])@])`(a:"_)@.-:

See the full solution.

The Bear's Den

Enter at your own risk

Scrambled Bans

Task 1: Popular Word

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Perl

J

Task 2: Scramble String

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Perl

J