It's all good
Tags: perl, python, theweeklychallenge
Published: 2023-01-14 05:47:02

## Weekly Challenge 199

[Challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-199/), [My solution](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-199/sgreen)

## 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](https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF) that the sum of `n` can be expressed a `n × (n + 1) ÷ 2`, which is the formula that I use.

### Examples

```bash
$ ./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](https://docs.python.org/3.8/library/itertools.html#itertools.combinations) (Python) or [Algorithm::Combinatorics](https://metacpan.org/pod/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

```bash
$ ./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
```