## Weekly Challenge 199

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

## Top comments (0)