Simon Green

Posted on

# It's all good

## Weekly Challenge 199

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

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