The weekly challenge 253 - Task 2: Weakest Row

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