Robbie Hatley's Solutions To The Weekly Challenge #221

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle, usually with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

This week (2023-06-11 through 2023-06-17) is weekly challenge #221.

Task 1 is as follows:

"You are given a list of strings "@words" and a string "$chars". A string is "good" if it contains only characters from "$chars", with each character used once-only per string. Write a script to return the sum of lengths of all elements of "@words" which are "good"."

Example 1:
Input: @strings = ("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: @strings = ("hello", "world", "challenge"); $chars = "welldonehopper";
Output: 10
(The strings that can be formed are "hello" and "world",
so the answer is 5 + 5 = 10.)

Well, actually, the problem description, as originally stated on the Weekly Challenge web site, was this:

"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."

But that's problematic, because it contains these two ambiguities:

1. Does "only used once" apply to: (A) each good string individually? (B) all good strings taken together?
2. Does "strings in words" mean: (1) elements? (2) contiguous substrings? (3) combinations? (4) permutations?

That leaves 8 possible interpretations of this problem (A1, A2, A3, A4, B1, B2, B3, B4).

Fortunately, Example 1 rules out B1, B2, B3, B4, because "cat" and "hat" can both be formed even though $chars only contains one "t", so the "can be used only once" must apply only to one string at a time. And Example 2 rules out A2, A3, A4 because the word "hell" is disallowed, so "strings in words" must mean "elements of the array @words", rather than substrings, combinations, or permutations. Example 2 also rules out B1, B2, B3, B4 because "hello" and "world" collectively contain 3 copies of "l", whereas $chars only contains 2. This dramatically simplifies the solution, as one needs only consider each element of @words and ask "is it good?".

Case note: Since the problem says "characters", not "letters", I'm assuming that it's case sensitive, as while "t" and "T" are the same letter, they're not the same character. So, "ran" can be made from "Charles R. Tanner", but not "tan", as "T" is not the same "character" as "t".

My solution approach was to determine "goodness" based on whether an element of @words can be "formed" by pasting together letters spliced from a fresh copy of $chars by using substr(), then just sum the lengths of all "good" elements, like so:

Robbie Hatley's Solution to The Weekly Challenge 221-1

Task 2 is as follows:

"You are given an array of integers, @ints. Write a script to find the length of the longest Arithmetic Subsequence in the given array. A subsequence is an array that can be derived from another array by deleting some or none elements without changing the order of the remaining elements. A subsquence is arithmetic if ints[i + 1] - ints[i] are all the same value (for 0 <= i < ints.length - 1)."

I solved this by using slices with indexes consisting of all combinations, of all lengths, of the set of all indices [0..$#ints]. Math::Combinatorics came to my aid once again. I start with the entire array and keep decrementing the size until I get to a subsequence which is arithmetic. And ALL sequences of integers always WILL contain an arithmetic subsquence, becuase all sequences of integers which are length 2, 1, or 0 are automatically arithmetic. So my solution was as follows:

Robbie Hatley's Solution to The Weekly Challenge 221-2

That's it for 221; see you on 222!