Letter frequency

Weekly Challenge 216

Challenge, My solutions

Task 1: Registration Number

Task

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.

My solution

Both of this week's task involve frequency of letters. I have a function get_frequency which takes a word, and returns a dict (hash in Perl) of the frequency of each letter. For example with an input of apple, it would return {'a': 1, 'p': 2, 'l': 1, 'e': 1}.

The first thing I do is remove the last item from the input (being the licence plate) and store this as plate. The frequency of each letter is stored as plate_freq. I also defined an empty list (array in Perl) called solution, which will store any words that match the criteria.

I loop through each word, storing the frequency in the dict word_freq. I then have an inner loop that checks that the frequency of letters in the plate are contained in word_freq. If that passes, then I add to the solution list.

Finally, I print the items in the solution list.

Examples

$ ./ch-1.py abc abcd bcd 'AB1 2CD'
abcd

$ ./ch-1.py job james bjorg '007 JB'
job, bjorg

$ ./ch-1.py crack road rac 'C7 RA2'
crack, rac

Task 2: Word Stickers

Task

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.

My solution

This task is very similar to the previous one except I don't know how many sticker of which sticker we need to start with. The solution I have come up might not be the most efficient, but it does work.

I start this task by removing the last item from the input (being the target word) and store this as target_word. The frequency of each letter is stored as target_freq.

The next thing is I check that every letter in the target_freq dict is in at least one of the other words. If it is, no solution is possible and I print '0' and return.

I then find the letter(s) that appear the most. This is done by find the highest value from the target_freq dict, and store it as highest. This means in the worst case scenario we would need to use that many of each sticker to find a solution.

The next step I take is to loop through all combinations of zero to highest for each word. Thankfully Python's itertools has a product function, while Perl's Algorithm::Combinatorics has a variations_with_repetition function that does this easily.

For each iteration, I first check the the sum of the word frequency isn't equal to or higher than the current min_stickers value. No point spending CPU cycles on possible solutions that aren't better than our current one.

Then the iteration calculates the frequency of all the letters in the stickers we are going to use. It checks that the frequency of the letters in target_freq occurs that many times in the currently selected stickers. If it is, I set min_stickers to the number of stickers used.

Finally I display the number of stickers used.

Examples

$ ./ch-2.py perl raku python peon
2

$ ./ch-2.py love hate angry goat
3

$ ./ch-2.py come nation delta accommodation
4

$ ./ch-2.py come country delta accommodation
0