The weekly challenge 218 - Task 2: Matrix Score

  1 #!/usr/bin/perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-218/#TASK2
  3 #
  4 # Task 2: Matrix Score
  5 # ====================
  6 #
  7 # You are given a m x n binary matrix i.e. having only 1 and 0.
  8 #
  9 # You are allowed to make as many moves as you want to get the highest score.
 10 #
 11 ###  A move can be either toggling each value in a row or column.
 12 #
 13 # To get the score, convert the each row binary to dec and return the sum.
 14 #
 15 ## Example 1:
 16 ##
 17 ## Input: @matrix = [ [0,0,1,1],
 18 ##                    [1,0,1,0],
 19 ##                    [1,1,0,0], ]
 20 ## Output: 39
 21 ##
 22 ## Move #1: convert row #1 => 1100
 23 ##          [ [1,1,0,0],
 24 ##            [1,0,1,0],
 25 ##            [1,1,0,0], ]
 26 ##
 27 ## Move #2: convert col #3 => 101
 28 ##          [ [1,1,1,0],
 29 ##            [1,0,0,0],
 30 ##            [1,1,1,0], ]
 31 ##
 32 ## Move #3: convert col #4 => 111
 33 ##          [ [1,1,1,1],
 34 ##            [1,0,0,1],
 35 ##            [1,1,1,1], ]
 36 ##
 37 ## Score: 0b1111 + 0b1001 + 0b1111 => 15 + 9 + 15 => 39
 38 #
 39 ## Example 2:
 40 ##
 41 ## Input: @matrix = [ [0] ]
 42 ## Output: 1
 43 #
 44 ############################################################
 45 ##
 46 ## discussion
 47 ##
 48 ############################################################
 49 #
 50 # Each row and each column can either be flipped or not, since
 51 # flipping it twice returns it into its previous state. So we
 52 # can get all possible scores by calculating the score with
 53 # each column and row either flipped or not and then select
 54 # the maximum. To calculate each combination, we can say we flip
 55 # row $i if the $i-th bit of a bitfield is set, and column $i
 56 # if the ($i-$number_of_rows)-th bit of the bitfield is set.
 57 # In order to create the bitfield, we count from 0 to
 58 # 2**($rows+$columns)-1 and convert the result into a bitfield
 59 # of length ($rows+$columns). Then we calculate the new matrix
 60 # with the corresponding rows and columns flipped, and then the
 61 # score for this new matrix. In the end we take the maximum of
 62 # those values.
 63 
 64 use strict;
 65 use warnings;
 66 
 67 matrix_score( [ [0,0,1,1], [1,0,1,0], [1,1,0,0], ] );
 68 matrix_score( [ [0] ] );
 69 
 70 sub matrix_score {
 71    my $matrix = shift;
 72    my ($rows, $columns) = get_dimensions($matrix);
 73    my $highest = 0;
 74    print "Input:\n";
 75    print_matrix($matrix);
 76    foreach my $index (0..2**($rows+$columns)-1) {
 77       my $score = get_score($matrix, $index, $rows, $columns);
 78       $highest = $score if $score > $highest;
 79    }
 80    print "Output: $highest\n";
 81 }
 82 
 83 # this helper function calculates the number of rows and columns
 84 # of the matrix, and also checks if all rows have the same amount
 85 # of columns
 86 sub get_dimensions {
 87    my $matrix = shift;
 88    my $rows = @$matrix;
 89    my $columns = scalar(@{$matrix->[0]});
 90    foreach my $row (@$matrix) {
 91       my $c = scalar(@$row);
 92       die "Not a matrix, dimension mismatch!" unless $c == $columns;
 93    }
 94    return ($rows, $columns);
 95 }
 96 
 97 # helper function to print the matrix, just for the output
 98 sub print_matrix {
 99    my $matrix = shift;
100    my $first = 1;
101    foreach my $row (@$matrix) {
102       if($first) {
103          $first = 0;
104          print "[ ";
105       } else {
106          print "  ";
107       }
108       print "[" . join(",", @$row) . "],\n";
109    }
110    print "]\n";
111 }
112 
113 # given the original matrix and the index (the number we will turn
114 # into the bitfield for determining which rows and columns to flip),
115 # this function will first create a copy of the matrix, then flip
116 # the corresponding rows and columns, and then calculate the score.
117 sub get_score {
118    my ($matrix, $index, $rows, $columns) = @_;
119    my $copy_matrix;
120    # create a copy of the matrix
121    foreach my $row (0..$rows-1) {
122       foreach my $column (0..$columns-1) {
123          $copy_matrix->[$row]->[$column] = $matrix->[$row]->[$column];
124       }
125    }
126    # turn the index into a bitfield
127    my $x = $rows+$columns;
128    my @bits = split //, sprintf("%0${x}b", $index);
129    foreach my $i (0..$rows+$columns-1) {
130       if($bits[$i]) { # the bit is set
131          if($i < $rows) {
132             # flip everything in row $i
133             foreach my $j (0..$columns-1) {
134                $copy_matrix->[$i]->[$j] = $copy_matrix->[$i]->[$j] ? 0 : 1;
135             }
136          } else {
137             # flip everything in column $i-$rows
138             foreach my $j (0..$rows-1) {
139                $copy_matrix->[$j]->[$i-$rows] = $copy_matrix->[$j]->[$i-$rows] ? 0 : 1;
140             }
141          }
142       }
143    }
144    # calculate the score
145    my $score = 0;
146    foreach my $row (0..$rows-1) {
147       $score += bin_to_dec($copy_matrix->[$row]);
148    }
149    return $score;
150 }
151 
152 # helper function to turn an array of bits into an integer
153 sub bin_to_dec {
154    my $digits = shift;
155    my $result = 0;
156    foreach my $digit (@$digits) {
157       $result*=2;
158       $result+=$digit;
159    }
160    return $result;
161 }
162