Task — Matrix sum

You are given a m x n binary matrix (ie cells being only 1 or 0). You are allowed to make as many moves as you want to get the highest score. A move can be either toggling every value in a row or column. To get the score, convert each row as a binary number, convert it to decimal and return the sum.

Analysis

Here is a possible solution.

First toggle every row that has 0 in column 0. That will leave every row with 1 in column 0, and because eg 1000 is greater than 0111, it must be the case that the solution has all the cells in column 0 containing 1.

Second, toggle any column that contains more 0s than 1s. That will increase, and hopefully maximise, the value these cells contribute to the final sum.

I cannot prove that this always maximises the score, but I have not been able to find a counter-example.

Try it 

Script

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-05-22
use utf8;     # Week 218 task 2 - Matrix score
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

matrix_score( [ [0,0,1,1],
                [1,0,1,0],
                [1,1,0,0] ]);
matrix_score( [ [0] ]);
matrix_score( [ [0, 0, 0, 0, 1],
                [0, 1, 0, 0, 0],
                [0, 0, 0, 1, 0],
                [0, 0, 1, 0, 0] ]);


sub matrix_score {
    
    my ($matrix, $last_row, $last_col, $row, $col, $sum, $value);
    
    # initialise
    $matrix = $_[0];
    say '';
    show_matrix(qq{Input:  }, $matrix);
    $last_row = scalar @$matrix - 1;
    $last_col = scalar @{$matrix->[0]} - 1;
    
    # flip rows so that column 1 is 1
    for $row (0 .. $last_row) {
        if ($matrix->[$row]->[0] == 0 ) {
            for $col (0 .. $last_col) {
                $matrix->[$row]->[$col] = 1 - $matrix->[$row]->[$col];
            }
        }
    }
    
    # flip columns to maximise no of 1s
    for $col (1 .. $last_col) {
        $sum = 0;
        for $row (0 .. $last_row) {
            $sum += $matrix->[$row]->[$col];
        }
        if ($sum < ($last_row + 1) / 2) {
            for $row (0 .. $last_row) {
                $matrix->[$row]->[$col] = 1 - $matrix->[$row]->[$col];
            }
        }
    }
    
    # evaluate
    $value = 2 ** $last_col;
    $sum = 0;
    for $col (0 .. $last_col) {
        for $row (0 .. $last_row) {
            $sum += $matrix->[$row]->[$col] * $value;
        }
        $value /= 2;
    }
    
    say '';
    show_matrix(qq[Output: ], $matrix);
    say qq[        sum = $sum];
}

sub show_matrix {
    
    my ($intro, $row, $matrix, $last_row);  
    ($intro, $matrix) = @_;
    
    # print out a matrix
    $last_row = scalar @$matrix - 1;
    for $row (0 .. $last_row) {
        say qq{$intro\[ } . join(', ', @{$matrix->[$row]}) . ' ]';
        $intro = ' ' x length($intro);
    }

}

Output

Input:  [ 0, 0, 1, 1 ]
        [ 1, 0, 1, 0 ]
        [ 1, 1, 0, 0 ]

Output: [ 1, 1, 1, 1 ]
        [ 1, 0, 0, 1 ]
        [ 1, 1, 1, 1 ]
        sum = 39

Input:  [ 0 ]

Output: [ 1 ]
        sum = 1

Input:  [ 0, 0, 0, 0, 1 ]
        [ 0, 1, 0, 0, 0 ]
        [ 0, 0, 0, 1, 0 ]
        [ 0, 0, 1, 0, 0 ]

Output: [ 1, 1, 1, 1, 0 ]
        [ 1, 0, 1, 1, 1 ]
        [ 1, 1, 1, 0, 1 ]
        [ 1, 1, 0, 1, 1 ]
        sum = 109