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.
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.
- Set the
special_position
value to0
. - Set
rows
andcols
to the number of rows and columns in the matrix - Create two lists (arrays in Perl) called
row_count
andcol_count
with zeros for the number of rows and columns respectively. - Loop through each row and each column in the matrix. If the value is
1
, increment therow_count
for the row andcol_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. - 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 thecol_count
is 1, add one to thespecial_position
variable. - 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
Top comments (0)