Similar frequency

Weekly Challenge 233

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: Similar Words

Task

You are given an array of words made up of alphabets only.

Write a script to find the number of pairs of similar words. Two words are similar if they consist of the same characters.

My solution

This task can be broken in to two steps. The first is to find the frequency of 'similar words' (as defined by the task description). For this I take the alphabetically-sorted lower-cased unique letter of each word. I store this in a dict (hash in Perl) called freq. The value is the number of times each similar word occurs.

for w in words:
    s = ''.join(sorted(set(w.lower())))
    freq[s] = freq.get(s, 0) + 1

The next step is to calculate the pairs of similar words. I know the formula for this is n × (n-1) / 2 (or alternatively (n² - n) / 2) for n items. I use this formula on all the values in the dict to come to the final solution.

for v in freq.values():
    if v > 1:
        solution += v * (v-1) // 2

Examples

$ ./ch-1.py aba aabb abcd bac aabc
2

$ ./ch-1.py aabb ab ba
3

$ ./ch-1.py nba cba dba
0

Task 2: Frequency Sort

Task

You are given an array of integers.

Write a script to sort the given array in increasing order based on the frequency of the values. If multiple values have the same frequency then sort them in decreasing order.

My solution

This also starts a similar way in that I create a dict (hash in Perl) called freq with the frequency of each integer.

for i in ints:
    freq[i] = freq.get(i, 0) + 1

In Python, sorting is stable. This means if two things are equal the original order is preserved.

I sort the list twice. The first sort is numerically in reverse (highest number first), and then the frequency of the number (lowest frequency first).

sorted_ints = sorted(freq, reverse=True)
sorted_ints = sorted(sorted_ints, key=lambda i: freq[i])

Finally, I reconstitute the array by the frequency of each integer.

for f in sorted_ints:
    solution += [str(f)] * freq[f]

print('(' + ','.join(solution) + ')')

The Perl code is very similar. The main difference is that I do the sort in a single operation.

my @sorted_ints = sort { $freq{$a} <=> $freq{$b} || $b <=> $a } keys %freq;

Examples

$ ./ch-2.py 1 1 2 2 2 3
(3,1,1,2,2,2)

$ ./ch-2.py 2 3 1 3 2
(1,3,3,2,2)

$ ./ch-2.py -1 1 -6 4 5 -6 1 4 1
(5,-1,4,4,-6,-6,1,1,1)