Equalizing positions

Weekly Challenge 270

Each week Mohammad S. Anwar sends out The Weekly Challenge, 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, My solutions

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.
2. Set rows and cols to the number of rows and columns in the matrix
3. Create two lists (arrays in Perl) called row_count and col_count with zeros for the number of rows and columns respectively.
4. 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.
5. 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.
6. Return the special_position value.

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

$ ./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).

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.

    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.

    score += sum(needed) * x
    return score

Examples

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

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