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

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

## Top comments (0)