Equalizing positions
Tags: perl, python, theweeklychallenge
Published: 2024-05-26 12:29:48

## Weekly Challenge 270

Each week Mohammad S. Anwar sends out [The Weekly Challenge](https://theweeklychallenge.org/), 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.

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

## Task 1: Special Positions

### Task

You are given a `m x n` binary matrix.

Write a script to return the number of special positions in the given binary matrix.

A position `(i, j)` is called special if `$matrix[i][j] == 1` and all other elements in the row `i` and column `j` are 0.

### My solution

For the input from the command line, I take a JSON string and convert that into a list of lists of integers.

This is a break down of the steps I take to complete the task.

1. Set the `special_position` value to `0`.
1. Set `rows` and `cols` to the number of rows and columns in the matrix
1. Create two lists (arrays in Perl) called `row_count` and `col_count` with zeros for the number of rows and columns respectively.
1. Loop through each row and each column in the matrix. If the value is `1`, increment the `row_count` for the row and `col_count` for the column by one. I also check that the number of items in this row is the same as the number of items in the first row.
1.  Loop through each row and each column in the matrix. If the value  at that position is 1 and the `row_count` for the row is 1 (this would indicate that the other elements in the row are 0) and the `col_count` is 1, add one to the `special_position` variable.
1. Return the `special_position` value.

```python
def special_positions(matrix: list) -> int:
    rows = len(matrix)
    cols = len(matrix[0])
    special_position = 0

    row_count = [0] * rows
    col_count = [0] * cols

    for row in range(rows):
        if len(matrix[row]) != cols:
            raise ValueError("Row %s has the wrong number of columns", row)

        for col in range(cols):
            if matrix[row][col]:
                row_count[row] += 1
                col_count[col] += 1

    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] and row_count[row] == 1 and col_count[col] == 1:
                special_position += 1

    return special_position
```

### Examples

```bash
$ ./ch-1.py "[[1, 0, 0],[0, 0, 1],[1, 0, 0]]"
1

$ ./ch-1.py "[[1, 0, 0],[0, 1, 0],[0, 0, 1]]"
3
```

## Task 2: Equalize Array

### Task

You are give an array of integers, `@ints` and two integers, `$x` and `$y`.

Write a script to execute one of the two options:

* Level 1: Pick an index `i` of the given array and do `$ints[i] += 1`.
* Level 2: Pick two different indices `i`,`j` and do `$ints[i] +=1` and `$ints[j] += 1`.

You are allowed to perform as many levels as you want to make every elements in the given array equal. There is cost attach for each level, for Level 1, the cost is `$x` and `$y` for Level 2.

In the end return the minimum cost to get the work done.

### Known issue

Before I write about my solution, it will return the expected results for the two examples, but will not always give the minimum score.

For the array (4, 4, 2) with `$x` of 10 and `$y` of 1, it will return 20 (perform level 1 on the third value twice). However if you perform level 2 on the first and third value (5, 4, 3), and then on the second and third value (5, 5, 4), and finally level 1 on the last value (5, 5, 5), you'd get a score of 12.

File a bug in Bugzilla, Jira or Github, and we'll fix it later :P

### My solution

For input from the command line, I take the last two values to be `x` and `y`, and the rest of the input to be `ints`.

The first step I take is to flip the array to be the number needed to reach the target value (maximum of the values).

```python
def equalize_array(ints: list, x: int, y: int) -> str:
    score = 0
    # Calculate the needed values
    max_value = max(ints)
    needed = [max_value - i for i in ints]
```

I then perform level two only if `y` is less than twice the value of `x`. If it isn't, then I will always get the same or a lower score by performing level one on each value.

For level two, I sort the indexes (not values) of the `needed` list by their value, with the highest value first. If the second highest value is `0`, it means there is no more level two tasks to perform, and I exit the loop. Otherwise I take one off the top two values in the `needed` array, and continue until the second highest value is `0`. For each iteration, I add `y` to the `score` value.

```python
    if len(ints) > 1 and y < x * 2:
        while True:
            sorted_index = sorted(
                range(len(ints)),
                key=lambda index: needed[index],
                reverse=True
            )

            if needed[sorted_index[1]] == 0:
                break

            needed[sorted_index[0]] -= 1
            needed[sorted_index[1]] -= 1
            score += y
```

Finally, my code perform the Level One operation. As level one takes one off each `needed` number, I simply multiple the sum of the remaining `needed` values by the `x` value and add it to `score`. I then return the value of `score` variable.

```python
    score += sum(needed) * x
    return score
```

### Examples

```bash
$ ./ch-2.py 4 1 3 2
9

$ ./ch-2.py 2 3 3 3 5 2 1
6
```