1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#!/usr/bin/python3
# https://theweeklychallenge.org/blog/perl-weekly-challenge-253/#TASK2
#
# Task 2: Weakest Row
# ===================
#
# You are given an m x n binary matrix i.e. only 0 and 1 where 1 always appear before 0.
#
# A row i is weaker than a row j if one of the following is true:
#
## a) The number of 1s in row i is less than the number of 1s in row j.
## b) Both rows have the same number of 1 and i < j.
#
# Write a script to return the order of rows from weakest to strongest.
#
## Example 1
##
## Input: $matrix = [
## [1, 1, 0, 0, 0],
## [1, 1, 1, 1, 0],
## [1, 0, 0, 0, 0],
## [1, 1, 0, 0, 0],
## [1, 1, 1, 1, 1]
## ]
## Output: (2, 0, 3, 1, 4)
##
## The number of 1s in each row is:
## - Row 0: 2
## - Row 1: 4
## - Row 2: 1
## - Row 3: 2
## - Row 4: 5
#
## Example 2
##
## Input: $matrix = [
## [1, 0, 0, 0],
## [1, 1, 1, 1],
## [1, 0, 0, 0],
## [1, 0, 0, 0]
## ]
## Output: (0, 2, 3, 1)
##
## The number of 1s in each row is:
## - Row 0: 1
## - Row 1: 4
## - Row 2: 1
## - Row 3: 1
#
############################################################
##
## discussion
##
############################################################
#
# First, we create a second array which contains the number of 1's
# in each row and the row's index, then we sort that array by the
# number of ones and the index - which means we only sort by the
# number of ones since python's sort is stable, keeping the order
# of elements intact if the values are the same, and the index is
# therefore already sorted after sorting by number of ones.
#
from operator import itemgetter
def number_of_ones( array: list) -> int:
output = 0
for value in array:
if value > 0:
output += 1
return output
def weakest_row(matrix: list) -> None:
print("Input: [")
for array in matrix:
print(" [", ", ".join([str(x) for x in array]), "],")
print(" ]")
sort_by_me = []
i = 0
for array in matrix:
num = number_of_ones(array)
pos = i
i += 1
sort_by_me.append([num, pos])
sorted_array = sorted(sort_by_me, key=itemgetter(0))
print("Output: (", ", ".join([str(x[1]) for x in sorted_array]), ")", sep=None)
weakest_row([ [1, 1, 0, 0, 0], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 1, 1, 1] ])
weakest_row([ [1, 0, 0, 0], [1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0] ])
|
