Weekly Challenge: Popular Scrambling

Weekly Challenge 370

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Popular Word

Task

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.

My solution

These are the steps I took to solve this challenge.

1. Convert the banned words list to lower case, and store this as banned_list.
2. Create a list called words that has all the words that aren't in the banned_list list or empty.
3. Create a Counter of the frequency of each word. This is stored in a dict called freq.
4. Create a list called sorted_freq that stores the keys of the above dict by their frequency.
5. Return the last item in the sorted_freq list. This is the word that appears the most that isn't banned.

def popular_word(paragraph: str, banned: list[str]) -> str:
    banned_list = list(map(lambda x: x.lower(), banned))
    words = [
        word for word in re.split('[^a-z]+', paragraph.lower())
        if word != '' and word not in banned_list
    ]
    freq = Counter(words)
    sorted_freq = sorted(freq.keys(), key=lambda x: freq[x])
    return sorted_freq[-1]

The Perl solution is very similar.

use List::Util qw(none max);
use List::MoreUtils 'first_value';

sub main (@args) {
    my ( $paragraph, @banned_words ) = @args;

    $paragraph    = lc $paragraph;
    @banned_words = map { lc } @banned_words;

    my %freq = ();
    for my $word ( split /[^a-z]+/, $paragraph ) {
        if ( $word ne '' and none { $_ eq $word } @banned_words ) {
            $freq{$word}++;
        }
    }

    my $max_freq = max( values %freq );
    my $word     = first_value { $freq{$_} == $max_freq } keys %freq;
    say $word;
}

Examples

$ ./ch-1.py "Bob hit a ball, the hit BALL flew far after it was hit." hit
"ball"

$ ./ch-1.py "Apple? apple! Apple, pear, orange, pear, apple, orange." apple pear
"orange"

$ ./ch-1.py "A. a, a! A. B. b. b." b
"a"

$ ./ch-1.py 'Ball.ball,ball:apple!apple.banana' ball
"apple"

$ ./ch-1.py "The dog chased the cat, but the dog was faster than the cat." the dog
"cat"

Task 2: Scramble String

Task

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.

My solution

This is another excellent challenge from Roger. For both the Python and Perl solutions, I have a function called same_letters. It takes two strings, and returns True if they have the same frequency of letters (not necessarily in the same order). For the Python solution, I use the Counter function to get the frequency and compare if the resulting dicts are the same.

from collections import Counter

def same_letters(str1: str, str2: str) -> bool:
    return Counter(str1) == Counter(str2)

For the Perl solution, I add 1 for each letter from the first string to the %freq hash, and subtract 1 for each letter from the second string. If there are any items in the hash that aren't zero, it means they are not the same.

use List::Util 'any';

sub same_letters ( $str1, $str2 ) {
    my %freq = ();
    for my $letter ( split //, $str1 ) {
        $freq{$letter}++;
    }
    for my $letter ( split //, $str2 ) {
        $freq{$letter}--;
    }
    if ( any { $_ } values(%freq) ) {
        return undef;
    }
    return 1;
}

For the main function, I have a recursive function which also takes two strings. I start by checking if both string have the same frequency of letters. If they don't, I return False. No amount of splitting or swapping is going to produce a solution!

def scramble_string(str1: str, str2: str) -> bool:
    if not same_letters(str1, str2):
        # If they don't, there is no possible solution
        return False

If the length of the strings is one or two characters, the strings are the same or can be swapped to make them the same, so I return True.

This could be more efficient by also comparing strings of three characters. From abc, it is possible to make all six permutations of the scrambled the string by splitting and/or swapping.

    if len(str1) < 3:
        return True

The next part of the function is to split the string at all possible positions (from 1 to one less than the length of string). I call this variable split_pos.

For each position, I call the scramble_string function again on the left side and right side of the split. If a match is found, I return True.

    for split_pos in range(1, len(str1)):
        if (scramble_string(str1[:split_pos], str2[:split_pos]) and
                scramble_string(str1[split_pos:], str2[split_pos:])):
            return True

It's also possible to swap the parts. This uses negative indexing which counts from the end of the string, not the beginning.

        if (scramble_string(str1[:split_pos], str2[-split_pos:]) and
                scramble_string(str1[split_pos:], str2[:-split_pos])):
            return True

If all that fails, I return False.

    return False

The main function of the Perl solution uses the same logic, and uses the substr function to get the parts of each string.

Examples

$ ./ch-2.py abc acb
true

$ ./ch-2.py abcd cdba
true

$ ./ch-2.py hello hiiii
false

$ ./ch-2.py ateer eater
true

$ ./ch-2.py abcd bdac
false