It's all good

Weekly Challenge 199

Challenge, My solution

Task 1: Good Pairs

Task

You are given a list of integers, @list.

Write a script to find the total count of Good Pairs. A pair (i, j) is called good if list[i] == list[j] and i < j.

My solution

One of the challenges when completing these tasks is needless optimizations. Given that the input list is relatively small there is a fine line between being clever and just brute forcing the solution.

The brute force solution is (where n is the length of the array) to go through all combinations of i and j (where i is an iterator from 0 to n - 2 and j is an iterator from i + 1 to n - 1), and count the occurrences where the value in that position is the same. And that's a perfectly acceptable solution in solving the task. I'd approve that pull request every day of the week :)

The solution I took is a little more complex, but will work on extremely large lists better. The first thing I do is count the frequency of each 'integer'. I put that in quotes as in Python they really are strings. This is stored as the freq dict (hash in Perl).

I then loop through the frequency counts (the values of the freq dict). If the frequency is greater than one, we have good pairs. The number pairs is the sum of 1 + ... + n-1. Rather than calculating the sum by hand, we know that the sum of n can be expressed a n × (n + 1) ÷ 2, which is the formula that I use.

Examples

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

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

$ ./ch-1.py 1 1 1 1
6

Task 2: Good Triplets

Task

You are given an array of integers, @array and three integers $x, $y, $z.

Write a script to find out total Good Triplets in the given array.

A triplet array[i], array[j], array[k] is good if it satisfies the following conditions:

1) 0 <= i < j < k <= n (size of given array)
1) abs(array[i] - array[j]) <= x
1) abs(array[j] - array[k]) <= y
1) abs(array[i] - array[k]) <= z

My solution

My first observation is that k can be the size of the array. This will cause an out of bounds errors. For example, if an array has three elements, array[3] is not valid. So I'm assuming that for the first condition it is meant that k < n.

My next observation is that this very similar to the first task in week 196, so most of the code comes from that solution.

The first thing I do is remove the last three values from the input to represent x, y and z.

For this task I used the combinations method from itertools (Python) or Algorithm::Combinatorics (Perl) to generate all combinations of positions (not values) from 0 to one less than the length of the array.

For each iteration, I (numerically) sort the numbers to ensure i < j < k. I then check if the other three criteria are met. If it is, I add one to count.

Examples

$ ./ch-2.py 3 0 1 1 9 7 7 2 3
4

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