Counting and ranking
Tags: perl, python, theweeklychallenge
Published: 2024-03-17 07:19:08

## Weekly Challenge 260

Each week Mohammad S. Anwar sends out [The Weekly Challenge](https://theweeklychallenge.org/), 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](https://theweeklychallenge.org/blog/perl-weekly-challenge-260/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-260/sgreen)

## Task 1: Unique Occurrences

### Task

You are given an array of integers, `@ints`.

Write a script to return `1` if the number of occurrences of each value in the given array is unique or `0` otherwise.

### My solution

For this task I start by calculating the frequency of each integer, and store this in a dict (hash in Perl) called `freq`.

```python
def uniq_occurrences(ints: list) -> bool:
    freq = defaultdict(int)
    for i in ints:
        freq[i] += 1
```

I then loop through the values of the dict (the frequency). If I have seen this frequency before, we know it is not unique, and can return False. If I haven't seen it, I add it to the `seen` dict in case we see it again.

Once I have looped through all values, I return True to indicate the occurrences are unique.

```python
    seen = {}
    for i in freq.values():
        if i in seen:
            return False
        seen[i] = 1
```

The second part definitely fails under [TMTOWTDI](https://en.wiktionary.org/wiki/TMTOWTDI). One possible alternate solution is `len(freq) == len(set(freq.values())`. While probably quicker, it's not as straight forward to understand.

### Examples

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

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

$ ./ch-1.py -2 0 1 -2 1 1 0 1 -2 9
1
```

## Task 2: Dictionary Rank

### Task

You are given a word, `$word`.

Write a script to compute the dictionary rank of the given word.

### My solution

This task was a little more challenging than a first thought, and more so for the Perl solution. This is because while I can calculate all the permutations of letters easily, I only want to count unique permutations. For example, the word `baa` has 3! (6) permutations, but only 3 are unique (`aab`, `aba`, `baa`).

Thankfully there is a [distinct_permutations](https://more-itertools.readthedocs.io/en/stable/api.html#more_itertools.distinct_permutations) method in more_itertools that makes this easy.

The first thing I do is convert the word into lower case and convert it into a tuple. I store this as the variable `tuple_word`.

I then sort the tuple alphabetically and store this as `letters` and parse it to the `distinct_permutations` generator. I keep counting until I find the tuple that has the original word.

```python
def dictionary_rank(word: str) -> int:

    tuple_word = tuple(word.lower())
    letters = sorted(tuple_word)
    count = 0

    for perm in distinct_permutations(letters):
        count += 1
        if perm == tuple_word:
            break

    return count
```

It should be noted that the performance of the solutions are really only good if it appears early (alphabetically) or has less than 11 characters. Calculating the rank of 'kjihgfedcba' took 35 seconds on my PC. For the record it is ranked 39,916,800th which is also 11!.

#### Perl solution

The Perl solution is slightly different. My go to for permutations in Perl is usually Algorithm::Combinatorics, but this doesn't have a function for distinct permutations. [Math::Combinatorics](https://metacpan.org/pod/Math::Combinatorics) does, however the order of them is not guaranteed.

For the task, I count all unique permutations that are less than or equal to the word, and print that.

### Examples

```bash
$ ./ch-2.py CAT
3

$ ./ch-2.py GOOGLE
88

$ ./ch-2.py SECRET
255
```