DEV Community

Simon Green
Simon Green

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Examples

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

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

$ ./ch-1.py nba cba dba
0
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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])
Enter fullscreen mode Exit fullscreen mode

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

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

print('(' + ','.join(solution) + ')')
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)