Robbie Hatley's Solutions To The Weekly Challenge #216

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-05-07 through 2023-05-13) is weekly challenge #216.

Task 1 is as follows:

"You are given a list of words and a random registration number. Write a script to find all the words in the given list that has every letter in the given registration number."

This is pretty simple. Just check each word to see if it contains all of the letters from the registration string, then output the subset of the original word set which contains those members which contain all registration letters. I use a ranged for loop to push "registered" words onto a "@regd_wrds" array:

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

Task 2 is as follows:

"You are given a list of word stickers and a target word. Write a script to find out how many word stickers is needed to make up the given target word."

This one is tricky. I can't see an iterative way of doing it, and recursive approaches are usually nightmares. Let me see if I can find a CPAN for this.... Ah, there is "Math::Combinatorics". Ok, I'll use that, then get all 1,2,3...n combinations of "stickers" and stop when I'm either able to make the word (in which case print n), or I've run out of combinations (in which case print 0).

COMPLICATION #1: The examples appear to indicate that any letter in any "sticker" may only be used ONCE, much like making a sign using letter decals. My first attempt did not get this right, so I had to change the code to make sticker letters "non-reusable".

COMPLICATION #2: Example 4 appears to indicate that we have large (unlimited?) numbers of each kind of sticker at our disposal. That's going to be very tricky. Should I write code to determine whether it's even POSSIBLE to make a work from a given set of skickers, regardless of having multiple copies of each kind available? That could get quite complicated. But a simple (if not efficient) approach is, I'll limit sticker copies to the number of letters in the word being made, because we know that if a word has n letters, and we can't make it even though we have n copies of each sticker in our set, then we can't make that word using those stickers.

COMPLICATION #3: Oops, while the approach I lay out in #2 above technically works, for a word such as "accomodation", with a sticker-type set NOT containing all those letters, it can take HOURS for the program to realized that it simply can't be done and print "0". So I had to also create a "cant_make" sub to check for that. Now the run time dropped from "several hours" down to about 810µs.

COMPLICATION #4: The approach in #3 above works well enough for words requiring 1, 2, or 3 "multiples" of the original set of sticker types, but for more multiples, it can take several seconds. This could be dramatically improved by having sub "can_make" report back info on which letters we "ran out of", then have number_of_stickers_needed only duplicate the NECESSARY sticker types instead of duplicating ALL sticker types. But I'm not going to Level 4 with this program; I spent an entire Saturday afternoon on it as it is. Level 3, while not "optimum", is "good enough" for this exercise.

Robbie Hatley's Perl Solution to The Weekly Challenge 216-2

That's it for 216; see you on 217!