Counting and ranking

Weekly Challenge 260

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: 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.

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.

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

The second part definitely fails under TMTOWTDI. One possible alternate solution is len(freq) == len(set(freq.values()). While probably quicker, it's not as straight forward to understand.

Examples

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

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

$ ./ch-2.py CAT
3

$ ./ch-2.py GOOGLE
88

$ ./ch-2.py SECRET
255