laurent_r

These are some answers to the Week 221, task 1, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on June 18, 2023 at 23:59). This blog post offers some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Good Strings

You are given a list of @words and a string $chars.

A string is good if it can be formed by characters from $chars, each character can be used only once.

Write a script to return the sum of lengths of all good strings in words.

Example 1

Input: @words = ("cat", "bt", "hat", "tree")
       $chars = "atach"
Output: 6` 

The good strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2

Input: @words = ("hello", "world", "challenge")
       $chars = "welldonehopper"
Output: 10

The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Good Strings in Raku

We can store the input characters in a Bag and use the ⊆ subset of or equal operator,infix%E2%8A%86) to figure out whether all letters of a word can be found in the input string. In this context, bags are clever enough to manage duplicates in the input characters and use input characters only once.

sub find-good ($string, @words) {
    my $chars = $string.comb.Bag;
    my $length = 0;
    for @words -> $word {
        $length += $word.chars if $word.comb.Bag ⊆ $chars;
    }
    return $length
}
for (("atach", <cat bt hat tree atac>), 
    ("atach", <cat bt hat tree ataca>),
    ("welldonehopper", <hello world challenge>)) -> @test {
    printf "%-15s - %-22s => ", "@test[0]", "@test[1]";
    say find-good  @test[0], @test[1];
}

This program displays the following output:

$ raku ./good-string.raku
atach           - cat bt hat tree atac   => 10
atach           - cat bt hat tree ataca  => 6
welldonehopper  - hello world challenge  => 10

Good Strings in Perl

Perl doesn't have Bags and set operators, but we can use hashes as histograms to the same effect, with a loop to check whether each letter of an input word can be found in the input character string.

use strict;
use warnings;
use feature 'say';

sub find_good {
    my ($string, @words) = @_;
    # say $string, " - ", "@words"; 
    my $length = 0;
    my %chars;
    $chars{$_}++ for split //, $string;
    WORD: for my $word (@words) {
        my %char_cpy = %chars;
        for my $let (split //, $word) {
            next WORD unless $char_cpy{$let};
            $char_cpy{$let}--;
        }
        $length += length $word;
    }
    return $length
}
for my $test (
    ["atach", [<cat bt hat tree>]], 
    ["atach", [<cat bt hat tree cata>]], 
    ["atach", [<cat bt hat tree ataca>]],
    ["welldonehopper", [<hello world challenge>]]) {
    printf "%-15s - %-22s => ", "@$test[0]", "@{@$test[1]}";
    say find_good  @$test[0], @{@$test[1]};
}

This program displays the following output:

$ perl ./good-string.pl
atach           - cat bt hat tree        => 6
atach           - cat bt hat tree cata   => 10
atach           - cat bt hat tree ataca  => 6
welldonehopper  - hello world challenge  => 10

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on June 25, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.