Letter frequency
Tags: perl, python, theweeklychallenge
Published: 2023-05-14 07:52:36

## Weekly Challenge 216

[Challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-216/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-216/sgreen)

## 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

```bash
$ ./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](https://docs.python.org/3/library/itertools.html#itertools.product) function, while Perl's Algorithm::Combinatorics has a [variations_with_repetition](https://metacpan.org/pod/Algorithm::Combinatorics#variations_with_repetition%28%5C%40data%2C-%24k%29) 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

```bash
$ ./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

```