Completing Appearance

Weekly Challenge 265

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. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: 33% Appearance

Task

You are given an array of integers, @ints.

Write a script to find an integer in the given array that appeared 33% or more. If more than one found, return the smallest. If none found then return undef.

My solution

In past challenges if I had to calculate the frequency of a thing (be it a number, letters or strings), I would do this in a for loop. I discovered the Counter function that does this for me.

Once I've used this method to get the frequency of each integer and stored in a value freq, I calculate the value that represents 33% of the number of items in the list and store it as percent_33.

The last step is to loop through the sorted listed of integers and return the value that appears at least percent_33 times. I return None (undef in Perl) if no values match the criterion.

def appearance_33(ints: list) -> int | None:
    freq = Counter(ints)
    percent_33 = 0.33 * len(ints)


    for i in sorted(freq):
        if freq[i] >= percent_33:
            return i

    return None

Examples

$ ./ch-1.py 1 2 3 3 3 3 4 2
3

$ ./ch-1.py 1 1
1

$ ./ch-1.py 1 2 3
1

Task 2: Completing Word

Task

You are given a string, $str containing alphanumeric characters and array of strings (alphabetic characters only), @str.

Write a script to find the shortest completing word. If none found return empty string.

A completing word is a word that contains all the letters in the given string, ignoring space and number. If a letter appeared more than once in the given string then it must appear the same number or more in the word.

My solution

str is a reserved word in Python, so I used s for the given string and str_list for the list. For this challenge, I also use the Counter function in my Python solution.

These are the steps I perform:

1. Calculate the frequency of letters in the given string once converting it to lower case and removing anything that isn't an English letter of the alphabet (i.e. a to z).
2. Sort the str_list list by the length of the string, shortest first.
3. Loop through each item in str_list as a variable word. For each word:
   1. Caluclate the frequency of each letter, after converting it to lower case. This is stored as word_freq.
   2. For each letter in the original string (the freq dict), check that it occurs at least that many times in the word_freq dict. If it doesn't, move to the next word.

def completing_word(s: str, str_list: list) -> str | None:
    freq = Counter(re.sub('[^a-z]', '', s.lower()))
    str_list.sort(key=len)

    for word in str_list:
        word_freq = Counter(word.lower())

        for letter, count in freq.items():
            if word_freq.get(letter, 0) < count:
                break
        else:
            return word

    return None

Examples

$ ./ch-2.pl "aBc 11c" accbbb abc abbc
accbbb

$ ./ch-2.pl "Da2 abc" abcm baacd abaadc
baacd

$ ./ch-2.pl "JB 007" jj bb bjb
bjb